SVP Solved in 2^{0.6039n} Time via Mid-point Hessian
Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-Point Hessian
We present randomized algorithms for the shortest vector problem (SVP) on n-dimensional lattices, achieving time 2^{0.6039n+o(n)} classically and 2^{0.5411n+o(n)} quantumly, with space 2^{0.5n+o(n)}. This improves the previous best of 2^{n+o(n)} time and space by Aggarwal, Dadush, Regev, and Stephens-Davidowitz. Our method exploits the Hessian of the periodic Gaussian function at half the shortest vector: the eigenvector close to v can be recovered via bounded distance decoding. We search over parity classes in L/2L, estimating Hessians with discrete Gaussian samples, and optimize using random sublattice cosets and sampling techniques.
For a shortest vector v∈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.