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


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


Каждый несбоящий процессор Pj распространяет h(j,0) на шаге 7 и, таким образом, h(·,0) - интерполируемый полином аккумулируемого множества Ui

процессора Pi на шаге 8. Следовательно, выход процедуры СКОП на шаге 8 будет h(·,0) и выход протокола АВсПр будет h(0,0)=r.

Завершение. Условие 1. Если дилер честен, то для каждых двух несбоящих процессоров Pj и Pk, оба сообщения (ОК,j,k) и (ОК,k,j) будут распространены так как fj(k)=h(k,j)=gk(j) и gj(k)=h(j,k)=fk(j). Таким образом, каждый несбоящий процессор Pi будет в конечном счете иметь клику размера n-t в графе OKi. Поэтому процедура ЗВЗ будет находить звезду в OKi и шаг 4 будет завершен. Шаг 6 будет завершен, так как вход процедуры СКОП (а именно, аккумулируемое множество Ui, которое базируется на звезде, найденной на шагах 4 или 5) - событийно (t,t)-интерполируем.

Условие 2. Пусть Pi – несбоящий процессор, который завершил протокол АРзПр и пусть (Ci,Di) - звезда, найденная процессором Pi. Тогда (Ci,Di) будет в конечном счете звездой в графе OKj для каждого несбоящего процессора Pj, даже если Pj не завершил протокол АРзПр. Кроме того, процессор Pj получит (Ci,Di) сообщение (посланное Pi на шаге 4), и будет проверять на шаге 5, что множества (Ci,Di) формируют звезду в OKj. После нахождения звезды процессор Pj

выполнит шаг 6 и завершит протокол АРзПр.

Условие 3. Если все несбоящие процессоры начали выполнять протокол АВсПр, тогда аккумулируемое множество Si на шаге 8 для каждого несбоящего процессора Pi, событийно (t,t)-интерполируемо. Таким образом, все несбоящие процессоры завершат процедуру СКОП и протокол АВсПр.

Конфиденциальность. Мы используем следующую систему обозначения. Для значения v пусть Hv

обозначает множество полиномов степени t

от двух переменных со свободным коэффициентом v. Будем говорить, что последовательность f1(·),...,ft(·), g1(·),...,gt(·) полиномов чередуемы, если для каждых 1£i,j£t мы имеем fi(j)=gj(i).


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