Публично проверяемое разделение секрета

Публично проверяемое разделение секрета (PVSS) — схема проверяемого разделения секрета такая, что любая сторона (а не только стороны-участники протокола) может подтвердить достоверность долей, распределённых дилером.

В схеме каждой стороне $P_{i}$ назначается публичная функция шифрования $E_{i}$, при этом соответствующую функцию дешифрования $D_{i}$ не знает никто, кроме самого $P_{i}$.

Дилер использует открытые функции шифрования для распределения долей, вычисляя:

$S_{i}=E_{i}\left(s_{i}\right),\quad i=1,\ldots ,n$

и публикуя зашифрованные доли $S_{i}$. Для проверки достоверности всех зашифрованных долей существует алгоритм PubVerify, свойство которого состоит в том, что:

$\exists u\forall A\in 2^{\{1,\ldots ,n\}}:\quad \left({\text{ PubVerify }}\left(\left\{S_{i}\mid i\in A\right\}\right)=1\right)\Rightarrow \operatorname {Recover} \left(\left\{D_{i}\left(S_{i}\right)\mid i\in A\right\}\right)=u$

и $u=s$, если дилер был честен.

Иными словами, если набор зашифрованных долей «достоверен» согласно PubVerify, то честные участники могут расшифровать их и восстановить секрет. Стоит обратить внимание, что PubVerify может быть выполнено, даже если стороны ещё не получили свои доли. Для запуска PubVerify может потребоваться связь с дилером (но не с участником). Схема PVSS называется неинтерактивной, если PubVerify вообще не требует взаимодействия с дилером, или интерактивной, если это не так.

Среди возможных применений PVSS — электронное голосование, пороговые криптосистемы, пороговые отзывные электронные деньги, пороговое программное обеспечение депонирования ключей, пороговые подписи.

Реализация

Фиксируется $G_{p}$ — группа простого порядка $p$, $g,G$ — независимо выбранные генераторы этой группы. Задача дилера — разделить случайное значение из данной группы. Для этого дилер сначала выбирает $s\in _{R}Z_{p}$, а затем распространяет доли секрета $S=G^{S}$.

Возможно использовать протокол Чаума — Педерсена для подтверждения $\log _{g_{1}}{h_{1}}=\log _{g_{2}}{h_{1}}$, где $g_{1},g_{2},h_{1},h_{2}\in G_{p}$: если подтверждающий знает такое $\alpha$, что $h_{1}=g_{1}^{\alpha }$ и $h_{2}=g_{2}^{\alpha }$ (дискретные логарифмы), где $g_{1}$ и $g_{2}$ — генераторы группы простого порядка $p$:

• подтверждающий выбирает случайную $r\in {\boldsymbol {\mathrm {Z} }}_{q^{*}}$ и отправляет $a_{1}=g_{1}^{r}$ и $a_{2}=g_{2}^{r}$;
• проверяющий отправляет случайную посылку $c\in _{R}{\boldsymbol {\mathrm {Z} }}_{q}$;
• подтверждающий отвечает $s=r-\alpha c(\mathrm {mod} \,q)$;
• проверяющий проверяет что $a_{1}=g_{1}^{s}h_{1}^{c}$ и $a_{2}=g_{2}^{s}h_{2}^{c}$.

Протокол Чаума — Педерсена является интерактивным и требует некоторой модификации для использования в неинтерактивном режиме: замены случайно выбранной $c$ на «безопасную хэш-функцию» с $m$ в качестве входного значения.

Сама схема PVSS состоит из трёх фаз: инициализации, распределения и восстановления.

На этапе инициализации выбирается группа $G_{p}$ и её генераторы $g,G$. Непосредственно алгоритм выбора надежных параметров является отдельной задачей криптографии и не относится к протоколу PVSS. Каждая сторона $P_{i}i=1\ldots n$ генерирует закрытый ключ $x_{i}\in _{R}Z_{p}^{*}$ и регистрирует $y_{i}=G^{x_{i}}$ в качестве своего открытого ключа.

