Esquema de cifrado GGH

El Goldreich-Goldwasser-Halevi (GGH) basado en enrejado criptosistema es un asimétrica criptosistema basado en celosías . También hay un esquema de firma GGH .

El criptosistema Goldreich-Goldwasser-Halevi (GGH) hace uso del hecho de que el problema de 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 trampilla unidireccional que se basa en la dificultad de la reducción de celosía. La idea incluida en esta función de trampilla es que, dada cualquier base para una celosía, es fácil generar un vector que esté cerca de un punto de celosía, por ejemplo, tomando un punto de celosía y agregando un pequeño vector de error. Pero para volver de este vector erróneo al punto de celosía original se necesita una base especial.

El esquema de cifrado GGH fue criptoanalizado en 1999 por Phong Q. Nguyen.

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 del entramado del formulario .${\displaystyle L}$${\displaystyle B'=UB}$

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

Cifrado

Dado un mensaje , el error , y una clave pública de 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 celosía, por lo que v también es un punto de celosía. 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}}$

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

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

para obtener el texto del mensaje.

Ejemplo

Sea una celosía con la base y su inverso${\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 uno debe 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

1999 Nguyen demostró en la conferencia Crypto que el esquema de cifrado GGH tiene una falla en el diseño de los esquemas. Nguyen demostró que cada texto cifrado revela información sobre el texto plano y que el problema del descifrado podría convertirse en un problema de vector especial más cercano mucho más fácil de resolver que el CVP general.

Referencias

• Uth, Max . Diccionario de artistas Benezit. Prensa de la Universidad de Oxford. 2011-10-31. doi : 10.1093 / benz / 9780199773787.article.b00187394 .

Bibliografía

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997). "Criptosistemas de clave pública de problemas de reducción de celosía". 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 19a Conferencia Anual Internacional de Criptología sobre Avances en Criptología . Londres: Springer-Verlag. págs. 288-304.