February 25, 2025, Tuesday. 4PM. Room TG23.
Speaker: Sanjay Bhattacherjee (University of Kent)
Title: New results on lattice reduction algorithms
Abstract: A lattice is a discrete subgroup of ℝ^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. In this talk, we look at some new results around DeepLLL. The talk is based on a joint work with Jack Moyler.
Biography: Sanjay Bhattacherjee works as a Lecturer at the University of Kent, UK. He works on the design, analysis and implementations of algorithms, primarily in cryptology and game theory. His research papers are available at: https://sites.google.com/site/sanjaybhattacherjee/research