Esquema Karnin-Green-Hellman

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 16 de octubre de 2018; las comprobaciones requieren 52 ediciones .

El esquema Karnin-Green-Hellman es un esquema de intercambio secreto de umbral basado en la resolución de sistemas de ecuaciones . Los autores son Ehud D. Karnin , Jonathan W. Greene y Martin E. Hellman .

Introducción

Un esquema de intercambio de secretos de umbral en campos finitos es un esquema para intercambiar una clave secreta entre participantes de tal manera que cualquiera de ellos puede recuperar el secreto, pero cualquier grupo de o menos no puede. El esquema consta de dos fases. En la primera fase, la fase de asignación , alguna parte (llamada proveedor ) crea acciones usando un algoritmo de asignación . Para cada uno , el proveedor entrega personalmente la parte de participación al participante . La segunda fase, denominada fase de recuperación , se produce cuando los participantes quieren recuperar la clave secreta . $k$ $norte$ $t$ $t-1$ $s_1, s_2, \puntos, s_n$ $D$ $i$ $si}$ $Pi}$ $t$ $P_{i_1}, P_{i_2}, \puntos, P_{i_t}$ $k$

Tipos de esquemas de umbral

Se dice que un esquema de umbral de intercambio de secretos es perfecto si al menos las partes pueden recuperar el secreto, pero cualquier grupo de partes o menos no puede. $t$ $t-1$
Un esquema de umbral de intercambio de secretos se denomina lineal si el secreto se recupera tomando una combinación lineal de apuestas. $k$ $t$
Un esquema de umbral de uso compartido de secretos se denomina ideal si el tamaño de las acciones es el mismo que el del secreto . $k$
Un esquema de intercambio de secretos de umbral perfecto, ideal y lineal se denomina esquema de intercambio de secretos de umbral perfecto, ideal y lineal (PIL) .

El esquema de umbral de PIL se puede especificar en términos de propiedades de la matriz de distribución ${\ estilo de visualización D:}$

1. Completitud : cualquier grupo que incluya al menos miembros puede calcular el secreto . Por lo tanto, cualquier fila de la matriz de distribución debe tener un intervalo que incluya la fila $t$ $k$ $t$ $D$

\izquierda[ 1, 0, 0, \puntos, 0 \derecha]

2. Confidencialidad : ningún grupo con menos de miembros puede obtener información sobre la clave secreta . En otras palabras, o menos filas de la matriz de distribución no pueden incluir un intervalo que incluya la fila $t$ $k$ $t-1$ $D$

\izquierda[ 1, 0, 0, \puntos, 0 \derecha]

Descripción

Considere un campo finito . Sea un elemento simple y sea $\mathrm{GF}(q^{m})$ $\alfa$ $\mathrm{GF}(q^{m})$

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

El proveedor elige aleatoriamente de . $a_{1},a_{2},\puntos,a_{{t-1}}$ $\mathrm{GF}(q^{m})$

Luego traza la equidad de la siguiente manera $norte$ $si}$

\left[ \begin{matriz}{c} s_{1}\\s_{2}\\\vdots \\s_{r}\\s_{r+1} \\ \end{matriz}\right] = \quad\left[\begin{array}{cccc} 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{matriz}\right] \ izquierda[ \begin{matriz}{c} k\\a_1\\a_2\\\vdots\\a_{t-1}\\ \end{matriz}\right]

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

Luego, el proveedor envía al participante , asegurándose de que cualquier fila de la matriz , indicada como , forme una matriz invertible . $si}$ $Pi}$ $t$ $D$ $D_{i_1, i_2, \puntos, i_t}$ $t\veces t$

Por lo tanto, , donde el vector es una columna que consta de . $\bar{y} = D_{i_1, i_2, \puntos, i_t}^{-1} \cdot \bar{S}_{i_1, i_2, \puntos, i_t}$ ${\bar {S}}_{i_{1},i_{2},\dots,i_{t}}-$ $s_{{i_{1}}},s_{{i_{2}}},\puntos,s_{{i_{t}}}$

Por lo tanto, el secreto se puede calcular. $k$

Además, para cualquier fila de matrix , row , no se incluirá en $t-1$ $D$ $[{\begin{matriz}{ccccc}\gamma,0,0,\cdots,0\\\end{matriz}}]$ ${\displaystyle \forall \gamma \in \mathrm {GF} (q^{m})\setminus \{0\))$ $D_{i_{1},i_{2},\dots,i_{t-1)).$

Esto significa que menos o menos participantes no pueden obtener ninguna información sobre el secreto . Por lo tanto, es posible construir un esquema de uso compartido secreto de umbral para , donde , es decir, el número de participantes puede ser igual al tamaño del campo. $t-1$ $k$ $r+1$ $r+1=\mid {\mathbb{F}}\mid$ $norte$

Así, desde el punto de vista de la determinación del máximo , podemos decir que el esquema Karnin-Green-Hellman es más eficiente que el esquema Shamir . $norte$

Un ejemplo de un esquema óptimo

