On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving

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

IEEE Trans. Information Theory 2019

Time bound

2^{0.8795 n + o(n)}

Space bound

—

Source / version date

9 Jan 2019

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

Optimized constant γ

Memory access

Coherent indexed reads; Grover search

Assumptions and source notes

Quantum-search variant, optimized common factor. This coefficient is also reproduced in Mårtensson 2019 Table I.

Primary source ↗

@article{paper-c64ff7d0568b,
  author = {Qian Guo and Thomas Johansson and Erik Mårtensson and Paul Stankovski Wagner},
  title = {{On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving}},
  journal = {IEEE Transactions on Information Theory},
  year = {2019},
  volume = {65},
  number = {8},
  pages = {5243--5259},
  doi = {10.1109/TIT.2019.2906233},
  url = {https://eprint.iacr.org/2019/009},
  cr_date = {2019-01-09},
  cr_status = {published},
  cr_venue = {IEEE Transactions on Information Theory},
  cr_author_ids = {qian-guo; thomas-johansson; erik-martensson; paul-stankovski-wagner}
}