Improving Convergence and Practicality of Slide-type Reductions

Jianwei Li; Michael Walter

Paper 2023/140

Improving Convergence and Practicality of Slide-type Reductions

Jianwei Li

, Inria and DIENS, PSL

Michael Walter

, Zama, France

Abstract

The best lattice reduction algorithm known in theory for approximating the Shortest Vector Problem (SVP) over lattices is the slide reduction algorithm (STOC '08 & CRYPTO '20). In this paper, we first improve the running time analysis of computing slide-reduced bases based on potential functions. This analysis applies to a generic slide reduction algorithm that includes (natural variants of) slide reduction and block-Rankin reduction (ANTS '14). We then present a rigorous dynamic analysis of generic slide reduction using techniques originally applied to a variant of BKZ (CRYPTO '11). This provides guarantees on the quality of the current lattice basis during execution. This dynamic analysis not only implies sharper convergence for these algorithms to find a short nonzero vector (rather than a fully reduced basis), but also allows to heuristically model/trace the practical behaviour of slide reduction. Interestingly, this dynamic analysis inspires us to introduce a new slide reduction variant with better time/quality trade-offs. This is confirmed by both our experiments and simulation, which also show that our variant is competitive with state-of-the-art reduction algorithms. To the best of our knowledge, this work is the first attempt of improving the practical performance of slide reduction beyond speeding up the SVP oracle.

Note: This work was accepted by Information and Computation.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Information and Computation
Keywords: Lattice Reduction Slide Reduction (H)SVP Dynamical Systems Gaussian Heuristic
Contact author(s): lijianweisk @ sina com
michael walter @ zama ai
History: 2023-02-15: approved; 2023-02-06: received; See all versions
Short URL: https://ia.cr/2023/140
License: CC BY

BibTeX

@misc{cryptoeprint:2023/140,
      author = {Jianwei Li and Michael Walter},
      title = {Improving Convergence and Practicality of Slide-type Reductions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/140},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/140}},
      url = {https://eprint.iacr.org/2023/140}
}