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


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


Теорема 3.1.

Схема ПРСК является (n/3-1)-устойчивой.

Доказательство.  Пусть

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

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

и

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

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

где si=f0(i), f0(x)=s+a1x+...+at+1xt+1 и r=a1

....
ad

(то есть полином, созданный, с использованием случайного параметра r дилера Д).

При рассмотрении протокола РзПр

напомним, что ti – трафик процессора Pi. Ясно, что для всех процессоров Pi, i£n, функция входа всегда возвращает пустую строку Ii(ti)=e, так как процессоры не вносят никакие входы в процессе вычисления функции g. Для дилера Д, Д=Pn+1, функция входа немного сложнее. Пусть mi

- сообщение, которое дилер распространяет процессору Pi в 5-м раунде, если Pi сообщил об ошибке в 4-м раунде или сообщение, которое дилер послал процессору Pi в 1-м раунде, если Pi не заявлял об ошибке. Тогда ID(tD)=f(0), где f=BW(m1,...,mn) – полином степени t+1, следующий из интерполяции Берлекампа-Велча. Функция выхода более простая: Oi(ti)=mi, где mD=e.

При рассмотрении протокола ВсПр, определим вход и выход функции g. Функция входа Ii для процессора Pi определена как следующая: пусть mi,j – сообщение, посланное процессором Pi

процессору Pj

в 1-м раунде; Ii(ti)=hi(0), где hi=BW(mi,1,...,mi,n) - многочлен степени t+1, следующий из интерполяции Берлекампа-Велча. Если такого полинома не существует, то Ii(ti)=0. Функция выхода следующая: пусть Mi – сообщение, распространяемая процессором Pi в раунде 9; Oi(ti)=F(0)=s, где F=BW(M1,...,Mn) – полином степени t+1, следующий из интерполяции Берлекампа-Велча.

Далее для доказательства теоремы необходимо доказать выполнения условий полноты, корректности и конфиденциальности.

Полнота. Если дилер Д - честный, исходя из свойств схемы ПРСК, любой несбоящий процессор может восстановить секрет s с вероятностью 1, так как посредством определенных выше функций g и h




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