Given the following definition of a psuedorandom generator, I'm having trouble understanding what exactly the "distinguisher" D is outputting, and when?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Please cite the source of the definition you included. $\endgroup$– otusJan 28, 2016 at 10:13
-
$\begingroup$ It was from my lecture notes, but it's functionally equivalent to that of Katz/Lindell's Intro to Modern Crypto.. $\endgroup$– Aggressive Sneeze.Jan 28, 2016 at 10:31
-
1$\begingroup$ 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. $\endgroup$– Aggressive Sneeze.Jan 28, 2016 at 10:35
-
1$\begingroup$ It outputs 1 when it thinks its input was produced by G, and 0 when it thinks it's truly random. $\endgroup$– fkraiemJan 28, 2016 at 10:41
-
$\begingroup$ 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. $\endgroup$– fkraiemJan 28, 2016 at 11:28
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
$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).
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ +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 $\endgroup$ Dec 28, 2018 at 13:01