Let $F(k,x):\{0,1\}^n\times \{0,1\}^n\rightarrow \{0,1\}^n$ be a secure PRF. Prove or disprove whether $F_1(k,x)=F(F(k,0^n),x)$ is a secure PRF.

My guess would be that it is PRF, and the part of the proof I have completed till now:

Assume by contradiction that $F_1$ is not a PRF. Then, there exists a PPT $D$, such that for every negligible function $\text{negl}(n)$, the following holds: $$ \left| \Pr_{\text{$k$: uniformly random}}\left[ D^{\left(F_1\right)_k(1^n)}(1^n) = 1 \right] - \Pr_{\text{$f$: uniformly random}}\left[ D^{f(1^n)}(1^n) = 1 \right] \right| > \text{negl}(n) $$

We will try to construct a PPT $D'$ for $F(k,x)$ which will violate its PRF property, therefore obtaining the contradiction. This $D'$ is quite simple: first of all, query our oracle $\mathcal{O}'$ (which can be either $F_k(x)$ or $f(x)$ where $f$ is uniformly random) and store $c_0=\mathcal{O}'(0^n)$. Then, we call $D$ and when it makes a call to "its oracle" $\mathcal{O}$, we compute and return (with no further calls to our oracle) $F(c_0,x)$, and return the result of $D$ in the end.

So, now trying to prove its sanity, we need that the two probabilities from the difference in the advantage are equal to the ones of $D$ in our way. First of all, for the first probability, given $\mathcal{O}'=F_k(x)$ for uniformly random $k$, our constructed oracle $\mathcal{O}(x)=F(c_0,x)$ is by definition correct, so these two probabilities are indeed equal. And now, the part where I am stuck: for the second probability, it suffices to prove that given $\mathcal{O}'(x)=f(x)$ where $f$ is uniformly random, that $\mathcal{O}(x)=F(c_0,x)=F(f(0^n),x)$ is a uniformly random function. Now, I don't actually see that happening.

This was my first concern as regards this construction of $D'$, and my second concern is that I only need to make 1 call for my whole $D'$, no matter how many polynomial calls $D$ makes, which can be thought of (at least by me) as quite weird. Any thoughts on these two concerns and any hint for the exercise? Maybe I should change the path of my proof? Note: I would like to make my proof completely formal, no loopholes or logical gaps anywhere.


Your Answer

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

Browse other questions tagged or ask your own question.