Paper 2014/907

Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven, Michele Mosca, and Joop van de Pol

Abstract

By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time $2^{1.799n + o(n)}$, improving upon the classical time complexities of $2^{2.465n + o(n)}$ of Pujol and Stehlé and the $2^{2n + o(n)}$ of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time $2^{0.286n + o(n)}$, improving upon the classical time complexity of $2^{0.337n + o(n)}$ of Laarhoven. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.

Note: This article is a minor revision of the version published in Design, Codes and Cryptography.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Designs, Codes and Cryptography
DOI
10.1007/s10623-015-0067-5
Keywords
latticesshortest vector problemsievingquantum search
Contact author(s)
joop vandepol @ bristol ac uk
History
2015-04-17: revised
2014-11-04: received
See all versions
Short URL
https://ia.cr/2014/907
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/907,
      author = {Thijs Laarhoven and Michele Mosca and Joop van de Pol},
      title = {Finding shortest lattice vectors faster using quantum search},
      howpublished = {Cryptology ePrint Archive, Paper 2014/907},
      year = {2014},
      doi = {10.1007/s10623-015-0067-5},
      note = {\url{https://eprint.iacr.org/2014/907}},
      url = {https://eprint.iacr.org/2014/907}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.