Paper 2012/087

Collision Bounds for the Additive Pollard Rho Algorithm for Solving Discrete Logarithms

Joppe W. Bos, Alina Dudeanu, and Dimitar Jetchev

Abstract

We prove collision bounds for the Pollard rho algorithm to solve the discrete logarithm problem in a general cyclic group $G$. Unlike the setting studied by Kim et al. we consider additive walks: the setting used in practice to solve the elliptic curve discrete logarithm problem. Our bounds differ from the birthday bound $O(\sqrt{|G|})$ by a factor of $\sqrt{\log{|G|}}$ and are based on mixing time estimates for random walks on finite abelian groups due to Hildebrand.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Pollard rhoadditive walkcollision boundrandom walkmixing times
Contact author(s)
joppe bos @ epfl ch
History
2012-02-23: received
Short URL
https://ia.cr/2012/087
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/087,
      author = {Joppe W.  Bos and Alina Dudeanu and Dimitar Jetchev},
      title = {Collision Bounds for the Additive Pollard Rho Algorithm for Solving Discrete Logarithms},
      howpublished = {Cryptology ePrint Archive, Paper 2012/087},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/087}},
      url = {https://eprint.iacr.org/2012/087}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.