# Pollard Rho pseudorandom function

In Pollard Rho's Algorithm, a function $$f$$ with pseudorandom properties is required. Through this property, the birthday paradox can be leveraged to find a collision. But not all functions are pseudorandom. I am trying to understand what makes a function a good pseudorandom function.

Consider the following sample functions

$$f(x)=a x+b \bmod N, a, b \in \mathbb{Z}_{N}$$

$$f(x)=x^{2}-2 \bmod N$$

$$f(x)=x^{2} \bmod N$$

How can i show that these functions are not good pseudorandom functions?

In general a function $$F:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$$ is a PRF, if you can not distinguish it from a real random function. For that you can play a game with an adversary. The adversary get eather a real random function or your random function. If the adversary can distinguish these functions better than with negigible probability, the function is not pseudorandom. If he can't distinguish them that good, the function is pseudorandom. In Katz & Lindell's textbook (2nd edition) on page 448ff you can find more about this. But for a PRF you need to arguments and I don't see, that your functions are defined over two.
In your case: For your first function I can't tell weather it is a PRG or not, because I don't know more about $$a$$ and $$b$$. For the rest you can build an adversary, if N is known, that can distinguish them pretty easily. If you want to learn how to write a correct proof for that, you should definitely look into Katz & Lindell's textbook (2nd edition) or Katz & Lindell's textbook (3nd edition).
• Be aware that this might be quite an HW problem. The $f$'s are clearly functions, not permutations. May 22, 2021 at 8:24