Collision Times in Multicolor Urn Models and Sequential Graph Coloring With Applications to Discrete Logarithms
This work provides theoretical foundations for analyzing collision times in probabilistic models, with applications to improving algorithms for discrete logarithms in cryptography, though it is incremental by extending previous results from expected to distributional analysis.
The paper tackles the problem of determining the distribution of first collision times in multicolor urn models and sequential graph coloring, using a Poisson embedding technique to derive limiting distributions. The results are applied to obtain asymptotic running time distributions for birthday problem-based algorithms solving the discrete logarithm problem, generalizing prior work that only considered expected times.
Consider an urn model where at each step one of $q$ colors is sampled according to some probability distribution and a ball of that color is placed in an urn. The distribution of assigning balls to urns may depend on the color of the ball. Collisions occur when a ball is placed in an urn which already contains a ball of different color. Equivalently, this can be viewed as sequentially coloring a complete $q$-partite graph wherein a collision corresponds to the appearance of a monochromatic edge. Using a Poisson embedding technique, the limiting distribution of the first collision time is determined and the possible limits are explicitly described. Joint distribution of successive collision times and multi-fold collision times are also derived. The results can be used to obtain the limiting distributions of running times in various birthday problem based algorithms for solving the discrete logarithm problem, generalizing previous results which only consider expected running times. Asymptotic distributions of the time of appearance of a monochromatic edge are also obtained for other graphs.