An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
Crypto 2015
- Time bound
- 2(1+o(1)) n/log₂ n
- Space bound
- 2(1+o(1)) n/log₂ n
- Source / version date
- 29 Jun 2015
- Comparison variant
- Decision · fixed noise · unlimited samples
- Cost scale
- limsup log₂(T) log₂(n) / n
- Input samples
- 2^{(1+o(1)) n/log₂ n}
- Model / assumptions
- Independent samples; decision LPN
- Exact coefficient / bound
- Leading normalized coefficient 1
Assumptions and source notes
Fixed-noise specialization of the paper’s decision-LPN bound.
Source location
§3.1; Appendix C, Theorem 18
Version: arXiv:1506.02717v4, 29 June 2015
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}
}