Asymptotic runtime analysis of DeepLLL

Join a Cyber Security Seminar at the University of Essex exploring the runtime analysis of DeepLLL, a lattice reduction algorithm used in modern cryptography. The talk will be delivered by Sajay Bhattacherjee (University of Kent).

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' 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 joint work with Jack Moyler, who recently completed his PhD.