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?
$\begingroup$
$\endgroup$
-
$\begingroup$ just saw it and it doesn't answer my question. $\endgroup$ – Baby desta Mar 3 '19 at 0:03
$\begingroup$
$\endgroup$
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 '19 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 '19 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 '19 at 1:09
-
-
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 '19 at 1:23
