GGH encryption algorithm
Encyclopedia
The Goldreich-Goldwasser-Halevi (GGH) encryption 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.
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
algorithm proposed in 1995 and published in 1997, based on solving the close vector problem
Lattice problems
In computer science, lattice problems are a class of optimization problems on lattices. The conjectured intractability of such problems is central to construction of secure lattice-based cryptosystems...
(CVP) in a lattice
Lattice (group)
In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
. 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
GGH signature scheme
The Goldreich-Goldwasser-Halevi signature scheme is a digital signature scheme proposed in 1995 and published in 1997, based on solving the closest vector problem in a lattice...
, a digital signature
Digital signature
A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...
algorithm.