Advertisement
Published in:
2012 | OriginalPaper | Chapter
Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures
Authors : Léo Ducas, Phong Q. Nguyen
Published in: Advances in Cryptology – ASIACRYPT 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
NTRU
Sign
is the most practical lattice signature scheme. Its basic version was broken by Nguyen and Regev in 2006: one can efficiently recover the secret key from about 400 signatures. However, countermeasures have been proposed to repair the scheme, such as the perturbation used in NTRU
Sign
standardization proposals, and the deformation proposed by Hu
et al.
at IEEE Trans. Inform. Theory in 2008. These two countermeasures were claimed to prevent the NR attack. Surprisingly, we show that these two claims are incorrect by revisiting the NR gradient-descent attack: the attack is more powerful than previously expected, and actually breaks both countermeasures in practice,
e.g.
8,000 signatures suffice to break NTRU
Sign
-251 with one perturbation as submitted to IEEE P1363 in 2003. More precisely, we explain why the Nguyen-Regev algorithm for learning a parallelepiped is heuristically able to learn more complex objects, such as zonotopes and deformed parallelepipeds.