GGH encryption algorithm

The Goldreich-Goldwasser-Halevi (GGH) signature scheme is an asymmetric key encryption algorithm proposed in 1995 and published in 1997, based on solving the close vector problem (CVP) in a lattice. The encrypter uses the public key, a bad lattice basis, to select a lattice point that represents the message and add a small random noise to that point to form the ciphertext. The decrypter uses the private key, a good basis for the lattice, to solve CVP on the ciphertext; the resulting lattice point is the message representative.

A version of the algorithm was cryptanalyzed by Nguyen in 1999.

The original paper also proposed the GGH signature scheme, a digital signature algorithm.

External links

• The webpage of the original paper
• The paper cryptanalyzing the original proposal