ACAC Seminar Abstract

ACAC Seminar Abstract

ACAC Seminars

ACAC Seminar Abstract

Strong Lattice Reduction: New Upper and Lower Bounds

Speaker: Damien Stehlé (joint work with G. Hanrot)
Date, Time: Fri, 11 Jan 2008 15:00

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.

Back to the top of this page