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

André Chailloux · Johanna Loyer

PQCrypto 2023

Time bound

2^{0.3098 n + o(n)}

Space bound

2^{0.1887 n + o(n)}

Source / version date

2 Aug 2023

Comparison variant

Quantum · heuristic

Cost scale

2^{c n + o(n)}

Operation model

Sequential quantum time; .1887n classical QCRAM exponent; poly(n) qubits

preprocessing

Included

reference

Theorem 6

QRAM / random access

Coherent access to classical memory; exponent 0.1887

Quantum memory

2^{o(n)}; see the source’s access model

Assumptions and source notes

Tailored filtering before quantum tuple search improves triple sieving at the stated memory budget. It is not an unrestricted quantum-SVP time record. 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

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