Abstract
A module lattice is a lattice with an extra algebraic structure that can be used to improve the efficiency of cryptographic constructions. This algebraic structure can also be used to view the module lattice as a lattice of small dimension over a ring R, rather than a lattice of large dimension over the integers ZZ. The LLL algorithm is a fundamental algorithm that allows us to solve in polynomial time the approximate shortest vector problem in a lattice over ZZ, with an approximation factor exponential in the dimension of the lattice. In this talk, I will describe an LLL algorithm for lattices over rings R rather than ZZ. This algorithm can be applied to module lattices in order to solve the shortest vector problem with an approximation factor exponential in the rank of the module, rather than its dimension over ZZ. The run time of this LLL algorithm over R in polynomial provided that we have an oracle solving the closest vector problem (CVP) in a fixed lattice depending only on the ring R (note that solving CVP is usually hard, and we do not know how to instantiate this oracle in practice to obtain an algorithm with a reasonable run time). This is a joint work with Changmin Lee, Damien Stehlé and Alexandre Wallet