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

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

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

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

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

${\displaystyle \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}$

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

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

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

Реализация

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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}}$ ,

где ${\displaystyle \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,
• Berry Schoenmakers, , Advances in Cryptology—CRYPTO, 1999, pp. 148—164