LPN / Classical · noise probability 1/√n

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

Paul Kirchner · Pierre-Alain Fouque

Crypto 2015

PublishedSource checked

Time bound: O(n⁴ exp(√n))
Space bound: poly(n)

Source / version date: 29 Jun 2015
Comparison variant: Classical · noise probability 1/√n
Cost scale: 2^{c √n + o(√n)}
Input samples: Fresh batches of 34n; repeated n(1−p)^{−n} times
Model / assumptions: Sequential repetitions; polynomial working memory
Exact coefficient / bound: log₂(e) on the √n scale

Assumptions and source notes

The stated p=1/√n specialization solves search LPN with negligible failure.

Source location

Appendix C, Theorem 19 and following specialization
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}
}