Finding shortest lattice vectors faster using quantum search

Thijs Laarhoven, Michele Mosca, Joop Van De Pol

Research output: Contribution to journalArticle (Academic Journal)peer-review

36 Citations (Scopus)
292 Downloads (Pure)

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 21.799n+o(n), improving upon the classical time complexities of 22.465n+o(n) of Pujol and Stehlé and the 22n+o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.268n+o(n), improving upon the classical time complexity of 20.298n+o(n) of Laarhoven and De Weger. 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.
Original languageEnglish
Pages (from-to)375-400
Number of pages26
JournalDesigns, Codes and Cryptography
Volume77
Issue number2
Early online date14 Apr 2015
DOIs
Publication statusPublished - Dec 2015

Fingerprint Dive into the research topics of 'Finding shortest lattice vectors faster using quantum search'. Together they form a unique fingerprint.

Cite this