Протокол аРзПр

Вычисления дилера (по входу s):

1. Выбрать случайный полином h(^,^) степениtот двух переменных такой, чтоh(0,0)=s(Т.е.h(x,y)=, гдеh_0,0=sи все другие коэффициентыh_0,1,...,h_t,tвыбраны однородно и независимо над F). Для каждого 1inпосылает полиномыf_i(^)=h(^,i) иg_i(^)=(h_i, ^) процессоруP_i.

Вычисления процессора P_i:

2. После полученияf_i(^) иg_i(^) от дилера и для каждого 1jnпосылаетf_i(j) процессоруP_j.

3. После получения v_i,jот процессораP_jпроверяет, еслиv_i,j=g_i(j), тогда этот процессор распространяет (OK,i,j).

4. После получения (OK,j,k), контролирует существование звезды вOK, используя процедуруЗВЗ, описанную выше. Если звезда (C_i,D_i) найдена, переходит к шагу 6 и посылает (C_i,D_i) всем процессорам.

5. После получения сообщения (C_j,D_j) добавляет (C_j,D_j) к множеству «предлагаемых звезд». Пока звезда не найдена, всякий раз, когда получено распространяемое сообщение (OK,k,l), проверяет, формируют ли (Cj,D_j) звезду в графе OK_i.

6. После нахождения звезды (C_i,D_i) и еслиiD_iскорректировать полиномg_i(^), основываясь на сообщении о верификации, полученном от процессоров изD_iи с использованием кодовcисправлением ошибок (процедурыСКОП, описанной ниже). А именно, пустьV_i={(j,v_i,j)jD_i}, тогда установить (t,V_i)СКОП=(g_i(^)).

7. Как толькоg_i(^) локально скорректирован, выдаетg(0).

Протокол аВсПр

Вычисления для процессора P_i (по входу i и с параметрами R{P₁,...,P_n}).

7. Посылает a_iпроцессорам изR.