$n_{{máx,t}}$ es el más grande para el que es posible construir un esquema de intercambio secreto de umbral PIL sobre un campo finito . $norte$ ${\ estilo de visualización (t, n)-}$ ${\matemáticas {F}}$
$D$ - matriz de distribución PIL - esquema de compartición de secretos de umbral sobre el campo final se escribe en forma normal KGH si satisface la siguiente igualdad: ${\ estilo de visualización (t, n)}$ ${\matemáticas {F}}$

D=\quad \left[{\begin{matriz}{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{matriz}}\right]

Para cualquier PIL , un esquema de intercambio secreto de umbral sobre un campo finito , la matriz de distribución se puede escribir en forma normal KGH. ${\ estilo de visualización (t, n)}$ ${\matemáticas {F}}$ $D$

Teorema 1. Digamos que tenemos un espacio secreto = = ${\ matemáticas {S))$ ${\matemáticas {F}}$ $\mathrm{GF}(q^{m})$

Entonces satisface: $n_{{máx,t}}$

\mid {\mathbb {F}}\mid \leq n_{{max,t}}\leq \mid {\mathbb {F}}\mid +t-2

. .

q^{{m}}>t

n_{{máx,t}}=t

. .

q^{{m}}\leq t

Teorema 2. Sea un campo finito y . Luego hay un PIL confiable : un esquema de umbral de intercambio de secretos sobre el campo . $\mathbb {F} =\mathrm {GF} (2^{m})$ $n=\mid \mathbb {F} \mid +1$ ${\ estilo de visualización (3, n)}$ ${\matemáticas {F}}$

Prueba. La característica del campo es . Todos los campos de elementos no triviales (elementos que no son iguales a o ) tienen un orden multiplicativo mayor que . Sean elementos de campo no iguales a o . $\mathbb {F} =\mathrm {GF} (2^{m})$ $2$ ${\ estilo de visualización 0}$ $una$ ${\matemáticas {F}}$ $2$ ${\displaystyle x_{1},x_{2},\cdots,x_{\mid \mathbb {F} \mid -2))$ ${\matemáticas {F}}$ ${\ estilo de visualización 0}$ $una$

Entonces la matriz de distribución tomará la siguiente forma:

D=\quad \left[{\begin{matriz}{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{matriz}}\right]

Por lo tanto, es la matriz PIL del esquema de intercambio secreto de umbral de tamaño $D$ ${\ estilo de visualización (3, n) -}$ $(\mid \mathbb {F} \mid +1)\times 3.$

Considere la integridad .

Numeramos las filas de la matriz de arriba a abajo. $D$ $una$ $norte$

Caso I. Cualquiera de las 3 filas del conjunto puede recuperar el secreto debido a la invertibilidad de la matriz de Vandermonde . $\{1,\cdots,n-2\}$
Caso II. Digamos cadenas dadas y una cadena más del conjunto . Entonces es obvio que el secreto se puede recuperar. ${\ estilo de visualización \ izquierda [0,1,0 \ derecha]}$ ${\ estilo de visualización \ izquierda [0,0,1 \ derecha]}$ $\{1,\cdots,n-2\}$
Caso III. Supongamos que una de las cadenas pertenece al conjunto y las otras dos se seleccionan de Entonces, utilizando transformaciones elementales de cadenas, puede eliminar la cadena del conjunto . Como resultado, habrá un sistema Vandermont de tamaño , que es reversible. ${\displaystyle \{\left[0,1,0\right],\left[0,0,1\right]\))$ ${\ estilo de visualización \ {1, \ cdots, n-2 \}.}$ ${\displaystyle \{\left[0,1,0\right],\left[0,0,1\right]\))$ $2 veces 2$

Se prueba la propiedad de completitud. La prueba de confidencialidad funciona de manera similar.

Para cualquier campo con una característica , resulta que: ${\matemáticas {F}}$ $2$

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

En consecuencia, para campos con características en el esquema Karnin-Green-Hellman, por el Teorema 1, alcanza el límite superior. $2$ ${\ estilo de visualización n_ {máx, 3}}$

Literatura

Schneier B. 23.2 Algoritmos para compartir un secreto. Karnin - Greene - Hellman // Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumf, 2002. - S. 590. - 816 p. - 3000 copias. - ISBN 5-89392-055-4 .
Yvo Desmedt, Brian King, Berry Schoenmakers. Revisando los límites de Karnin, Greene y Hellman // Actas de ICITS '08 de la 3.ª conferencia internacional sobre seguridad teórica de la información. - 2008. - S. 183-198 . — ISBN 978-3-540-85092-2 . -doi : 10.1007 / 978-3-540-85093-9_18 .
Karnin ED, Greene J. , Hellman ME Sobre sistemas secretos para compartir // Teoría de la información, IEEE Transactions on. - 2003. - S. 35-41 . — ISSN 0018-9448 . -doi : 10.1109/ TIT.1983.1056621 .
Stinson, D. R. Criptografía: teoría y práctica. - Chapman and Hall/CRC, 2005. - ISBN 978-1584885085 .