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

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

Пороговая схема разделения секрета на конечных полях — схема обмена секретного ключа ${\displaystyle k}$ между ${\displaystyle n}$ участниками таким образом, что любые ${\displaystyle t}$ из них могут восстановить секрет, но любая группа из ${\displaystyle t-1}$ или менее — не может. Схема состоит из двух фаз. В первой фазе — фазе распределения — некоторая сторона (называемая поставщиком) создаёт доли участия ${\displaystyle s_{1},s_{2},\dots ,s_{n}}$, используя алгоритм распределения ${\displaystyle D}$. Для каждого ${\displaystyle i}$ поставщик лично отдает долю участия ${\displaystyle s_{i}}$ участнику ${\displaystyle P_{i}}$. Вторая фаза, называемая фазой восстановления, происходит, когда ${\displaystyle t}$ участников ${\displaystyle P_{i_{1}},P_{i_{2}},\dots ,P_{i_{t}}}$ хотят восстановить секретный ключ ${\displaystyle k}$.

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

Для PIL пороговой схемы можно задать требования в терминах свойств матрицы распределения ${\displaystyle D:}$

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

${\displaystyle \left[1,0,0,\dots ,0\right]}$.

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

${\displaystyle \left[1,0,0,\dots ,0\right]}$.

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

${\displaystyle \alpha _{i}\equiv \alpha ^{i},i={\overline {1,q^{m-1}}}}$.

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

Затем он строит ${\displaystyle n}$ долей участия ${\displaystyle s_{i}}$ следующим образом

${\displaystyle \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]}$

${\displaystyle n=r+1,r\leq q^{m}-1}$.

Потом поставщик отправляет ${\displaystyle s_{i}}$ участнику ${\displaystyle P_{i}}$, следя за тем, чтобы любые ${\displaystyle t}$ строк матрицы ${\displaystyle D}$, обозначенные как ${\displaystyle D_{i_{1},i_{2},\dots ,i_{t}}}$, составляли обратимую матрицу ${\displaystyle t\times t}$.

Отсюда, ${\displaystyle {\bar {y}}=D_{i_{1},i_{2},\dots ,i_{t}}^{-1}\cdot {\bar {S}}_{i_{1},i_{2},\dots ,i_{t}}}$, где ${\displaystyle {\bar {S}}_{i_{1},i_{2},\dots ,i_{t}}-}$ вектор — столбец, состоящий из ${\displaystyle s_{i_{1}},s_{i_{2}},\dots ,s_{i_{t}}}$.

Таким образом, секрет ${\displaystyle k}$ может быть вычислен.

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

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

Таким образом, с точки зрения определения максимального ${\displaystyle n}$ мы можем сказать, что схема Карнина — Грина — Хеллмана эффективней, чем схема Шамира.

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

${\displaystyle 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]}$

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

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

Тогда ${\displaystyle n_{max,t}}$ удовлетворяет:

${\displaystyle \mid \mathbb {F} \mid \leq n_{max,t}\leq \mid \mathbb {F} \mid +t-2}$, ${\displaystyle q^{m}>t}$,

${\displaystyle n_{max,t}=t}$, ${\displaystyle q^{m}\leq t}$,

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

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

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

${\displaystyle 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]}$

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

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

Пронумеруем строки матрицы ${\displaystyle D}$ от ${\displaystyle 1}$ до ${\displaystyle n}$ сверху вниз.

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

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

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

${\displaystyle n_{max,3}=\mid \mathbb {F} \mid +1=\mid \mathbb {F} \mid +3-2=\mid \mathbb {F} \mid +t-2}$.

Следовательно, для полей с характеристикой ${\displaystyle 2}$ в схеме Карнина — Грина — Хеллмана ${\displaystyle n_{max,3}}$ по теореме 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 0018-9448. — doi:10.1109/TIT.1983.1056621.
• Stinson, D. R. Cryptography: theory and practice. — Chapman and Hall/CRC, 2005. — ISBN 978-1584885085.