The Convergence of Slide-type Reductions

We analyze a new trade-off between the running time and output quality of slide reduction. We show that exploiting this trade-off can be favorable in practice and yields variants that are competitive with state-of-the-art reduction algorithms.  Since slide reduction offers some straight-forward parallelization, this could allow larger scale lattice reduction attacks in practice. As a side result we obtain sharper bounds on the polynomial running time (in the query model) for slide reduction and its generalization, block-Rankin reduction.