Esquema de cifrado GGH

El esquema de cifrado GGH ( Ing. Goldreich–Goldwasser–Halevi ) es un sistema criptográfico asimétrico basado en redes . También hay un esquema de firma GGH .

El criptosistema se basa en soluciones al problema de encontrar el vector más corto y el problema de encontrar el vector más cercano . El esquema de cifrado GGH, publicado en 1997 por los científicos Oded Goldreich , Shafi Goldwasser y Shai Halevi , utiliza una función de entrada secreta unidireccional , porque dada cualquier base de celosía, es fácil generar un vector cerca de un punto de celosía. Por ejemplo, tomar un punto de red y agregar un pequeño vector de error. Para volver del vector de error al punto inicial de la red, se necesita una base especial. En 1999, Phong Q. Nguyen [1] perfeccionó el esquema de cifrado GGH original, lo que permitió resolver cuatro de los cinco problemas de GGH y obtener información parcial sobre este último. Si bien GGH puede ser seguro con ciertas opciones de parámetros, su eficacia sobre los criptosistemas tradicionales de clave pública sigue siendo discutible [2] . A menudo, el cifrado requiere una dimensión de red alta, mientras que el tamaño de la clave crece aproximadamente cuadráticamente con respecto al tamaño de la red [2] .

El único esquema de celosía que puede manejar grandes dimensiones es NTRU [3] .

Algoritmo

GGH incluye una clave pública y una clave privada [4] . La clave privada es la base de la red con matriz unimodular . $B$ $L$ $tu$

La clave pública es otra base de la red del formulario . $L$ $B'=UB$

Deje que el espacio de mensajes M consista en vectores pertenecientes al intervalo . ${\ estilo de visualización (m_{1},...,m_{n})}$ $-M<m_{i}<M$

Cifrado

Dado un mensaje , un error y una clave pública : $m=(m_{1},...,m_{n})$ $mi$ $B'$

v=\suma m_{i}b_{i}'

En notación matricial:

v=m\cdot B'

Debe recordarse que consta de valores enteros, es un punto de celosía y, por lo tanto , también es un punto de celosía. Entonces el texto cifrado es: $metro$ $b'$ $v$

c=v+e=m\cdot B'+e

Transcripción

Para descifrar el texto cifrado se calcula:

c\cdot B^{-1}=(m\cdot B^{\prime }+e)B^{-1}=m\cdot U\cdot B\cdot B^{-1}+e\cdot B ^{-1}=m\cdot U+e\cdot B^{-1}

Para eliminar , si es lo suficientemente pequeño, se utiliza el método de redondeo de Babai [5] . $e\cdot B^{-1}$

Luego para obtener el texto:

m=m\cdot U\cdot U^{-1}

Análisis de seguridad

Esta sección analiza varias formas de atacar un criptosistema [6] .

Ataque por redondeo

El ataque de redondeo es el ataque más obvio de este sistema criptográfico, a excepción del ataque de fuerza bruta - búsqueda del vector de error Su esencia es usar la clave pública B para invertir la función de la misma manera que cuando se usa la clave privada R Es decir, sabiendo , puedes calcular . Por lo tanto, puede encontrar un vector . En dimensiones inferiores a 80 LLL , el algoritmo puede determinar correctamente la base; sin embargo, a partir de dimensiones 100 y superiores, este ataque es peor que una enumeración trivial del vector de error. ${\ estilo de visualización e.}$ $c=B\cdot v+e$ $B^{-1}\cdot c=v+B^{-1}\cdot e$ $d=B^{-1}\cdot e$

Ataque de tormenta

