2
$\begingroup$

I'd like to know which strategy is adopted by an unlimited adversary to distinguish PRF's from Truly Random Functions

$\endgroup$
  • $\begingroup$ Yes, truly random function $\endgroup$ – Pippo Pluto Nov 10 '18 at 19:13
  • $\begingroup$ Welcome to Cryptography. Is this homework? If so, please write it in the question and show your effort. $\endgroup$ – kelalaka Nov 10 '18 at 19:17
0
$\begingroup$

Let's first define the domain and range of the function we want to distinguish to be $M = \{0,1\}^m$ and $N = \{ 0,1\}^n$.

Now, what does it mean for a function to be truly random? It means that it was selected uniformly at random from the space $\mathsf{FUNC}(M, N)$, which consists of all functions from $M$ to $N$. How many such functions are there? I.e., how big is the space $\mathsf{FUNC}(M, N)$? Answer: $N^M = 2^{n \cdot 2^m}$ (exercise: prove this).

On the other hand, if the function is a PRF, then it was not drawn from the full space $\mathsf{FUNC}(M, N)$, but rather from a much smaller space indexed by the key of the PRF. That is, a PRF is formally a family of functions $\{F_k \}_{k \in K}$, where each member is a function $F_k \colon M \to N$. What we really mean when we say that the function is a PRF, is that we first pick a key $k \in K$ uniformly at random from the key space, and then we use the function $F_k$ indexed by this key to answer all queries. So how big is the PRF "function space"? It's simply the size of the key space $K$, i.e., $|K|$.

In the PRF distinguishing game we are then asked to distinguish a function which is either randomly selected from the set $\mathsf{FUNC}(M, N)$, or randomly selected from the family $\{F_k \}_{k \in K}$. For concreteness, suppose $M = N = K = \{0, 1\}^{128}$. Thus, in this case we are asked to distinguish a function which is either drawn from a set of size $2^{128 \cdot 2^{128}}$, or from a set of size $2^{128}$. Notice the massive difference in size between these two sets! The PRF family lives inside a tiny tiny tiny bubble of the whole space $\mathsf{FUNC}(M, N)$. In other words, the functions in the PRF family only exhibits a very tiny portion of all possible functional behaviors between the sets $M$ and $N$.

So how can we use this to distinguish whether the function we are given is truly random or only a PRF? Well, since we are an unlimited adversary, we can simply query the function at all possible inputs in $M$ to determine exactly which function in $\mathsf{FUNC}(M, N)$ we are dealing with. If the function does not belong to the function family $\{F_k \}_{k \in K}$, then we of course know that it was selected as a truly random function and not as a PRF. But if it does belong to $\{F_k \}_{k \in K}$, what should we guess then? I claim that we should guess that the function was selected as a PRF. Why? Well, if the function was selected uniformly at random from $\mathsf{FUNC}(M, N)$, what is the probability that it would happen to coincide with a function in $\{F_k \}_{k \in K}$? Answer: really tiny. (Exactly how tiny I leave to you to figure out).

$\endgroup$
  • $\begingroup$ Is it the ratio between the number of PRF functions(cardinality of the key) and the number of TRF? $\endgroup$ – Pippo Pluto Nov 13 '18 at 15:19
  • $\begingroup$ @PippoPluto Yes, exactly. $\endgroup$ – hakoja Nov 13 '18 at 15:35

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.