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.
Note: Included doi in copyright footnote.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published by the IACR in PKC 2021
- DOI
- 10.1007/978-3-030-75245-3_3
- 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
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1409,
author = {Michael Walter},
title = {The Convergence of Slide-type Reductions},
howpublished = {Cryptology ePrint Archive, Paper 2020/1409},
year = {2020},
doi = {10.1007/978-3-030-75245-3_3},
note = {\url{https://eprint.iacr.org/2020/1409}},
url = {https://eprint.iacr.org/2020/1409}
}
