Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Phong Q. Nguyen <>
Submitted on : Saturday, September 21, 2013 - 3:05:40 AM
Last modification on : Tuesday, June 1, 2021 - 2:34:08 PM
Long-term archiving on: : Friday, April 7, 2017 - 12:52:12 AM


Files produced by the author(s)




Mingjie Liu, Phong Q. Nguyen. Solving BDD by Enumeration: An Update. CT-RSA 2013 - The Cryptographers' Track at the RSA Conference 2013, Feb 2013, San Francisco, United States. pp.293-309, ⟨10.1007/978-3-642-36095-4_19⟩. ⟨hal-00864361⟩



Record views


Files downloads