Speaker:

Ravi Montenegro

Title:

A simple heuristic for precisely determining complexity of many Birthday attacks

Abstract:

Birthday attacks exploit the Birthday Paradox to solve a difficult mathematical problem, such as factoring or discrete logarithm. The complexity is the time until a state has been hit twice, a sort of self-intersection time for Markov chains. Existing heuristics fail to explain differing performance of related attacks, such as a threshold where the walk on certain degree 4 random digraphs (Teske's additive walks) have sub-optimal self-intersection complexity but the degree 5 or more version has optimal order. Drawing on work with Kim, Peres and Tetali, we give a new heuristic which explains these performance differences and is sufficiently sharp that estimates on lead coefficients match experimental data to over 99.7% accuracy.