SVP / Quantum · heuristic

Improved Quantum Hypercone Locality Sensitive Filtering in Lattice Sieving

Max Heiser

ePrint 2021/1295

PreprintSource checked

Time bound: 2^{0.2571 n + o(n)}
Space bound: —

Source / version date: 27 Sept 2021
Comparison variant: Quantum · heuristic
Cost scale: 2^{c n + o(n)}
QRAM / random access: Quantum access to classical sieve buckets
Quantum memory: No single workspace coefficient extracted
Operation model: Grover search with random-product-code filter sampling

Assumptions and source notes

Independent filter-sampling approach; .2570 via quantum walks was already available.

Source location

Theorem 1; Section 3.2.3
Version: ePrint 2021/1295, received 27 September 2021

Selected earlier references

Selected sources cited by this paper.

Search problems in cryptography: from fingerprinting to lattice sieving
Thijs Laarhoven · 2016
Improves the earlier Grover-search filtering algorithm. Section 3.2.2; reference [16]
Lattice sieving via quantum random walks
André Chailloux · Johanna Loyer · 2021
Acknowledges the independently developed quantum-walk improvement. Introduction; reference [7]

Primary source ↗

BibTeXDownload .bib

@misc{heiser-2021,
  author = {Max Heiser},
  title = {{Improved Quantum Hypercone Locality Sensitive Filtering in Lattice Sieving}},
  year = {2021},
  url = {https://eprint.iacr.org/2021/1295},
  keywords = {SVP, lattice sieving},
  cr_date = {2021-09-27},
  cr_status = {preprint},
  cr_author_ids = {max-heiser},
  howpublished = {Cryptology ePrint Archive}
}