CryptoDB
A 2^{n/2}Time Algorithm for \sqrt{n}SVP and \sqrt{n}Hermite SVP, and an Improved TimeApproximation Tradeoff for (H)SVP
Authors: 


Download: 

Conference:  EUROCRYPT 2021 
Abstract:  We show a 2^{n/2+o(n)}time algorithm that, given as input a basis of a lattice $\lat \subset \R^n$, finds a (nonzero) vector in whose length is at most $\widetilde{O}(\sqrt{n})\cdot \min\{\lambda_1(\lat), \det(\lat)^{1/n}\}$, where $\lambda_1(\lat)$ is the length of a shortest nonzero lattice vector and $\det(\lat)$ is the lattice determinant. Minkowski showed that $\lambda_1(\lat) \leq \sqrt{n} \det(\lat)^{1/n}$ and that there exist lattices with $\lambda_1(\lat) \geq \Omega(\sqrt{n}) \cdot \det(\lat)^{1/n}$, so that our algorithm finds vectors that are as short as possible relative to the determinant (up to a polylogarithmic factor). The main technical contribution behind this result is new analysis of (a simpler variant of) a 2^{n/2 + o(n)}time algorithm from [ADRS15], which was only previously known to solve less useful problems. To achieve this, we rely crucially on the ``reverse Minkowski theorem'' (conjectured by Dadush [DR16] and proven by [RS17]), which can be thought of as a partial converse to the fact that $\lambda_1(\lat) \leq \sqrt{n} \det(\lat)^{1/n}$. Previously, the fastest known algorithm for finding such a vector was the 2^{0.802n + o(n)}time algorithm due to [LWXZ11], which actually found a nonzero lattice vector with length $O(1) \cdot \lambda_1(\lat)$. Though we do not show how to find lattice vectors with this length in time $2^{n/2+o(n)}$, we do show that our algorithm suffices for the most important application of such algorithms: basis reduction. In particular, we show a modified version of Gama and Nguyen's slidereduction algorithm [GN08], which can be combined with the algorithm above to improve the timelength tradeoff for shortestvector algorithms in nearly all regimesincluding the regimes relevant to cryptography. 
Video from EUROCRYPT 2021
BibTeX
@inproceedings{eurocrypt202130789, title={A 2^{n/2}Time Algorithm for \sqrt{n}SVP and \sqrt{n}Hermite SVP, and an Improved TimeApproximation Tradeoff for (H)SVP}, publisher={SpringerVerlag}, doi={10.1007/9783030778705_17}, author={Divesh Aggarwal and Zeyong Li and Noah StephensDavidowitz}, year=2021 }