Esquema de cifrado GGH

Criptosistema basado en celosía

El criptosistema basado en retículas Goldreich–Goldwasser–Halevi (GGH) es un criptosistema asimétrico roto basado en retículas . También existe un esquema de firma GGH que no se ha roto hasta 2024.

El criptosistema Goldreich–Goldwasser–Halevi (GGH) aprovecha el hecho de que el problema del vector más cercano puede ser un problema difícil. Este sistema fue publicado en 1997 por Oded Goldreich , Shafi Goldwasser y Shai Halevi , y utiliza una función unidireccional de trampa que se basa en la dificultad de la reducción de red . La idea incluida en esta función de trampa es que, dada cualquier base para una red, es fácil generar un vector que esté cerca de un punto de red, por ejemplo, tomando un punto de red y agregando un pequeño vector de error. Pero para regresar de este vector erróneo al punto de red original se necesita una base especial.

El esquema de cifrado GGH fue criptoanalizado (descifrado) en 1999 por Phong Q. Nguyen  [fr] . Nguyen y Oded Regev habían criptoanalizado el esquema de firma GGH relacionado en 2006.

Operación

GGH implica una clave privada y una clave pública .

La clave privada es la base de una red con buenas propiedades (como vectores cortos casi ortogonales ) y una matriz unimodular . ${\displaystyle B}$ ${\displaystyle L}$ ${\displaystyle U}$

La clave pública es otra base de la red de la forma . ${\displaystyle L}$ ${\displaystyle B'=UB}$

Para algún M elegido, el espacio del mensaje consiste en el vector en el rango . ${\displaystyle (m_{1},...,m_{n})}$ ${\displaystyle -M<m_{i}<M}$

Encriptación

Dado un mensaje , un error y una clave pública, cómputo ${\displaystyle m=(m_{1},...,m_{n})}$ ${\displaystyle e}$ ${\displaystyle B'}$

${\displaystyle v=\sum m_{i}b_{i}'}$

En notación matricial esto es

${\displaystyle v=m\cdot B'}$.

Recuerde que consta de valores enteros y es un punto de red, por lo que v también es un punto de red. El texto cifrado es entonces ${\displaystyle m}$ ${\displaystyle b'}$

${\displaystyle c=v+e=m\cdot B'+e}$

Descifrado

Para descifrar el texto cifrado se calcula

${\displaystyle 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}}$

Se utilizará la técnica de redondeo de Babai para eliminar el término siempre que sea lo suficientemente pequeño. Finalmente, calcule ${\displaystyle e\cdot B^{-1}}$

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

Para recibir el mensaje.

Ejemplo

Sea una red con la base y su inversa ${\displaystyle L\subset \mathbb {R} ^{2}}$ ${\displaystyle B}$ ${\displaystyle B^{-1}}$

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

Con

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

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

Esto da

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

Sea el mensaje y el vector de error . Entonces el texto cifrado es ${\displaystyle m=(3,-7)}$ ${\displaystyle e=(1,-1)}$

${\displaystyle c=mB'+e=(-104,-79).\,}$

Para descifrar hay que calcular

${\displaystyle cB^{-1}=\left({\frac {-104}{7}},{\frac {-79}{3}}\right).}$

Esto se redondea a y el mensaje se recupera con ${\displaystyle (-15,-26)}$

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

Seguridad del esquema

En 1999, Nguyen ^[1] demostró que el esquema de cifrado GGH tiene un fallo en el diseño. Demostró que cada texto cifrado revela información sobre el texto simple y que el problema del descifrado podría convertirse en un problema especial de vector más cercano mucho más fácil de resolver que el CVP general.

Referencias

1. Phong Nguyen. Criptoanálisis del criptosistema Goldreich-Goldwasser-Halevi de Crypto '97 . CRYPTO, 1999

Bibliografía

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997). "Criptosistemas de clave pública a partir de problemas de reducción de red". CRYPTO '97: Actas de la 17.ª Conferencia Anual Internacional de Criptología sobre Avances en Criptología . Londres: Springer-Verlag. págs. 112–131.
• Nguyen, Phong Q. (1999). "Criptoanálisis del criptosistema Goldreich–Goldwasser–Halevi de Crypto '97". CRYPTO '99: Actas de la 19.ª Conferencia Anual Internacional de Criptología sobre Avances en Criptología . Londres: Springer-Verlag. págs. 288–304.
• Nguyen, Phong Q.; Regev, Oded (11 de noviembre de 2008). "Aprendizaje de un paralelepípedo: criptoanálisis de firmas GGH y NTRU" (PDF) . Journal of Cryptology . 22 (2): 139–160. doi :10.1007/s00145-008-9031-0. eISSN  1432-1378. ISSN  0933-2790. S2CID  2164840.Versión preliminar en EUROCRYPT 2006.