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.
- hyperhello
For those who don’t have math extensions in the browser, if that is 2^0.6039, then why don’t math extensions just detect math syntax and style it directly?
- slwvx
I was very happy to see an "AI use disclosure" right on the title page under the abstract.
It's not clear if this is solely a possible theoretical result or if it has any practical value. I.e. is it only useful on lattices that are so large as to not be of use, or could it be used for cryptanalysis? If one is using AI to generate a theory paper such as this, why not use the AI to also generate code that uses it, put it on GitHub, and show the results, say against fplll and the tool in the paper below?
- GracefullyShot
could this be a problem for the security of Falcon (aka FN-DSA) post quantum signature scheme?