Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-39555-5_31 | Lecture Notes in Computer Science |
Keywords | DocType | Volume |
Lwe security,Bounded distance decoding,Lattices | Conference | 9696 |
ISSN | Citations | PageRank |
0302-9743 | 8 | 0.49 |
References | Authors | |
12 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Elena Kirshanova | 1 | 16 | 3.33 |
| Alexander May | 2 | 89 | 5.98 |
| Friedrich Wiemer | 3 | 8 | 0.49 |