Improvements on Making BKW Practical for Solving LWE
(2021) In Cryptography 5(4).- Abstract
The learning with errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum–Kalai–Wasserman (BKW) algorithm. This paper presents new improvements of BKW-style algorithms for solving LWE instances. We target minimum concrete complexity, and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the fast Walsh Hadamard transform. The complexity of the resulting algorithm compares favorably with all other... (More)
The learning with errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum–Kalai–Wasserman (BKW) algorithm. This paper presents new improvements of BKW-style algorithms for solving LWE instances. We target minimum concrete complexity, and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the fast Walsh Hadamard transform. The complexity of the resulting algorithm compares favorably with all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. We provide two implementations of the algorithm, one RAM-based approach that is optimized for speed, and one file-based approach which overcomes RAM limitations by using file-based storage.
(Less)
- author
- Budroni, Alessandro
LU
; Guo, Qian
LU
; Johansson, Thomas
LU
; Mårtensson, Erik LU
and Wagner, Paul Stankovski LU
- organization
- publishing date
- 2021
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- BKW, FWHT, Lattice-based cryptography, LWE, Post-quantum cryptography
- in
- Cryptography
- volume
- 5
- issue
- 4
- article number
- 31
- publisher
- MDPI AG
- external identifiers
-
- scopus:85118417190
- ISSN
- 2410-387X
- DOI
- 10.3390/cryptography5040031
- project
- Lightweight Cryptography for Autonomous Vehicles
- language
- English
- LU publication?
- yes
- additional info
- Publisher Copyright: © 2021 by the authors. Licensee MDPI, Basel, Switzerland.
- id
- 8b36fc4c-af37-404b-9da2-881ebd85cabe
- date added to LUP
- 2021-11-24 15:47:45
- date last changed
- 2024-01-20 17:40:15
@article{8b36fc4c-af37-404b-9da2-881ebd85cabe, abstract = {{<p>The learning with errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum–Kalai–Wasserman (BKW) algorithm. This paper presents new improvements of BKW-style algorithms for solving LWE instances. We target minimum concrete complexity, and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the fast Walsh Hadamard transform. The complexity of the resulting algorithm compares favorably with all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. We provide two implementations of the algorithm, one RAM-based approach that is optimized for speed, and one file-based approach which overcomes RAM limitations by using file-based storage.</p>}}, author = {{Budroni, Alessandro and Guo, Qian and Johansson, Thomas and Mårtensson, Erik and Wagner, Paul Stankovski}}, issn = {{2410-387X}}, keywords = {{BKW; FWHT; Lattice-based cryptography; LWE; Post-quantum cryptography}}, language = {{eng}}, number = {{4}}, publisher = {{MDPI AG}}, series = {{Cryptography}}, title = {{Improvements on Making BKW Practical for Solving LWE}}, url = {{http://dx.doi.org/10.3390/cryptography5040031}}, doi = {{10.3390/cryptography5040031}}, volume = {{5}}, year = {{2021}}, }