On birthday attacks and catching kangaroos

摘要

Birthday Attacks and other Monte Carlo methods are popular approaches to breaking cryptographic schemes. While it is not hard to give heuristic arguments justifying these methods, until recently little had been shown rigorously. In this talk we discuss the first proofs of the efficiency of two such attacks, Pollard's Rho and Pollard's Kangaroo methods for Discrete Logarithm, the former related to the well known Birthday Paradox and the latter to the lesser known Kruskal Count.