Why is this function pseudo random (PRF)? First, I want to clarify this is not homework. I encountered this question (here How can I prove that a function F isn&#39;t a pseudo random function?) while studying for a test coming soon.


$F'_k(x) = F_k(0||x) || F_k(1||x)$
$F'_k(x) = F_k(0||x) || F_k(x||1)$


(Here $||$ representing concatenation, $F$ is a PRF).

I know that the second function is not a PRF and I came up with an adversary for it by myself. 

As for the first fuction, I read comments saying it is a PRF, but I couldn't find a way to formally prove this.
I know the method of proving these kinds of questions.

I should assume by contradiction that $F'_K$ is not a PRF, namely it has an adversary $D'$ that distinguishes between $F'_K$ and a random function $f'$ with non-negligible probability.  Using $D'$, I should construct an adversary $D$ that distinguishes between $F_K$ and a random function $f$ with non-negligible probability - which is a contradiction.

I thought of the following reduction for constructing $D$:

Given an input $x$, and a oracle access $O$ (for $F_K$), $D$ runs $D'$ on $O(0||x)||O(1||x)$. Then, $D$ answers what $D'$ answers.


If $O=F_k$ , then $D$'s probability of distinguishing is equal to $D'$'s.  
If $O=f$ (the random function) - Well, here I'm stuck.
This is not exactly the way you're going about it, but I find it an easier way to deal with this kind of construction in general. First we switch to an information-theoretic setting, then go back to the concrete construction. This is very similar to proving the security of counter mode encryption.

First, we replace $F_k$ by a real random function $G$. Every new input to $G$ results in a uniformly random output $G(x) \in \{0,1\}^{n}$. Now we have the corresponding
$$
G'(x) = G(0\|x)\|G(1\|x)\,.
$$
Since every call to $F_k'$ gives you two free calls to $F_k$, we have
$$
\mathbf{Adv}^{\mathrm{prf}}_{F_k'}(D) \le \mathbf{Adv}^{\mathrm{prf}}_{F_k}(D') + |\mathbf{Pr}[D(G') = 1] - \mathbf{Pr}[D(\$) = 1]| \,,
$$
for a distinguisher $D'$ that performs at most $2q$ queries, by the triangle inequality (the first term being $\Delta_D(F_k', G')$, and the second being $\Delta_D(G', \$)$. $\$$ represents the ideal random function).

Our goal now is to distinguish $G'$ from a uniformly random function from $\{0,1\}^{n-1}$ to $\{0,1\}^{2n}$, to determine the second term of the above inequality. Notice that the inputs to $G$ are properly domain-separated: there are never any collisions between $0\|x$ and $1\|x$ for any distinct $x$.

More concretely, take any set of (distinct) queries $((x_1, y_1), (x_2, y_2), \dots, (x_q, y_q))$, where $y_i = \mathcal{O}(x_i)$. The probability that $G'(x_1) = y_1$, $G'(x_2) = y_2$, $\dots$, $G'(x_q) = y_q$ is $\left(\frac{1}{2^{n}}\frac{1}{2^{n}}\right)^q = 2^{-2nq}$. The probability for a random function is also $2^{-2nq}$, as each output has independent probability $2^{-2n}$. 

The definition of advantage is
$$
|\mathbf{Pr}[D(F) = 1] - \mathbf{Pr}[D(\$) = 1]|\,,
$$
for any distinguisher $D$. From this we conclude that the advantage of any attacker against $G'$ is $0$, since it has exactly the same probability distribution as the random function. So we conclude that
$$
\mathbf{Adv}^{\mathrm{prf}}_{F_k'}(D) \le \mathbf{Adv}^{\mathrm{prf}}_{F_k}(D') + 0 \,.
$$