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 |

- Efficient Hashing using the AES Instruction Set
- On the Security of 1024-bit RSA and 160-bit Elliptic Curve Cryptography
- Private Predictive Analysis on Encrypted Medical Data

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