Joppe W. Bos, Alina Dudeanu, and Dimitar Jetchev
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