Теория и практика защиты программ


Доказательство безопасности схемы проверяемого разделения секрета - часть 2


g((w1,...,wn-1,s

r),(
,...,
))=((s1,...,sn-1,wn),(
,...,
)),

h((s1,...,sn-1,wn),(

,...,
))=((s,s,...,s,wn),(
,...,
))

реализуется

f(w1,...,wn-1,s)=((s,s,...,s,wn),(

,...,
)).

Корректность. Для доказательства теоремы необходимо доказать следующие две леммы.

Лемма 3.1. Пусть функция g имеет вид

g((w1,...,wn-1,s

r),(
,...,
))=((s1,...,sn-1,wn),(
,...,
)).

Тогда g корректно вычисляет доли секрета s1,...,sn-1.

Доказательство. Сначала мы должны доказать, что для всех несбоящих процессоров Pi, значение Ii(ti) равно корректному входу. Если дилер Д - честный, то mi=f(i), где f - многочлен степени t+1 со свободным членом s

(секретом). Таким образом, ID(tD)=s, если дилер честный. Второе условие корректности состоит в том, что с высокой вероятностью должно выполняться O(t)=g(I(t)). В нашем случае это означает, что с высокой вероятностью значения mi, находящиеся у несбоящих процессоров, должны предназначаться для единственного полинома степени t+1. Это справедливо с вероятностью ³

, где не менее
 битов выбраны действительно случайно несбоящими процессорами в раундах 2 и 6. Каждый бит представляет запрос, на который нечестный дилер, распределивший «плохие» доли, должен будет ответить правильно в следующем раунде только с вероятностью 1/2 (то есть, если он предскажет правильно значение бита). Следовательно, это и есть граница для вероятности ошибки.       -

Лемма 3.2. Пусть функция h имеет вид

h((s1,...,sn-1),(

,...,
))=((s,s,...,s,wn),(
,...,
)).

Тогда h корректно восстанавливает секрет s.

Доказательство. Понятно, что для всех несбоящих процессоров Ii(ti)=si – корректная доля входа. В этом случае необходимо проверить, что с высокой вероятностью O(t)=h(I,t), а это означает, что необходимо доказать, что

h((s1,...,sn-1),(

,...,
))=((s,s,...,s,e),(
,...,
)).

Это равенство не выполняется, если:

·     любой сбоящий процессор Pl «преуспевает» в получении случайного «мусора» вместо значений pl(j) в раунде 2 (в этом случае, сообщения Mi не будут интерполировать полином);




- Начало -  - Назад -  - Вперед -