IACR News item: 14 April 2016
Elena Kirshanova, Alexander May, Friedrich Wiemer
ePrint Report
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.
Additional news items may be found on the IACR news page.