Classical and quantum 3 and 4-sieves to solve SVP with low memory

André Chailloux · Johanna Loyer

PQCrypto 2023

Time bound

2^{0.3383 n + o(n)}

Space bound

2^{0.1887 n + o(n)}

Source / version date

2 Aug 2023

Comparison variant

Classical · heuristic

Cost scale

2^{c n + o(n)}

Computation model

Classical Nguyen–Vidick style; spherical-list heuristic

preprocessing

Included

reference

Theorem 4; later Table 1

Assumptions and source notes

Tailored filtering improves the low-memory triple-sieving method. It does not lower the unrestricted pair-sieving exponent. The original theorem rounds time to 0.338; the displayed 0.3383 is the later comparison-table precision, not another improvement. 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

Primary source ↗

@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}
}