Схема Карнина — Грина — Хеллмана

Схема Карнина — Грина — Хеллмана — пороговая схема разделения секрета на основе решения систем уравнений. Авторы — Эхуд Карнин (англ. Ehud D. Karnin), Джонатан Грин (Jonathan W. Greene) и Мартин Хеллман (Martin E. Hellman).

Введение

Пороговая схема разделения секрета на конечных полях — схема обмена секретного ключа <math>k</math> между <math>n</math> участниками таким образом, что любые <math>t</math> из них могут восстановить секрет, но любая группа из <math>t-1</math> или менее — не может. Схема состоит из двух фаз. В первой фазе — фазе распределения — некоторая сторона (называемая поставщиком) создаёт доли участия <math>s_1, s_2, \dots, s_n</math>, используя алгоритм распределения <math>D</math>. Для каждого <math>i</math> поставщик лично отдает долю участия <math>s_i</math> участнику <math>P_i</math>. Вторая фаза, называемая фазой восстановления, происходит, когда <math>t</math> участников <math>P_{i_1}, P_{i_2}, \dots, P_{i_t}</math> хотят восстановить секретный ключ <math>k</math>.

Типы пороговых схем

• Пороговая схема разделения секрета называется совершенной, если по крайней мере <math> t </math> участников могут восстановить секрет, а любая группа из <math>t-1</math> или менее сторон — не может.
• Пороговая схема разделения секрета называется линейной, если восстановление секрета <math> k </math> происходит путём взятия линейной комбинации <math> t </math> долей участия.
• Пороговая схема разделения секрета называется идеальной, если размер долей участий такой же, как у секрета <math> k </math>.
• Совершенная, идеальная и линейная пороговая схема разделения секрета называется PIL (perfect, ideal and linear) пороговой схемой разделения секрета.

Для PIL пороговой схемы можно задать требования в терминах свойств матрицы распределения <math>D:</math>

1.Полнота — любая группа, включающая не менее <math>t</math> участников, может вычислить секрет <math>k</math>. Таким образом, любые <math>t</math> строк матрицы распределения <math>D</math> должны иметь интервал, включающий строку

<math>\left[ 1, 0, 0, \dots, 0 \right]</math>.

2.Конфиденциальность — ни одна группа, включающая менее чем <math>t</math> участников, не может получить информацию о секретном ключе <math>k</math>. Инными словами, <math>t-1</math> или меньше строк матрицы распределения <math>D</math> не могут включать интервал, включающий строку

<math>\left[ 1, 0, 0, \dots, 0 \right]</math>.

Описание

Рассмотрим конечное поле <math>\mathrm{GF}(q^{m})</math>. Пусть <math>\alpha</math> простой элемент <math>\mathrm{GF}(q^{m})</math> и пусть

<math>\alpha_i \equiv \alpha^{i}, i = \overline{1,q^{m-1}}</math>.

Поставщик случайно выбирает <math>a_1, a_2, \dots, a_{t-1} </math> из <math>\mathrm{GF}(q^{m})</math>.

Затем он строит <math>n</math> долей участия <math>s_i</math> следующим образом

