• Главная
• Новости
• Статьи
• Карта сайта
• Поиск
• Контакт
• Рекомендации

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

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

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,_(i1)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,(i1)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 точки.

Новостной блок