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

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

Введение

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

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

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

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

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

$\left[1,0,0,\dots ,0\right]$.

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

$\left[1,0,0,\dots ,0\right]$.

Описание

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

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

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

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

$\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]$

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

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

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

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

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

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

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

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

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

$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 $(t,n)$ — пороговой схемы разделения секрета над конечным полем $\mathbb {F}$ матрицу распределения $D$ можно записать в KGH нормальной форме.

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

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

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

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

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

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

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

$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]$

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

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

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

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

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

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

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

Следовательно, для полей с характеристикой $2$ в схеме Карнина — Грина — Хеллмана $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.