<math>\left[

\begin{array}{c} s_{1}\\s_{2}\\\vdots \\s_{r}\\s_{r+1} \\ \end{array}\right] =\quad\left[\begin{array}{ccccc} 1 & \alpha_{1} & \alpha_{1}^{2} & \cdots & \alpha_{1}^{t-1} \\ 1 & \alpha_{2} & \alpha_{2}^{2} & \cdots & \alpha_{2}^{t-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \alpha_{r} & \alpha_{r}^{2} & \cdots & \alpha_{r}^{t-1} \\ 0 & 0 & 0 & \cdots & 1 \end{array}\right] \left[ \begin{array}{c} k\\a_1\\a_2\\\vdots\\a_{t-1}\\ \end{array}\right]</math>

<math> n = r + 1, r \le q^{m} - 1 </math>.

Потом поставщик отправляет <math>s_i</math> участнику <math>P_i</math>, следя за тем, чтобы любые <math> t </math> строк матрицы <math> D </math>, обозначенные как <math> D_{i_1, i_2, \dots, i_t} </math>, составляли обратимую матрицу <math>t \times t</math>.

Отсюда, <math> \bar{y} = D_{i_1, i_2, \dots, i_t}^{-1} \cdot \bar{S}_{i_1, i_2, \dots, i_t}</math>, где <math> \bar{S}_{i_1, i_2, \dots, i_t} -</math> вектор - столбец, состоящий из <math> s_{i_1}, s_{i_2}, \dots, s_{i_t}</math>.

Таким образом, секрет <math> k </math> может быть вычислен.

Кроме того, для любых <math> t-1 </math> строк матрицы <math> D </math>, строка <math>[\begin{array}{ccccc}\gamma, 0, 0, \cdots, 0\\\end{array}]</math>, <math>\forall \gamma \in \mathrm{GF}(q^{m}) \setminus \{0\}</math> не будет входить в <math> D_{i_1, i_2, \dots, i_{t-1}} .</math>

Значит, <math> t - 1 </math> или менее участников не могут получить никакой информации о секрете <math> k </math>. Следовательно, можно построить пороговую схему разделения секрета для <math> r + 1 </math>, где <math> r + 1 = \mid \mathbb{F} \mid </math>, т.е. число участников <math> n </math> может быть равно размеру поля.

Таким образом, с точки зрения определения максимального <math> n </math> мы можем сказать, что схема Карнина — Грина — Хеллмана эффективней, чем схема Шамира.

Пример оптимальной схемы

• <math> n_{max, t} </math> — это наибольшее <math> n </math>, для которого можно построить PIL <math> (t, n) -</math> пороговую схему разделения секрета над конечным полем <math> \mathbb{F} </math>.
• <math> D </math> — матрица распределения PIL <math> (t, n) </math> - пороговой схемы разделения секрета над конечным полем <math> \mathbb{F} </math> записана в KGH нормальной форме, если удовлетворяет следующему равенству:

<math> D =

\quad\left[\begin{array}{ccccc} 1 & x_{12} & x_{13} & \cdots & x_{1t} \\ 1 & x_{22} & x_{23} & \cdots & x_{2t} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{r2} & x_{r3} & \cdots & x_{rt} \\ 1 & 1 & 1 & \cdots & 1 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1\\ \end{array}\right] </math>

Для любой PIL <math> (t, n) </math> - пороговой схемы разделения секрета над конечным полем <math> \mathbb{F} </math> матрицу распределения <math> D </math> можно записать в KGH нормальной форме.

Теорема 1. Допустим, у нас есть секретное пространство <math> \mathcal{S} </math> = <math> \mathbb{F} </math> = <math>\mathrm{GF}(q^{m})</math>

Тогда <math> n_{max, t} </math> удовлетворяет:

<math> \mid \mathbb{F} \mid \le n_{max, t} \le \mid \mathbb{F} \mid + t - 2</math>, <math>q^{m} > t</math>,

<math> n_{max,t} = t</math>, <math> q^{m} \le t </math>,

Теорема 2. Пусть <math>\mathbb{F} = \mathrm{GF}(2^{m})</math> — конечное поле и <math> n = \mid \mathbb{F} \mid+ 1</math>. Тогда существует надежная PIL <math> (3, n) </math> - пороговая схема разделения секрета над полем <math> \mathbb{F} </math>.

Доказательство. Характеристикой поля <math>\mathbb{F} = \mathrm{GF}(2^{m})</math> является <math> 2 </math>. Все нетривиальные элементы (элементы не равные <math> 0 </math> или <math> 1 </math>) поля <math> \mathbb{F} </math> имеют мультипликативный порядок больше, чем <math> 2 </math>. Пусть <math> x_{1}, x_{2}, \cdots, x_{\mid \mathbb{F} \mid - 2} </math> — элементы поля <math> \mathbb{F} </math> не равные <math> 0 </math> или <math> 1 </math>.

Тогда матрица распределения примет следующий вид:

<math> D =

\quad\left[\begin{array}{ccccc} 1 & x_{1} & x_{1}^{2} \\ \vdots & \vdots & \vdots \\ 1 & x_{\mid \mathbb{F} \mid - 2} & x_{\mid \mathbb{F} \mid - 2}^{2} \\ 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array}\right] </math>

Таким образом, <math> D </math> — это матрица PIL <math> (3, n) -</math> пороговой схемы разделения секрета размером <math> (\mid \mathbb{F} \mid + 1) \times 3 .</math>

Рассмотрим полноту.

Пронумеруем строки матрицы <math> D </math> от <math> 1 </math> до <math> n </math> сверху-вниз.

• Случай I. Любые 3 строки из набора <math> \{1, \cdots, n - 2\} </math> могут восстановить секрет ввиду обратимости матрицы Вандермонда.
• Случай II. Допустим даны строки <math>\left[ 0, 1, 0 \right]</math> и <math>\left[ 0, 0, 1\right]</math> и еще одна строка из набора <math> \{1, \cdots, n - 2\} </math>. Тогда очевидно, что можно восстановить секрет.
• Случай III. Допустим одна из строк принадлежит набору <math>\{ \left[ 0, 1, 0\right], \left[ 0, 0, 1\right] \} </math>, а две остальные выбраны из <math> \{1, \cdots, n - 2\}. </math> Тогда с помощью элементарных преобразований строк можно убрать строку из набора <math>\{ \left[ 0, 1, 0\right], \left[ 0, 0, 1\right] \} </math>. В итоге, останется система Вандермонта размером <math> 2 \times 2 </math>, которая обратима.

Свойство полноты доказано. Доказательство конфиденциальности проходит похожим образом.

Для любого поля <math> \mathbb{F} </math> с характеристикой <math> 2 </math> получается, что:

<math> n_{max, 3} = \mid \mathbb{F} \mid + 1 = \mid \mathbb{F} \mid + 3 -2 = \mid \mathbb{F} \mid + t - 2 </math>.

Следовательно, для полей с характеристикой <math> 2 </math> в схеме Карнина — Грина — Хеллмана <math> n_{max, 3} </math> по теореме 1 достигает верхней границы.

Литература

• Шнайер Б. 23.2 Алгоритмы разделения секрета. Karnin — Greene — Hellman // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 590. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• Yvo Desmedt, Brian King, Berry Schoenmakers Revisiting the Karnin, Greene and Hellman Bounds // ICITS '08 Proceedings of the 3rd international conference on Information Theoretic Security. — 2008. — С. 183 - 198. — ISBN 978-3-540-85092-2. — DOI:10.1007/978-3-540-85093-9_18.
• Karnin E.D., Greene J. , Hellman M.E. On secret sharing systems // Information Theory, IEEE Transactions on. — 2003. — С. 35 - 41. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0018-9448&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0018-9448]. — DOI:10.1109/TIT.1983.1056621.
• Stinson, D. R. Cryptography: theory and practice. — Chapman and Hall/CRC, 2005. — ISBN 978-1584885085.