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 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

Details

Publication typeArticle
Published inJournal of Mathematical Cryptology
Publisherde Gruyter
> Publications > Collision Bounds for the Additive Pollard Rho Algorithm for Solving Discrete Logarithms