# Formal definition PRNG

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?

• just saw it and it doesn't answer my question. – Baby desta Mar 3 at 0:03

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.
• 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. – Paul Uszak Mar 3 at 0:55
• 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. – Paul Uszak Mar 3 at 0:57
• I should also mention that $m > k$ – Marc Ilunga Mar 3 at 1:13
• 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. – Marc Ilunga Mar 3 at 1:23