Institute of Information Science, Academia Sinica

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.3098d} to 2^{0.2846d}, 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}.