A 2n/2-Time Algorithm for $\sqrt{n}$-SVP and $\sqrt{n}$-Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP

We show a 2 n/2+o(n) -time algorithm that finds a (non-zero) vector in a lattice L ⊂ R n with norm at most O( √ n) • minλ 1 (L), det(L) 1/n , where λ 1 (L) is the length of a shortest non-zero lattice vector and det(L) is the lattice determinant. Minkowski showed that λ 1 (L) ≤ √ n det(L) 1/n and that there exist lattices with λ 1 (L) ≥ Ω( √ n)•det(L) 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 λ 1 (L) ≤ √ n det(L) 1/n . Previously, the fastest known algorithm for finding such a vector was the 2 .802n+o(n) -time algorithm due to [LWXZ11], which actually found a non-zero lattice vector with length O(1) • λ 1 (L). 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 slide-reduction algorithm [GN08], which can be combined with the algorithm above to improve the time-length tradeoff for shortest-vector algorithms in nearly all regimes-including the regimes relevant to cryptography.