Minki Hhan Breaks 2015 Barrier on Shortest Vector Problem

A new algorithm solves the Shortest Vector Problem in 2^0.6039n time, breaking a bound that had held since STOC 2015, according to a preprint from Minki Hhan.

Lattice hardness underpins post-quantum cryptography, and security estimates for those schemes rest on how hard SVP is believed to be. A faster algorithm doesn't crack any deployed key, but it's the kind of result concrete-security estimates get rebuilt around.

Hhan's algorithm is randomized. The classical version runs in 2^{0.6039n+o(n)} time, improving on the STOC 2015 bound set by Aggarwal, Dadush, Regev and Stephens-Davidowitz.

That 2015 bound stood as the best known result for eleven years, per the preprint.

A quantum version does better: 2^{0.5411n+o(n)} time, using 2^{0.5n+o(n)} space.

The technique is analytic. It works through the Hessian, the matrix of second derivatives, of a periodic Gaussian evaluated at the midpoint of the shortest vector, per the preprint.

Nothing here cracks a real-world key, and the paper hasn't been through peer review.