1
$\begingroup$

In Introduction to Modern Cryptography by Katz and Lindell, p. 70, they define a pseudorandom generator by:

Let $l(\cdot)$ be a polynomial and let $G$ be a deterministic poly-time alg. s.t. for any input $s \in \{0,1\}^n,$ algo $G$ outputs a string of length $l(n).$ We say $G$ is a pseudorandom generator if the following conditions hold:

(Expansion) For every $n$ we have $l(n)>n$

(Pseudorandomness) For all probabilistic poly-time distinguishers $D,$ there exists a negligible function $negl$ s.t. $$\left| P[D(r)=1] - P[D(G(s))=1] \le negl(n) \right|,$$ where $r$ is chosen unif. at random from $\{0,1\}^{l(n)}, $ the seed $s$ is chosen unif. at random from $\{0,1\}^n,$ and the probabilities are taken over the random coins used by $D$ and the choice of $r$ and $s.$

I would like to clarify how we should be thinking about the distinguisher, $D$. I understand that it is typically any polynomial-time algorithm, but how do we interpret its output? Do we assume that when $D$ "thinks" its input is truly random then it outputs a $1$, and otherwise outputs a $0$?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Actually, if you look at the above definition, it doesn't matter if $D$ is more likely to produce a 1 if given a random function, or if it tends to produce a 0; the important thing is that it acts differently between the two cases... $\endgroup$
    – poncho
    Commented Sep 28, 2017 at 16:27
  • 2
    $\begingroup$ Note it's not "any polynomial-time algorithm" as you paraphrase it, it's the larger set of probabilistic polynomial-time algorithms—programs that run on a machine that, in addition to the usual Turing-complete machinery, also has an operation to generate random bits (the "random coins" of the definition) and read them into program memory so they can influence the execution and result of the programs. $\endgroup$
    – Luis Casillas
    Commented Sep 28, 2017 at 17:10

1 Answer 1

Reset to default
6
$\begingroup$

I think of it this way: think of a distinguisher as an adversarially-chosen statistical experiment that attempts to support or refute some hypothesis, that again is adversarially selected. This means that the honest party doesn't get to assume what meaning the adversary assigns to $0$ or $1$; their PRG has to behave like a random distribution no matter what the adversary does (with the proviso that the adversary's experiment must complete within polynomial time).

For example, a distinguisher could be an algorithm that takes the output of the PRG, chooses a random position in the bit string, tests whether the bits starting from this location are equal to some ASCII representation of the Gettysburg Address, and outputs $0$ if they are, $1$ otherwise. If that's the statistical test the adversary wants to use, they can do it.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This clarifies things a bit, but to try to clarify my confusion a bit: Katz and Lindell don't actually specify what the range of a distinguisher is, do they? The above definition allows us to conclude that the value $1$ should be in the range, but as to what $D$ does when it doesn't output $1$, well that doesn't really matter? A perfectly valid distinguisher can output $1$ when it wants to indicate "RANDOM!" and $19283498$ otherwise? $\endgroup$
    – theQman
    Commented Sep 29, 2017 at 1:14
  • $\begingroup$ @theQman: Huh, looking at my 2nd Edition copy I can't find a definition of the range of a distinguisher either, at least not in the vicinity. But note that $D(r) = 1$ and $D(G(s)) = 1$ are truth-valued functions of $r$ and $s$ respectively, so whatever the range of $D$, the definition is implicitly injecting it into a two-element set. $\endgroup$
    – Luis Casillas
    Commented Sep 29, 2017 at 18:49

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.