УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу ИНТЕРПОЛЯЦИЯ


Разделение секрета

И

В книге [1] со ссылкой на путеводитель [2] описывается следующий исторический пример. В XIII-XIV веках в бельгийском городе Генте была построена ратушная башня. В «секрете», то есть самом надежном помещении, хранились уставы и привилегии, имевшие важное значение для средневековой экономической жизни.

Преодолевавшая свое невежество цивилизация жаждала письменных формулировок. Более мощные коллективы, прежде всего городские группы, требовали фиксирования законов, туманный характер которых приводил к стольким злоупотреблениям. Перегруппировка социальных элементов в большие государства или в крупные княжества была благоприятна не только для возрождения законодательства, но также для распространения на обшрные территории унифицирующей юриспруденции [3].

Помещение имело две двери, каждая с тремя замками. Ключи от этих замков находились во владении различных цехов. Документы хранились в шкафу, запиравшемся на три замка. Один ключ от шкафа хранился у фогта1) а два других –– у главного шеффена2) Таким образом, получить доступ к документам могли только совместно собравшиеся представители трех цехов, фогт и шеффен.


Пусть требуется ``расщепить'' натуральное число (ключ) S на n частей, т.е. создать новые натуральные числа S_1,\dots, S_n (доли) и распределить их среди n участников некоторого консорциума дольщиков (акционеров). Разделение должно быть организовано таким образом, чтобы для данного значения k < n (порога3)), ключ S

1. можно восстановить из любой подсистемы \{ S_{i_1},\dots, S_{i_k} \} \subset \{S_1,\dots,S_n\}, содержащей k долей;

2. нельзя восстановить из меньшего числа долей.

Создание собственно ключа S, а также организация вычисления его долей и распространения между дольщиками доверяются честному посреднику (дилеру). Такая схема разделения секрета называется (k,n)-пороговой.

Схема Шамира разделения секрета

Среди нескольких существующих алгоритмов разделения секрета имеется следующая схема, предложенная Шамиром [1]. Она основана на решении задаче полиномиальной интерполяции. Сначала посредник выбирает достаточно большое простое число p> S, p \gg n и составляется полином степени k-1

f(x):=S+a_1x+a_2x^2+\dots + a_{k-1} x^{k-1} , \quad \{a_1,\dots,a_{k-1} \} \subset \{0,1,\dots, p-1 \} \, .

Свободный член совпадает с ключом, а все остальные коэффициенты — произвольные. Далее, посредник нумерует акционеров числами 1,2 \dots, n, и j-му из них сообщает значение y_j= f(j) \pmod p; это значение и считается j-й долей секретного ключа S. Для восстановления секрета S, дольщики должны собрать не менее k пар (j, y_j). Далее, по формуле Лагранжа восстанавливается полином f(x) степени k-1 по модулю p. Этот полином единствен и не может быть вычислен по любому набору долей, количество которых меньше k. Свободный член этого полинома совпадает с S. Единственной спецификой вычислений в \mathbb Z_p является та, что операцию деления, используемую в формуле Лагранжа, следует интерпретировать как операцию обращения знаменателя по модулю p.

Вероятность подбора ключа случайным перебором может быть сведена к минимуму увеличением p (и техническим ограничением числа допустимых попыток его проверки).

Децентрализованный протокол голосования

Предположим, что в консорциуме из n участников нужно провести голосование — анонимное и бинарное («за» или «против»). Имеется некоторое количество k>2 администраторов — счётчиков голосов, которым каждый участник посылает свои сообщения, но, которым не доверяет результатов подсчета голосов. Как организовать подсчет результатов так, чтобы избежать их подделки?

Нумеруем голосующих и администраторов. Организуем разделение секрета. С этой целью \ellый администратор придумывает и выкладывает в открытый доступ произвольное ненулевое целое число x_{\ell}. Полученные k чисел x_1,\dots, x_k должны быть различными (если это не так, то коллизии нужно устранить).

В то же время, j-й голосующий придумывает полином f_j(x) c целыми коэффициентами степени \le k-1, и с фиксированным свободным членом f_j(0)=+1 если он голосует «за» и f_j(0)=-1 если он голосует «против». Этот полином он держит в секрете.

