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

Схема Карнина — Грина — Хеллмана — пороговая схема разделения секрета на основе решения систем уравнений. Авторы — Эхуд Карнин (Шаблон:Lang-en), Джонатан Грин (Шаблон:Lang-en2) и Мартин Хеллман (Шаблон:Lang-en2).

Введение

Пороговая схема разделения секрета на конечных полях — схема обмена секретного ключа $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$ должны иметь интервал, включающий строку

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

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

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

Описание

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

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

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

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

$\left[\begin{array}{c}{s}_1\\ s_2\\ ⋮\\ s_r\\ s_{r+1}\end{array}\right]=\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}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 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\\ ⋮\\ a_{t-1}\end{array}\right]$

$n=r+1,r\le q^m-1$.

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

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

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

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

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

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

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

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

$D=\left[\begin{array}{ccccc}1& x_{12}& x_{13}& \cdots & x_{1t}\\ 1& x_{22}& x_{23}& \cdots & x_{2t}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& x_{r2}& x_{r3}& \cdots & x_{rt}\\ 1& 1& 1& \cdots & 1\\ 0& 1& 0& \cdots & 0\\ 0& 0& 1& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & 1\end{array}\right]$

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

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

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

$\mid 𝔽\mid \le n_{max,t}\le \mid 𝔽\mid +t-2$, $q^m>t$,

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

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

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

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

$D=\left[\begin{array}{ccc}1& x_1& x_1^2\\ ⋮& ⋮& ⋮\\ 1& x_{\mid 𝔽\mid -2}& x_{\mid 𝔽\mid -2}^2\\ 1& 1& 1\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$

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

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

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

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

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

Для любого поля $𝔽$ с характеристикой $2$ получается, что:

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

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

Литература

• Шаблон:Книга:Шнайер Б.: Прикладная криптография
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга