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.

  • $\begingroup$ This allows you to construct related PRG inputs which probably is exploitable for a suitable PRG definition. $\endgroup$ – SEJPM Feb 20 '20 at 15:41
  • $\begingroup$ Consider the counter-example in your recent question. $\endgroup$ – Maeher Feb 20 '20 at 17:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Luis Casillas Feb 20 '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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.