Classical and quantum 3 and 4-sieves to solve SVP with low memory
PQCrypto 2023
PublishedSource checked
- Time bound
- 20.3098 n + o(n)
- Space bound
- 20.1887 n + o(n)
- Source / version date
- 2 Aug 2023
- Comparison variant
- Heuristic · quantum · memory ≤ 0.1887n
- Cost scale
- 2c n + o(n)
- Computation model
- Sequential quantum time; .1887n classical QCRAM exponent; poly(n) qubits
- Preprocessing cost
- Included
- Source locator
- Theorem 6
Assumptions and source notes
Triple-sieving point using tailored filtering.
Source location
Theorem 6, pp. 26–27; Table 3
Version: ePrint 2023/200 revision 2 August 2023; original full text checked via public mirror
Selected earlier references
Selected sources cited by this paper.
- Quantum Algorithms for the Approximate $k$-List Problem and their Application to Lattice Sieving
Elena Kirshanova · Erik Mårtensson · Eamonn W. Postlethwaite · Subhayan Roy Moulik · 2019
Adds tailored filtering before quantum tuple search. Section 4.6 and bibliography [Kir+19]
- Speed-ups and time-memory trade-offs for tuple lattice sieving
Gottfried Herold · Elena Kirshanova · Thijs Laarhoven · 2018
Earlier classical tuple-sieving tradeoffs. Introduction and bibliography [HKL18]
- New directions in nearest neighbor searching with applications to lattice sieving
Anja Becker · Léo Ducas · Nicolas Gama · Thijs Laarhoven · 2016
Modifies random-product-code filtering for tuples. Section 3 and bibliography [Bec+16]
BibTeXDownload .bib
@inproceedings{chailloux-loyer-tuple-2023,
author = {André Chailloux and Johanna Loyer},
title = {{Classical and quantum 3 and 4-sieves to solve SVP with low memory}},
booktitle = {Post-Quantum Cryptography – PQCrypto 2023},
year = {2023},
doi = {10.1007/978-3-031-40003-2_9},
url = {https://eprint.iacr.org/2023/200},
keywords = {SVP, lattice sieving},
cr_date = {2023-02-15},
cr_status = {published},
cr_venue = {Post-Quantum Cryptography – PQCrypto 2023},
cr_author_ids = {andre-chailloux; johanna-loyer}
}