Is this a PRF? Fk(x) = G(k⊕x) where G is a PRG This is not homework, but a random thought.

Let $G(x)$ be a PRG.
We define the following function:
$$F_k(x) = G(k\oplus x)$$ 

My intuition is that it shouldn't be a PRF but I couldn't come with an example yet.

I tried to build a reduction from identifying G to identifying F but I'm not certain how you can simulate an oracle call when all you have is some string.
Given some PRG $G : \{0,1\}^n \to \{0,1\}^m$ with $m &gt; n+1$, define $G' : \{0,1\}^{n+1} \to \{0,1\}^m$ like this:

$$
\begin{align}
G'(0\|x) &amp; = G(x) \\
G'(1\|x) &amp; = G(x) 
\end{align}
$$



Lemma: If $G$ is a PRG, so is $G'$.

Proof: Let $s \in \{0,1\}^{n+1}$ be a randomly chosen seed, and let $s' \in \{0,1\}^{n}$ be its suffix (with the first bit of $s$ removed), which is also distributed uniformly at random. Since $G$ is a PRG, then $G(s')$ has a pseudorandom distribution. And since $G'(s) = G(s')$, so does $G'(s)$ have a pseudorandom distribution. So then, since $G'(s)$ is pseudorandom for random $s$, $G'$ is a PRG.



Theorem: $F_k(x) = G'(k \oplus x)$ is not a PRF. 

Proof: Because of the definitions of $F$ and $G'$, we see that for all $k$ and $s$, $F_k(0\|s) = F_k(1\|s)$. Given oracle access to an $f$ that's either $F_k$ or a random function, we have the following distinguisher:


Pick an arbitrary $s$;
Query the oracle for $x_0 = f(0\|s)$;
Query the oracle for $x_1 = f(1\|s)$;
If $x_0 = x_1$, then output $1$, otherwise output $0$.


If $f$ is a random function, this outputs $1$ with probability $2^{-m}$.  But if $f$ is $F_k$, then it outputs $1$ with probability $1$.



So, there exists a choice of PRG for which your proposed construction is not a PRF.