LWE / BKW · Regev · quantum / Grover

Coded-BKW with Sieving

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

Asiacrypt 2017

PublishedSource checked

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

Source / version date: 3 Dec 2017
Comparison variant: BKW · Regev · quantum / Grover
Cost scale: 2^{c n + o(n)}
Input samples: 2^{Θ(n)} fresh classical equations
Distribution model: Assumptions of the cited BKW/list analysis
Reduction schedule: Exact prefix; common factor γ = 1
Memory access: Coherent indexed reads; Grover search

Assumptions and source notes

Quantum-search variant; Table I of Mårtensson 2019 reproduces this coefficient. Date uses the ASIACRYPT 2017 opening day.

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