Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice Sieving
Asiacrypt 2019
PublishedSource checked
- Time bound
- 20.3349 n + o(n)
- Space bound
- 20.1887 n + o(n)
- Source / version date
- 10 Sept 2019
- Comparison variant
- Heuristic · quantum · memory ≤ 0.1887n
- Cost scale
- 2c n + o(n)
- Computation model
- Sequential quantum time; .1887n classical QRAM exponent; poly(n) qubits
- Preprocessing cost
- Included
- Source locator
- Table 2, low-memory k=3 column; Section 5.1
Assumptions and source notes
Configuration search without LSF.
Source location
Table 2, low-memory k=3 column; Section 5.1
Version: ePrint 2019/1016, 10 September 2019
Selected earlier references
Selected sources cited by this paper.
- Search problems in cryptography: from fingerprinting to lattice sieving
Thijs Laarhoven · 2016
Uses the thesis .2653 quantum pair-sieve baseline. Introduction and bibliography [Laa15]
- Speed-ups and time-memory trade-offs for tuple lattice sieving
Gottfried Herold · Elena Kirshanova · Thijs Laarhoven · 2018
Quantum acceleration of configuration search. Introduction; Sections 3–4; reference [HKL18]
- Space-efficient classical and quantum algorithms for the shortest vector problem
Yanlin Chen · Kai-Min Chung · Ching-Yi Lai · 2018
Cites the .5-space provable quantum SVP algorithm. Introduction; reference [CCL17]
BibTeXDownload .bib
@inproceedings{kirshanova-et-al-2019,
author = {Elena Kirshanova and Erik Mårtensson and Eamonn W. Postlethwaite and Subhayan Roy Moulik},
title = {{Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice Sieving}},
booktitle = {ASIACRYPT 2019},
year = {2019},
url = {https://eprint.iacr.org/2019/1016},
keywords = {SVP, quantum, tuple sieving, QRAM},
cr_date = {2019-09-10},
cr_status = {published},
cr_venue = {ASIACRYPT 2019},
cr_author_ids = {elena-kirshanova; erik-martensson; eamonn-w-postlethwaite; subhayan-roy-moulik}
}