I wanted to do some practice on security reduction proofs, and I am stumped on this one from the Boneh-Shoup book.

If $F(k, x)$ is a secure PRF, then show that $F'(k, x) := F(F(k, 0^{n}), x)$ is a secure PRF.

What I have so far is:

Suppose $F'$ is insecure, with a distingisher $D'$. This means that $F$ is also insecure, with a distinguisher $D$. I will now show construct $D$ using $D'$.

  1. $D$ receives a key, $k$.
  2. $D$ starts running $D'$.
  3. Whenever $D'$ queries its oracle on a message $x \leftarrow \lbrace0,1\rbrace^{n}$, give $x$ to $D$, compute $y:= O(x)$, where $O$ is $D$'s oracle. Then send $F(F(k, y), x)$ to $D'$.
  4. Output whatever $D'$ outputs.

This means that:

Pr[$D'^{F'}(1^{n}) = 1] =$ Pr[$D^{F}(1^{n}) = 1]$ and Pr[$D'^{r}(1^{n}) = 1] =$ Pr[$D^{r}(1^{n}) = 1]$, where $r$ is a random function. As well,

$|$Pr$[D^{F}(1^{n}) = 1] - Pr[D^{r}(1^{n}) = 1]| > $ negl($n$)

by assumption. However, since $F$ is a PRF, this is a contradiction, so $F'$ is a PRF. $\square$

Does this proof make sense? I have a feeling I messed up defining $D$, but I'm not sure. Thanks for any help!

  • 1
    $\begingroup$ Why does $D$ receive a key? You have $F(F(k,y),x)$ sent to $D'$ (with $y=F(k, x)$), while it distinguishes the shape $F(F(k,0),x)$. Can you fix that? You also need to argue why what you send to $D'$ is "like random" when $F(k, .)$ is random. $\endgroup$
    – Fractalice
    Dec 8, 2021 at 6:07
  • 1
    $\begingroup$ @Fractalice Hmm, so instead of $y=O(x)$, would it just be $y=O(0^{n})$, and then $D$ sends $F(y,x)$ to $D'$? I guess instead of getting a tag $D$ can compute $y = O(0^{n})$ in step 1. $\endgroup$
    – ness64
    Dec 8, 2021 at 9:39