Solving BDD by enumeration: an update. (English) Zbl 1312.94070

Dawson, Ed (ed.), Topics in cryptology – CT-RSA 2013. The cryptographers’ track at the RSA conference 2013, San Francisco, CA, USA, February 25–March 1, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36094-7/pbk). Lecture Notes in Computer Science 7779, 293-309 (2013).
Summary: 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 [N. Gama et al., Eurocrypt 2010, Lect. Notes Comput. Sci. 6110, 257–278 (2010; Zbl 1280.94056)]. We obtain significant improvements upon Lindner-Peikert’s Search-LWE algorithm (from [R. Lindner and C. Peikert, CT-RSA 2011, Lect. Notes Comput. Sci. 6558, 319–339 (2011; Zbl 1284.94088)]), 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.
For the entire collection see [Zbl 1258.94003].


94A60 Cryptography
Full Text: DOI Link