# 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 '16 at 10:13
• It was from my lecture notes, but it's functionally equivalent to that of Katz/Lindell's Intro to Modern Crypto.. – Aggressive Sneeze. Jan 28 '16 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. – Aggressive Sneeze. Jan 28 '16 at 10:35
• It outputs 1 when it thinks its input was produced by G, and 0 when it thinks it's truly random. – fkraiem Jan 28 '16 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. – fkraiem Jan 28 '16 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).
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)|$$.