3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ You want the cheapest possible function that's still good enough. Exponentiation is expensive. $\endgroup$ – CodesInChaos Jan 16 '15 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 '15 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.