The Goldreich-Goldwasser-Halevi (GGH) signature scheme is 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...

 scheme proposed in 1995 and published in 1997, based on solving the closest vector problem (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 signer demonstrates knowledge of a good basis for the lattice by using it to solve CVP on a point representing the message; the verifier uses a bad basis for the same lattice to verify that the signature under consideration is actually a lattice point and is sufficiently close to the message point.

The idea was not developed in detail in the original paper, which focussed more on the associated encryption algorithm

GGH encryption algorithm

The Goldreich-Goldwasser-Halevi encryption scheme is an asymmetric key encryption algorithm proposed in 1995 and published in 1997, based on solving the close vector problem in a lattice. The encrypter uses the public key, a bad lattice basis, to select a lattice point that represents the message...

.

GGH signatures form the basis for the NTRUSign

NTRUSign

NTRUSign, also known as the NTRU Signature Algorithm, is a public key cryptography digital signature algorithm based on the GGH signature scheme. It was first presented at the rump session of Asiacrypt 2001 and published in peer-reviewed form at the RSA Conference 2003. The 2003 publication...

signature algorithm.

External links

• The webpage of the original paper