Доказательство безопасности схемы АПРС
Теорема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 с |F|³m
такие, что для каждого 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 с |F|³d и пусть v1,...,vd+1 - различные элементы в F. Предположим, что для каждого 1£i,j£d+1 мы имеем h(vi,vj)=h¢(vi,vj). Тогда h(·,·)=h¢(·,·).
Далее, пусть 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,j|³t+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).
Каждый несбоящий процессор 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).
Пусть I обозначает множество чередуемых последовательностей 2t полиномов степени t.
Лемма 3.7.
Пусть F – поле с |F|³d
и пусть sÎF. Тогда для каждой чередуемой последовательности f1(·),...,fd(·), g1(·),...,gd(·) в I существует единственный полином h(·,·)ÎHs такой, что для каждого 1£i£d мы имеем h(·,i)=fi(·) и h(i,·)=gi(·).
Доказательство.
См. работу [BCG].
Далее предположим, что дилер честен и пусть s
– разделяемое значение. Тогда дилер имеет на шаге 1 протокола АРзПр полином h(·,·) с равномерным распределением вероятностей над Hs. Кроме того, вся необходимая информация о множестве из t
процессоров, полученная во время выполнения протокола АРзПр, является чередуемой последовательностью f1(·),...,ft(·), g1(·),...,gt(·) в I такой, что для каждого 1£i£t мы имеем h(·,i)=fi(·) и h(i,·)=gi(·).
Из леммы 3.7 следует, что для каждого разделяемого значения sÎF это соответствие между полиномами в Hs и чередуемыми последовательностями в I
– является взаимнооднозначным. Следовательно, равномерное распределение над полиномами из Hs индуцирует равномерное распределение вероятностей над чередуемыми последовательностями в I. <
