Теория и практика защиты программ


         

-Пороговые схемы


Используемая в данном подразделе (n,t)-пороговая схема, известная как схема разделения секрета Шамира, – это протокол между n+1 участниками, в котором один из участников, именуемый дилер - Д, распределяет частичную информацию (доли) о секрете между n участниками так, что:

·     любая группа из менее чем t участников не может получить любую информацию о секрете;

·     любая группа из не менее чем t участников может вычислить секрет за полиномиальное время.

Пусть секрет s

- элемент поля F. Чтобы распределить s

среди участников P1,...,Pn, (где n<÷F÷) дилер выбирает полином fÎF[x] степени не более t-1, удовлетворяющий f(0)=s. Участник Pi

получает si=f(xi) как свою долю секрета s, где xiÎF\{0} – общедоступная информация для Pi (xi¹xj для i¹j).

Вследствие того, что существует один и только один полином степени не менее k-1, удовлетворяющий f(xi)=si для k значений i, схема Шамира удовлетворяет определению (n,t)-пороговых схем. Любые t участников могут найти значение f по формуле:

.

Следовательно

,

где a1,...,ak получаются из

Таким образом, каждый ai является ненулевым и может быть легко вычислен из общедоступной информации.



Содержание  Назад  Вперед