GGH encryption scheme

Short description: Lattice-based cryptosystem

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.

Operation

GGH involves a private key and a public key.

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

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

For some chosen M, the message space consists of the vector $(m_1,...,m_n)$ in the range $-M<m_i<M$.

Encryption

Given a message $m=(m_1,...,m_n)$, error $e$, and a public key $B^{\prime }$ compute

$v=\sum m_i{b_i}^{\prime }$

In matrix notation this is

$v=m\cdot B^{\prime }$.

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

$c=v+e=m\cdot B^{\prime }+e$

Decryption

To decrypt the ciphertext one computes

$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 $e\cdot B^{-1}$ as long as it is small enough. Finally compute

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

to get the message.

Example

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

$B=\left(\begin{array}{cc}7& 0\\ 0& 3\\ \end{array}\right)$ and $B^{-1}=\left(\begin{array}{cc}\frac{1}{7}& 0\\ 0& \frac{1}{3}\\ \end{array}\right)$

With

$U=\left(\begin{array}{cc}2& 3\\ 3& 5\\ \end{array}\right)$ and

$U^{-1}=\left(\begin{array}{cc}5& -3\\ -3& 2\\ \end{array}\right)$

this gives

$B^{\prime }=UB=\left(\begin{array}{cc}14& 9\\ 21& 15\\ \end{array}\right)$

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

$c=m{B}^{\prime }+e=(-104,-79).$

To decrypt one must compute

$c{B}^{-1}=(\frac{-104}{7},\frac{-79}{3}).$

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

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

Security of the scheme

In 1999, Nguyen 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.

In 2020, Mandangan, Kamarulhaili & Asbullah proposed a countermeasure that repairs the specific flaw exploited by Nguyen's attack without altering the rest of the original GGH design. Nguyen's attack works by first eliminating the error vector $e$ from the encryption equation, which is only possible because the original scheme draws every entry of $e$ from the two-element set $\{-\sigma ,+\sigma \}$. The countermeasure instead draws each entry of $e$ from the four-element set $\{\sigma -2,\sigma -1,\sigma ,\sigma +1\}$, using a specified distribution across the four values. This breaks the congruence used in the elimination stage of Nguyen's attack, so the attack can no longer reduce the problem to the easier Nguyen_GGH-CVP instance, while a matching choice of distribution keeps the Euclidean norm of the error vector at $\Vert e\Vert =\sigma \sqrt{n}$, the same benchmark norm as the original scheme. The authors show that decryption still succeeds without error under this modification, so the countermeasure preserves both the practicality of GGH and its reliance on the original (harder) GGH-CVP instance.

Implementations

• TheGaBr0/GGH – A Python implementation of the GGH cryptosystem and its optimized variant GGH-HNF. 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.

Bibliography

• 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. https://www.di.ens.fr/~pnguyen/pub_Ng99.htm. 
• Nguyen, Phong Q.; Regev, Oded (11 November 2008). "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures". Journal of Cryptology 22 (2): 139–160. doi:10.1007/s00145-008-9031-0. ISSN 0933-2790. https://iacr.org/archive/eurocrypt2006/40040273/40040273.pdf. 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. 2146. Springer. pp. 126–145. doi:10.1007/3-540-44670-2_11. 
• Mandangan, Arif; Kamarulhaili, Hailiza; Asbullah, Muhammad Asyraf (2020). "A Security Upgrade on the GGH Lattice-Based Cryptosystem". Sains Malaysiana 49 (6): 1471–1478. doi:10.17576/jsm-2020-4906-25.