Computational Algebra Seminar: Stehle -- Lattice Point Enumeration Revisited

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.