Paper 2026/1587

Solving the Shortest Vector Problem in $2^{0.7314n+o(n)}$ Time via Discrete Gaussian Sampling on Superlattices

Abstract

We give a classical randomized algorithm for the exact Euclidean Shortest Vector Problem (SVP) on arbitrary full-rank lattices. It runs in $2^{0.7314n+o(n)}$ time and$2^{n/2+o(n)}$ space. More precisely, it returns a shortest vector with high probability and runs in $$ 2^{E_0n+o(n)} \quad\text{time and}\quad 2^{n/2+o(n)} \quad\text{space}, \qquad E_0=0.73133754\ldots . $$ This improves the $2^{n+o(n)}$ classical bound of Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS, STOC 2015). It also beats the previous best known worst-case quantum bounds of Aggarwal, Chen, Kumar, and Shen (ACKS, SIAM J.Comp. 2025), namely $2^{0.9497n+o(n)}$ without QRAM and $2^{0.8345n+o(n)}$ with QRAM. The algorithm constructs a random prime-index superlattice $\Gamma\supset L$ and applies the above-smoothing honest discrete Gaussian sampler of ADRS to $\Gamma$. Then it simply scans the resulting samples and retains the shortest nonzero one that lies in $L$. The analysis passes to the dual lattice $M=\Gamma^*$. The random codimension-one constraint reduces the expected contribution of vectors outside $pL^*$ by a factor smaller than $1/p$, while the forced Gaussian mass on $pL^*$ is controlled geometrically using the Kabatiansky--Levenshtein sphere-packing bound. Consequently, $\Gamma$ is smooth at the sampling scale and a fixed shortest vector of $L$ is hit with probability at least $2^{-E_0n-o(n)}$ per ideal sample.