First, I want to clarify this is not homework. I encountered this question (here How can I prove that a function F isn'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.