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 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 \mathcal{L}$ and applies the honest discrete Gaussian sampler of ADRS to $\Gamma$ with a parameter above the smoothing threshold. Then it simply scans the resulting samples and retains the shortest nonzero one that lies in $\mathcal{L}$. The analysis passes to the dual lattice $M=\Gamma^*$. A random linear constraint reduces the expected contribution of vectors outside $p\mathcal{L}^*$ by a factor smaller than $1/p$. A dual minimum bound, obtained by applying Poisson summation to a shortest dual line, controls the forced Gaussian mass on $p\mathcal{L}^*$. Consequently, $\Gamma$ is smooth at the sampling scale and a fixed shortest vector of $\mathcal{L}$ is hit with probability at least $2^{-E_0n-o(n)}$ per ideal sample.