GGH encryption scheme


The Goldreich–Goldwasser–Halevi 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 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 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.
The private key is a basis of a lattice with good properties and a unimodular matrix.
The public key is another basis of the lattice of the form.
For some chosen M, the message space consists of the vector in the range.

Encryption

Given a message, error, and a
public key compute
In matrix notation this is
Remember consists of integer values, and is a lattice point, so v is also a lattice point. The ciphertext is then

Decryption

To decrypt the ciphertext one computes
The Babai rounding technique will be used to remove the term as long as it is small enough. Finally compute
to get the message.

Example

Let be a lattice with the basis and its inverse
With
this gives
Let the message be and the error vector. Then the ciphertext is
To decrypt one must compute
This is rounded to 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.

Implementations