# 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.

• This allows you to construct related PRG inputs which probably is exploitable for a suitable PRG definition. – SEJPM Feb 20 at 15:41
• Consider the counter-example in your recent question. – Maeher Feb 20 at 17:10
• One possible proof technique here might be to assume that $G$ is not some arbitrary PRG, but one that you opportunistically construct to make it easily exploitable in the $F$ construction. I.e., don't try to write a proof that attacks any choice of $G$, but rather figure out what properties $G$ could have that don't disqualify it as a PRG but are exploitable when used as a component in $F$. And one way to construct a suitable $G$ might be to assume you're given an arbitrary PRG $G'$ and define some construction that delegates to it but makes some changes to its input or output. – Luis Casillas Feb 20 at 17:34

Given some PRG $$G : \{0,1\}^n \to \{0,1\}^m$$ with $$m > n+1$$, define $$G' : \{0,1\}^{n+1} \to \{0,1\}^m$$ like this:

\begin{align} G'(0\|x) & = G(x) \\ G'(1\|x) & = 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:

1. Pick an arbitrary $$s$$;
2. Query the oracle for $$x_0 = f(0\|s)$$;
3. Query the oracle for $$x_1 = f(1\|s)$$;
4. 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.