International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: A Note on the Security of NTRUSign

Phong Q. Nguyen
Search ePrint
Search Google
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.
  title={A Note on the Security of NTRUSign},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Cryptanalysis, NTRUSign},
  note={ 13455 received 3 Nov 2006},
  author={Phong Q. Nguyen},