SVP / Heuristic · quantum · minimal sieve-list space

Search problems in cryptography: from fingerprinting to lattice sieving

Thijs Laarhoven

Technische Universiteit Eindhoven 2016

PublishedSource checked

Time bound: (13/9)^n/2+o(n)
Space bound: (4/3)^n/2+o(n)

Source / version date: 16 Feb 2016
Comparison variant: Heuristic · quantum · minimal sieve-list space
Cost scale: 2^{c n + o(n)}
Computation model: Nguyen–Vidick; sequential processing of filter structures
Coherent classical access: RAM-like quantumly addressable classical memory
Quantum workspace: Quantum search workspace; see Section 14.1

Assumptions and source notes

Batch variant; the GaussSieve variant has different memory costs.

Source location

Table 14.1; Figure 14.1 caption; Section 14.2.10
Version: TU/e thesis public catalogue date 16 February 2016

Selected earlier references

Selected sources cited by this paper.

Finding shortest lattice vectors faster using quantum search
Thijs Laarhoven · Michele Mosca · Joop van de Pol · 2015
Extends the quantum-search complexity analysis. Chapter 14, introductory references [LMvdP15]
New directions in nearest neighbor searching with applications to lattice sieving
Anja Becker · Léo Ducas · Nicolas Gama · Thijs Laarhoven · 2016
Quantum filtering builds on the classical locality-sensitive filters. Sections 13 and 14.2.10; reference [BDGL16]

Primary source ↗

BibTeXDownload .bib

@phdthesis{laarhoven-thesis-2016,
  author = {Thijs Laarhoven},
  title = {{Search problems in cryptography: from fingerprinting to lattice sieving}},
  school = {Technische Universiteit Eindhoven},
  year = {2016},
  url = {https://research.tue.nl/en/publications/search-problems-in-cryptography-from-fingerprinting-to-lattice-si/},
  keywords = {SVP, quantum sieving, nearest neighbors},
  cr_date = {2016-02-16},
  cr_status = {published},
  cr_venue = {Technische Universiteit Eindhoven},
  cr_author_ids = {thijs-laarhoven}
}