Place : LIX, Salle Philippe Flajolet
Title: An LLL Algorithm for Module Lattices
Abstract: A lattice is a discrete subgroup (i.e., ZZ-module) of RR^n (where ZZ and RR are the sets of integers and real numbers). The LLL algorithm is a central algorithm to manipulate lattice bases. It takes as input a basis of a Euclidean lattice, and, within a polynomial number of operations, it outputs another basis of the same lattice but consisting of rather short vectors. Lattices are used in post-quantum cryptography, as finding a shortest vector of a lattice, given an arbitrary basis, is supposed to be intractable even with a quantum computer. For practical reasons, many constructions based on lattices use structured lattices, in order to improve the efficiency of the schemes. Most of the time, these structured lattices are R-modules of small rank, where R is the ring of integers of some number field. As an example, 11 schemes among the 12 lattice-based candidates for the NIST post-quantum standardization process use module lattices, with modules of small rank. It is then tempting to try and adapt the LLL algorithm, which works over lattices (i.e., ZZ-modules), to these R-modules, as this would allow us to find rather short vectors of these module lattices. Previous works trying to extend the LLL algorithm to other rings of integers R focused on rings R that were Euclidean, as the LLL algorithm over ZZ crucially relies on the Euclidean division. In this talk, I will describe an LLL algorithm which works in any ring of integers R. This algorithm is heuristic and runs in quantum polynomial time if given access to an oracle solving the closest vector problem in a fixed lattice, depending only on the ring of integers R. This is a joint work with Changmin Lee, Damien Stehlé and Alexandre Wallet
