AG Diskrete Mathematik und Mathematische Informatik
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
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.