# 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!

• This construction is a PRF with advantage roughly $q^2/2^n$ + PRF-Adv. – SEJPM Jul 29 at 8:38
• Feistel ciphers do not fit the description $f(K, f(K, x)) = x$ directly ... – Leo Jul 29 at 8:43
• I'm now confused by your question. Are you asking whether for a general PRF $f$ whether $f(K,f(K,x))$ is a PRF? (to which the answer is yes) Are you asking whether there exists a PRF / PRP $f$ such that for all keys and values $f(K,f(K,x))=x$ but $f$ itself is a PRF / PRP? (to which the answer is no) Or is it something else? – SEJPM Jul 29 at 14:27
• A PRP with the property $f(K, f(K,x)) = x$ isn't a PRP. This is because you can trivially distinguish it from a random permutation by checking the equality $f(K, f(K, x)) = x$ on a few random points. More specifically, a permutation with the property you describe is called an involution, which is a proper subset of the set of all permutations. Querying the equation on some number of randomly chosen $x$ is simply an efficient (probabilistic) construction for testing membership in the subset of all involutions (the particular number you query it on probably matters, but not for your purpose). – Mark Jul 29 at 17:39
• Generically you shouldn't hope to construct some (pseudo-random object) with some easily checkable structure, because checking that structure becomes an efficient distinguishing test for distinguishing your object from random. I believe this is related to the concept of "natural proofs" in complexity theory, but don't have a great understanding of that concept. – Mark Jul 29 at 17:41

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.

• Thank you very much, Mark! I didn't notice that to an oracle adv. I/O relation is everything. If the results of distinct queries seem to follow independent uniform distributions, there is no way for the adv. to distinguish the function from a truly random one. I only paid attention to the "function" part and totally forgot the "observation" part. Thanks for your great answer! – Leo Jul 30 at 8:07