!!§!! Вспомогательная страница к разделу ((:interpolation ИНТЕРПОЛЯЦИЯ))
----
==Разделение секрета==
~~TOC~~
В книге ((#источники [1])) со ссылкой на путеводитель ((#источники [2])) описывается следующий исторический пример. В XIII-XIV веках в бельгийском городе Генте была построена ратушная башня. В «секрете», то есть самом надежном помещении,
хранились уставы и привилегии, имевшие важное значение для средневековой экономической жизни.
>//Преодолевавшая свое невежество цивилизация жаждала письменных формулировок. Более мощные коллективы, прежде всего городские группы, требовали фиксирования законов, туманный характер которых приводил к стольким злоупотреблениям. Перегруппировка социальных элементов в большие государства или в крупные княжества была благоприятна не только для возрождения законодательства, но также для распространения на обшрные территории унифицирующей юриспруденции// ((#источники [3])).
Помещение имело две двери, каждая с
тремя замками. Ключи от этих замков находились во владении различных цехов.
Документы хранились в шкафу, запиравшемся на три замка.
Один ключ от шкафа хранился у фогта[[( нем.) Vogt --- в средневековой Европе судебный чиновник, назначаемый императором или феодальным сеньором.]] а два других –-- у главного шеффена[[( нем.) Schöffen --- в средневековой Европе член судебной коллегии ; что-то вроде современного //народного заседателя//.]] Таким образом, получить доступ к документам могли только совместно собравшиеся
представители трех цехов, фогт и шеффен.
См. также и современную историю хранения ((https://ru.wikipedia.org/wiki/%D0%91%D0%B0%D0%BA%D1%82%D1%80%D0%B8%D0%B9%D1%81%D0%BA%D0%BE%D0%B5_%D0%B7%D0%BE%D0%BB%D0%BE%D1%82%D0%BE#cite_note-bbcmarch2011-2 Бактрийского золота))
----
Пусть требуется ``расщепить'' натуральное число (**ключ**) $ S $ на $ n $ частей, т.е. создать новые натуральные числа (**доли**) $ S_1,\dots, S_n $ и распределить их среди $ n $ участников некоторого консорциума дольщиков (**акционеров**). Разделение должно быть организовано таким образом, чтобы для данного значения (**порога**[[threshold (//англ.//)]]) $ k < n $ ключ $ 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) $. Далее, по ((:interpolation#интерполяционый_полином_в_форме_лагранжа формуле Лагранжа)) восстанавливается полином $ f(x) $ степени $ k-1 $ по модулю $ p $. Этот полином единствен и не может быть вычислен по любому набору долей, количество которых меньше $ k $. Свободный член этого полинома совпадает с $ S $. Единственной спецификой вычислений в $ \mathbb Z_p $
является та, что операцию деления, используемую в формуле Лагранжа, следует интерпретировать как операцию ((:modular#алгоритм_решения обращения знаменателя по модулю))
$ p $.
Вероятность подбора ключа случайным перебором может быть сведена к минимуму увеличением $ p $ (и техническим ограничением числа допустимых попыток его проверки).
===Децентрализованный протокол голосования==
Предположим, что в консорциуме из $ n $ участников нужно провести голосование --- анонимное и бинарное ("за" или "против"). Имеется некоторое количество $ k>2 $ администраторов --- счётчиков голосов, которым каждый участник посылает свои сообщения, но, которым не доверяет результатов подсчета голосов. Как организовать подсчет результатов так, чтобы избежать их подделки?
{{ :interpolation:scheme1.png?400 |}}
Нумеруем голосующих и администраторов. Организуем разделение секрета. С этой целью $ \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 $ если он голосует "против". Этот полином он держит в секрете.
{{ interpolation:scheme3.png |}}
Таким образом, у участников голосования образуются система полиномов $ f_1(x),\dots, f_n(x) $ таких, что составленная из них сумма, т.е. полином
$$ F(x)=\sum_{j=1}^n f_j(x) $$
обладает степенью $ \deg F \le k-1 $ и свободным членом равным количеству голосов "за" минус количество голосов "против", т.е. как раз результату голосования $ S $.
Теперь осталось организовать вычисление полинома $ F(x) $ при условии, что полиномы $ \{f_j(x)\}_{j=1}^n $ остаются секретными.
$ j $-й голосующий вычисляет значения своего полинома при аргументах $ x_1,\dots, x_k $ и посылает получившиеся значения соответствующим администраторам: число
$$ f_j(x_{\ell}) $$
отсылается от $ j $-го голосующего $ \ell $-му администратору. Фактически $ j $-й голосующий разделяет между администраторами свой секрет (результат своего голосования) по
☝
((#схема_Шамира_разделения_секрета схеме Шамира)).
{{ interpolation:scheme4.png |}}
Каждый администратор суммирует полученные им значения
$$
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{Red} 1.} $ Что препятствует подделке результата голосования $ \ell $-м администратором? --- Отсутствие видимой связи полученного им числа $ f_j(x_{\ell}) $ с числом $ f_j(0) $ (результатом голосования участника). В какую сторону его подделывать, чтобы добиться нужного жулику изменения результата голосования? Тем не менее, можно предположить, что в половине случаев случайное изменение доли секрета приведет именно к желаемой для жулика коррекции.
$ {\color{Red} 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} $. Таким образом, мы получаем задачу о восстановлении истинных значений полинома в узлах интерполяции, количество и расположение которых исходно не известно. Подобные задачи возникают в теории ((:codes:cyclic:bch кодов, исправляющих ошибки)). Конструктивное решение этой задачи возможно при условии, что количество истинных значений полинома $ F(x) $ значительно превосходит потенциальное количество искаженных. Более того, этих истинных значений должно быть в избытке и по отношению к количеству коэффициентов полинома, т.е. к его степени.
В схеме предыдущего пункта будем по-прежнему считать, что степень полинома $ F(x) $ не превосходит $ k-1 $. Но вот количество администраторов увеличим: пусть их теперь будет $ K>k $.
===Интерполяция по избыточной таблице==
!!§!! Подробное изложение математических результатов настоящего пункта
☞
((:interpolation:systemerr ЗДЕСЬ))
Предположим, что задана таблица рациональных чисел
$$
\begin{array}{c||c|c|c|c}
x & x_1 & x_2 & \ldots & x_K \\
\hline
y & y_1 & y_2 & \ldots & y_K
\end{array} \quad
\quad \{x_j,y_j\}_{j=1}^K \subset \mathbb Q,
$$
узлы $ \{x_j\}_{j=1}^K $ --- все различны.
Эта таблица ((:interpolation#интерполяция однозначно определяет)) полином $ f(x) \in \mathbb R[x] $ такой, что $ \left\{f(x_j)=y_j \right\}_{j=1}^K $ и $ \deg f \le K-1 $. Если же оказывается, что $ k=\deg f < K-1 $, то получается, что таблица избыточна: тот же полином $ f(x) $ можно построить --- например, в формах ((:interpolation#интерполяционый_полином_в_форме_лагранжа Лагранжа)) или ((:interpolation#интерполяционный_полином_в_форме_ньютона Ньютона)) --- по любой выборке из этой таблицы, состоящей из $ (k+1) $-го узла.
Можно ли установить точную степень полинома $ f(x) $, не вычисляя его непосредственно?
Обозначим
$$ W(x)=\prod_{j=1}^K (x-x_j) $$
и вычислим последовательность величин:
$$
\tau_k = \sum_{j=1}^{K} y_j \frac{x_j^{k}}{W^{\prime}(x_j)} \quad \mbox{ при } \ k \in \{0,\dots, 2\,K-2 \} \, .
$$
!!Т!! **Теорема 1.** //Для того, чтобы полином, построенный по таблице, имел степень// $ k
☞