Collision times in multicolor urn models and sequential graph coloring with applications to discrete logarithms

DOI10.1214/16-AAP1176zbMATH Open1356.05045arXiv1311.4243MaRDI QIDQ511468FDOQ511468

Bhaswar B. Bhattacharya

Publication date: 21 February 2017

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1311.4243

Recommendations

• A non-uniform birthday problem with applications to discrete logarithms
• Collision of random walks and a refined analysis of attacks on the discrete logarithm problem
• A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm
• The number of collisions for the occupancy problem with unequal probabilities
• A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm

zbMATH Keywords

graph coloringdiscrete logarithmlimit theoremsPoisson embedding

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Central limit and other weak theorems (60F05) Coloring of graphs and hypergraphs (05C15) Authentication, digital signatures and secret sharing (94A62)

Cited In (3)

• A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs
• Monochromatic subgraphs in randomly colored graphons
• Normal approximation and fourth moment theorems for monochromatic triangles

This page was built for publication: Collision times in multicolor urn models and sequential graph coloring with applications to discrete logarithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511468)