×

Nearest planes in practice. (English) Zbl 1401.94139

Ors, Berna (ed.) et al., Cryptography and information security in the Balkans. First international conference, BalkanCryptSec 2014, Istanbul, Turkey, October 16–17, 2014. Revised selected papers. Cham: Springer (ISBN 978-3-319-21355-2/pbk; 978-3-319-21356-9/ebook). Lecture Notes in Computer Science 9024, 203-215 (2015).
Summary: The learning with errors (LWE) problem is one of the most attractive problems that lattice-based cryptosystems base their security on. Thus, assessing the hardness in theory and practice is of prime importance. Series of work investigated the hardness of LWE from a theoretical point of view. However, it is quite common that in practice one can solve lattice problems much faster than theoretical estimates predict.{ } The most promising approach to solve LWE is the decoding method, which converts an LWE instance to an instance of the closest vector problem (CVP). The latter instance can then be solved by a CVP solver. In this work, we investigate how the nearest planes algorithm proposed by [R. Lindner and C. Peikert, CT-RSA 2011, Lect. Notes Comput. Sci. 6558, 319–339 (2011; Zbl 1284.94088)] performs in practice. This algorithm improves an algorithm by Babai, and is a state-of-the-art CVP solver.{ } We present the first parallel version of the nearest planes algorithm. Our implementation achieves speedup factors of more than \(11\times\) on a machine with four CPU-chips totaling 16 cores. In fact, to the best of our knowledge, there is not even a single parallel implementation publicly available of any LWE solver so far. We also compare our results with heuristics on the running time of a single nearest planes run claimed by Lindner and Peikert and subsequently used by others for runtime estimations.
For the entire collection see [Zbl 1316.94003].

MSC:

94A60 Cryptography

Citations:

Zbl 1284.94088
PDFBibTeX XMLCite
Full Text: DOI