Solving BDD by Enumeration: An Update

Mingjie Liu 1, 2 Phong Q. Nguyen 2, 3
3 CRYPT - Cryptanalyse
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
Abstract : Bounded Distance Decoding (BDD) is a basic lattice problem used in cryptanalysis: the security of most lattice-based encryption schemes relies on the hardness of some BDD, such as LWE. We study how to solve BDD using a classical method for finding shortest vectors in lattices: enumeration with pruning speedup, such as Gama-Nguyen-Regev extreme pruning from EUROCRYPT '10. We obtain significant improvements upon Lindner-Peikert's Search-LWE algorithm (from CT-RSA '11), and update experimental cryptanalytic results, such as attacks on DSA with partially known nonces and GGH encryption challenges. Our work shows that any security estimate of BDD-based cryptosystems must take into account enumeration attacks, and that BDD enumeration can be practical even in high dimension like 350.
Type de document :
Communication dans un congrès
Ed Dawson. CT-RSA 2013 - The Cryptographers' Track at the RSA Conference 2013, Feb 2013, San Francisco, United States. Springer, 7779, pp.293-309, 2013, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007%2F978-3-642-36095-4_19〉. 〈10.1007/978-3-642-36095-4_19〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00864361
Contributeur : Phong Q. Nguyen <>
Soumis le : samedi 21 septembre 2013 - 03:05:40
Dernière modification le : jeudi 11 janvier 2018 - 06:25:20
Document(s) archivé(s) le : vendredi 7 avril 2017 - 00:52:12

Fichier

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

Identifiants

Collections

Citation

Mingjie Liu, Phong Q. Nguyen. Solving BDD by Enumeration: An Update. Ed Dawson. CT-RSA 2013 - The Cryptographers' Track at the RSA Conference 2013, Feb 2013, San Francisco, United States. Springer, 7779, pp.293-309, 2013, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007%2F978-3-642-36095-4_19〉. 〈10.1007/978-3-642-36095-4_19〉. 〈hal-00864361〉

Partager

Métriques

Consultations de la notice

617

Téléchargements de fichiers

1147