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

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

ВведениеПравить

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

Типы пороговых схемПравить

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

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

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

$\left[1,0,0,\dots <!--\; \dots \; -->,0\right]$$\left[ 1, 0, 0, \dots, 0 \right]$ .

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

$\left[1,0,0,\dots <!--\; \dots \; -->,0\right]$$\left[ 1, 0, 0, \dots, 0 \right]$ .

ОписаниеПравить

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

${\mathrm{\alpha <!--\; \alpha \; -->}}_i\equiv <!--\; \equiv \; -->{\mathrm{\alpha <!--\; \alpha \; -->}}^i,i=\stackrel{¯<!--\; ¯\; -->}{1,q^{m-<!--\; -\; -->1}}$$\alpha _{i}\equiv \alpha ^{i},i={\overline {1,q^{m-1}}}$ .

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

Затем он строит $n$$n$  долей участия $s_i$$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\le <!--\; \le \; -->q^m-<!--\; -\; -->1$$n=r+1,r\leq q^{m}-1$ .

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

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

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

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

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

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

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

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

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

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

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

$n_{max,t}=t$$n_{{max,t}}=t$ , $q^m\le <!--\; \le \; -->t$$q^{{m}}\leq t$ ,

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

Доказательство. Характеристикой поля $\mathbb{F}=\mathrm{G}\mathrm{F}(2^m)$$\mathbb {F} =\mathrm {GF} (2^{m})$  является $2$$2$ . Все нетривиальные элементы (элементы не равные $0$$0$  или $1$$1$ ) поля $\mathbb{F}$${\mathbb {F}}$  имеют мультипликативный порядок больше, чем $2$$2$ . Пусть $x_1,x_2,\cdots <!--\; \cdots \; -->,x_{\mid <!--\; \mid \; -->\mathbb{F}\mid <!--\; \mid \; -->-<!--\; -\; -->2}$$x_{1},x_{2},\cdots ,x_{\mid \mathbb {F} \mid -2}$  — элементы поля $\mathbb{F}$${\mathbb {F}}$  не равные $0$$0$  или $1$$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$$D$  — это матрица PIL $(3,n)-<!--\; -\; -->$$(3,n)-$  пороговой схемы разделения секрета размером $(\mid <!--\; \mid \; -->\mathbb{F}\mid <!--\; \mid \; -->+1)\times <!--\; \times \; -->3.$$(\mid \mathbb {F} \mid +1)\times 3.$ 

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

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

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

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

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

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

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