Esquema de cifrado GGH

El criptosistema basado en retículos Goldreich–Goldwasser–Halevi (GGH) es un criptosistema asimétrico basado en retículos que ha sido vulnerado . Existe también un esquema de firma GGH que, a fecha de 2024, no ha sido vulnerado.

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 de puerta trasera unidireccional que se basa en la dificultad de la reducción de retículos . La idea que incluye esta función de puerta trasera es que, dada cualquier base para un retículo, es fácil generar un vector cercano a un punto del retículo, por ejemplo, tomando un punto del retículo y sumándole un pequeño vector de error. Pero para regresar desde este vector erróneo al punto original del retículo se necesita una base especial.

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

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

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

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

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

Dejar${\displaystyle L\subset \mathbb {R} ^{2}}$ser una red con la base${\displaystyle B}$y su inversa${\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}}}$

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

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

Para descifrar uno debe calcular

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

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

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

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

En 2020, Mandangan, Kamarulhaili y Asbullah ^{[ 2 ]} propusieron una contramedida que repara la vulnerabilidad específica explotada por el ataque de Nguyen sin alterar el resto del diseño original de GGH. El ataque de Nguyen funciona eliminando primero el vector de error.${\displaystyle e}$de la ecuación de cifrado, lo cual solo es posible porque el esquema original extrae cada entrada de${\displaystyle e}$del conjunto de dos elementos${\displaystyle \{-\sigma ,+\sigma \}}$. La contramedida en cambio extrae cada entrada de${\displaystyle e}$del conjunto de cuatro elementos${\displaystyle \{\sigma -2,\ \sigma -1,\ \sigma ,\ \sigma +1\}}$, utilizando una distribución específica en los cuatro valores. Esto rompe la congruencia utilizada en la etapa de eliminación del ataque de Nguyen, por lo que el ataque ya no puede reducir el problema a la instancia más sencilla de Nguyen _GGH -CVP, mientras que una elección de distribución coincidente mantiene la norma euclidiana del vector de error en${\displaystyle \|e\|=\sigma {\sqrt {n}}}$, la misma norma de referencia que el esquema original. Los autores demuestran que el descifrado sigue teniendo éxito sin errores bajo esta modificación, por lo que la contramedida conserva tanto la practicidad de GGH como su dependencia de la instancia original (más difícil) de GGH-CVP.

• TheGaBr0/GGH – Una implementación en Python del criptosistema GGH y su variante optimizada GGH-HNF. ^{[ 3 ]} La biblioteca incluye generación de claves , cifrado, descifrado, técnicas básicas de reducción de retículos y demostraciones de ataques conocidos. Está destinada a fines educativos y de investigación y está disponible a través de PyPI .

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997). «Sistemas criptográficos de clave pública a partir de problemas de reducción reticular». CRYPTO '97: Actas de la 17.ª Conferencia Internacional Anual de Criptología sobre Avances en Criptología . Londres: Springer-Verlag. pp. 112–131 . 
• Nguyen, Phong Q. (1999). "Criptoanálisis del sistema criptográfico Goldreich–Goldwasser–Halevi de Crypto '97" . CRYPTO '99: Actas de la 19.ª Conferencia Internacional Anual de Criptología sobre Avances en Criptología . Londres: Springer-Verlag. pp. 288–304 . 
• Nguyen, Phong Q.; Regev, Oded (11 de noviembre de 2008). "Aprendiendo 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.
• Micciancio, Daniele (2001). "Mejora de los criptosistemas basados ​​en retículos mediante la forma normal de Hermite". Criptografía y retículos . Notas de clase en informática. Vol.  2146. Springer. pp. 126–145 . doi : 10.1007/3-540-44670-2_11 . 
• Mandangan, Arif; Kamarulhaili, Hailiza; Asbullah, Muhammad Asyraf (2020). "Una mejora de seguridad en el criptosistema basado en celosía GGH" . Sains Malaysiana . 49 (6): 1471–1478.doi : 10.17576 / jsm-2020-4906-25 .