Probability for success of exhaustive search on PRF keys

Question

I saw this example for exhaustive search to break the security of a PRF $F_k:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$ where the key space is of size $|\mathcal{K}|=2^n$.

The claim is that there is an adversary $\mathcal{A}$ of size $2^n\cdot\text{poly}(n)$ that computes the values of $S_k = F_k([1]_2),F_k([2]_2),\dots,F_k([2n]_2)$ for all the keys. Queries the oracle $\mathcal{O(\cdot)}$ (which might be either $\mathcal{R(\cdot)}$ or $F_k(\cdot)$) for the same queries, i.e. $S_{\mathcal{O}}=\mathcal{O}([1]_2),\mathcal{O}([2]_2),\dots,\mathcal{O}([2n]_2)$, and returns $1$ if there exists a key $k$ for which $S_{\mathcal{O}}=S_k$, otherwise returns 0. It also mentioned that the probability to distinguish:

$\left|\Pr_{k\leftarrow\mathcal{K}}\left[\mathcal{A}^{F_k(\cdot)}=1\right]-\Pr_{k\leftarrow\mathcal{K}}\left[\mathcal{A}^{R(\cdot)}=1\right]\right|\geq1-2^{-n}$

(Where $[x]_2$ represents the binary representation in $n$ bits of $x$.)

I understand we must calculate the PRF for several messages in order to have significant number of bits and ensure $S_{\mathcal{O}}=S_k$ does not equal by chance. But I couldn't figure out why specificly choose $2n$? (I thought maybe we want to have somthing which depends on $n$ bits to have inverse-exponantial probaility for identical strings, but why the factor of 2 is added?)

Also, I don't understand why the probability isn't $\geq1-2^{-2n}$ since the chance for collision in random should be $2^{-2n}$?

Finally, is bruteforce attacks and exhaustive search are basically the same method with different name?

Answer 1

Let $q$ be the number of queries made by the attacker. Consider that the view of $\mathcal{A}$ in the experiment is equivalent to their view in a modified experiment, where the oracle is restricted to the domain $\{1,\dots,q\}$.

Now consider, that in this modified experiment, there are exactly $2^q$ functions of the form $R : \{1,\dots,q\} \to \{0,1\}$. If we sample one of those functions uniformly at random, what is the chance that one of the keys of the PRF will "hit" this function? Well, we can't say exactly, but we can give an upper bound. There are $2^n$ keys, which means at most, if each each of those keys hits a different function, $2^n$ functions can be hit. This mean the probability of one of the keys hitting our uniformly sampled function is upper bounded by $$\frac{\# \text{ of keys}}{\# \text{ of functions}} = \frac{2^n}{2^q} = 2^{n-q}.$$

This means, we have $$\Pr[\mathcal{A}^{R(\cdot)}=1] \leq 2^{n-q}$$

and also (by definition) $$\Pr[\mathcal{A}^{F_k(\cdot)}=1] = 1.$$

Therefore $$\left|\Pr\left[\mathcal{A}^{F_k(\cdot)}=1\right]-\Pr\left[\mathcal{A}^{R(\cdot)}=1\right]\right|\geq 1-2^{n-q}.$$

Now we need to choose a value for $q$ that makes this attack successful. If you plug in you suggested value of $q=n$, you'll notice, that we get $$1-2^{n-n}=1-2^0=1-1=0,$$ which is unfortunate. We notice that as soon as we choose something a bit larger, say $q=n+1$ , we have a successful attack by standard definitions of PRFs: $$1-2^{n-(n+1)}=1-2^{-1}=1-\frac{1}{2}=\frac{1}{2}$$ which is non-negligible.

However, we like to go for attacks that are successful with overwhelming probability and we like to go for simple easily recognizable negligible functions. So we choose $q=2n$ and get $$1-2^{n-2n}=1-2^{-n}$$ which is easy to read and readily recognizable as an overwhelming probability.