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

2 Answers 2

1
$\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$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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