Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures

Léo Ducas 1 Phong Q. Nguyen 2, 3
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
2 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
Abstract : NTRUsign 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 NTRUsign 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 NTRUsign-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.
Type de document :
Communication dans un congrès
Xiaoyun Wang and Kazue Sako. ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2012, Beijing, China. Springer, 7658, pp.433-450, 2012, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007%2F978-3-642-34961-4_27〉. 〈10.1007/978-3-642-34961-4_27〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00864359
Contributeur : Phong Q. Nguyen <>
Soumis le : samedi 21 septembre 2013 - 02:18:07
Dernière modification le : mardi 24 avril 2018 - 17:20:13
Document(s) archivé(s) le : vendredi 7 avril 2017 - 00:54:20

Fichier

DucasNguyen_Learning.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Léo Ducas, Phong Q. Nguyen. Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures. Xiaoyun Wang and Kazue Sako. ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Dec 2012, Beijing, China. Springer, 7658, pp.433-450, 2012, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007%2F978-3-642-34961-4_27〉. 〈10.1007/978-3-642-34961-4_27〉. 〈hal-00864359〉

Partager

Métriques

Consultations de la notice

576

Téléchargements de fichiers

253