TIME: 1:30-2:20 pm,  May 2, 2006

PLACE: CSE 403

TITLE: Spectra analysis of Pollard Rho Collisions

SPEAKER:  Ramarathnam Venkatesan
          Microsoft Research

ABSTRACT:
We show that the classical Pollard Rho algorithm for discrete logarithms
produces a collision in expected time O(\sqrt{n}(log n)^3).
This is the first nontrivial rigorous estimate for the collision probability
for the unaltered Pollard Rho graph, and is close to the conjectured optimal
bound of O(sqrt{n}). The result is derived by showing that the mixing
time for the random walk on this graph is O((log n)^3); without the squaring
step in the Pollard Rho algorithm, the mixing time would be exponential
in log n. The technique involves a spectral analysis of directed graphs,
which captures the effect of the squaring step.

The graph's generalizations are suitable for stream cipher for
constructions and in fact our analysis originated there.

A mini survey of discrete log, cayley/expander graphs, and characters on
abelian groups will be included.


Joint work with Stephen Miller.
Paper at http://www.math.rutgers.edu/~sdmiller/