Таким образом, у участников голосования образуются система полиномов f_1(x),\dots, f_n(x) таких, что составленная из них сумма, т.е. полином

F(x)=\sum_{j=1}^n f_j(x)

обладает степенью \deg F \le k-1 и свободным членом равным количеству голосов «за» минус количество голосов «против», т.е. как раз результату голосования.

Теперь осталось организовать вычисление полинома F(x) при условии, что полиномы \{f_j(x)\}_{j=1}^n остаются секретными.

j-й голосующий вычисляет значения своего полинома при аргументах x_1,\dots, x_k и посылает получившиеся значения соответствующим администраторам: число

f_j(x_{\ell})

отсылается от j-го голосующего \ell-му администратору. Фактически j-й голосующий разделяет между администраторами свой секрет (результат своего голосования) по схеме Шамира.

Каждый администратор суммирует полученные им значения

Y_{\ell}=\sum_{j=1}^n f_j(x_{\ell})

и выкладывает Y_{\ell} в открытый доступ.

Очевидно Y_{\ell}= F(x_{\ell}), т.е. в открытом доступе оказываются k значений полинома F(x), степень которого не превышает k-1. Значениями \{Y_{\ell}\}_{\ell=1}^k полином F(x) восстанавливается однозначно, и, следовательно, любой участник процесса голосования способен определить его результат по значению F(0).

Возможности фальсификации

{\color{RubineRed} 1.} Что препятствует подделке результата голосования \ellм администратором? — Отсутствие видимой связи полученного им числа f_j(x_{\ell}) с числом f_j(0) (результатом голосования участника). В какую сторону его подделывать, чтобы добиться нужного жулику изменения результата голосования? Тем не менее, можно предположить, что в половине случаев случайное изменение доли секрета приведет именно к желаемой для жулика коррекции.

{\color{RubineRed} 2.} Сами участники голосования предполагаются честными. Если jй из них сгенерирует полином \widetilde f_j(x) такой, что \widetilde f_j(0)=+3 и потом разошлет администраторам значения \widetilde f_j(x_{\ell}), то результатом подсчета голосов будет +2 лишних голоса «за»…

Как проконтролировать возможность подделки значений Y_1,Y_2,\dots администраторами? Заметим, что подмена истинного значения Y_{\ell} может произойти и неумышлено, а именно, в результате искажения при пересылке какой-то доли y_{j \ell}. Таким образом, мы получаем задачу о восстановлении истинных значений полинома в узлах интерполяции, количество и расположение которых исходно не известно. Подобные задачи возникают в теории кодов, исправляющих ошибки. Конструктивное решение этой задачи возможно при условии, что количество истинных значений полинома F(x) значительно превосходит потенциальное количество искаженных. Более того, этих истинных значений должно быть в избытке и по отношению к количеству коэффициентов полинома, т.е. к его степени.

В схеме предыдущего пункта будем по-прежнему считать, что степень полинома F(x) не превосходит k-1. Но вот количество администраторов увеличим: пусть их теперь будет K>k.

Источники

[1]. Kersten A.G., Shared Secret Schemes aus geometrischer Sicht. Dissertation, Mitteilungen aus dem Mathematischen Seminar Gießen, Hefte 208, 1992

[2]. Gent und seine Schönheiten. Thill Verlag, Brüssel,1990

[3]. Блох М. Феодальное общество. М.Наука, 1986

[4]. Shamir A., How to share a secret, Communications of the ACM, 1979, 22 (11),pp. 612–613

[5]. Bogdanov A., Uteshev A., Khvatov V., Error detection in the decentralized voting protocol. Computational Science and Its Applications – ICCSA 2019. ICCSA 2019. Springer, LNCS, 2019, v.11620, pp. 485-494.

1) ( нем.) Vogt — в средневековой Европе судебный чиновник, назначаемый императором или феодальным сеньором.
2) ( нем.) Schöffen — в средневековой Европе член судебной коллегии ; что-то вроде современного народного заседателя.
3) threshold (англ.)

2019/07/19 16:07 редактировал au