對 PRF 鍵進行窮舉搜尋的成功機率
我看到這個例子是為了徹底搜尋來破壞 PRF 的安全性 $ F_k:{0,1}^n\times{0,1}^n\rightarrow{0,1} $ 其中關鍵空間的大小 $ |\mathcal{K}|=2^n $ .
聲稱有一個對手 $ \mathcal{A} $ 大小的 $ 2^n\cdot\text{poly}(n) $ 計算的值 $ S_k = F_k([1]_2),F_k([2]_2),\dots,F_k([2n]2) $ 對於所有的鍵。查詢神諭 $ \mathcal{O(\cdot)} $ （這可能是 $ \mathcal{R(\cdot)} $ 或者 $ F_k(\cdot) $ ) 對於相同的查詢，即 $ S{\mathcal{O}}=\mathcal{O}([1]_2),\mathcal{O}([2]_2),\dots,\mathcal{O}([2n]2) $ , 並返回 $ 1 $ 如果存在密鑰 $ k $ 為此 $ S{\mathcal{O}}=S_k $ ，否則返回0。還提到了區分的機率：
$ \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} $
（在哪裡 $ [x]_2 $ 表示二進製表示 $ n $ 位 $ x $ .)
我知道我們必須計算多條消息的 PRF 才能獲得大量比特並確保 $ S_{\mathcal{O}}=S_k $ 不等於偶然。但我想不通為什麼具體選擇 $ 2n $ ? （我想也許我們想要一些取決於 $ n $ 位具有相同字元串的反指數機率，但為什麼要添加因子 2？）
另外，我不明白為什麼機率不是 $ \geq1-2^{-2n} $ 因為隨機碰撞的機會應該是 $ 2^{-2n} $ ?
最後，暴力攻擊和窮舉搜尋基本上是同一種方法，但名稱不同嗎？
讓 $ q $ 是攻擊者進行的查詢次數。考慮到 $ \mathcal{A} $ 在實驗中相當於他們在修改後的實驗中的觀點，其中預言機僅限於域 $ {1,\dots,q} $ .
現在考慮，在這個修改後的實驗中，有 $ 2^q $ 表格的功能 $ R : {1,\dots,q} \to {0,1} $ . 如果我們隨機均勻地採樣其中一個函式，那麼 PRF 的一個鍵“命中”這個函式的機會有多大？好吧，我們不能準確地說，但我們可以給出一個上限。有 $ 2^n $ 鍵，這最多意味著，如果每個鍵都擊中不同的功能， $ 2^n $ 功能可以被擊中。這意味著其中一個鍵擊中我們的均勻採樣函式的機率上限為$$ \frac{# \text{ of keys}}{# \text{ of functions}} = \frac{2^n}{2^q} = 2^{n-q}. $$
這意味著，我們有 $$ \Pr[\mathcal{A}^{R(\cdot)}=1] \leq 2^{n-q} $$
還有（根據定義） $$ \Pr[\mathcal{A}^{F_k(\cdot)}=1] = 1. $$
所以 $$ \left|\Pr\left[\mathcal{A}^{F_k(\cdot)}=1\right]-\Pr\left[\mathcal{A}^{R(\cdot)}=1\right]\right|\geq 1-2^{n-q}. $$
現在我們需要為 $ q $ 這使得這次攻擊成功。如果您插入您的建議值 $ q=n $ ，你會注意到，我們得到$$ 1-2^{n-n}=1-2^0=1-1=0, $$ 這是不幸的。我們注意到，一旦我們選擇了一些更大的東西，比如說 $ q=n+1 $ ，我們通過 PRF 的標准定義成功攻擊： $$ 1-2^{n-(n+1)}=1-2^{-1}=1-\frac{1}{2}=\frac{1}{2} $$ 這是不可忽略的。
然而，我們喜歡以壓倒性的機率成功的攻擊，我們喜歡簡單容易辨識的可忽略的功能。所以我們選擇 $ q=2n $ 並得到 $$ 1-2^{n-2n}=1-2^{-n} $$ 這很容易閱讀並且很容易被辨識為壓倒性的機率。