An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
Crypto 2015
- Time bound
- 2(ln(2)/2+o(1)) n/log₂ log₂ n
- Space bound
- Not separately normalized
- Source / version date
- 29 Jun 2015
- Comparison variant
- Decision · binary secret and error · n samples
- Cost scale
- 2c n / log₂ log₂ n + o(n/log₂ log₂ n)
- Input samples
- n original equations
- Model / assumptions
- Uniform binary secret and errors; prime modulus q≈n²
- Exact coefficient / bound
- ln(2)/2 on the n/log₂log₂n scale
Assumptions and source notes
Decision bound for binary secret/error, q≈n², m=n. The corollary gap is Θ(log n), satisfying HKM’s stronger amplification condition.
Source location
Abstract; §5.2, Definition 11 and Corollary 6
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}
}