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?
2
-
1$\begingroup$ You want the cheapest possible function that's still good enough. Exponentiation is expensive. $\endgroup$– CodesInChaosCommented 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$– 111Commented Jan 17, 2015 at 11:12
Add a comment
|