How long does it take to catch a wild kangaroo?

DOI10.1145/1536414.1536490MaRDI QIDQ5172750zbMATH OpenOpenAlexFDO

Authors Ravi Montenegro, Prasad Tetali

Publication date 4 February 2015

Published in Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

digital signaturediscrete logarithmMarkov chainmixing timePollard's kangaroo method

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Authentication, digital signatures and secret sharing (94A62)

Abstract: We develop probabilistic tools for upper and lower bounding the expected time until two independent random walks on $$ intersect each other. This leads to the first sharp analysis of a non-trivial Birthday attack, proving that Pollard's Kangaroo method solves the discrete logarithm problem $g^x=h$ on a cyclic group in expected time $(2+o(1))sqrtb-a$ for an average $xi{n}_{uar}[a,b]$. Our methods also resolve a conjecture of Pollard's, by showing that the same bound holds when step sizes are generalized from powers of 2 to powers of any fixed $n$.

Recommendations

• Kangaroos, monopoly and discrete logarithms
• Solving discrete logarithm problem in an interval using periodic iterates
• Computing discrete logarithms with the parallelized kangaroo method.
• The parallelized Pollard kangaroo method in real quadratic function fields
• Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval

Cited in

(6)

• Kangaroos, monopoly and discrete logarithms
• Computing low-weight discrete logarithms
• Computing discrete logarithms in an interval
• Removing erasures with explainable hash proof systems
• $$\mathsf {HIKE}$$ : Walking the Privacy Trail
• Recent progress on the elliptic curve discrete logarithm problem

This page was built for publication: How long does it take to catch a wild kangaroo?

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