The Preprocessing of Lattice Point Enumeration (DLS in Cybersecurity)

17.10,2014, 11:00 – 12:00

2014/10/16 11:00-12:00

Speaker: Michael Walter, University of California, San Diego | Location: Hochschulstraße 10 (S2|02), Piloty Building, Room B002, Darmstadt

Organizer: CROSSING, Prof. J. Buchmann

Abstract

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.

Short Bio

Website of Michael Walter.