# Showing that $F'(k, x) := F(F(k, 0^{n}), x)$ is a PRF [duplicate]

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!

• 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. Dec 8, 2021 at 6:07
• @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. Dec 8, 2021 at 9:39