Sunday, May 14, 2006, 11:15-12:15
Room 309
--------------------------------------------------------------------------------
Oded Regev
TAU
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,