DSAug 10, 2019
Slide Reduction, Revisited---Filling the Gaps in SVP ApproximationDivesh Aggarwal, Jianwei Li, Phong Q. Nguyen et al.
We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP). As a result, we show the fastest provably correct algorithm for $δ$-approximate SVP for all approximation factors $n^{1/2+\varepsilon} \leq δ\leq n^{O(1)}$. This is the range of approximation factors most relevant for cryptography.