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