 Hey crypto SE, i'm having a bit of trouble with this question. Can anyone help me to understand how to go about solving this problem? Any help is appreciated :)

• Would trying to find $F_K(F_K(F_K(x)))$ help you? (Hint: It does!)
– SEJPM
Feb 3 '17 at 19:37

(a) Adaptive case: To show that the adversary can get a very large advantage, send an arbitrary query $x$ to the oracle. The left part of the response is the input of the second query. If the oracle is a PRF, the left part of the second response equals the right part of the first response. If the oracle is a random oracle the two parts are not equal with a very high probability $p \rightarrow 1$ for $n \rightarrow \infty$.
Let $$L: \{0,1\}^{2n} \rightarrow \{0,1\}^n, ~L(x_1, \ldots, x_n, x_{n+1}, \ldots, x_{2n}) = (x_1, \ldots, x_n)$$ and $$R: \{0,1\}^{2n} \rightarrow \{0,1\}^n, L(x_1, \ldots, x_n, x_{n+1}, \ldots, x_{2n}) = (x_{n+1}, \ldots, x_{2n})$$ be the projection to the left and right $n$ Bits, respectively.
1. Query $$G_k(x) = F_K(x) \parallel F_K(F_K(x))$$
2. Query $$G_k(L(G_k(x))) = F_K(L(G_k(x))) \parallel F_K(F_K(L(G_k(x)))) = F_K(F_K(x)) \parallel F_K(F_K(F_K(x)))$$
And hence $$R(G_k(x)) = L(G_k(L(G_k(x))))$$
(b) Non-adaptive case: Since $F$ is a PRF both $F_K(x)$ and $F_K(F_K(x))$, and hence $G_k(x)$ cannot be distinguished from random output. Since the inputs in a sequence of queries are chosen beforehand, their responses appear completely unrelated and do not provide any information about the nature of the oracle.