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?


1 Answer 1


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.

Therefore I think you mean pseudorandom generator PRG instead of PRF. For the game with the PRG an adversary only gets two strings and he has to distinguish a real random string from a string that was constructed by the PRG. If he can distinguish them better than with negigible probability, the PRG is not pseudorandom. If he can't, it is pseudorandom.

For both games you don't look at one case, but for all cases. So if the adversary can find a strategy to only distinguish 1% correctly, he "won" the game and the PRF or PRG is not pseudorandom.

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).

In general: Easy mathematical function like linear or quadratic functions are no good PRG in general. Even logistic functions aren't. For beginners in cryptographie and learning abouot PRG you mainly assume you got a PRF and then build another based on it and then proof is using reduction. In practise you can use a hash-function as a PRG.

  • 1
    $\begingroup$ Be aware that this might be quite an HW problem. The $f$'s are clearly functions, not permutations. $\endgroup$
    – kelalaka
    May 22, 2021 at 8:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.