Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Making the BKW Algorithm Practical for LWE

Budroni, Alessandro ; Guo, Qian LU ; Johansson, Thomas LU orcid ; Mårtensson, Erik LU orcid and Stankovski Wagner, Paul LU (2020) International Conference on Cryptology in India - INDOCRYPT 2020 In Lecture Notes in Computer Science 12578. p.417-439
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 FastWalsh Hadamard Transform. The complexity of the resulting algorithm compares favourably to all other previous... (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 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 FastWalsh 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. (Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
BKW, LWE, Lattice-Based Cryptography, FWHT, Post- Quantum Cryptography
host publication
Progress in Cryptology – INDOCRYPT 2020 : 21st International Conference on Cryptology in India Bangalore, India, December 13–16, 2020 Proceedings - 21st International Conference on Cryptology in India Bangalore, India, December 13–16, 2020 Proceedings
series title
Lecture Notes in Computer Science
volume
12578
pages
23 pages
publisher
Springer
conference name
International Conference on Cryptology in India - INDOCRYPT 2020
conference location
Bangalore, India
conference dates
2020-12-13 - 2020-12-16
external identifiers
  • scopus:85098274127
ISSN
1611-3349
0302-9743
ISBN
978-3-030-65277-7
978-3-030-65276-0
DOI
10.1007/978-3-030-65277-7_19
project
Lightweight Cryptography for Autonomous Vehicles
language
English
LU publication?
yes
id
137c8112-cc8f-47f2-aa6a-74792497b266
date added to LUP
2020-12-16 16:48:42
date last changed
2024-05-30 01:35:10
@inproceedings{137c8112-cc8f-47f2-aa6a-74792497b266,
  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 FastWalsh 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.}},
  author       = {{Budroni, Alessandro and Guo, Qian and Johansson, Thomas and Mårtensson, Erik and Stankovski Wagner, Paul}},
  booktitle    = {{Progress in Cryptology – INDOCRYPT 2020 : 21st International Conference on Cryptology in India Bangalore, India, December 13–16, 2020 Proceedings}},
  isbn         = {{978-3-030-65277-7}},
  issn         = {{1611-3349}},
  keywords     = {{BKW; LWE; Lattice-Based Cryptography; FWHT; Post- Quantum Cryptography}},
  language     = {{eng}},
  pages        = {{417--439}},
  publisher    = {{Springer}},
  series       = {{Lecture Notes in Computer Science}},
  title        = {{Making the BKW Algorithm Practical for LWE}},
  url          = {{http://dx.doi.org/10.1007/978-3-030-65277-7_19}},
  doi          = {{10.1007/978-3-030-65277-7_19}},
  volume       = {{12578}},
  year         = {{2020}},
}