Organizer: CROSSING, Prof. J. Buchmann
When analyzing lattice based cryptosystems, we often need to solve the Shortest Vector Problem (SVP) in some lattice associated to the system under scrutiny. The go-to algorithms in practice to solve SVP are enumeration algorithms, which usually consist of a preprocessing step, followed by an exhaustive search. Obviously, the two steps offer a trade-off and should be balanced in their running time in order to minimize the overall complexity. However, this trade-off has, to the best of our knowledge, never been formally analyzed.
In this talk, we will discuss two recent results regarding this trade-off: First, we will present a new variant of Kannan's algorithm, that allows to fine-tune the preprocessing. Second (and time permitting), we will discuss the impact of block reduction on the exhaustive search. The latter has been common practice for a long time, but lacked any kind of serious analysis up to this point.