如果隨機數重複，對手的優勢是什麼？
證明加密方案的 CPA 安全性 $ (r, F_k(r)\oplus m ) $ 在哪裡：
- $ F_k $ 是鍵控功能
- $ r\in_R{0,1}^n $ 是一個隨機數，在現代密碼學簡介的第 85 頁上，我們有
價值 $ r^* $ 在回答 A 的至少一個加密預言機查詢時使用：在這種情況下，A 可以很容易地確定是否 $ m_0 $ 或者 $ m_1 $ 被加密了。之所以如此，是因為如果加密預言機曾經返回密文 $ \langle r^,s \rangle $ , si 響應加密消息的請求 $ m $ , 對手得知 $ f(r^) = s\oplus m. $
- 我的問題是對手如何使用 $ f(r^*) $ ?
- 我們不是假設對手不知道 $ f $ ?
我的理解是，如果我們使用了鍵控功能 $ F_k $ ，那麼由於對手不知道 $ k $ , 的知識 $ F_k(r^*) $ 不能使用，因為他/她還需要很多時間，也就是說 $ 2^{|k|} $ , 檢查哪個函式 $ F_k $ 在哪裡使用。所以在我看來使用加密方案是安全的，即使我們重複隨機數 $ r $ .
似乎我錯過了一些東西，但我找不到它。
感謝@fgrieu，我明白了我錯過的重點。關鍵是對手不想找到關鍵函式，當然，如果知道了，他/他會很高興，但他/她想要資訊並贏得一些遊戲。
所以讓我們像對手一樣思考，我們已經問過 $ z $ 查詢 $ m_1, \cdots, m_z $ 並得到 $ \langle r_1, F_k(r_1)\oplus m_1\rangle, \cdots , \langle r_z, F_k(r_z)\oplus m_z\rangle $ . 我們可以從查詢的答案中獲得以下資訊。
$ F_k(r_1) = F_k(r_1) \oplus m_1 \oplus m_1 $
$ \vdots $
$ F_k(r_z) = F_k(r_z) \oplus m_z \oplus m_z $
然後我們選擇 $ m’ $ 和 $ m’’ $ 並得到一個密文 $ F_k(r’)\oplus m_b $ . 如果隨機數 r 重複，例如 r’= r_i，那麼我們可以進行以下計算
$ F_k(r_i)\oplus m_i \oplus m_i \oplus F_k(r’) \oplus m_b = m_b $
並且我們僅僅通過檢查是否 $ m_b = m’ $ 或者 $ m_b=m’’ $ .
連對手都不知道 $ F_k $ 我們用他贏得了 CPA 遊戲。
查看“應用密碼學研究生課程”的第 47 頁（那裡還展示了一個攻擊遊戲）
$ PRG_{adv}[A,G]:= |Pr[W_0] - Pr[W_1] | $
（如圖 3.1 所示）
“Attack Game 3.1 可以重鑄成‘猜謎’遊戲”