Paper 2026/2711

Fast Provable Algorithms for Exact SVP and Approximate CVP on Random \(q\)-ary Lattices

Abstract

We give provable randomized algorithms for the exact shortest vector problem (SVP) and the $5/3$-approximate closest vector problem (CVP) in the Euclidean norm on random $q$-ary lattices $\Lambda=\{\boldsymbol x\in\mathbb{Z}^n:\mathbf H\boldsymbol x\equiv\boldsymbol 0_m\pmod q\}$, where $\mathbf H\in(\mathbb{Z}/q\mathbb{Z})^{m\times n}$ is uniformly random, for every integer modulus $q\ge2$. For density $\delta=m\log_2q/n\le1$, the SVP algorithm uses time $2^{0.2741n+o(n)}$ and space $2^{0.2614n+o(n)}$, and the CVP algorithm time $2^{0.2668n+o(n)}$ and space $2^{0.2628n+o(n)}$, on every input and execution. For $1<\delta\le3/2$, the SVP algorithm uses time $2^{0.468n+o(n)}$ and space $2^{0.329n+o(n)}$, and the CVP algorithm uses time $2^{0.56n+o(n)}$ and space $2^{0.325n+o(n)}$. For all but a $2^{-\Omega(n^{2/3})}$ fraction of input matrices, each algorithm succeeds with probability $1-2^{-\Omega(n)}$ over its internal randomness. For CVP, this success event holds simultaneously for every target. Notably, for $\delta\le1$, both time exponents are below the heuristic sieving exponent $0.2925$ for SVP and CVP. We use the Howgrave-Graham–Joux representation method, adapted to all integer moduli, to find short ternary solutions of random linear congruences. To apply this method to SVP, we must account for the dependence of a shortest vector on the random input matrix. We therefore consider a family of integer candidates, fixed independently of the matrix, that contains a shortest vector with high probability. For each candidate, we bound the probability that it belongs to the lattice but the algorithm fails to find a nonzero lattice vector at least as short. Conditioning on lattice membership allows us to apply the analysis of the representation method, while counting the candidates allows us to bound the total failure probability. Applying this method to CVP also raises an issue: the target is arbitrary and may depend on the input matrix. We round the target to an integer point and seek a short correction that moves this point into the lattice. Our construction finds such a correction with constant probability for any rational target, for most input matrices, while keeping the mean of successful corrections small. This mean bound limits the average contribution of the inner product between the correction and the rounding error to the squared distance. Repeated sampling then yields a lattice point satisfying a tighter distance bound, allowing a smaller radius for exact search.