A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm

DOI10.1214/09-AAP625zbMATH Open1195.60096arXiv0712.0220OpenAlexW2051025109WikidataQ123010543 ScholiaQ123010543MaRDI QIDQ968774FDOQ968774

Jeong Han Kim, Yuval Peres, Prasad Tetali, Ravi Montenegro

Publication date: 6 May 2010

Published in: The Annals of Applied Probability, Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: 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 $Theta(sqrt|G|)$ steps. Moreover, for the parallelized distinguished points algorithm on $J$ processors we find that $Theta(sqrt|G|/J)$ steps suffices. These are the first proofs of the correct order bounds which do not assume that every step of the algorithm produces an i.i.d. sample from $G$.

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

Recommendations

• A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm
• On random walks for Pollard's rho method
• Collision of random walks and a refined analysis of attacks on the discrete logarithm problem
• Non-Degeneracy of Pollard Rho Collisions
• Collision bounds for the additive Pollard rho algorithm for solving discrete logarithms

zbMATH Keywords

Markov chaindiscrete logarithmmixing timeself intersectionPollard rhocollision timeBirthday ParadoxPollard's Rho

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16)

Cites Work

• Title not available (Why is that?)
• An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
• Monte Carlo Methods for Index Computation (mod p)
• The range of stable random walks
• A monte carlo method for factorization
• Parallel collision search with cryptanalytic applications
• Random walks arising in random number generation
• Elementary thoughts on discrete logarithms
• Title not available (Why is that?)
• Square-root algorithms for the discrete logarithm problem (a survey)
• Markov chain intersections and the loop-erased walk
• On the Chung-Diaconis-Graham random process
• Title not available (Why is that?)
• Non-Degeneracy of Pollard Rho Collisions
• Algorithmic Number Theory

Cited In (11)

• Algorithmic Number Theory
• Solving discrete logarithm problems faster with the aid of pre-computation
• Recent progress on the elliptic curve discrete logarithm problem
• A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs
• A note on the exponentiation approximation of the birthday paradox
• Accelerating Pollard's rho algorithm on finite fields
• A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm
• Normal approximation and fourth moment theorems for monochromatic triangles
• Rigorous analysis of a randomised number field sieve
• The Second-Moment Phenomenon for Monochromatic Subgraphs
• On a lower bound for the Chung-Diaconis-Graham random process

This page was built for publication: A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm

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