Improvements on Making BKW Practical for Solving LWE

Research output: Contribution to journalArticlepeer-review

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 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.

Original languageEnglish
Article number31
JournalCryptography
Volume5
Issue number4
DOIs
Publication statusPublished - 2021

Subject classification (UKÄ)

  • Computer Science

Free keywords

  • BKW
  • FWHT
  • Lattice-based cryptography
  • LWE
  • Post-quantum cryptography

Fingerprint

Dive into the research topics of 'Improvements on Making BKW Practical for Solving LWE'. Together they form a unique fingerprint.

Cite this