Este algoritmo es un refinamiento obvio del ataque de redondeo. Aquí usamos el mejor algoritmo de aproximación para el problema del vector más corto. En particular, se usa el algoritmo del plano más cercano en lugar del algoritmo de redondeo de Babai. Funciona así. Dado un punto y base reducida c = { } para LLL . Se consideran todos los espacios afines = { + } : }. Para todos existe un hiperplano más cercano al punto . Además , se proyecta un punto en el espacio dimensional (n - 1), que está cubierto por = { } . Esto da un nuevo punto y una nueva base = { }. El algoritmo ahora procede recursivamente para encontrar un punto en esta red (n - 1)-dimensional cercana a . Finalmente, el algoritmo establece . Este método funciona mucho más rápido que el anterior. Sin embargo, su carga de trabajo también crece exponencialmente con la dimensión de la red. Los experimentos muestran que cuando se usa LLL como un algoritmo de reducción de celosía, se requiere cierto tiempo de búsqueda, a partir de los tamaños 110-120. El ataque se vuelve inviable a partir del tamaño 140-150. ${\ estilo de visualización c}$ $B$ ${b_{1}},\puntos {b_{n}}$ ${\ estilo de visualización {H_ {k}}}$ $k\cdot {b_{n))$ $\sum _{i=0}^{n-1}{a_{i}}\cdot {b_{i}}$ ${a_{i}}\in {\matemáticas {R}}$ $k\in {\mathcal {Z))$ ${\ estilo de visualización {H_ {k}}}$ ${\ estilo de visualización c}$ $B$ ${b_{1}},\puntos {b_{n}}$ $ck\cdot {b_{n))$ ${\ estilo de visualización c'}$ $B'$ ${b_{1}},\puntos {b_{n}}$ ${\ estilo de visualización p'}$ ${\ estilo de visualización c'}$ $p=p'+k\cdot {b_{n))$

Ataque de inyección

Otra forma que se usa a menudo para aproximar el problema de encontrar el vector más cercano es incrustar n vectores base y un punto para el cual es necesario encontrar un punto de red cercano en una red de (n + 1) dimensiones. ${\ estilo de visualización c}$

$B'={\begin{pmatrix}\vdots &\vdots &\vdots &\cdots &\vdots \\c&b_{1}&b_{2}&\cdots &b_{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&0&0&\cdots &0\end{pmatrix}}$

Luego, se utiliza el algoritmo de reducción de celosía para encontrar el vector distinto de cero más corto en , con la esperanza de que los primeros n elementos de este vector sean los puntos más cercanos a . Los experimentos realizados en este ataque (utilizando LLL como herramienta para encontrar los vectores más cortos) indican que funciona hasta dimensiones alrededor de 110-120, lo que es mejor que el ataque de redondeo, que se vuelve peor que la búsqueda trivial después de la dimensión 100. ${\ estilo de visualización L (B')}$ ${\ estilo de visualización c}$

Estimación de la efectividad de los ataques [7]

Ataque estimado por redondeo

Deje que se creen cinco bases cerradas en cada dimensión. Cada base se elige como = + rand , donde I es la matriz identidad y rand es una matriz cuadrada cuyos miembros se eligen uniformemente del rango . Para cada base se calcula el valor = , donde es la norma euclidiana de la fila más grande , y . Por cada base cerrada se generan cinco bases abiertas $norte$ ${\ estilo de visualización {R_ {i}}}$ $4\left|{\sqrt {n}}\right|\cdot I$ ${\ estilo de visualización (\ pm 4)}$ ${\ estilo de visualización (\ pm 4)}$ ${\ estilo de visualización {-4,...,4}}$ ${\ estilo de visualización {R_ {i}}}$ ${\ estilo de visualización {\ sigma _ {i}}}$ ${\displaystyle ({\gamma _{i)){\sqrt {8\ln({2n}/{\varepsilon}))))^{-1))$ ${\ estilo de visualización {\ gamma _ {i}}}$ ${\ estilo de visualización {R_{i}}^{-1}}$ ${\ estilo de visualización \ varepsilon = 10 ^ {-5}}$ ${\ estilo de visualización {R_ {i}}}$ ${\ estilo de visualización {B_ {ij}}}$

${carga de trabajo_{ij))$ = , donde es el defecto de doble ortogonalidad: donde denota la fila de la matriz . ${\ estilo de visualización ({\ pi} e) ^ {n/2))$ $\cdot {\sigma _{i}^{n))$ $\cdot {\frac {orto-defecto^{*}({B_{ij)))}{det|{B_{ij}}|}}$ $orth-defect^{*}$ $orth-defect^{*}(B)=|det(B)|\cdot \prod _{i}\|{\hat {b_{i))}\|,$ ${\ Displaystyle {\ sombrero {b_ {i}}}}$ $B^{{-1}}$

Puntuación de asalto

Para evaluar el ataque de asalto se utilizaron las mismas bases abiertas y cerradas que en el ataque por redondeo.

Evaluación de ataque de inyección

Dado que no se puede hablar de la "carga de trabajo" de un ataque de inyección, se midió el valor máximo (relacionado con el vector de error) para el que funciona este ataque. Para estos experimentos, se utilizaron las mismas bases cerradas y bases abiertas que para los dos ataques anteriores. Luego, cada base abierta se utilizó para evaluar la función en varios puntos utilizando varios valores diferentes y se verificó si el ataque de inyección recupera el mensaje cifrado. ${\sigma}$ ${R}$ ${\ estilo de visualización {B_ {ij}}}$ $\sigma$

Ejemplo

Sea el retículo con base y su recíproco : $L\subconjunto \mathbb {R} ^{2}$ $B$ $B^{{-1}}$

B={\begin{pmatrix}7&0\\0&3\\\end{pmatrix}}

B^{-1}={\begin{pmatrix}{\frac {1}{7}}&0\\0&{\frac {1}{3}}\\\end{pmatrix}}

Con una matriz unimodular:

U={\begin{pmatrix}2&3\\3&5\\\end{pmatrix}}

U^{-1}={\begin{pmatrix}5&-3\\-3&2\\\end{pmatrix}}

Obtenemos:

B'=UB={\begin{pmatrix}14&9\\21&15\\\end{pmatrix}}

Dejemos el mensaje y el vector de errores Luego el texto cifrado: $m=(3,-7)$ ${\ estilo de visualización e = (1,-1).}$

c=mB'+e=(-104,-79)

Para descifrar necesitas:

cB^{-1}=\izquierda({\frac {-104}{7)),{\frac {-79}{3}}\derecha)

Esto se redondea a ${\ estilo de visualización (-15, -26).}$

Y el mensaje se restaura con:

m=(-15,-26)U^{-1}=(3,-7).\,

Fuentes y lecturas adicionales

Oded Goldreich, Shafi Goldwasser y Shai Halevi. Criptosistemas de clave pública a partir de problemas de reducción de celosía. En CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, páginas 112-131, Londres, Reino Unido, 1997. Springer-Verlag.
Phong Q. Nguyen. Criptoanálisis del criptosistema Goldreich-Goldwasser-Halevi de Crypto '97. En CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, páginas 288-304, Londres, Reino Unido, 1999. Springer-Verlag.

Notas

↑ Phong Q. Nguyen. Criptoanálisis del criptosistema Goldreich-Goldwasser-Halevi de Crypto '97. . - S. 1-17 . Archivado desde el original el 16 de julio de 2018.
↑ 1 2 Phong Q. Nguyen. Criptoanálisis del criptosistema Goldreich-Goldwasser-Halevi de Crypto '97. S.- 1-2. . Archivado desde el original el 16 de julio de 2018. (indefinido)
↑ Phong Q. Nguyen. Criptoanálisis del criptosistema Goldreich-Goldwasser-Halevi de Crypto '97. S.- 1. . Archivado desde el original el 16 de julio de 2018. (indefinido)
↑ Oded Goldreich, Shafi Goldwasser y Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Criptosistemas de clave pública de problemas de reducción de celosía]. - S. 112-114 . Archivado el 4 de mayo de 2019.
↑ Phong Q. Nguyen. Criptoanálisis del criptosistema Goldreich-Goldwasser-Halevi de Crypto '97. . - S. 4 . Archivado desde el original el 16 de julio de 2018.
↑ Oded Goldreich, Shafi Goldwasser y Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Criptosistemas de clave pública de problemas de reducción de celosía]. — S. 122-124 . Archivado el 4 de mayo de 2019.
↑ Oded Goldreich, Shafi Goldwasser y Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Criptosistemas de clave pública de problemas de reducción de celosía]. - S. 127-130 . Archivado el 4 de mayo de 2019.