GGH encryption scheme

The Goldreich–Goldwasser–Halevi (GGH) lattice-based cryptosystem is a broken asymmetric cryptosystem based on lattices. There is also a GGH signature scheme which hasn't been broken as of 2024.

The Goldreich–Goldwasser–Halevi (GGH) cryptosystem makes use of the fact that the closest vector problem can be a hard problem. This system was published in 1997 by Oded Goldreich, Shafi Goldwasser, and Shai Halevi, and uses a trapdoor one-way function which relies on the difficulty of lattice reduction. The idea included in this trapdoor function is that, given any basis for a lattice, it is easy to generate a vector which is close to a lattice point, for example taking a lattice point and adding a small error vector. But to return from this erroneous vector to the original lattice point a special basis is needed.

The GGH encryption scheme was cryptanalyzed (broken) in 1999 by Phong Q. Nguyen  [fr]. Nguyen and Oded Regev had cryptanalyzed the related GGH signature scheme in 2006.

GGH involves a private key and a public key.

The private key is a basis ${\displaystyle B}${\displaystyle B} of a lattice ${\displaystyle L}${\displaystyle L} with good properties (such as short nearly orthogonal vectors) and a unimodular matrix ${\displaystyle U}${\displaystyle U}.

The public key is another basis of the lattice ${\displaystyle L}${\displaystyle L} of the form ${\displaystyle B'=UB}${\displaystyle B'=UB}.

For some chosen M, the message space consists of the vector ${\displaystyle (m_{1},...,m_{n})}${\displaystyle (m_{1},...,m_{n})} in the range ${\displaystyle -M<m_{i}<M}${\displaystyle -M<m_{i}<M}.

Given a message ${\displaystyle m=(m_{1},...,m_{n})}${\displaystyle m=(m_{1},...,m_{n})}, error ${\displaystyle e}${\displaystyle e}, and a public key ${\displaystyle B'}${\displaystyle B'} compute

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

In matrix notation this is

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

Remember ${\displaystyle m}${\displaystyle m} consists of integer values, and ${\displaystyle b'}${\displaystyle b'} is a lattice point, so v is also a lattice point. The ciphertext is then

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

To decrypt the ciphertext one computes

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

The Babai rounding technique will be used to remove the term ${\displaystyle e\cdot B^{-1}}${\displaystyle e\cdot B^{-1}} as long as it is small enough. Finally compute

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

to get the message.

Let ${\displaystyle L\subset \mathbb {R} ^{2}}${\displaystyle L\subset \mathbb {R} ^{2}} be a lattice with the basis ${\displaystyle B}${\displaystyle B} and its inverse ${\displaystyle B^{-1}}${\displaystyle B^{-1}}

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

With

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

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

this gives

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

Let the message be ${\displaystyle m=(3,-7)}${\displaystyle m=(3,-7)} and the error vector ${\displaystyle e=(1,-1)}${\displaystyle e=(1,-1)}. Then the ciphertext is

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

To decrypt one must compute

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

This is rounded to ${\displaystyle (-15,-26)}${\displaystyle (-15,-26)} and the message is recovered with

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

In 1999, Nguyen ^[1] showed that the GGH encryption scheme has a flaw in the design. He showed that every ciphertext reveals information about the plaintext and that the problem of decryption could be turned into a special closest vector problem much easier to solve than the general CVP.

• TheGaBr0/GGH – A Python implementation of the GGH cryptosystem and its optimized variant GGH-HNF.^[2] The library includes key generation, encryption, decryption, basic lattice reduction techniques, and demonstrations of known attacks. It is intended for educational and research purposes and is available via PyPI.

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997). "Public-key cryptosystems from lattice reduction problems". CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology. London: Springer-Verlag. pp. 112–131.
• Nguyen, Phong Q. (1999). "Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto '97". CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology. London: Springer-Verlag. pp. 288–304.
• Nguyen, Phong Q.; Regev, Oded (11 November 2008). "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures" (PDF). Journal of Cryptology. 22 (2): 139–160. doi:10.1007/s00145-008-9031-0. eISSN 1432-1378. ISSN 0933-2790. S2CID 2164840.Preliminary version in EUROCRYPT 2006.
• Micciancio, Daniele (2001). "Improving Lattice Based Cryptosystems Using the Hermite Normal Form". Cryptography and Lattices. Lecture Notes in Computer Science. Vol. 2146. Springer. pp. 126–145. doi:10.1007/3-540-44670-2_11.

• Lattice-based cryptography
• Public-key encryption schemes
• Broken cryptography algorithms

• Articles with short description
• Short description matches Wikidata