На фазе распределения данная часть протокола состоит из двух шагов — распределение долей и подтверждение долей. На шаге распределение долей дилер выбирает случайный полином $d$ степени $t-1$ с коэффициентами, принадлежащими $Z_{p}$:
$d(x)=\sum _{j=0}^{t-1}\beta _{j}x^{j}$
При этом нулевой коэффициент равен распределяемому секрету $\beta _{0}=s$.
Этот полином, в отличие от обычных схем разделения секрета, нигде не публикуется и приватно хранится у дилера. Вместо этого дилер публикует $C_{j}=g_{j}^{\beta },0\leq j\leq t$ и зашифрованные на публичных ключах каждой стороны полиномы $Y_{i}=y_{i}^{d(i)},1\leq i\leq n$. Дилер доказывает, что зашифрованные полиномы действительно лежат на одной прямой, если для $d(i),1\leq i\leq n$ удовлетворяются следующие уравнения:

$X_{i}=\prod _{j=0}^{t-1}C_{j}^{ij}=g^{d(i)}$ и $Y_{i}=y_{i}^{d(i)}$Для данной проверки протокол Чаума — Педерсена применяется параллельно всеми сторонами. На шаге подтверждение долей подтверждающая сторона вычисляет $X_{i}$ с помощью значений $C_{j}$. Затем, аналогично протоколу Чаума — Педерсена, вычисляются $a_{1i}=g^{s_{i}}X_{i}^{c}$ и $a_{2i}=y^{s_{i}}Y_{i}^{c}$. Если они совпадают, то доли считаются подтверждёнными.

На фазе восстановления каждый участник, используя свой закрытый ключ $x_{i}$, находит долю $S_{i}=G^{d(i)}$ из $Y_{i}$, вычисляя $S_{i}=Y_{i}^{1/x_{i}}$. Стороны публикуют $S_{i}$ плюс доказательство того, что значение $S_{i}$ является правильной расшифровкой $Y_{i}$. Для этого достаточно доказать знание $\alpha$ такого, что $y_{i}=G^{\alpha }$ и $Y_{i}=S_{i}^{\alpha }$, для чего опять же можно применить протокол Чаума — Педерсена.

Возможна операция объединения долей: если участники $P_{i}$ прошли все необходимые проверки и убедились, что значения $S_{i}$ верны для $i=1,\ldots ,t$. Секрет $G^{s}$, то можно применить интерполяцию Лагранжа:

$\prod _{i=1}^{t}S_{i}^{\lambda _{i}}=\prod _{i=1}^{t}\left(G^{d(i)}\right)^{\lambda _{i}}=G^{\sum _{i=1}^{t}d(i)\lambda _{i}}=G^{d(0)}=G^{s}$,

где $\lambda _{i}=\prod _{j\neq i}{\frac {j}{j-i}}$ — коэффициенты Лагранжа.

Литература

• Markus Stadler. Publicly verifiable secret sharing // International Conference on the Theory and Applications of Cryptographic Techniques. — Springer, 1996.

• Benny Chor , et al. Verifiable secret sharing and achieving simultaneity in the presence of faults // 26th Annual Symposium on Foundations of Computer Science. — IEEE, 1985.

• Paul Feldman. A practical scheme for non-interactive verifiable secret sharing // 28th Annual Symposium on Foundations of Computer Science. — IEEE, 1987.

• Torben Pryds Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing // Annual international cryptology conference. — Springer, 1991.
• B. Schoenmakers. A simple publicly verifiable secret sharing scheme and its application to electronic voting // In Annual International Cryptology Conference. — Springer, 1999.

Ссылки

• Markus Stadler, Publicly Verifiable Secret Sharing
• Berry Schoenmakers, A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting, Advances in Cryptology—CRYPTO, 1999, pp. 148—164