0
$\begingroup$

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

defo

$\endgroup$
  • $\begingroup$ Please cite the source of the definition you included. $\endgroup$ – otus Jan 28 '16 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 '16 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 '16 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$ – fkraiem Jan 28 '16 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$ – fkraiem Jan 28 '16 at 11:28
0
$\begingroup$

$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).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.