Русская Википедия:Публично проверяемое разделение секрета
Публично проверяемое разделение секрета (PVSS) — схема проверяемого разделения секрета такая, что любая сторона (а не только стороны-участники протокола) может подтвердить достоверность долей, распределённых дилером.
В схеме каждой стороне <math>P_i</math> назначается публичная функция шифрования <math>E_i</math>, при этом соответствующую функцию дешифрования <math>D_i</math> не знает никто, кроме самого <math>P_i</math>.
Дилер использует открытые функции шифрования для распределения долей, вычисляя:
- <math>
S_i=E_i\left(s_i\right), \quad i=1, \ldots, n </math> и публикуя зашифрованные доли <math>S_i</math>. Для проверки достоверности всех зашифрованных долей существует алгоритм PubVerify, свойство которого состоит в том, что:
- <math>
\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 </math> и <math>u=s</math>, если дилер был честенШаблон:Sfn.
Иными словами, если набор зашифрованных долей «достоверен» согласно PubVerify, то честные участники могут расшифровать их и восстановить секрет. Стоит обратить внимание, что PubVerify может быть выполнено, даже если стороны ещё не получили свои доли. Для запуска PubVerify может потребоваться связь с дилером (но не с участником). Схема PVSS называется неинтерактивной, если PubVerify вообще не требует взаимодействия с дилером, или интерактивной, если это не так.
Среди возможных применений PVSS — электронное голосование, пороговые криптосистемы, пороговые отзывные электронные деньги, пороговое программное обеспечение депонирования ключей, пороговые подписи.
Реализация
Фиксируется <math>G_p</math> — группа простого порядка <math>p</math>, <math>g,G</math> — независимо выбранные генераторы этой группы. Задача дилера — разделить случайное значение из данной группы. Для этого дилер сначала выбирает <math>s \in _R Z_p </math>, а затем распространяет доли секрета <math>S=G^S</math>.
Возможно использовать протокол Чаума — Педерсена для подтверждения <math>\log_{g_1}{h_1}=\log_{g_2}{h_1}</math>, где <math>g_1, g_2, h_1, h_2 \in G_p</math>: если подтверждающий знает такое <math>\alpha</math>, что <math>h_1=g_1^\alpha</math> и <math>h_2=g_2^\alpha</math> (дискретные логарифмы), где <math>g_1</math> и <math>g_2</math> — генераторы группы простого порядка <math>p</math>:
- подтверждающий выбирает случайную <math>r\in \boldsymbol{\Zeta}_{q^*} </math> и отправляет <math>a_1=g_1^r</math> и <math>a_2=g_2^r</math>;
- проверяющий отправляет случайную посылку <math>c \in _{R}\boldsymbol{\Zeta}_{q} </math>;
- подтверждающий отвечает <math>s = r - \alpha c(\mathrm{mod}\,q)</math>;
- проверяющий проверяет что <math>a_1 = g_{1}^s h_{1}^c </math> и <math>a_2 = g_{2}^s h_{2}^c </math>.
Протокол Чаума — Педерсена является интерактивным и требует некоторой модификации для использования в неинтерактивном режиме: замены случайно выбранной <math>c</math> на «безопасную хэш-функцию» с <math>m</math> в качестве входного значения.
Сама схема PVSS состоит из трёх фаз: инициализации, распределения и восстановленияШаблон:Sfn.
На этапе инициализации выбирается группа <math>G_p</math> и её генераторы <math>g,G</math>. Непосредственно алгоритм выбора надежных параметров является отдельной задачей криптографии и не относится к протоколу PVSS. Каждая сторона <math>P_i i=1 \ldots n</math> генерирует закрытый ключ <math>x_i \in _R Z_p^* </math> и регистрирует <math>y_i=G^{x_i}</math> в качестве своего открытого ключаШаблон:Sfn.
На фазе распределения данная часть протокола состоит из двух шагов — распределение долей и подтверждение долей. На шаге распределение долей дилер выбирает случайный полином <math>d</math> степени <math>t-1</math> с коэффициентами, принадлежащими <math>Z_p</math>:
<math>d(x)=\sum_{j=0}^{t-1}\beta _j x^j</math>
При этом нулевой коэффициент равен распределяемому секрету <math>\beta _0 = s</math>.
Этот полином, в отличие от обычных схем разделения секрета, нигде не публикуется и приватно хранится у дилера. Вместо этого дилер публикует <math>C_j=g^\beta_j, 0\leq j\leq t</math> и зашифрованные на публичных ключах каждой стороны полиномы <math>Y_i=y_i^{d(i)}, 1\leq i \leq n</math>. Дилер доказывает, что зашифрованные полиномы действительно лежат на одной прямой, если для <math>d(i), 1 \leq i \leq n</math> удовлетворяются следующие уравнения:
<math>X_i=\prod_{j=0}^{t-1}C_j^{ij}=g^{d(i)}</math> и <math>Y_i=y_i^{d(i)}</math>Для данной проверки протокол Чаума — Педерсена применяется параллельно всеми сторонами. На шаге подтверждение долей подтверждающая сторона вычисляет <math>X_i</math> с помощью значений <math>C_j</math>. Затем, аналогично протоколу Чаума — Педерсена, вычисляются <math>a_{1i}=g^{s_i}X_i^c</math> и <math>a_{2i}=y^{s_i}Y_i^c</math>. Если они совпадают, то доли считаются подтверждённымиШаблон:Sfn.
На фазе восстановления каждый участник, используя свой закрытый ключ <math>x_i</math>, находит долю <math>S_i=G^{d(i)}</math> из <math>Y_i</math>, вычисляя <math>S_i=Y_i^{1 / x_i}</math>. Стороны публикуют <math>S_i</math> плюс доказательство того, что значение <math>S_i</math> является правильной расшифровкой <math>Y_i</math>. Для этого достаточно доказать знание <math>\alpha</math> такого, что <math>y_i=G^\alpha</math> и <math>Y_i=S_i^\alpha</math>, для чего опять же можно применить протокол Чаума — Педерсена.
Возможна операция объединения долей: если участники <math>P_i</math> прошли все необходимые проверки и убедились, что значения <math>S_i</math> верны для <math>i=1, \ldots, t</math>. Секрет <math>G^s</math>, то можно применить интерполяцию Лагранжа:
- <math>\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</math>,
где <math>\lambda_i=\prod_{j \neq i} \frac{j}{j-i}</math> — коэффициенты ЛагранжаШаблон:Sfn.
Примечания
Литература
Ссылки
- 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
