Solving the Shortest Vector Problem in time $2^{0.6039n}$ Time via Mid-point Hessian
2026-08-03 • Data Structures and Algorithms
Data Structures and AlgorithmsCryptography and Security
AI summaryⓘ
The authors developed new randomized algorithms to find the shortest vector in a high-dimensional grid (lattice) more efficiently than previous methods. Their classical and quantum algorithms run much faster and use less memory than the best known algorithms before. They rely on mathematical properties of the lattice related to the Hessian matrix of a special Gaussian function centered at half the shortest vector. By cleverly using these properties and sampling techniques, the authors improve the speed and space usage for solving this important problem in lattice theory.
Shortest Vector Problem (SVP)LatticeRandomized AlgorithmsHessian MatrixPeriodic Gaussian FunctionDiscrete Gaussian SamplingBounded Distance DecodingQuantum AlgorithmsSublattice CosetsEigenvector
Authors
Minki Hhan
Abstract
We present randomized algorithms for the shortest vector problem (SVP). For the $n$-dimensional lattice $\mathcal L$, our algorithms solve SVP in time $2^{0.6039n+o(n)}$ classically and $2^{0.5411n+o(n)}$ quantumly and space $2^{0.5n+o(n)}$, improving the previous best algorithm running in $2^{n+o(n)}$ time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector $v \in \mathcal L$, the Hessian at $v/2$ has the eigenvector close to $v$, which can be used to recover $v$ using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo $\mathcal L$, the candidate midpoints are indexed by the parity classes in $\mathcal L/2\mathcal L$. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.