Paper 2016/380
Parallel Implementation of BDD enumeration for LWE
Elena Kirshanova, Alexander May, and Friedrich Wiemer
Abstract
One of the most attractive problems for post-quantum secure cryptographic schemes is the LWE problem. Beside combinatorial and algebraic attacks, LWE can be solved by a lattice-based Bounded Distance Decoding (BDD) approach. We provide the first parallel implementation of an enumeration-based BDD algorithm that employs the Lindner-Peikert and Linear Length pruning strategies. We ran our algorithm on a large variety of LWE parameters, from which we derive the following interesting results. First, our parallel enumeration achieves almost perfect speed-up, which allows us to provide for the first time practical cryptanalytic results on standard LWE parameters of meaningful size. Second, we conclude that lattice-based attacks perform better than recent advanced BKW-type algorithms even for small noise, while requiring way less samples. Third, we experimentally show weaknesses for a binary matrix LWE proposal of Galbraith.
Note: Renamed title of publication to match pdf title.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. ACNS 2016 - 14th International Conference on Applied Cryptography and Network Security
- Keywords
- cryptanalysisimplementationlattice techniques
- Contact author(s)
- friedrich wiemer @ rub de
- History
- 2016-06-03: revised
- 2016-04-14: received
- See all versions
- Short URL
- https://ia.cr/2016/380
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/380,
author = {Elena Kirshanova and Alexander May and Friedrich Wiemer},
title = {Parallel Implementation of BDD enumeration for LWE},
howpublished = {Cryptology ePrint Archive, Paper 2016/380},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/380}},
url = {https://eprint.iacr.org/2016/380}
}
