You are looking at a specific version 20201115:072829 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
lattice block reductionslide reduction
Contact author(s)
mwalter @ ist ac at
History
2021-04-15: last of 3 revisions
2020-11-15: received
See all versions
Short URL
https://ia.cr/2020/1409
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.