Swap $x$ and $k$ in GGM construction

Question

I'm studying the Goldreich-Goldwasser-Micali construction from pseudo-random generators to pseudo-random functions. In this specific construction, assume $G:\{0,1\}^n\rightarrow \{0,1\}^{2n}$ is a PRG, mapping $x$ to $G(x)=(G_0(x),G_1(x))$. Then the PRF in this construction is given by $$F_k(x)=G_{x_n}\circ\cdots\circ G_{x_1}(k),$$ with a random key $k$ in the same length as $x$. The proof is a hybrid argument, by replacing $G_{x_j}\circ\cdots\circ G_{x_1}(k)$ with a truly random function $\{0,1\}^j\rightarrow\{0,1\}^n$.

Now I wonder what if we swap the positions of $x$ and $k$ in this construction, that is to define $$F'_k(x)=G_{k_n}\circ\cdots\circ G_{k_1}(x).$$ Intuitively one cannot use similar hybrid techniques like above to prove its pseudo-randomness. However I didn't figure out a counter example, as I wanted to keep some information of $x$ within $G(x)$, but the possiblility that this information is maintained after $n$-round of iterations is always negligible. For instance, if we keep the first bit of $G(x)$ being $x_1$, with only $2^{-n}$ probability we can still see the bit $x_1$ in $F_k'(x)$, when $k$ is random.

Are there any methods to prove or disprove the construction $F'_k(x)$ is pseudo-random? Thanks in advance.

Answer 1

$F'_k(x)$ is not necessarily pseudo-random.

Proof:
Changing one output does not affect PRGness, so if there is a PRG
that stretches by a factor of 2 then there is a PRG that stretches
by a factor of 2 and sends all-zero strings to all-zero strings.
For all $n$ and $k$ and $x$, if $G$ is such a PRG then $F'_k(x)$ is the string of $n$ zeros.
For all $n$, if $\: n\neq 0 \:$ then there are other strings with that length.
Therefore $F'_k(x)$ is not necessarily pseudo-random.


(Of course, this doesn't prove that your construction can't be pseudo-random.)