Paper 2025/244

Provable Speedups for SVP Approximation Under Random Local Blocks

Abstract

We point out if assuming every local block appearing in the slide reduction algorithms [ALNS20] is `random' (as usual in the cryptographic background), then the combination of the slide reduction algorithms [ALNS20] and Pouly-Shen 's algorithm [PoSh24] yields exponentially faster provably correct algorithms for $\delta$-approximate SVP for all approximation factors $n^{1/2+\epsilon }\le \delta \le n^{O(1)}$, which is the regime most relevant for cryptography.