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

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

В схеме каждой стороне [math]\displaystyle{ P_i }[/math] назначается публичная функция шифрования [math]\displaystyle{ E_i }[/math], при этом соответствующую функцию дешифрования [math]\displaystyle{ D_i }[/math] не знает никто, кроме самого [math]\displaystyle{ P_i }[/math].

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

[math]\displaystyle{ S_i=E_i\left(s_i\right), \quad i=1, \ldots, n }[/math]

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

[math]\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 }[/math]

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

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

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

Реализация

Фиксируется [math]\displaystyle{ G_p }[/math] — группа простого порядка [math]\displaystyle{ p }[/math], [math]\displaystyle{ g,G }[/math] — независимо выбранные генераторы этой группы. Задача дилера — разделить случайное значение из данной группы. Для этого дилер сначала выбирает [math]\displaystyle{ s \in _R Z_p }[/math], а затем распространяет доли секрета [math]\displaystyle{ S=G^S }[/math].

Возможно использовать протокол Чаума — Педерсена для подтверждения [math]\displaystyle{ \log_{g_1}{h_1}=\log_{g_2}{h_1} }[/math], где [math]\displaystyle{ g_1, g_2, h_1, h_2 \in G_p }[/math]: если подтверждающий знает такое [math]\displaystyle{ \alpha }[/math], что [math]\displaystyle{ h_1=g_1^\alpha }[/math] и [math]\displaystyle{ h_2=g_2^\alpha }[/math] (дискретные логарифмы), где [math]\displaystyle{ g_1 }[/math] и [math]\displaystyle{ g_2 }[/math] — генераторы группы простого порядка [math]\displaystyle{ p }[/math]:

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

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

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

На этапе инициализации выбирается группа [math]\displaystyle{ G_p }[/math] и её генераторы [math]\displaystyle{ g,G }[/math]. Непосредственно алгоритм выбора надежных параметров является отдельной задачей криптографии и не относится к протоколу PVSS. Каждая сторона [math]\displaystyle{ P_i i=1 \ldots n }[/math] генерирует закрытый ключ [math]\displaystyle{ x_i \in _R Z_p^* }[/math] и регистрирует [math]\displaystyle{ y_i=G^{x_i} }[/math] в качестве своего открытого ключа.

На фазе распределения данная часть протокола состоит из двух шагов — распределение долей и подтверждение долей. На шаге распределение долей дилер выбирает случайный полином [math]\displaystyle{ d }[/math] степени [math]\displaystyle{ t-1 }[/math] с коэффициентами, принадлежащими [math]\displaystyle{ Z_p }[/math]:
[math]\displaystyle{ d(x)=\sum_{j=0}^{t-1}\beta _j x^j }[/math]
При этом нулевой коэффициент равен распределяемому секрету [math]\displaystyle{ \beta _0 = s }[/math].
Этот полином, в отличие от обычных схем разделения секрета, нигде не публикуется и приватно хранится у дилера. Вместо этого дилер публикует [math]\displaystyle{ C_j=g^\beta_j, 0\leq j\leq t }[/math] и зашифрованные на публичных ключах каждой стороны полиномы [math]\displaystyle{ Y_i=y_i^{d(i)}, 1\leq i \leq n }[/math]. Дилер доказывает, что зашифрованные полиномы действительно лежат на одной прямой, если для [math]\displaystyle{ d(i), 1 \leq i \leq n }[/math] удовлетворяются следующие уравнения:

[math]\displaystyle{ X_i=\prod_{j=0}^{t-1}C_j^{ij}=g^{d(i)} }[/math] и [math]\displaystyle{ Y_i=y_i^{d(i)} }[/math]Для данной проверки протокол Чаума — Педерсена применяется параллельно всеми сторонами. На шаге подтверждение долей подтверждающая сторона вычисляет [math]\displaystyle{ X_i }[/math] с помощью значений [math]\displaystyle{ C_j }[/math]. Затем, аналогично протоколу Чаума — Педерсена, вычисляются [math]\displaystyle{ a_{1i}=g^{s_i}X_i^c }[/math] и [math]\displaystyle{ a_{2i}=y^{s_i}Y_i^c }[/math]. Если они совпадают, то доли считаются подтверждёнными.

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

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

[math]\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 }[/math],

где [math]\displaystyle{ \lambda_i=\prod_{j \neq i} \frac{j}{j-i} }[/math] — коэффициенты Лагранжа.

Литература

• 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