Описание проверяемой схемы разделения секрета
Для вышеприведенных определений проверяемой схемы разделения секрета ПРС и обобщенных моделей противника, сбоев, взаимодействия и вычислений синтезируем схему разделения секрета, которая являлась бы работоспособной в протоколах конфиденциальных вычислений.
Рассматривается полностью синхронная сеть взаимодействующих процессоров в условиях проявления By-сбоев. Противник представляется как активный динамический t-противник. Взаимодействие процессоров осуществляется посредством конфиденциальных каналов связи. Кроме того, существует широковещательный канал связи.
Схема проверяемого разделения секрета, рассматриваемая как схема конфиденциального вычисления функции, значение которой является распределенный среди процессоров проверенный на корректность и затем восстановленный и проверенный секрет, обозначается как ПРСК.
Пусть сеть N состоит из n процессоров P1,P2,...,Pn-1,Pn, где Pn – дилер Д сетиN. Множество секретов обозначается через S, размерность этого множества ½S½=l. Множество случайных параметров, используемых всеми процессорами сети, обозначается через R, размерность ½R½=n. Через W обозначается рабочее пространство параметров сети.
Требуется вычислить посредством выполнения протокола P=(РзПр,ВсПр) функцию f(x),
где f – представляется в виде композиции двух функций g
Проверяемая схема разделения секрета ПРСК называется
t-устойчивой, если протокол разделения секрета и проверки правильности разделения РзПр и протокол восстановления секрета ВсПр
являются
t-устойчивыми. Функция f является конфиденциально вычислимой, если конфиденциально вычислимы функции g и h.
t-Устойчивая верифицируемая схема разделения секрета ПРСК – есть пара протоколов РзПр и ВсПр, при реализации которых выполняются следующие условия.
Условие полноты. Пусть событие A1 заключается в выполнении тождества
f(w1,...,wn-1,s)=
=g((w1,...,wn-1,s
h((s1,...,sn-1),(
Тогда для любой константы c>0 и для достаточно больших n вероятность Prob(A1)>1-n-c.
Условие корректности. Пусть событие A2 заключается в выполнении тождества
f(w1,...,wn-1,s)=
=g((w1,...,wn-1,s
h((s1,...,sn-1),(
где uj=s для jÎG и G – разрешенная коалиция процессоров.
Тогда для любой константы c>0, достаточно больших n, для границы t*<t и любого алгоритма Прот вероятность Prob(A2)<n-c.
Условие конфиденциальности.
Функция g((w1,...,wn-1,s
Функция h((s1,...,sn-1),(
Свойство полноты означает, что если все процессоры РзПр
и ВсПр следуют предопределенным вычислениям, тогда любая коалиция несбоящих процессоров может восстановить секрет s. Свойство корректности означает, что при действиях t-противника Прот, любая разрешенная коалиция из n процессоров сети может корректно разделить, восстановить и проверить секрет. Свойство конфиденциальности вытекает из свойства конфиденциальности функции g и h.
Схема ПРСК
Предлагаемая схема ПРСК [GM], является (n/3-1)-устойчивой и использует схему разделения секрета Шамира.
Пусть n=3t+4 и все вычисления выполняются по модулю большого простого числа p>n. Из теории кодов с исправлением ошибок известно, что если мы вычисляем полином f
степени t+1 в
n-1различных точках i, где i=1,...,n-1, тогда по данной последовательности si=f(i), можно восстановить коэффициенты полинома за время, ограниченное некоторым полиномом, даже если t элементов в последовательности произвольно изменены. Это вариант кода Рида-Соломона, известный как код Берлекампа-Велча (см., например, [КС]).
Пусть далее K – параметр безопасности и K/n означает éK/nù.
Протокол РзПр
1. Дилер Д
выбирает случайный полином f0(x) степени t+1 с единственным условием: f0(0)=s - его секрет. Затем он посылает процессору Pi
его долю si=f0(i). Кроме того, он выбирает 2К случайных полиномов f1,...,f2K степени t+1 и посылает процессору Pi значения fj(i) для каждого j=1,...,2К.
2. Каждый процессор Pi распространяет (посредством широковещательного канала) K/n случайных битов a(i-1)K/n+j, для j=1,...,K/n.
3. Дилер Д
распространяет полиномы gj=fj+ajf0 для всех j=1,...,K.
4. Процессор Pi проверяет, удовлетворяют ли его значения полиномам, распространяемым дилером. Если он обнаруживает ошибку, он ее декларирует для всех. Если более чем t
процессоров сообщают об этом, тогда дилер считается нечестным и все процессоры принимают по умолчанию значение нуля как секрет дилера Д.
5. Если менее чем t процессоров сообщили об ошибке, дилер распространяет значения, который он посылал в первом раунде тем процессорам, которые сообщали об ошибке дилера.
6. Каждый процессор Pi распространяет K/n
случайных битов b(i-1)K/n+j для j=1,...,K/n.
7. Дилер Д
распространяет полиномы hj=fK+j+bjf0 для всех j=1,...,K.
8. Процессор Pi проверяет, удовлетворяют ли значения, которые он имеет, полиномам, распространяемым дилером Д в 5-м раунде. Если он находит ошибку, он декларирует об этом всем процессорам сети. Если более чем t процессоров сообщают об ошибке, тогда дилер нечестный и все процессоры принимают по умолчанию значение нуля как секрет дилера Д.
Протокол ВсПр
1. Каждый процессор Pi выбирает случайный многочлен hi степени t+1 такой, что hi(0)=si - его собственная входная доля секрета.
Он посылает процессору Pj значение hi(j).
2. Каждый процессор Pi выбирает случайные полиномы pi(x), qi,1(x),...,qi,2K(x) степени t+1 со свободным членом 0 и посылает процессору Pj
значения pi(j), qi,1(j),...,qi,2K(j).
3. Каждый процессор Pi распространяет K случайных битов
gl,(i-1)K/n+m для l=1,...,n и m=K/n.
4. Каждый процессор распространяет следующие полиномы rj=qi,j+gi,jpi для каждого j=1,...,K.
5. Каждый процессор Pi проверяет, что информация процессора Pl, посланная ему в 1-м раунде, соответствует тому, что Pl распространяет в 3-м раунде. Если имеется ошибка или Pl распространяет полином с ненулевым свободным членом, процессор Pi распространяет сообщение badl. Если более чем t процессоров распространяют badl, процессор Pl
исключается из сети и все другие процессоры принимают как 0 долю процессора Pl. В противном случае, Pl распространяет информацию, которую он посылал в раунде 1 процессорам, распространявшим сообщение badl.
6. Каждый процессор Pi распространяет K случайных битов
dl,(i-1)K/n+m для l=1,...,n и m=1,...,K/n.
7. Каждый процессор Pi распространяет следующие полиномы rj=qi,K+j+di,jpi для каждый j=1,...,K.
8. Каждый процессор Pi проверяет, что информация, посланная процессором Pl, в 1-м раунде и распространенная в 5-м раунде соответствует полиномам процессора Pl, распространенным в 7-м раунде. Если имеется ошибка или Pl распространил полином с ненулевым свободным членом процессор Pi распространяет badlr. Если более чем t
процессоров распространили badl, тогда Pl – нечестен и все процессоры принимают его долю, равную 0.
9. Каждый процессор Pl распределяет всем другим процессорам следующее значение si+p1(i)+p2(i)+...+p(i), затем интерполирует полином F(x)=f0(x)+p1(x)+p2(x)+...+pn(x) c использованием алгоритма с исправлением ошибок Берлекампа-Велча.Секрет будет равен s=F(0)=f(0).
Заметим, что если дилер Д честен, в конце протокола ВсПр противник, даже зная секрет s и t долей «подкупленных» процессоров, ничего не узнает о долях секрета несбоящих процессоров, так как полином имеет степень t+1, а ему необходимо для интерполяции t
+2 точки.
