Cryptology ePrint Archive: Report 2014/907

Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven and 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.

Category / Keywords: public-key cryptography / lattices, shortest vector problem, sieving, quantum search

Original Publication (with minor differences): Designs, Codes and Cryptography
DOI: 10.1007/s10623-015-0067-5

Date: received 3 Nov 2014, last revised 17 Apr 2015

Contact author: joop vandepol at bristol ac uk

Available format(s): PDF | BibTeX Citation

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

Version: 20150417:130323 (All versions of this report)

Short URL: ia.cr/2014/907

Discussion forum: Show discussion | Start new discussion