Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces randomized algorithms that solve the shortest vector problem (SVP) in $n$-dimensional lattices with a time complexity of $2^{0.6039n+o(n)}$ classically and $2^{0.5411n+o(n)}$ quantumly, significantly improving upon the previous best-known time of $2^{n+o(n)}$. The core innovation lies in leveraging the Hessian of the periodic Gaussian function at the half shortest vector, which facilitates the recovery of the shortest vector through bounded distance decoding. Additionally, the authors optimize their approach using random sublattice cosets and advanced sampling techniques, which may have broader implications beyond SVP solving.
Achieving a breakthrough in SVP solving with algorithms that run exponentially faster than previous methods could redefine cryptographic security assumptions.
We present randomized algorithms for the shortest vector problem (SVP). For the $n$-dimensional lattice $\mathcal L$, our algorithms solve SVP in time $2^{0.6039n+o(n)}$ classically and $2^{0.5411n+o(n)}$ quantumly and space $2^{0.5n+o(n)}$, improving the previous best algorithm running in $2^{n+o(n)}$ time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector $v \in \mathcal 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. Given the periodicity modulo $\mathcal L$, the candidate midpoints are indexed by the parity classes in $\mathcal L/2\mathcal L$. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.