The Goldreich-Goldwasser-Halevi (GGH) signature scheme is a
digital signature
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...
scheme proposed in 1995 and published in 1997, based on solving the
closest vector problem (CVP) in a
lattice. 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
In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can dec ...
.
GGH signatures form the basis for the
NTRUSign
NTRUSign, also known as the NTRU Signature Algorithm, is an NTRU public-key cryptography digital signature algorithm based on the GGH signature scheme. The original version of NTRUSign was Polynomial Authentication and Signature Scheme (PASS), an ...
signature algorithm.
and
Oded Regev had cryptanalyzed (
broken) the original GGH signature scheme in 2006.
Bibliography
*
*
Preliminary version in EUROCRYPT 2006.
External links
The webpage of the original paper
Digital signature schemes
Lattice-based cryptography
{{crypto-stub