Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven; Michele Mosca; Joop van de Pol

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.799 n + o (n)}$ , improving upon the classical time complexities of $2^{2.465 n + o (n)}$ of Pujol and Stehlé and the $2^{2 n + o (n)}$ of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time $2^{0.286 n + o (n)}$ , improving upon the classical time complexity of $2^{0.337 n + 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: lattices shortest vector problem sieving quantum 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: 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},
      url = {https://eprint.iacr.org/2014/907}
}