Is $f(K, f(K, x))$ a pseudorandom function? Given a PRF $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}^n$, is $f(K, f(K, x))$ a PRF, too?

My hunch is to construct a PRP similar to Feistel ciphers but with the property $f(K, f(K, x)) = x$, and disprove the statement with PRP/PRF switching lemma. However, I haven't found a concrete instance with the desired properties above yet.

Can anyone share some hints? Thanks!
I'm responding to:


  "If the oracle accessed by B is truly random, how to prove the oracle B constructs for A is truly random, too?" I'd like to know if a solution to (or a construction which avoids) this problem exists.


This is a "good" thing to get stuck on, because it's not something you can just push under the rug.
Concretely, let $f_k(\cdot)$ be a random function, so for any $x_i$, you have that $y_i = f_k(x_i)$ is uniformly random (and independent of any other $y_j$).
If we knew that $z_i = f_k(y_i)$ was also uniformly random, and independent of all other $z_j$'s, we'd be done!

Is this the case? The answer is almost. Specifically, provided that $\forall i : y_i\neq y_j$, it shouldn't be hard to prove that all of the $z_i$'s are uniformly random (and independent), so everything works out well.

Intuitively, a random function can be expressed as a lookup table (and this is the most compact way to express it), so to compute $f_k(0)$ we lookup some value $U_0$.
The entries in this table are uniformly random, independent variables.
We can think about using this lookup table for $f_k$ to compute $f_k\circ f_k$ by doing two lookups (so precisely the way you'd expect to).

Now consider computing $q$ values $((f_k\circ f_k)(1),\dots, (f_k\circ f_k)(q))$.
This will all be uniformly random values, but there's a risk there's some dependence between them.
Specifically, if $f_k(i) = f_k(j)$ for $i\neq j$, then we'll have that $(f_k\circ f_k)(i) = (f_k\circ f_k)(j)$, so the random variables $(f_k\circ f_k)(i)$ and $(f_k\circ f_k)(j)$ will be correlated (and therefore not independent).
In terms of our lookup table analogy, the event $f_k(i) = f_k(j)$ happening means that our lookup table for $f_k\circ f_k$ ends up having $i$ and $j$ point to the same "slot" in the lookup table for $f_k$, which is the cause of the problem.

So, we want to bound the probability $\Pr[\exists (i,j)\in[q]^2\setminus\{(i,i)\mid i\in[q]\} : f_k(i) = f_k(j)]$.
This can be done with the birthday bound (which you should look up if you're not familiar with it), and can be upper bounded by $q^2/2^n$, which is where the term that was mentioned in the comments comes from.