# Understanding the distinguisher for a PRG

Given the following definition of a psuedorandom generator, I'm having trouble understanding what exactly the "distinguisher" D is outputting, and when?

• Please cite the source of the definition you included.
– otus
Jan 28, 2016 at 10:13
• It was from my lecture notes, but it's functionally equivalent to that of Katz/Lindell's Intro to Modern Crypto.. Jan 28, 2016 at 10:31
• I know the practical point of psuedorandomness is the notion that the distinguisher can only negligibly tell the difference between a psuedorandom function and truly random function, but I'm interested in knowing the output parameters of G itself. Jan 28, 2016 at 10:35
• It outputs 1 when it thinks its input was produced by G, and 0 when it thinks it's truly random. Jan 28, 2016 at 10:41
• What do you mean by "the output parameters of G", by the way? The output of $G$ is a string, as is the output of any algorithm, and this string has length $\ell(n)$, where $n$ is the length of the input. Jan 28, 2016 at 11:28

$D$ outputs a bit $b \in \lbrace 0,1 \rbrace$. When $b = 0$, it means that $D$ is guessing that the string it has been given was drawn uniformily at random from $\lbrace 0 , 1 \rbrace^{\ell(n)}$, while when $b = 1$, it means that $D$ believes the string it has been given was produced by the PRG $G$ (or vice versa).

As said before, the distinguisher D outputs a bit.

I would like to add that the advantage is a measurement for how good the distinguisher is doing. Say you have two distributions which are computationally indistinguishable, then $adv_D$ is negligigle close to 0. On the other hand, if the two distributions are easy to distinguish, then $adv_D$ would be close to 1.

On your formula, the advantage of D is: $$adv_D = |Pr(D(X)=1) - Pr(D(Y)=1)|$$.

If the distributions are indistinguishable, a distinguisher cannot succeed on doing its job, i.e. distinguishing the two distributions. Then, the output of D is the same regardless of having distribution X or distribution Y as input.

If you need further reading I strongly recommend you having a look at the paper "On the Role of Definitions in and Beyond Cryptography", by Rogaway. There he explains clearly the concept of distinguisher.

• +1 from me after reading the "On the Role of Definitions in and Beyond Cryptography" paper. Clearly written and only 20 pages. U can find it: web.cs.ucdavis.edu/~rogaway/papers/def.pdf Dec 28, 2018 at 13:01