2026/08/03 by Minki Hhan · 1 voice · 1 citation
Computer Science · #cs.CR #cs.DS
Corrected title
arxiv created 2026/08/04 · arxiv updated 2026/08/05
We present randomized algorithms for the shortest vector problem (SVP). For the n-dimensional lattice \mathcal L, our algorithms solve SVP in time 20.6039n+o(n) classically and 20.5411n+o(n) quantumly and space 20.5n+o(n), improving the previous best algorithm running in 2n+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 ∈ \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.