Séminaire de Cryptographie

Accueil     Présentation     Archives

Andy Novocin

L1 a new quasi-linear LLL algorithm

The LLL lattice reduction algorithm of 1982 has proven to be useful in a wide variety of fields. It can be used to approximately solve computationally difficult lattice-based problems, such as the shortest vector problem, in polynomial time. We present a new algorithm for lattice reduction which is the first algorithm to have a complexity bound which is both polynomial and quasi-linear bound in the bit-length of the input. To achieve this we present an independently interesting toolkit for analyzing incremental lattice reductions.