LWE / BKW · Regev · unlimited samples

Coded-BKW with Sieving

Qian Guo · Thomas Johansson · Erik Mårtensson · Paul Stankovski

Asiacrypt 2017

PublishedSource checked

Time bound: 2^{0.9054 n+o(n)}
Space bound: 2^{0.9054 n+o(n)}

Source / version date: 3 Dec 2017
Comparison variant: BKW · Regev · unlimited samples
Cost scale: 2^{c n + o(n)}
Input samples: Exponential fresh samples
Distribution model: Sieve/list-distribution heuristics
formula: λ/[1−exp(−λ(1+2(c_q−c_s))/c_s)], λ=.292,c_q=2,c_s=1.5

Assumptions and source notes

Published table’s four-decimal value for the version without plain-BKW preprocessing.

Source location

§6.1, Theorem 1; §6.3, Table 1
Version: ASIACRYPT 2017 proceedings version

Primary source ↗

BibTeXDownload .bib

@inproceedings{paper-46a7c73ed460,
  author = {Qian Guo and Thomas Johansson and Erik Mårtensson and Paul Stankovski},
  title = {{Coded-BKW with Sieving}},
  booktitle = {Advances in Cryptology -- ASIACRYPT 2017},
  year = {2017},
  volume = {10624},
  pages = {323--346},
  publisher = {Springer},
  doi = {10.1007/978-3-319-70694-8_12},
  url = {https://www.iacr.org/archive/asiacrypt2017/106240219/106240219.pdf},
  cr_date = {2017-12-03},
  cr_status = {published},
  cr_venue = {Advances in Cryptology -- ASIACRYPT 2017},
  cr_author_ids = {qian-guo; thomas-johansson; erik-martensson; paul-stankovski},
  series = {Lecture Notes in Computer Science}
}