Пусть требуется ``расщепить'' натуральное число (ключ) $ S $ на $ n $ частей, т.е. создать новые натуральные числа (доли) $ S_1,\dots, S_n $ и распределить их среди $ n $ участников некоторого консорциума дольщиков (акционеров). Разделение должно быть организовано таким образом, чтобы для данного значения (порога³⁾) $ 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) $. Далее, по формуле Лагранжа восстанавливается полином $ 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 $ и свободным членом равным количеству голосов «за» минус количество голосов «против», т.е. как раз результату голосования $ S $.

Теперь осталось организовать вычисление полинома $ 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{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} $. Таким образом, мы получаем задачу о восстановлении истинных значений полинома в узлах интерполяции, количество и расположение которых исходно не известно. Подобные задачи возникают в теории кодов, исправляющих ошибки. Конструктивное решение этой задачи возможно при условии, что количество истинных значений полинома $ F(x) $ значительно превосходит потенциальное количество искаженных. Более того, этих истинных значений должно быть в избытке и по отношению к количеству коэффициентов полинома, т.е. к его степени.

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

Подробное изложение математических результатов настоящего пункта ☞ ЗДЕСЬ

Предположим, что задана таблица рациональных чисел $$ \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 $ — все различны. Эта таблица однозначно определяет полином $ 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) $ можно построить — например, в формах Лагранжа или Ньютона — по любой выборке из этой таблицы, состоящей из $ (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<K-1 $ необходимо и достаточно, чтобы были выполнены условия

$$ \tau_0=0,\dots, \tau_{K-k-2}=0, \tau_{K-k-1} \ne 0 \, . $$

Выражения $ \tau_j $ можно использовать и для явного нахождения коэффициентов интерполяционного полинома; подробности ☞ ЗДЕСЬ. Но мы ограничимся здесь тем коэффициентом, который только и существен для нашей задачи разделения секрета.

Доказать, что при условии $ \{x_j\ne 0 \}_{j=1}^K $ свободный член интерполяционного полинома можно вычислить по формуле

$$ a_{K-1}=f(0) =(-1)^{K-1} \tau_{-1} \prod_{j=1}^K x_{j} \quad \mbox{ где } \ \tau_{-1}:= \sum_{j=1}^{K} y_j \frac{1}{x_jW^{\prime}(x_j)} \, . $$

Предположим теперь, что некоторые из значений $ y_1,\dots, y_K $, исходно сгенерированные полиномом степени $ k< K-1 $, впоследствии оказались искаженными. Но мы не знаем ни количества этих искажений, ни их местоположений. Можно ожидать, что наличие искажений приведет к тому, что степень полинома, построенного по искаженной таблице будет больше $ k $, и, следовательно, некоторые из равенств $ \tau_0=0,\dots, \tau_{K-k-2}=0 $ будут нарушены. Это обстоятельство дает нам достаточный критерий наличия ошибки в интерполяционной таблице.

Для обнаружения места этой ошибки в таблице (фактически номера узла, в котором эта ошибка произошла) вычислим значения $ \tau_k $ (в количестве, которое будет понятно из приведенных ниже результатов) и составим из этих величин определители вида $$ \mathcal H_{L}(x;\{ \tau \}) := \left| \begin{array}{lllll} \tau_0 & \tau_1 & \tau_2 & \ldots & \tau_{L} \\ \tau_1 & \tau_2 & \tau_3 &\ldots & \tau_{L+1} \\ \vdots & \vdots & \vdots & & \vdots \\ \tau_{L-1} & \tau_{L} & \tau_{L+1} & \ldots & \tau_{2L-1} \\ 1 & x & x^2 & \ldots & x^{L} \end{array} \right|_{(L+1) \times (L+1)} $$ для некоторого количества чисел $ L \in \mathbb N $. Раскладывая определитель по последней строке, получим представление $ \mathcal H_{L}(x;\{ \tau \}) $ в виде полинома по $ x $, который иногда называется $ L $-м ганкелевым полиномом, порожденным последовательностью $ \{\tau_k \} $.

Пример. Интерполяционная таблица

$$ \begin{array}{c||c|c|c|c|c|c|c|c|c} x & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline y & 19 & -2 & -7 & -8 & 3 & 14 & 37 & 35 & 107 \\ \end{array} $$ генерируется полиномом второй степени, за исключением некоторых ошибочных значений. Построим последовательные ганкелевы полиномы и проверим каждый из них на наличи корней среди значений узлов $ \{-3,-2,,\dots, 5 \} $.

Решение. Вычисляем значения $ \tau_k $. $$ W(x)=(x+3)(x+2)\times \dots \times (x-5) \, , $$ $$ W^{\prime}(-3)=40320, \ W^{\prime}(-2)=-5040, \dots, W^{\prime}(5)=40320 \, . $$ $$ \tau_0=\frac{19}{40320}+\frac{(-2)}{(-5040)}+\dots + \frac{107}{40320} =\frac{1}{70} \, . $$ Это значение отлично от нуля и, следовательно, предъявленная интерполяционная таблица не может соответствовать полиному $ 2 $-й степени: если она и была изначально сгенерирована таким полиномом, то факт наличия в ней ошибки считаем установленным. Вычисляем далее: $$ \ \tau_1=\frac{53}{1680},\ \tau_2 = \frac{193}{1680},\ \tau_3 =\frac{47}{112}, \ \tau_4=\frac{407}{240},\ \tau_5=\frac{11233}{1680}, \dots $$ Затем приступаем к вычислению собственно ганкелевых полиномов, порождаемых этими значениями: $$ \mathcal H_{1}(x; \{ \tau \})\equiv \frac{1}{70}x-\frac{53}{1680}, \ \mathcal H_{2}(x; \{ \tau \})\equiv \frac{1823}{2822400}x^2-\frac{6691}{2822400}x+\frac{29}{705600}, $$ Эти два полинома не обращаются в нуль ни при одном $ x $ из $ \{-3,-2,\dots, 5\} $. А вот следующий полином обладает этим свойством: $$ \mathcal H_{3}(x; \{ \tau \})\equiv \frac{33}{313600}(x+2)(x-1)(x-4) \, . $$ Оказывается, что числа $ \{-2,1,4 \} $ являются значениями узлов интерполяции, в которых табличные значения не совпадают со значениями полинома $ f(x):=4\,x^2+3\, x- 8 $; все остальные узлы $ x_j $ таблицы соответствуют истинным значениям $ f(x_j) $. Тем самым, полином $ \mathcal H_{3}(x; \{ \tau \}) $ можно назвать⁴⁾ полиномом локаторов ошибок для избыточной, но кое-где ошибочной интерполяционной таблицы. ♦

Эмпирически обнаруженный факт обосновывается следующим общим теоретическим результатом, в котором предполагается, что число ошибочных значений $ y $ в интерполяционной таблице равно $ E $.

Теорема 2. Пусть $ E \in \{1,2,\dots, \lfloor K/2 \rfloor-1 \} $ и $ e_1,\dots,e_E $ — различные числа из $ \{1,2,\dots, K\} $. Пусть полином $ f(x) $ имеет степень $ k< K-2E $. Пусть интерполяционная таблица удовлетворяет условиям

$ {\color{Red} 1.} $ $ y_j=f(x_j) $ при $ j \in \{1,\dots, K\} \setminus \{ e_1,\dots,e_E \} $,

$ {\color{Red} 2.} $ $ \widehat y_{e_s}:=f(x_{e_s}) \ne y_{e_s} $ при $ s\in \{1,\dots, E \} $.

Тогда $$ \mathcal H_{E} (x;\{\tau\}) \equiv \frac{ \displaystyle \prod_{s=1}^E ( y_{e_s} - \widehat y_{e_s}) \prod_{1\le s < t \le E } ( x_{e_t} - x_{e_s})^2 }{\displaystyle \prod_{s=1}^E W^{\prime}(x_{e_s})} \prod_{s=1}^E (x-x_{e_s}) \, . $$

Таким образом, при выполнении условий теоремы, полином $ \mathcal H_{E} (x;\{\tau\}) $ является полиномом локаторов ошибок. К сожалению, в нашей постановке задачи, точное число $ E $ заранее не известно и приходится проверять потенциальных кандидатов на локаторов ошибок последовательно, начиная с полиномов $ \mathcal H_{1} (x;\{\tau\}), \mathcal H_{2} (x;\{\tau\}) $ и т.д.

Возвращаемся к проблеме об искажении результатов голосования за счет (случайных или намеренных) ошибок в значениях величин $ \{ Y_j \} $, находящихся у администраторов. Предполагаем, что число возможных ошибок не превосходит некоторого заранее известной оценки $ E $, достаточно малой по сравнению с общим количеством долей. Для обнаружения этих ошибок в рамках подхода предыдущего пункта необходимо создать избыточность в задаче интерполяции. Этого возможно достичь двумя способами: либо уменьшением степеней полиномов $ f_j(x) $, генерируемых голосующими, либо увеличением количества администраторов. Математика, лежащая в основании этих альтернатив, будет одинаковой, поэтому мы ограничимся рассмотрением случая когда количество администраторов $ K $ избыточно по отношению к степени «секретного полинома»: $ K> k-1 \ge \deg f_j(x) -1 $. Алгоритм обнаружения ошибок работает следующим образом.

Алгоритм обнаружения ошибок

1. Последовательно вычисляем величины $ \tau_0,\dots, \tau_{K-k-3} $. Если все они равны нулю, то считаем, что ошибки не обнаружены.

2. Если какое-то из этих чисел обращается в нуль, факт наличия ошибки считается установленным. Последовательно вычисляем полиномы $$ \mathcal H_{1} (x;\{\tau\}), \mathcal H_{2} (x;\{\tau\}), \dots $$ Для каждого полинома $ \mathcal H_{L} (x;\{\tau\}) $ (отличного от тождественного нуля) проверяем находятся ли его корни во множестве $ \{x_1,\dots,x_K\} $.

3. Пусть $ \mathcal H_{E} (x;\{\tau\}) $ с $ E< \lfloor (K-k+1)/2 \rfloor $ будет первым из таких полиномов: все его корни $ x_{e_1},\dots, x_{e_E} $ лежат во множестве $ \{x_1,\dots,x_K\} $. Выбрасываем соответствующие значения $ \{(x_{e_s},Y_{e_s})\}_{s=1}^E $ из интерполяционной таблицы и на оставшейся ее части вычисляем значение $ F(0) $ с помощью формулы из упражнения предыдущего пункта $$ a_{k-1}= (-1)^{K-E-1}\tau_{-1} \prod x_j $$ (здесь $ \tau_{-1} $ и $ \prod $ вычисляются для таблицы, в которой остались только истинные значения). Получившееся значение считаем результатом голосованиия.

4. Если ни один из полиномов $$ \mathcal H_{1} (x;\{\tau\}),\dots, \mathcal H_{\lfloor (K-k+1)/2 \rfloor-1} (x;\{\tau\}) $$ не обладает свойством из пункта 3 , то число ошибочных долей превосходит предположенное ограничение на их количество, и локализация этих ошибок невозможна.

Теперь обратимся ко второй проблеме, поставленной в пункте ☝ ВОЗМОЖНОСТИ ФАЛЬСИФИКАЦИИ: как проверить корректность голосования каждого участника, не нарушив при этом принципа конфиденциальности?

[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. Текст ☞ bc2019_r.pdf