Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice Sieving
Asiacrypt 2019
PublishedSource checked
- Time bound
- 20.1037 n + o(n)
- Space bound
- 20.2075 n + o(n)
- Source / version date
- 10 Sept 2019
- Comparison variant
- Heuristic · parallel quantum depth
- Cost scale
- 2c n + o(n) depth
- Computation model
- Parallel quantum circuit model
- quantum-memory
- 2^{0.2075n+o(n)} qubits / memory cells
Assumptions and source notes
Parallel quantum circuit time; excluded from sequential-time rankings.
Source location
Abstract, final result
Version: 2019-09-10
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}
}