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

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

In  Journal of Mathematical Cryptology

Publisher  de Gruyter

Details

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