The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors
ISIT 2019
- Time bound
- 21.6507 n+o(n)
- Space bound
- 21.6507 n+o(n)
- Source / version date
- 19 Jan 2019
- Comparison variant
- BKW · Regev · polynomial samples
- Cost scale
- 2c n + o(n)
- Input samples
- Polynomially many original samples, amplified
- Distribution model
- Heuristics of the cited BKW/list analysis
- Reduction schedule
- Common factor γ=1
- Memory access
- Classical tables
- coefficient_source
- https://arxiv.org/html/1901.06558v2#S6.T1
- original_algorithm
- Guo–Johansson–Mårtensson–Stankovski, Coded-BKW with Sieving, ASIACRYPT 2017
- original_paper_id
- paper-46a7c73ed460
Assumptions and source notes
2019 source analysis of the earlier algorithm. The 2017 conference version §6.4 deferred this sample-limited comparison to future work.
Source location
§VI, Table I; §V.E polynomial-sample transformation
Version: arXiv:1901.06558v1, 19 January 2019, Table I checked directly
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}
}