AG Diskrete Mathematik und Mathematische Informatik

AG Diskrete Mathematik und Mathematische Informatik
Summer 2007

Prof. Dr. C.-P. Schnorr, Prof. Dr. T. Theobald
R. Hartung, C. Riener, A. Scemama, R. Steffens

Improving the analysis of Kannan's SVP algorithm

Lecture by Damien Stehlé, CNRS, ENS Lyon,
11. 05. 07, 14 ct, Raum 612

Abtract:

The shortest Euclidean lattice vector problem is NP-hard under randomised reductions. Several cryptosystems 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, is Kannan's enumeration algorithm. We improve its complexity upper bound, and generalise our analysis to other hard problems on lattices.

Joint work with Guillaume Hanrot.

AG Home