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.
Abstract The shortest vector problem (SVP) is one of the lattice problems and is the mathematical basis for lattice-based cryptography, which is expected to be post-quantum cryptography. The SVP can be mapped onto the Ising problem, which in principle can be solved by quantum annealing (QA). However, one issue in solving the SVP using QA is that the solution of the SVP corresponds to the first excited state of the problem Hamiltonian. Therefore, QA, which searches for ground states, cannot provide a solution with high probability. In this paper, we propose to adopt an excited-state search of the QA to solve the shortest vector problem. We numerically show that the excited-state search provides a solution with a higher probability than the ground-state search.
We present randomized algorithms for the shortest vector problem (SVP). For the
n-dimensional lattice
L, our algorithms solve SVP in time
20.6039n+o(n) classically and
20.5411n+o(n) quantumly and space
20.5n+o(n), improving the previous best algorithm running in
2n+o(n) time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector
v∈L, the Hessian at
v/2 has the eigenvector close to
v, which can be used to recover
v using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo
L, the candidate midpoints are indexed by the parity classes in
L/2L. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.