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 . Nguyen and Oded Regev had cryptanalyzed the related GGH signature scheme in 2006.

Operation

GGH involves a private key and a public key.

with good properties (such as short nearly orthogonal vectors) and a unimodular matrix.

.

.

Encryption

compute

In matrix notation this is

1. .

consists of integer is a lattice point, so v is also a lattice point. The ciphertext is then

Decryption

To decrypt the ciphertext one computes

as long as it is small enough. Finally compute

to get the message.

Example

With

1. and

this gives

. Then the ciphertext is

To decrypt one must compute

and the message is recovered with

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, 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 NguyenGGH, 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.

References

Bibliography

• Preliminary version in EUROCRYPT 2006.