An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
Crypto 2015
- Time bound
- 20.9299 n + o(n)
- Space bound
- —
- Source / version date
- 8 Jun 2015
- Comparison variant
- BKW · Regev · unlimited samples
- Cost scale
- 2c n + o(n)
- Input samples
- 2^{Θ(n)} fresh classical equations
- Distribution model
- Assumptions of the cited BKW/list analysis
- Reduction schedule
- Progressive quantization
- Memory access
- Classical tables
Assumptions and source notes
CRYPTO 2015. Rounded Regev specialization of progressive quantization; the asymptotic coefficient is (1/2 + 2 ln(4/3))⁻¹. This is an abundant-sample row, not the separate bounded-error subexponential theorem.
Selected earlier references
Selected sources cited by this paper.
- On the Complexity of the BKW Algorithm on LWE
Martin R. Albrecht · Carlos Cid · Jean-Charles Faugère · Robert Fitzpatrick · Ludovic Perret · 2015
Discusses the original LWE adaptation and its noise-growth analysis. §3.1, reference [4]; after Corollary 1
- Lazy Modulus Switching for the BKW Algorithm on LWE
Martin R. Albrecht · Jean-Charles Faugère · Robert Fitzpatrick · Ludovic Perret · 2014
Generalizes the lazy-modulus-switching viewpoint using stage-dependent quantization. §3.1, reference [5]
- An Improved LPN Algorithm
Éric Levieil · Pierre-Alain Fouque · 2006
Lists an earlier BKW improvement for the binary case. Introduction, reference [33]
- Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model
Avrim Blum · Adam Kalai · Hal Wasserman · 2000
Starts from the original blockwise Gaussian-elimination algorithm. §3.1, reference [12]
@inproceedings{paper-e014be9a6925,
author = {Paul Kirchner and Pierre-Alain Fouque},
title = {{An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices}},
booktitle = {Advances in Cryptology -- CRYPTO 2015},
year = {2015},
volume = {9215},
pages = {43--62},
publisher = {Springer},
doi = {10.1007/978-3-662-47989-6_3},
url = {https://arxiv.org/abs/1506.02717},
cr_date = {2015-06-08},
cr_status = {published},
cr_venue = {Advances in Cryptology -- CRYPTO 2015},
cr_author_ids = {paul-kirchner; pierre-alain-fouque},
series = {Lecture Notes in Computer Science}
}