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^{1.6417 n + o(n)}

Space bound

—

Source / version date

9 Jan 2019

Comparison variant

BKW · Regev · polynomial samples

Cost scale

2^{c n + o(n)}

Input samples

poly(n) fresh input equations; amplification allowed

Distribution model

Assumptions of the cited BKW/list analysis

Reduction schedule

Optimized constant γ

Memory access

Classical tables

coefficient_source

https://arxiv.org/html/1901.06558v2#S6.T1

Assumptions and source notes

Polynomial-sample column of Mårtensson 2019 Table I; amplification noise included. First public archive date shown.

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