# Is changing-key $F_1$ a secure PRF?

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.