The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors
ISIT 2019
- Time bound
- 21.6168 n + o(n)
- Space bound
- —
- Source / version date
- 19 Jan 2019
- Comparison variant
- BKW · Regev · polynomial samples · quantum
- Cost scale
- 2c n + o(n)
- Input samples
- poly(n) fresh input equations; amplification allowed
- Distribution model
- Assumptions of the cited BKW/list analysis
- Reduction schedule
- Arithmetic progression of γᵢ
- Memory access
- Coherent indexed reads; Grover search
- 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.
Selected earlier references
Selected sources cited by this paper.
- Coded-BKW with Sieving
Qian Guo · Thomas Johansson · Erik Mårtensson · Paul Stankovski · 2017
Analyzes the γ=1 variant of the earlier algorithm under four sample/computation settings. §III, reference [13]; §VI, Table I
- On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving
Qian Guo · Thomas Johansson · Erik Mårtensson · Paul Stankovski Wagner · 2019
Restates the earlier common-factor analysis before extending the reduction schedule. §III, reference [14]; Theorem 1
- An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
Paul Kirchner · Pierre-Alain Fouque · 2015
Identifies prior progressive quantization in the BKW history. §III, reference [12]; §V.C
- Coded-BKW: Solving LWE Using Lattice Codes
Qian Guo · Thomas Johansson · Paul Stankovski · 2015
Identifies independently developed lattice-code BKW reduction. §III, reference [11]; §V.C
- 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 detailed BKW analysis for LWE. §III, reference [9]; §V.B
- Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model
Avrim Blum · Adam Kalai · Hal Wasserman · 2000
Traces the original BKW algorithm to STOC 2000. §III, reference [8]
@inproceedings{paper-f792611a7feb,
author = {Erik Mårtensson},
title = {{The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors}},
booktitle = {2019 IEEE International Symposium on Information Theory (ISIT)},
year = {2019},
pages = {2579--2583},
publisher = {IEEE},
doi = {10.1109/ISIT.2019.8849218},
url = {https://arxiv.org/abs/1901.06558},
cr_date = {2019-01-19},
cr_status = {published},
cr_venue = {2019 IEEE International Symposium on Information Theory (ISIT)},
cr_author_ids = {erik-martensson},
archiveprefix = {arXiv},
eprint = {1901.06558}
}