Slide Reduction, Revisited---Filling the Gaps in SVP Approximation
This work addresses a key bottleneck in lattice-based cryptography by improving SVP approximation algorithms, though it is incremental as it builds on prior slide reduction methods.
The paper generalizes the slide reduction algorithm for solving the approximate Shortest Vector Problem (SVP) over lattices, resulting in the fastest provably correct algorithm for δ-approximate SVP across a range of approximation factors relevant to cryptography, specifically for n^{1/2+ε} ≤ δ ≤ n^{O(1)}.
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.