Search: onr:"swepub:oai:lup.lub.lu.se:8b36fc4c-af37-404b-9da2-881ebd85cabe" >
Improvements on Mak...
Improvements on Making BKW Practical for Solving LWE
-
- Budroni, Alessandro (author)
- University of Bergen
-
- Guo, Qian (author)
- Lund University,Lunds universitet,Nätverk och säkerhet,Forskargrupper vid Lunds universitet,Networks and Security,Lund University Research Groups,University of Bergen
-
- Johansson, Thomas (author)
- Lund University,Lunds universitet,Nätverk och säkerhet,Forskargrupper vid Lunds universitet,Networks and Security,Lund University Research Groups
-
show more...
-
- Mårtensson, Erik (author)
- Lund University,Lunds universitet,Nätverk och säkerhet,Forskargrupper vid Lunds universitet,Networks and Security,Lund University Research Groups,University of Bergen
-
- Wagner, Paul Stankovski (author)
- Lund University,Lunds universitet,Nätverk och säkerhet,Forskargrupper vid Lunds universitet,Networks and Security,Lund University Research Groups
-
show less...
-
(creator_code:org_t)
- 2021-10-28
- 2021
- English.
-
In: Cryptography. - : MDPI AG. - 2410-387X. ; 5:4
- Related links:
-
http://dx.doi.org/10... (free)
-
show more...
-
https://www.mdpi.com...
-
https://lup.lub.lu.s...
-
https://doi.org/10.3...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- BKW
- FWHT
- Lattice-based cryptography
- LWE
- Post-quantum cryptography
Publication and Content Type
- art (subject category)
- ref (subject category)
Find in a library
To the university's database