Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-Point Hessian
Summary
The paper presents randomized algorithms for the shortest vector problem (SVP) with asymptotic time 2^{0.6039n+o(n)} classically and 2^{0.5411n+o(n)} quantumly, using the Hessian of the periodic Gaussian function at half the shortest vector. It leverages parity classes in L/2L, discrete Gaussian sampling, and sublattice coset optimizations to achieve the improved complexity and space bounds. The work has potential implications for lattice-based cryptography and related security considerations.