Схемы проверяемого разделения секрета.

шающих эту задачу, основанные на сложности задачи дискретного логарифмирования: СРС Фельдмана и СРС Педерсена.

Схема проверяемого разделения секрета Фельдмана. Пусть p,q- большие простые числа, -1 = 0(modгруппы Z*, т. е. gq s l(mod р). Для любой доли у,- вычисляется от-крытая величина Zj = gy< (mod р), которая по свойству гомоморфизма функции экспоненцирования позволяет каждому Р, проверять, что его собственная доля секрета совместима с открытой информа-цией.

D выбирает многочлен а(х)є Z(j [х] с коэффициентами а0 = af_x и раздает всем участникам соответствующие про

верочные значения g"'-' .

Положим хі = і, і = 1 ,/і. Дилер D секретно передает каждому уча-стнику схемы Pi предназначенную ему долю yi = а (г) mod q.

Каждый участник Р; проверяет свою долю, используя провероч-ное уравнение

У-И2 -(^Т (m°dp)-

В случае положительного результата проверки Р, передает всем остальным участникам схемы сообщение, что он принял свою долю, так как у,- = а0 +axi + a2i2 +... +дмі/_1 (modg). В случае отрицательного результата он делает вывод, что ему дилером была выдана неверная доля.

Если все = 1, л распространили сообщения о принятии долей, фаза распределения долей завершилась успешно. Такая же проверка может выполняться при восстановлении секрета.

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

1. Базовые криптографические протоколы 79

Схема проверяемого разделения секрета Педерсена.

ОТКрЫТОе общедоступное ЧИСЛО, НО Такое, ЧТО d&Zq, ГДЄ?^ =

= /z(mod р) неизвестно.

Чтобы распределить секрет К, дилер выбирает два многочлена 5(-),у(-) степени t-1 над полем Zq с коэффициентом 50 = К и слу-чайными коэффициентами {5„,}jwe{1 и {у,„}„,е{0 м) соответственно, т. е.

5(z) = 80 + 51z + 5222 + ...+5,_1Z'4GZJZ]5 50 = К,

y(z)^y0+ylz + y2z2 + ZQ[z], Y0 - случайное число,

и распространяет всем участникам схемы величину

єт ~ S&"' ' hy"' (mod р),т = 0,/ -1. Затем дилер D секретно пересылает

всем Pj, І = 1,11 ИХ ДОЛИ {w;, и>;}, где =5(i'),w(. =у(/) ¦ Проверочное уравнение для участника Р{.

(modр).

При положительном результате проверки будет выполнено ра-венство

) • hb )' • • /г7'-1 j'' = . /2YO+Y.«"+-+Y,V~' _

= *e(/,-AvW(modp).

Схема Педерсена обеспечивает теоретико-информационную секретность, так как даже если вычислительно неограниченный про-тивник, видящий gKhy(> (mod р) умеет решать задачу дискретного логарифмирования и может вычислить К + dy0 (mod q), это все равно не дает ему никакой информации о секрете К. Таким образом, схема Педерсена не позволяет противнику вычислить g к, тогда как схема Фельдмана обладает лишь теоретико-сложностной стойко-стью относительно знания противником g к.