A Birthday Paradox for Markov Chains, with an Optimal Bound for Collision in the Pollard Rho Algorithm for Discrete Logarithm

摘要

We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group G and find that, if the partition in the algorithm is given by a random oracle, then with high probability a collision occurs in Θ(|G|~(1/2)) steps. This is the first proof of the correct bound which does not assume that every step of the algorithm produces an i.i.d. sample from G.