2
$\begingroup$

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?

|improve this question
$\endgroup$
  • $\begingroup$ just saw it and it doesn't answer my question. $\endgroup$ – Baby desta Mar 3 at 0:03
4
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\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 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 at 0:57
  • $\begingroup$ For such a high block count, aren't we slowly leaving the realm of efficient distinguishers? $\endgroup$ – Marc Ilunga Mar 3 at 1:09
  • $\begingroup$ I should also mention that $m > k$ $\endgroup$ – Marc Ilunga Mar 3 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$ – Marc Ilunga Mar 3 at 1:23

Your Answer

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

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