# Existence of PRF $\implies$ existence of PRG

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

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.

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