3
$\begingroup$

Let $F:\{0,1\}^n\times \{0,1\}^m \to \{0,1\}^l$ be a PRF. I want to show that $G(-)=F(-,x_0)$ is a PRG for every $x_0\in \{0,1\}^m$.

Proof attempt:

Let $D$ be an efficient distinguisher against $G$ in the PRG experiment (see below). We aim to show that $D$ has negligible advantage.

Consider the following efficient distinguisher $D'$ in the PRF experiment. Given access to a function $\mathcal O$ which is either a random function $\{0,1\}^m\to \{0,1\}^l$ or $F_k$, then $D'$ outputs precisely the accept/reject choice of $D$ on the string $\mathcal O(x_0)$.

By construction $D'$ wins if and only if $D$ accepts. By assumptions, since $F$ is a PRF, the former event has probability bounded above by $\frac{1}{2} + \text{negl}(n)$ for some negligible $\text{negl}$, and hence the same is true for the latter event.

My questions:

  1. Is the proof correct?
  2. Is the level of rigor sufficient?

Additional information: Here are the two experiments I was referring to (taken from Katz/Lindell).

enter image description here

enter image description here

$\endgroup$
  • $\begingroup$ What do you mean by "the accept/reject choice of $D$"? $\endgroup$ – fkraiem Sep 23 '17 at 8:41
  • $\begingroup$ I just mean the output of $D$ @fkraiem $\endgroup$ – CRYPTONEWBIE Sep 23 '17 at 8:43
  • $\begingroup$ Then that is clearly not correct $\endgroup$ – fkraiem Sep 23 '17 at 8:44
  • $\begingroup$ What is not correct, @fkraiem? Could you elaborate? $\endgroup$ – CRYPTONEWBIE Sep 23 '17 at 8:48
  • $\begingroup$ It is not correct that $D'$ wins if and only if $D$ outputs $1$. $\endgroup$ – fkraiem Sep 23 '17 at 9:22
3
$\begingroup$

Your proof did not convince me at first.

Given access to a function $\mathcal O$ which is either a random function $\{0,1\}^m\to \{0,1\}^l$ or $F_k$, then $D'$ outputs precisely the accept/reject choice of $D$ on the string $\mathcal O(x_0)$.

The word "then" threw me off. The output of $D'$ is not a consequence of the first clause. I'd reword this to explicitly state that we're constructing a $D'$ that uses $D$ in a particular way. This may seem silly, but this did make me do a double take.

By construction $D'$ wins if and only if $D$ accepts. By assumptions, since $F$ is a PRF, the former event has probability bounded above by $\frac{1}{2} + \text{negl}(n)$ for some negligible $\text{negl}$, and hence the same is true for the latter event.

The first sentence isn't true. In the PRG game, sometimes $D$ will actually be given a random string instead of $G(s)$, and in those cases, $D$ should reject the input, not accept it, to win. Perhaps you mean $D'$ wins if and only if $D$ wins?

Furthermore, there isn't really a justification (even a sketch of one) given. The reader needs to work out the details of $\mathcal{O}(x_0)$ on his own to even understand the argument; that's its failing. A proof's correctness is only half the battle: it must also convince the reader of its correctness, which can be far harder.

Why is it the case that $D' = D(\mathcal{O}(x_0))$ is a distinguisher for $F$, and thus must have negligible advantage? That is the meat of the proof -- which you've omitted.


I think a proof by contradiction is easier to understand. Let's also try to be explicit in our reasoning.

We're given a PRF $F_k$ and we want to show $G(s) = F_s(x_0)$, where $x_0$ is a fixed constant in $\{0,1\}^m$, is a PRG.

Assume (toward a contradiction) that $G$ is not a PRG, so there exists an efficient distinguisher $D$ with non-negligible advantage in the PRG indistinguishability game for $G$.

We will build an efficient distinguisher $D'$ in the PRF experiment using $D$. In that experiment, $D'$ will be given either:

  • a uniform function $\mathcal{O} \in \mathsf{Func}_m$, or
  • the function $\mathcal{O}(x) = F_k(x)$ where $k$ is a uniform string in $\{0,1\}^n$

Conveniently, if we evaluate $\mathcal{O}(x_0)$, we get either

  • a uniform value in $\{0,1\}^m$, by definition of $\mathcal{O} \in \mathsf{Func}_m$, or
  • the value $F_k(x_0) = G(k)$

Notice that the possible values of $\mathcal{O}(x_0)$ exactly match the parameters of the PRG indistinguishability game for $G$. As a result, $D$ can distinguish between the two above situations with non-negligible advantage, since we assumed $G$ is not a PRG.

Therefore, if we let the output of $D'$ be the output of $D$, then $D'$ has non-negligible advantage in the PRF game for $F_k$. This violates our assumption that $F_k$ is a PRF. Therefore, our original assumption that $G$ is not a PRG must be false, i.e., $G$ must be a PRG.


The above proof may not be as rigorous as some would like, but I think it's acceptable enough as a brief sketch (and could be filled-in with real mathematical details if necessary).

Notice that I did not really say anything different than your post -- I was just more explicit. I did switch to a proof by contradiction, but that's because when I went to state the conclusion, it ended up sounding like a proof by contradiction anyway.

$\endgroup$
  • $\begingroup$ Thank you for the useful feedback, I appreciate it @Reid $\endgroup$ – CRYPTONEWBIE Sep 24 '17 at 7:00

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.