On the Asymptotic Complexity of Solving LWE
Designs, Codes and Cryptography 2018
- Time bound
- 2(1/[2 ln(12/7)]+o(1)) n
- Space bound
- 2(1/[2 ln(12/7)]+o(1)) n
- Source / version date
- 2018
- Comparison variant
- BKW · q ≍ n², width ≍ n · 8n samples
- Cost scale
- 2c n + o(n)
- Input samples
- m=(8+o(1))n original samples
- Model / assumptions
- q exponent 2; Gaussian-width exponent 1; the strict theorem inequalities hold
- Exact coefficient / bound
- 1/[2 ln(12/7)]
Assumptions and source notes
Parameter substitution in the checked analysis; no priority claim for the underlying algorithm.
Source location
Theorem 11, second display
Version: Undated 30-page author manuscript checked 2026-11-08; journal 86(1), 2018; original 2015 preprint not version-compared
Selected earlier references
Selected sources cited by this paper.
- An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
Paul Kirchner · Pierre-Alain Fouque · 2015
Uses the improved unlimited-sample analysis and examines its amplification proof. §7.1–7.2, reference [27]; §7.3
- Coded-BKW: Solving LWE Using Lattice Codes
Qian Guo · Thomas Johansson · Paul Stankovski · 2015
Credits an independently proposed first-phase BKW modification. §7.2, reference [22]
- On the Complexity of the BKW Algorithm on LWE
Martin R. Albrecht · Carlos Cid · Jean-Charles Faugère · Robert Fitzpatrick · Ludovic Perret · 2015
Explains the simplified search analysis’s parameter choice and presents the +1/2 refinement. §7.1, reference [4], after Equation (10)
- The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem
Vadim Lyubashevsky · 2005
Extends the polynomial-sample amplification idea from LPN to LWE. §7.3, reference [34]
- Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model
Avrim Blum · Adam Kalai · Hal Wasserman · 2000
Uses the original LPN BKW algorithm as the starting point. Introduction; §7, reference [13]
@article{hkm2015-asymptotic,
author = {Gottfried Herold and Elena Kirshanova and Alexander May},
title = {{On the Asymptotic Complexity of Solving LWE}},
journal = {Designs, Codes and Cryptography},
year = {2018},
volume = {86},
number = {1},
pages = {55--83},
doi = {10.1007/s10623-016-0326-0},
url = {https://elenakirshanova.github.io/Papers/on_the_asymptotic_complexity.pdf},
keywords = {LWE, BKW, sample amplification, asymptotic analysis},
cr_date = {2018-12-31},
cr_date_precision = {year},
cr_status = {published},
cr_venue = {Designs, Codes and Cryptography 86(1)},
cr_author_ids = {gottfried-herold; elena-kirshanova; alexander-may},
note = {First preprint: IACR ePrint 2015/1222; checked author manuscript is undated}
}