Shortest Vector Problem Solved in 2^0.6039n Time, Breaking the 2^n Barrier Standing Since STOC 2015

arXiv 2608.02478·medium signalXBlueskyLinkedInCopy link

Minki Hhan presents randomized algorithms solving SVP in 2^{0.6039n+o(n)} classically and 2^{0.5411n+o(n)} quantumly with 2^{0.5n+o(n)} space, improving on the 2^{n+o(n)} time and space algorithm of Aggarwal, Dadush, Regev, and Stephens-Davidowitz from STOC'15. The technique analyzes the Hessian of a periodic Gaussian at the midpoint v/2 of the shortest vector, whose eigenvector is close to v, then recovers v via bounded distance decoding while searching parity classes in the quotient lattice L/2L. Because lattice hardness underpins post-quantum cryptography, concrete-security parameter estimates for lattice schemes are the thing to watch downstream.