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


Доказательство безопасности схемы АПРС


Теорема3.7. Пара протоколов (АРзПрАВсПр) является t-устойчивой схемой АПРС в сети из n процессоров, если n³4t+1.

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

Из определения 3.6 видно, что нам необходимо доказать условия завершения, корректности и конфиденциальности. Начнем с доказательства корректности схемы АПРС.

Корректность. С каждым несбоящим процессором Pi, который завершает протокол АРзПр мы ассоциируем уникальный полином hi(·,·) степени t от двух переменных и показываем, что каждые два несбоящих процессора Pi

и Pj имеют hi(·,·)=hj(·,·). Затем, мы показываем, что условия 1 и 2 корректности выполняются, относительно r=hi(0,0) (для некоторого несбоящего процессора Pi). Кроме того, мы показываем, что выход процессора Pi протокола АРзПр есть hi(i,0).

Для демонстрации этого мы используем две технических леммы, которые приведем без доказательства [BCG]. В лемме 3.5 показывается, что если 4t+1 долей несбоящих процессоров, находящихся в звезде в графе ОK

определяют единственный полином степени t от двух переменных. Лемма 3.6 демонстрирует тот факт, что полиномы индуцированные звездами каждой из двух процессоров одинаковы. Таким образом, только несбоящий процессор находит звезду, и, следовательно, секрет определяется единственным образом.

Лемма 3.5.

Пусть m³d+1, и пусть f1(·),...,fm(·) и g1(·),...,gm(·) - полиномы степени d над полем F с |Fm

такие, что для каждого 1£i£d+1 и каждого 1£j£m мы имеем fi(j)=gj(i) и gi(j)=fj(i). Тогда существует единственный полином h(·,·) степени d от двух переменных такой, что для каждого 1£i£m мы имеем h(·,i)=fi(·) и h(i,·)=gi(·).

Лемма 3.6.

Пусть h(·,·), h¢(·,·) – два полинома степени d от двух переменных над полем F с |Fd и пусть v1,...,vd+1 - различные элементы в F. Предположим, что для каждого 1£i,j£d+1 мы имеем h(vi,vj)=h¢(vi,vj). Тогда h(·,·)=h¢(·,·).




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