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!

  • $\begingroup$ This construction is a PRF with advantage roughly $q^2/2^n$ + PRF-Adv. $\endgroup$ – SEJPM Jul 29 '19 at 8:38
  • $\begingroup$ Feistel ciphers do not fit the description $f(K, f(K, x)) = x$ directly ... $\endgroup$ – Leo Jul 29 '19 at 8:43
  • 1
    $\begingroup$ 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? $\endgroup$ – SEJPM Jul 29 '19 at 14:27
  • 1
    $\begingroup$ 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). $\endgroup$ – Mark Jul 29 '19 at 17:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark Jul 29 '19 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.

  • $\begingroup$ 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! $\endgroup$ – Leo Jul 30 '19 at 8:07
  • $\begingroup$ How does this austerely lead to a mathematical proof of PRF-property of $f(K,f(K,x))$? I can see the intuition, but not how this would lead to a totally formal proof. $\endgroup$ – Jason Nov 16 '19 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.