Making the BKW Algorithm Practical for LWE

Alessandro Budroni; Qian Guo; Thomas Johansson; Erik Mårtensson; Paul Stankovski Wagner

Paper 2020/1467 Original: eprint.iacr.org/2020/1467 ↗

Making the BKW Algorithm Practical for LWE

Alessandro Budroni

Qian Guo

Thomas Johansson

Erik Mårtensson

Paul Stankovski Wagner

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 for 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 favourably to all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. The core idea here is to overcome RAM limitations by using large file-based memory.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2020-11-24: last updated; 2020-11-24: published
Short URL: https://ia.cr/2020/1467
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2020/1467,
      author = {Alessandro Budroni and Qian Guo and Thomas Johansson and Erik Mårtensson and Paul Stankovski Wagner},
      title = {Making the BKW Algorithm Practical for LWE},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1467},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1467}
}