SVP / Quantum · heuristic

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: (13/9)^{n/2 + o(n)}

Source / version date: 16 Feb 2016
Comparison variant: Quantum · heuristic
Cost scale: 2^{c n + o(n)}
Operation model: Quantum RAM access to classical data; heuristic spherical list model
reference: Section 14.2.10

Assumptions and source notes

Section 14.2.10, equation (14.6)–(14.7): heuristic quantum LSF bound. The author-hosted draft is dated 10 November 2015; chronology uses the documented thesis publication date.

Source location

Chapter 14, Section 14.2.10, printed p.186 / PDF p.193
Version: 2016-02-16

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