Spring 2020

The Convergence of Slide-type Reductions

Monday, Jun. 14, 2021 11:00 am11:30 am PDT

Add to Calendar


Michael Walter (IST Austria)



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.