A Note on the Security of NTRUSign

Phong Q.  Nguyen

Paper 2006/387

A Note on the Security of NTRUSign

Phong Q. Nguyen

Abstract

At Eurocrypt '06, Nguyen and Regev presented a new key-recovery attack on the Goldreich-Goldwasser-Halevi (GGH) lattice-based signature scheme: when applied to NTRUSign-251 without perturbation, the attack recovers the secret key given only 90,000 signatures. At the rump session, Whyte speculated whether the number of required signatures might be significantly decreased to say 1,000, due to the special properties of NTRU lattices. This short note shows that this is indeed the case: it turns out that as few as 400 NTRUSign-251 signatures are sufficient in practice to recover the secret key. Hence, NTRUSign without perturbation should be considered totally insecure.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Cryptanalysis NTRUSign
Contact author(s): pnguyen @ di ens fr
History: 2006-11-03: received
Short URL: https://ia.cr/2006/387
License: CC BY

BibTeX

@misc{cryptoeprint:2006/387,
      author = {Phong Q.  Nguyen},
      title = {A Note on the Security of {NTRUSign}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/387},
      year = {2006},
      url = {https://eprint.iacr.org/2006/387}
}