Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
This work addresses the problem of lattice-based cryptography for post-quantum security, providing incremental improvements by applying quantum techniques to known classical methods.
The paper tackles the shortest vector problem in lattices by applying Grover's quantum search algorithm to existing classical algorithms, resulting in improved asymptotic quantum time complexities, such as provably reducing the time from 2^{2.465n + o(n)} to 2^{1.799n + o(n)} and heuristically from 2^{0.384n + o(n)} to 2^{0.312n + o(n)}.
By applying Grover's quantum search algorithm to the lattice algorithms of Micciancio and Voulgaris, Nguyen and Vidick, Wang et al., and Pujol and Stehlé, we obtain improved asymptotic quantum results for solving the shortest vector problem. With quantum computers we can provably find a shortest vector in time $2^{1.799n + o(n)}$, improving upon the classical time complexity 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.312n + o(n)}$, improving upon the classical time complexity of $2^{0.384n + o(n)}$ of Wang et al. 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.