Computational cryptography › Public-key encryption and key exchange › Post-quantum public-key › Lattices
SIGNATUREPrimitiveHistorically broken

GGH, NTRUSign

In plain words

Early lattice signatures from 1997 and 2003, broken by what their own signatures leaked.

The idea: The core idea was sound: a good secret basis finds a lattice point near the message's hash, which is hopeless with the public, bad basis. The flaw was in how the signatures were distributed, not in the hard problem (see "Signatures hide the secret basis").

Why it matters: Their failure shaped how today's quantum-safe signatures are designed.

The details

On the map: ✗ 1997, 2003. Patched NTRUSign fell too (2012)

GGH (Goldreich, Goldwasser and Halevi, 1997)[1] was an early lattice signature and encryption scheme. NTRUSign (2003)[2] applied the same idea to compact NTRU lattices and was considered for IEEE standardization. Both signatures fell to statistical leakage (GGH encryption had separately been broken by Nguyen in 1999[3]).

Their failure is the reason today's lattice signatures look the way they do.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

Nothing on the map depends on it: it is an end point, something people use directly.

References

  1. Oded Goldreich, Shafi Goldwasser and Shai Halevi. Public-key cryptosystems from lattice reduction problems. Advances in Cryptology — CRYPTO '97, 1997. doi:10.1007/bfb0052231
  2. Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher et al. NTRUSign: Digital Signatures Using the NTRU Lattice. Topics in Cryptology — CT-RSA 2003. doi:10.1007/3-540-36563-x_9
  3. Phong Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto ’97. Advances in Cryptology — CRYPTO’ 99, 1999. doi:10.1007/3-540-48405-1_18