Description
The famous LLL algorithm improves the global quality of a lattice basis by improving it locally on two dimensional blocks until no more progress can be made. The most well-known generalization of LLL to larger blocksizes is BKZ, which has been reported to behave very well in practice, but is cumbersome to analyze both in the average case and in the worst case. On the other hand, the algorithm with the best provable bounds in terms of running time and output quality is slide reduction, a different generalization of LLL, but one which has been reported to be significantly outperformed in practice by BKZ. In this talk, we will consider a third generalization of LLL, Self-Dual BKZ (introduced in eprint.iacr.org/2015/1123), which can be seen as getting the best of both worlds: competitive practical performance and clean and convenient analysis of average case and worst case behavior.