Asymptotic runtime analysis of DeepLLL

Title of the Talk: Asymptotic runtime analysis of DeepLLL
Speakers: Dr. Sanjay Bhattacherjee
Host Faculty: Dr.M V Panduranga Rao
Date: Dec 22, 2025
Time: 10:30 pm.
Venue: CS-105

Abstract: A lattice is a discrete subgroup of \mathbb{R}^m – a set of all integer linear combinations of linearly independent vectors, called its basis. A lattice has infinitely many bases. A lattice reduction algorithm transforms an input basis into one that has shorter and more orthogonal vectors. (Finding the shortest non-zero vector in a lattice is NP-hard.) It is a fundamental cryptanalytic tool for lattice-based post-quantum cryptology, with wider applications as well. DeepLLL and BKZ are lattice reduction algorithms that were proposed simultaneously in 1994. They are strong lattice reduction algorithms that provide much shorter vectors (better approximations) than the legacy LLL algorithm, while being significantly slower. BKZ has been well studied and improved upon, emerging as the de facto lattice reduction algorithm for cryptanalysis. However, the runtime of BKZ remains exponential in its blocksize. DeepLLL, on the other hand, has received much less attention. There is no theoretical analysis of its runtime which is largely believed to be super-polynomial over the last 30 years. In this talk, we explore a new technique for the first runtime analysis of DeepLLL. It is based on a joint work with my PhD student Jack Moyler.

Meeting link: https://meet.google.com/ubn-xwkh-ztj