GGH signature scheme

The Goldreich-Goldwasser-Halevi (GGH) signature scheme is a <a href="/facts/Digital_signature/tY7e2pnW">digital signature</a> scheme proposed in 1995 and published in 1997, based on solving the <a href="/facts/Closest_vector_problem/YHXNNrrG">closest vector problem</a> (CVP) in a <a href="/facts/Lattice_(group)/2ls9Iv9N">lattice</a>. 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 <a href="/facts/GGH_encryption_algorithm/4dX4kxxB">encryption algorithm</a>. 
GGH signatures form the basis for the <a href="/facts/NTRUSign/Njl2bmRf">NTRUSign</a> signature algorithm.
Phong Q. Nguyen [fr] and <a href="/facts/Oded_Regev_(computer_scientist)/qb5CDFDC">Oded Regev</a> had cryptanalyzed (<a href="/facts/Broken_cipher/z7BMcnjn">broken</a>) the original GGH signature scheme in 2006.

GGH signature scheme open-in-new

GGH signature scheme