9. Пусть S_i={(j,a_j)a_jполучен изP_j. ЕслиP_iR, заканчивает без выхода. В противном случае установить (t,S_i)СКОП=z_i(^) и выдаетz_i(0).

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

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

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

Корректность.С каждым несбоящим процессоромP_i, который завершает протоколАРзПрмы ассоциируем уникальный полиномh_i(^,^) степениtот двух переменных и показываем, что каждые два несбоящих процессораP_iиP_jимеютh_i(^,^)=h_j(^,^). Затем, мы показываем, что условия 1 и 2 корректности выполняются, относительноr=h_i(0,0) (для некоторого несбоящего процессораP_i). Кроме того, мы показываем, что выход процессораP_iпротоколаАРзПрестьh_i(i,0).

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

Лемма 3.5.Пустьmd+1, и пустьf₁(^),...,f_m(^) иg₁(^),...,g_m(^) - полиномы степениdнад полемFсFmтакие, что для каждого 1id+1 и каждого 1jmмы имеемf_i(j)=g_j(i) иg_i(j)=f_j(i). Тогда существует единственный полиномh(^,^) степениdот двух переменных такой, что для каждого 1imмы имеемh(^,i)=f_i(^) иh(i,^)=g_i(^).

Лемма 3.6.Пустьh(^,^),h(^,^) – два полинома степениdот двух переменных над полемFсFdи пустьv₁,...,v_d+1- различные элементы вF. Предположим, что для каждого 1i,jd+1 мы имеемh(v_i,v_j)=h(v_i,v_j). Тогдаh(^,^)=h(^,^).

Далее, пусть P_i– несбоящий процессор, который завершил протоколАРзПри пусть (C_i,D_i) - звезда, найденная процессоромP_i. ПустьD_i- множество несбоящих процессоров вD_iпустьC_i- множество несбоящих процессоров вC_iи, таким образом,D_iD_i-tn-2tиC_iC_i-tn-3tt+1 (так как 4t+1). В соответствии с леммой 3.5 полиномыf_j(^),g_j(^) процессоровjD_iопределяют единственный полином степениtот двух переменных. Пустьh_i(^,^) обозначает этот полином. А именно,h_i(^,^) - полином, ассоциированный сP_i. Отметим также, чтоh_i(^,^) фиксирован, как толькоP_iзавершает протоколАРзПр. Для каждого другого несбоящего процессораP_jпустьI_i,j- множество несбоящих процессоров изD_iD_j. Так какn4t+1, мы имеемD_iD_jn-2t2t+1 и, таким образом,I_i,jt+1. Для каждых двух процессоровk,lI_i,j, мы имеемh_i(k,l)=v_k,l=h_j(k,l), гдеv_k,l– верификационная часть, посланнаяP_kкP_lна шаге 2 протоколаАРзПр. Применяя результаты леммы 3.6, мы имеемh_i(^,^)=h_j(^,^). Значениеr, требуемое в условии корректности, является равнымh_i(0,0).

Мы утверждаем, что условие 1 (а именно, что если дилер честен и выдает значение s, тоr=s). Если дилер честен и он выбрал полиномh(^,^) на шаге 1, тогда для каждых двух процессоровP_k,P_lD_iмы имеемh_i(k,l)=h(k,l). В соответствии с леммой 3.6 мы снова можем получитьh_i(^,^)=h(^,^). Далее нижний индекс в полиномеh(^,^) опускается.

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

В заключение мы показываем, как выполняется условие 2 (а именно, что выход P_iпротоколаАВсПрестьr). Каждый несбоящий процессорP_jраспространяетh(j,0) на шаге 7 и, таким образом,h(^,0) - интерполируемый полином аккумулируемого множестваU_iпроцессораP_iна шаге 8. Следовательно, выход процедурыСКОПна шаге 8 будетh(^,0) и выход протоколаАВсПрбудетh(0,0)=r.

Завершение.Условие 1. Если дилер честен, то для каждых двух несбоящих процессоровP_jиP_k, оба сообщения (ОК,j,k) и (ОК,k,j) будут распространены так какf_j(k)=h(k,j)=g_k(j) иg_j(k)=h(j,k)=f_k(j). Таким образом, каждый несбоящий процессорP_iбудет в конечном счете иметь клику размераn-tв графеOK_i. Поэтому процедураЗВЗбудет находить звезду вOK_iи шаг 4 будет завершен. Шаг 6 будет завершен, так как вход процедурыСКОП(а именно, аккумулируемое множествоU_i, которое базируется на звезде, найденной на шагах 4 или 5) - событийно (t,t)-интерполируем.

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

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

Конфиденциальность.Мы используем следующую систему обозначения. Для значенияvпустьH_vобозначает множество полиномов степениtот двух переменных со свободным коэффициентомv. Будем говорить, что последовательностьf₁(^),...,f_t(^),g₁(^),...,g_t(^) полиномовчередуемы, если для каждых 1i,jtмы имеемf_i(j)=g_j(i). ПустьIобозначает множество чередуемых последовательностей 2tполиномов степениt.

Лемма 3.7.ПустьF– поле сFdи пустьsF. Тогда для каждой чередуемой последовательностиf₁(^),...,f_d(^),g₁(^),...,g_d(^) вIсуществует единственный полиномh(^,^)H_sтакой, что для каждого 1idмы имеемh(^,i)=f_i(^) иh(i,^)=g_i(^).

Доказательство.См. работу [BCG].

Далее предположим, что дилер честен и пусть s– разделяемое значение. Тогда дилер имеет на шаге 1 протоколаАРзПрполиномh(^,^) с равномерным распределением вероятностей надH_s. Кроме того, вся необходимая информация о множестве изtпроцессоров, полученная во время выполнения протоколаАРзПр, является чередуемой последовательностьюf₁(^),...,f_t(^),g₁(^),...,g_t(^) вIтакой, что для каждого 1itмы имеемh(^,i)=f_i(^) иh(i,^)=g_i(^).

Из леммы 3.7 следует, что для каждого разделяемого значения sFэто соответствие между полиномами вH_sи чередуемыми последовательностями в I– является взаимнооднозначным. Следовательно, равномерное распределение над полиномами изH_sиндуцирует равномерное распределение вероятностей над чередуемыми последовательностями вI.