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:


Is the proof correct?
Is the level of rigor sufficient?


Additional information:
Here are the two experiments I was referring to (taken from Katz/Lindell).
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.