Cryptology ePrint Archive: Report 2020/1409

The Convergence of Slide-type Reductions

Michael Walter

Abstract: In this work we apply the dynamical systems analysis of Hanrot et al. (CRYPTO'11) to a class of lattice block reduction algorithms that includes (natural variants of) slide reduction and block-Rankin reduction. This implies sharper bounds on the polynomial running times (in the query model) for these algorithms and opens the door to faster practical variants of slide reduction. We give heuristic arguments showing that such variants can indeed speed up slide reduction significantly in practice. This is confirmed by experimental evidence, which also shows that our variants are competitive with state-of-the-art reduction algorithms.

Category / Keywords: lattice block reduction, slide reduction

Original Publication (in the same form): IACR-PKC-2021

Date: received 12 Nov 2020, last revised 25 Feb 2021

Contact author: mwalter at ist ac at

Available format(s): PDF | BibTeX Citation

Note: Revised version as submitted as camera-ready to PKC'21.

Version: 20210225:095658 (All versions of this report)

Short URL: ia.cr/2020/1409