Dissection-BKW
Crypto 2018
- Time bound
- 2(((1−1/3) log₂ 4)+ε) n/log₂ n
- Space bound
- 2(log₂(4)/3+ε) n/log₂ n
- Source / version date
- 2018
- Comparison variant
- Classical · memory coefficient ≤ 2/3
- Cost scale
- limsup log₂(T) log₂(n) / n
- Input samples
- Same leading exponent as memory
- Model / assumptions
- Independence Heuristic
- Exact coefficient / bound
- Magic-sequence index i=1, c_i=4
Assumptions and source notes
For every fixed ε>0.
Source location
Theorem 5.1; Definition 5.3
Version: ePrint 2018/569 full version, 31 pages, checked 2026-11-08; original-version diff not available
Selected earlier references
Selected sources cited by this paper.
- Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model
Avrim Blum · Adam Kalai · Hal Wasserman · 2000
Develops memory-saving trade-offs from the original BKW endpoint. Introduction; reference [6]
- An Improved LPN Algorithm
Éric Levieil · Pierre-Alain Fouque · 2006
Discusses the earlier LF1/LF2 variants and multi-sample extensions. Introduction, reference [28]
- Coded-BKW: Solving LWE Using Lattice Codes
Qian Guo · Thomas Johansson · Paul Stankovski · 2015
Places the memory trade-offs alongside prior coded-BKW work. Introduction, reference [17]
- On the Asymptotic Complexity of Solving LWE
Gottfried Herold · Elena Kirshanova · Alexander May · 2018
Cites the preceding asymptotic LWE comparison. Introduction, reference [20]
- An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
Paul Kirchner · Pierre-Alain Fouque · 2015
Cites the preceding quantization improvement. Introduction, reference [24]
@inproceedings{esser2018-dissection-bkw,
author = {Andre Esser and Felix Heuer and Robert Kübler and Alexander May and Christian Sohler},
title = {{Dissection-BKW}},
booktitle = {Advances in Cryptology -- CRYPTO 2018},
year = {2018},
volume = {10992},
pages = {638--666},
publisher = {Springer},
doi = {10.1007/978-3-319-96881-0_22},
url = {https://eprint.iacr.org/2018/569},
keywords = {LPN, time-memory tradeoffs, quantum, BKW},
cr_date = {2018-12-31},
cr_date_precision = {year},
cr_status = {published},
cr_venue = {Advances in Cryptology — CRYPTO 2018, LNCS 10992},
cr_author_ids = {andre-esser; felix-heuer; robert-kubler; alexander-may; christian-sohler},
series = {Lecture Notes in Computer Science}
}