Pollard's Rho is usually constructed using a function $f:G \rightarrow G$ which behaves 'random enough' in order to detect a collision with Floyd's cycle detection trick. It is easy enough to observe, however, that a uniformly random distribution on $\mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ induces a uniform random distribution on $G$ via the map $(a,b) \mapsto g^ah^b$ where $g^x=h$ is the DLP we aim to solve. So instead of looking for functions on $G$ which behave uniformly random, we might as well restrict ourselves to 'random' functions on $\mathbb{Z}/n\mathbb{Z}$ and proceed as usual with Floyd and the collision detection. However, as far as I can make out nobody has used this so far; is there something I am missing as to why this does not work, or is it simply not useful enough to be used in practice?

  • 1
    $\begingroup$ You want the cheapest possible function that's still good enough. Exponentiation is expensive. $\endgroup$ Jan 16, 2015 at 20:35
  • 1
    $\begingroup$ This is not new, for instance Teske suggests the use of $f(x)=xg^{m_s}h^{n_s}$ for $m_s,n_s\in M_s$ fos some set $M_s...$ see for instance disco.ethz.ch/publications/sac01.pdf $\endgroup$
    – 111
    Jan 17, 2015 at 11:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.