International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Slide Reduction, Revisited—Filling the Gaps in SVP Approximation

Authors:
Divesh Aggarwal , National University of Singapore
Jianwei Li , Information Security Group, Royal Holloway, University of London
Phong Nguyen , Inria and DIENS, PSL
Noah Stephens-Davidowitz , MIT
Download:
DOI: 10.1007/978-3-030-56880-1_10 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2020
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 \delta-approximate SVP for all approximation factors n^{1/2+\eps} \leq \delta \leq n^{O(1)}, which is the regime most relevant for cryptography. For the specific values of \delta = n^{1-\eps} and \delta = n^{2-\eps}, we improve the exponent in the running time by a factor of 2 and a factor of 1.5 respectively.
Video from CRYPTO 2020
BibTeX
@inproceedings{crypto-2020-30474,
  title={Slide Reduction, Revisited—Filling the Gaps in SVP Approximation},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-56880-1_10},
  author={Divesh Aggarwal and Jianwei Li and Phong Nguyen and Noah Stephens-Davidowitz},
  year=2020
}