The shortest Euclidean lattice vector problem is NP-hard under randomised reductions. Several cryptosystems, such as NTRU, rely on weakened variants of this problem. For this reason, it is important to know precisely the complexity of the best algorithms solving it. The more classical one, and the sole being of practical interest so far, is Kannan's enumeration algorithm. We improve its complexity upper bound, and generalise our analysis to other hard problems on lattices. We also obtain a new worst-case complexity lower bound that essentially match the upper bound. The lower bound is obtained by a random generation of particularly bad lattice bases.

Joint work with Guillaume Hanrot.