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

1. Дилер Двыбирает случайный полиномf₀(x) степениt+1 с единственным условием:f₀(0)=s- его секрет. Затем он посылает процессоруP_iего долюs_i=f₀(i). Кроме того, он выбирает 2Кслучайных полиномовf₁,...,f_2Kстепениt+1 и посылает процессоруP_iзначенияf_j(i) для каждогоj=1,...,2К.

2. Каждый процессор P_iраспространяет (посредством широковещательного канала)K/nслучайных битов(i-1)_K/n+j, дляj=1,...,K/n.

3. Дилер Драспространяет полиномыg_j=f_j+_jf₀для всехj=1,...,K.

4. Процессор P_iпроверяет, удовлетворяют ли его значения полиномам, распространяемым дилером. Если он обнаруживает ошибку, он ее декларирует для всех. Если более чемtпроцессоров сообщают об этом, тогда дилер считается нечестным и все процессоры принимают по умолчанию значение нуля как секрет дилераД.

5. Если менее чем tпроцессоров сообщили об ошибке, дилер распространяет значения, который он посылал в первом раунде тем процессорам, которые сообщали об ошибке дилера.

6. Каждый процессор P_iраспространяетK/nслучайных битов(i-1)_K/n+jдляj=1,...,K/n.

7. Дилер Драспространяет полиномыh_j=f_K+j+_jf₀для всехj=1,...,K.

8. Процессор P_iпроверяет, удовлетворяют ли значения, которые он имеет, полиномам, распространяемым дилеромД в 5-м раунде. Если он находит ошибку, он декларирует об этом всем процессорам сети. Если более чемtпроцессоров сообщают об ошибке, тогда дилер нечестный и все процессоры принимают по умолчанию значение нуля как секрет дилераД.

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

1. Каждый процессор P_iвыбирает случайный многочленh_iстепениt+1 такой, чтоh_i(0)=s_i- его собственная входная доля секрета. Он посылает процессоруP_jзначениеh_i(j).

2. Каждый процессор P_iвыбирает случайные полиномыp_i(x),q_i,1(x),...,q_i,2K(x) степениt+1 со свободным членом 0 и посылает процессоруP_jзначенияp_i(j),q_i,1(j),...,q_i,2K(j).

3. Каждый процессор P_iраспространяетKслучайных битов_l,(i-1)K/n+mдляl=1,...,nиm=K/n.

4. Каждый процессор распространяет следующие полиномы r_j=q_i,j+_i,jp_iдля каждогоj=1,...,K.

5. Каждый процессор P_iпроверяет, что информация процессораP_l, посланная ему в 1-м раунде, соответствует тому, чтоP_lраспространяет в 3-м раунде. Если имеется ошибка илиP_lраспространяет полином с ненулевым свободным членом, процессорP_iраспространяет сообщениеbad_l. Если более чемtпроцессоров распространяютbad_l, процессорP_lисключается из сети и все другие процессоры принимают как 0 долю процессораP_l. В противном случае,P_lраспространяет информацию, которую он посылал в раунде 1 процессорам, распространявшим сообщениеbad_l.

6. Каждый процессор P_iраспространяетKслучайных битов_l,(i-1)K/n+mдляl=1,...,nиm=1,...,K/n.

7. Каждый процессор P_iраспространяет следующие полиномыr_j=q_i,K+j+_i,jp_iдля каждыйj=1,...,K.

8. Каждый процессор P_iпроверяет, что информация, посланная процессоромP_l, в 1-м раунде и распространенная в 5-м раунде соответствует полиномам процессораP_l, распространенным в 7-м раунде. Если имеется ошибка илиP_lраспространил полином с ненулевым свободным членом процессорP_iраспространяетbad_l^r. Если более чемtпроцессоров распространилиbad_l, тогдаP_l– нечестен и все процессоры принимают его долю, равную 0.

9. Каждый процессор P_lраспределяет всем другим процессорам следующее значениеs_i+p₁(i)+p₂(i)+...+p(i), затем интерполирует полиномF(x)=f₀(x)+p₁(x)+p₂(x)+...+p_n(x)cиспользованием алгоритма с исправлением ошибок Берлекампа-Велча. Секрет будет равенs=F(0)=f(0).

Заметим, что если дилер Дчестен, в конце протоколаВсПрпротивник, даже зная секретsиtдолей «подкупленных» процессоров, ничего не узнает о долях секрета несбоящих процессоров, так как полином имеет степеньt+1, а ему необходимо для интерполяцииt+2 точки.