LWE / BKW · q ≍ n², width ≍ n · unlimited samples

An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices

Paul Kirchner · Pierre-Alain Fouque

Crypto 2015

PublishedSource checked

Time bound: 2^{(1/(1/2+2 ln 2)+o(1)) n}
Space bound: 2^{(1/(1/2+2 ln 2)+o(1)) n}

Source / version date: 29 Jun 2015
Comparison variant: BKW · q ≍ n², width ≍ n · unlimited samples
Cost scale: 2^{c n + o(n)}
Input samples: Exponential fresh samples
Model / assumptions: Independent samples; normal-form secret
Exact coefficient / bound: d=2,c=3/2 in Corollary 1

Assumptions and source notes

Gaussian-width exponent 1 corresponds to β=n^{3/2+o(1)} in this paper’s normalization.

Source location

Corollary 1; Theorem 5; Definition 2
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]

Primary source ↗

BibTeXDownload .bib

@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}
}