2006 | OriginalPaper | Buchkapitel
Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures
verfasst von : Phong Q. Nguyen, Oded Regev
Erschienen in: Advances in Cryptology - EUROCRYPT 2006
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Lattice-based signature schemes following the Goldreich- Goldwasser-Halevi (GGH) design have the unusual property that each signature leaks information on the signer’s secret key, but this does not necessarily imply that such schemes are insecure. At Eurocrypt ’03, Szydlo proposed a potential attack by showing that the leakage reduces the key-recovery problem to that of distinguishing integral quadratic forms. He proposed a heuristic method to solve the latter problem, but it was unclear whether his method could attack real-life parameters of GGH and
NTRU Cryptosystems
sign. Here, we propose an alternative method to attack signature schemes à la GGH, by studying the following learning problem: given many random points uniformly distributed over an unknown
n
-dimensional parallelepiped, recover the parallelepiped or an approximation thereof. We transform this problem into a multivariate optimization problem that can be solved by a gradient descent. Our approach is very effective in practice: we present the first succesful key-recovery experiments on
NTRU Cryptosystems
sign-251 without perturbation, as proposed in half of the parameter choices in NTRU standards under consideration by IEEE P1363.1. Experimentally, 90,000 signatures are sufficient to recover the
NTRU Cryptosystems
sign-251 secret key. We are also able to recover the secret key in the signature analogue of all the GGH encryption challenges, using a number of signatures which is roughly quadratic in the lattice dimension.