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

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

  1. Каждый процессор Pi выбирает случайный многочлен hi степени t+1 такой, что hi(0)=si его собственная входная доля секрета. Он посылает процессору Pj значение hi(j).
  2. Каждый процессор Pi выбирает случайные полиномы pi(x), qi,1(x),...,qi,2K(x) степени t+1 со свободным членом 0 и посылает участнику Pj значения pi(j), qi,1(j),...,qi,2K(j).
  3. Каждый процессор Pi распространяет K случайных битов
    γl,(i1)K/n+m для l=1,...,n и m=K/n.
  4. Каждый процессор распространяет следующие полиномы rj=qi,j+ γi,jpi для каждого j=1,...,K.
  5. Каждый процессор Pi проверяет, что информация процессора Pl, посланная ему в 1м раунде, соответствует тому, что Pl распространяет в 3м раунде. Если имеется ошибка или Pl распространяет полином с ненулевым свободным членом, процессор Pi распространяет сообщение badl. Если более чем t процессоров распространяют badl, процессор Pl исключается из сети и все другие процессоры принимают как 0 долю процессора Pl. В противном случае, Pl распространяет информацию, которую он посылал в раунде 1 процессорам, распространявшим сообщение badl.
  6. Каждый процессор Pi распространяет K случайных битов
    δl,(i1)K/n+m для l=1,...,n и m=1,...,K/n.
  7. Каждый процессор Pi распространяет следующие полиномы rj=qi,K+j+ δi,jpi для каждый j=1,...,K.
  8. Каждый процессор Pi проверяет, что информация, посланная процессором Pl, в 1м раунде и распространенная в 5м раунде, соответствует полиномам процессора Pl, распространенным в 7м раунде. Если имеется ошибка или Pl распространил полином с ненулевым свободным членом процессор Pi распространяет badlr. Если более чем t процессоров распространили badl, тогда Pl нечестен и все процессоры принимают его долю, равную 0.
  9. Каждый процессор Pl распределяет всем другим процессорам следующее значение si+p1(i)+p2(i)+...+p(i), затем интерполирует полином F(x)=f0(x)+p1(x)+p2(x)+...+pn(x) c использованием алгоритма с исправлением ошибок БерлекампаВелча. Секрет будет равен s=F(0)=f(0).

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


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

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