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


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


Далее, пусть Pi – несбоящий процессор, который завершил протокол АРзПр и пусть (Ci,Di) - звезда, найденная процессором Pi. Пусть Di¢ - множество несбоящих процессоров в Di пусть Ci¢ - множество несбоящих процессоров в Ci и, таким образом, |Di¢|³|Di|-t³n-2t и |Ci¢|³|Ci|-t³n-3t³t+1 (так как 4t+1). В соответствии с леммой 3.5 полиномы fj(·),gj(·) процессоров jÎDi¢ определяют единственный полином степени t от двух переменных. Пусть hi(·,·) обозначает этот полином. А именно, hi(·,·) - полином, ассоциированный с Pi. Отметим также, что hi(·,·) фиксирован, как только Pi завершает протокол АРзПр. Для каждого другого несбоящего процессора Pj

пусть Ii,j - множество несбоящих процессоров из DiÇDj. Так как n³4t+1, мы имеем |DiÇDj|n-2t³2t+1 и, таким образом, |Ii,jt+1. Для каждых двух процессоров k,lÎIi,j, мы имеем hi(k,l)=vk,l=hj(k,l), где vk,l – верификационная часть, посланная Pk к Pl на шаге 2 протокола АРзПр. Применяя результаты леммы 3.6, мы имеем hi(·,·)=hj(·,·). Значение r, требуемое в условии корректности, является равным hi(0,0).

Мы утверждаем, что условие 1 (а именно, что если дилер честен и выдает значение s, то r=s). Если дилер честен и он выбрал полином h(·,·) на шаге 1, тогда для каждых двух процессоров Pk,PlÎDi¢ мы имеем hi(k,l)=h(k,l). В соответствии с леммой 3.6 мы снова можем получить hi(·,·)=h(·,·). Далее нижний индекс в полиноме h(·,·) опускается.

Далее мы показываем, что выход каждого несбоящего процессора Pi протокола АРзПр есть h(i,0). Полином h(i,·) - интерполируемый полином аккумулируемого множества Ui процессора Pi на шаге 6. Следовательно, выход процедуры СКОП на шаге 6 будет h(i,·) и выход протокола АРзПр будет h(i,0).

В заключение мы показываем, как выполняется условие 2 (а именно, что выход Pi протокола АВсПр есть r).


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