0
$\begingroup$

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.

$\endgroup$

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.