eprint.iacr.org will be offline for approximately an hour
for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between
April 12 and April 14, and some authors have been notified that they need to resubmit their papers.
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
-
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}
}
