Tel-Aviv University - Computer Science Colloquium

Sunday, May 14, 2006, 11:15-12:15

Room 309
Schreiber Building


Oded Regev


Title: Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures


Abstract:  I will describe a recent practical attack on lattice-based signature

schemes. The attack is based on an algorithm for the following learning problem:

Given many random points uniformly distributed over an unknown n-dimensional

parallelepiped, find an approximation of the parallelepiped.


The attack applies to signature schemes based on the

Goldreich-Goldwasser-Halevi approach, such as (most variants of) the signature

scheme NTRUsign-251, which is currently

under consideration by IEEE P1363.1 and was developed by the company NTRU.

The attack is very effective in practice: for example, 90,000 signatures

are sufficient to recover the secret key of NTRUsign-251.


Joint work with Phong Q. Nguyen (ENS, Paris, France).