Welcome to the resource topic for 2014/907
Title:
Finding shortest lattice vectors faster using quantum search
Authors: Thijs Laarhoven, Michele Mosca, 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.
ePrint: https://eprint.iacr.org/2014/907
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .