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

Joppe W. Bos, Alina Dudeanu, and Dimitar Jetchev

January 2014

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 Dou and Hildebrand.

See also: http://eprint.iacr.org/2012/087 and http://www.degruyter.com/view/j/jmc.2014.8.issue-1/jmc-2012-0032/jmc-2012-0032.xml

Publication type | Article |

Published in | Journal of Mathematical Cryptology |

Publisher | de Gruyter |

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