Classical and quantum 3 and 4-sieves to solve SVP with low memory
PQCrypto 2023
- Time bound
- 20.3383 n + o(n)
- Space bound
- 20.1887 n + o(n)
- Source / version date
- 2 Aug 2023
- Comparison variant
- Heuristic · triple sieving
- Cost scale
- 2c n + o(n)
- Computation model
- Classical Nguyen–Vidick style; spherical-list heuristic
- Preprocessing cost
- Included
- Source locator
- Theorem 4; later Table 1
Assumptions and source notes
Original theorem uses .338; .3383 follows the later comparison table. This is one result, not two improvements.
Source location
Original Theorem 4 rounds to .338; finer .3383 in Engelberts et al., Table 1 (arXiv:2510.08473v3)
Version: CL23 ePrint revision 2 August 2023; finer precision checked in arXiv:2510.08473v3, 7 July 2026
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]
@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}
}