Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Cryptanalysis, NTRUSign

Date: received 3 Nov 2006

Contact author: pnguyen at di ens fr

Available formats: PDF | BibTeX Citation

Version: 20061103:164207 (All versions of this report)

Discussion forum: Show discussion | Start new discussion