I tried to look for a book that presents cryptographic concepts(specially PRNG) in a formal way but what I find is an intuitive approach. So my question is what is the formal definition of Psuedo-random-number-generator(PRNG) or function?


1 Answer 1


If we call $U_k$ the random variable uniformly distributed over bit strings of length $k$, then a function $g: \{0,1\}^k \to \{0,1\}^m$ is called pseudo-random generator if no feasible(poly-time if you want) algorithm can distinguish $g(U_k)$ and $U_m$ with non-negligible probability.

More formally let $U'_m = g(U_k)$ then the distinguishing advantage of any distinguisher efficient $D$ that we denote as $\Delta^D(U'_m, U_m) = Pr^{DU_m}[Z = 1] - Pr^{DU'_m}[Z = 1]$ is negligible.

Here $Z$ is the output of the distinguisher, and negligible is any suitable notion of "really small"; same for efficient.

  • $\begingroup$ Yet practically $k < \infty$, so when $m = k$, $g$ either stops or repeats and thus $Z \rightarrow 1$. And $k$ might only be 32 which isn't a lot at all. $\endgroup$
    – Paul Uszak
    Mar 3, 2019 at 0:55
  • $\begingroup$ And, AES-CTR is considered a good PRNG. Yet as the block count tends to $2^{128}$, $Z \rightarrow 1$ again as the p value for non repeated blocks in a perfectly random sequence tends to zero. $\endgroup$
    – Paul Uszak
    Mar 3, 2019 at 0:57
  • $\begingroup$ For such a high block count, aren't we slowly leaving the realm of efficient distinguishers? $\endgroup$ Mar 3, 2019 at 1:09
  • $\begingroup$ I should also mention that $m > k$ $\endgroup$ Mar 3, 2019 at 1:13
  • 3
    $\begingroup$ I still can't understand the repetition/stop issue. I should probably not doing crypto late at night but.... Given that $g$ is supposed to be called every time with input from hopefully the uniform distribution or a chunk of it's previous output, we don't really need to make a state explicit. $\endgroup$ Mar 3, 2019 at 1:23

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.