Skip to Main content Skip to Navigation
Conference papers

Slide Reduction, Revisited—Filling the Gaps in SVP Approximation

Abstract : We show how to generalize Gama and Nguyen's slide reduction algorithm [STOC '08] for solving the approximate Shortest Vector Problem over lattices (SVP) to allow for arbitrary block sizes, rather than just block sizes that divide the rank n of the lattice. This leads to significantly better running times for most approximation factors. We accomplish this by combining slide reduction with the DBKZ algorithm of Micciancio and Walter [Eurocrypt '16]. We also show a different algorithm that works when the block size is quite large-at least half the total rank. This yields the first non-trivial algorithm for sublinear approximation factors. Together with some additional optimizations, these results yield significantly faster provably correct algorithms for δ-approximate SVP for all approximation factors n 1/2+ε ≤ δ ≤ n O(1) , which is the regime most relevant for cryptography. For the specific values of δ = n 1−ε and δ = n 2−ε , we improve the exponent in the running time by a factor of 2 and a factor of 1.5 respectively.
Document type :
Conference papers
Complete list of metadata
Contributor : Phong Q. Nguyen Connect in order to contact the contributor
Submitted on : Tuesday, December 15, 2020 - 3:32:44 PM
Last modification on : Friday, January 21, 2022 - 3:16:44 AM
Long-term archiving on: : Tuesday, March 16, 2021 - 7:55:37 PM


Slide reduction from ALNS.pdf
Files produced by the author(s)




Divesh Aggarwal, Jianwei Li, Phong Nguyen, Noah Stephens-Davidowitz. Slide Reduction, Revisited—Filling the Gaps in SVP Approximation. CRYPTO 2020 - 40th Annual International Cryptology Conference, Aug 2020, Santa Barbara / Virtual, United States. pp.274-295, ⟨10.1007/978-3-030-56880-1_10⟩. ⟨hal-03068203⟩



Les métriques sont temporairement indisponibles