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 In computer science, lattice problems are a class of Mathematical optimization, optimization problems related to mathematical objects called Lattice (group), lattices. The conjectured intractability of such problems is central to the construction o ...

(CVP) in a

lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an ornam ...

. 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 decip ...

. 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