SMS scnews item created by Bill Unger at Mon 15 Jan 2007 1638
Type: Seminar
Distribution: World
Expiry: 18 Jan 2007
Calendar1: 18 Jan 2007 1500-1600
CalLoc1: Carslaw 535
Auth: billu@galois.maths.usyd.edu.au

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.


If you are registered you may mark the scnews item as read.
School members may try to .