SVP / Quantum · worst case

Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven · Michele Mosca · Joop van de Pol

Designs, Codes and Cryptography 2015

PublishedSource checked

Time bound: 2^{1.986 n + o(n)}
Space bound: 2^{1.324 n + o(n)}

Source / version date: 14 Apr 2015
Comparison variant: Quantum · worst case
Cost scale: 2^{c n + o(n)}
Norm: Euclidean ℓ₂
Success guarantee: Randomized, provable analysis
Computation model: Sequential quantum search
QRAM / coherent access: Quantum-addressable classical lists

Assumptions and source notes

AKS-Sieve-Birthday analysis; alternative bound rather than a new best-time milestone.

Source location

Table 1; Section 8.3
Version: DCC version published online 14 April 2015

Selected earlier references

Selected sources cited by this paper.

Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
Thijs Laarhoven · Michele Mosca · Joop van de Pol · 2013
Expanded journal version of the PQCrypto 2013 work. Title-page note; reference [50]
Sieving for shortest vectors in lattices using angular locality-sensitive hashing
Thijs Laarhoven · 2015
Quantum search applied to angular-LSH sieving. Section 5; reference [47]
Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
Thijs Laarhoven · Benne de Weger · 2015
Quantum search applied to spherical-LSH sieving. Section 6; reference [48]
Solving the Shortest Lattice Vector Problem in Time 2^(2.465n)
Xavier Pujol · Damien Stehlé · 2009
Provable quantum analysis builds on the earlier birthday sieve. Section 2; reference [65]

Primary source ↗

BibTeXDownload .bib

@article{paper-caa5f6c38871,
  author = {Thijs Laarhoven and Michele Mosca and Joop van de Pol},
  title = {{Finding shortest lattice vectors faster using quantum search}},
  journal = {Designs, Codes and Cryptography},
  year = {2015},
  volume = {77},
  pages = {375--400},
  doi = {10.1007/s10623-015-0067-5},
  url = {https://doi.org/10.1007/s10623-015-0067-5},
  cr_date = {2015-04-14},
  cr_status = {published},
  cr_venue = {Designs, Codes and Cryptography},
  cr_author_ids = {thijs-laarhoven; michele-mosca; joop-van-de-pol}
}