Abstract: Grids and cryptography are connected in two ways. On the one hand grid problems can be used to design cryptographic methods. On the other hand the LLL-algorithm for computing the shortest vector in a grid is one of the most important tools in the cryptoanalysis of many cryptographic methods. In the talk we will elaborate on both aspects. We will consider the complexity of computing the successive minima of a grid. This problem is the basis of an encryption method suggested by Ajtai some years ago. The average complexity of Ajtai's method corresponds to the worst-case complexity of computing the last successive minimum of a grid. In the second part of the lecture we will explain how the LLL-algorithm can be used to crack certain variants of the RSA-algorithm.
Colloquium - 16:00
Abstract: Motion planning with non-holonomic constraints, such as the restriction on the radius of curvature natural for car-like robots, is of considerable practical interest, but even simple theoretical questions turn out to be quite hard. We discuss some fundamental results on bounded curvature paths that can be applied to robot motion planning. In particular, we characterize the region of all points inside a convex polygon that can be reached by a bounded-curvature robot from a given starting configuration. We also show that no robot can effectively visit a sequence of points that are given on-line (that is, one by one) using a bounded curvature path, while giving an algorithm to compute a short path if the whole sequence is given in advance.
(Joint work with Hee-kap Ahn, Kyung-Yong Chwa, Jae-Ha Lee, Jiri Matousek, Woo-Cheol Kwon, Sung-Yong Shin, and Antoine Vigneron)