Cryptology ePrint Archive: Report 2016/380
Parallel Implementation of BDD enumeration for LWE
Elena Kirshanova and 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.
Category / Keywords: implementation / cryptanalysis, implementation, lattice techniques
Original Publication (in the same form): ACNS 2016 - 14th International Conference on Applied Cryptography and Network Security
Date: received 14 Apr 2016, last revised 3 Jun 2016
Contact author: friedrich wiemer at rub de
Available format(s): PDF | BibTeX Citation
Note: Renamed title of publication to match pdf title.
Version: 20160603:084330 (All versions of this report)
Short URL: ia.cr/2016/380
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]