Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Improvements on Making BKW Practical for Solving LWE

Budroni, Alessandro LU ; Guo, Qian LU ; Johansson, Thomas LU orcid ; Mårtensson, Erik LU orcid and Wagner, Paul Stankovski LU (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)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
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}},
}