Type: Seminar

Distribution: World

Expiry: 18 Jan 2007

Auth: billu@galois.maths.usyd.edu.au

Speaker: Damien Stehle Title: Lattice Point Enumeration Revisited Time & Place: 3-4pm, Thursday 18 January, Carslaw 535 Abstract: Lattice point enumeration is the basis of the best known algorithm to solve exactly the shortest vector problem. This is also the time-consuming part of Schnorr’s block-based lattice reductions, that are very famous in the cryptography community. This enumeration algorithm, known as Fincke-Pohst algorithm for number theorists and Kannan’s algorithm for cryptographers, has a d^{d/2 +o(d)} complexity, where d is the lattice dimension. This upper bound was proved by Hellfrich more than 20 years ago. In this talk, I will show that this analysis is far from being tight, and describe the proof of an improved upper bound.