This is a well-known exercise that has already even been posted here.
I understand both arguments to prove and disprove that $F'$ and $\bar{F}$ are PRFs, as I explain below, however, it seems that the proof also applies to the case where $\bar{F}$ is not a PRF!
Assume $F$ is a PRF, then we have to prove that each of the following functions is a PRF or show a counter example
- $F'_k(x) = F_k(0\mathbin\|x) \mathbin\| F_k(1\mathbin\|x)$
- $\bar{F}_k(x) = F_k(0\mathbin\|x) \mathbin\| F_k(x\mathbin\|1)$
(Here $\mathbin\|$ represents concatenation)
The $\bar{F}$ from (2.) is not a PRF because a distinguisher can compute $\bar{F}_k(00...0) = F_k(000...0) \mathbin\| F_k(00...01)$ and $\bar{F}_k(00...1) = F_k(00...01) \mathbin\| F_k(00...011)$ and check if the first half of the bits of $\bar{F}_k(00...1)$ is equal to the second half of the bits of $\bar{F}_k(00...0)$. For a uniform $f$, this happens only with negligible probability.
Now, for $F'$ from (1.), since it is a PRF, we can construct a distinguisher $D$ for $F$ given a distinguisher $D'$ for $F'$
- $D'$ sends $x$ to $D$
- $D$ queries two times the oracle of $F$ to get $f(0\mathbin\|x)$ and $f(1\mathbin\|x)$ (where $f$ is uniform or $F_k$)
- $D$ sends $f'(x) = f(0\mathbin\|x) \mathbin\| f(1\mathbin\|x)$ to $D'$
- $D'$ outputs a bit $b'$
- $D$ outputs the same bit
The advantage of $D$ against $F$ is the same as the advantage of $D'$ in distinguishing $F'$ (unless I am missing something), but $\operatorname{Adv}(D')$ is non negligible by hypothesis, so $\operatorname{Adv}(D)$ is non-negligible, which contradicts the fact that $F$ is a PRF.
Therefore, $F'$ is also a PRF (end of proof)
Now it is the point where I am confused... It seems that if we replace steps (2.) and (3.) in the proof above so that $D$ obtains $f(0\mathbin\|x)\mathbin\|f(x\mathbin\|1)$, then we obtain a proof that $\bar{F}$ (from item (2.)) is a PRF, although we know it is not a PRF!
So what am I missing?
Or what is wrong with the proof?