An Improved Quantum Algorithm for 3-Tuple Lattice Sieving

The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension d, they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. k-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of k of the input vectors. Iterating these "sieving steps" sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for k=2, but taking larger k reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from 2^{0.3098 d} to 2^{0.2846 d}, using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby "center points" to focus the search on the neighborhoods of these center points. Our algorithm uses 2^0.1887d classical bits and QCRAM bits, and 2^o(d) qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to 2^0.1887d.