證明語義安全意味著密鑰恢復攻擊的安全性
我正在研究書中的問題 2.11：Dan Boneh 和 Victor Shoup 的應用密碼學研究生課程。問題如下：
**問題 2.11：**讓 $ \mathcal{E} = (E, D) $ 是一個密碼定義在 $ (\mathcal{K}, \mathcal{M}, \mathcal{C}) $ . 密鑰恢復攻擊由挑戰者和對手之間的以下博弈建模 $ \mathcal{A} $ ：挑戰者選擇一個隨機密鑰 $ k $ 在 $ \mathcal{K} $ , 一條隨機消息 $ m $ 在 $ \mathcal{M} $ , 計算 $ c \leftarrow E(k, m) $ , 並發送 $ (m, c) $ 至 $ \mathcal{A} $ . 作為回應 $ \mathcal{A} $ 輸出猜測 $ \hat{k} $ 在 $ \mathcal{K} $ .
我們說 $ \mathcal{A} $ 贏得比賽，如果 $ D(\hat{k}, c) = m $ 並定義 $ \text{KRadv}[\mathcal{A}, \mathcal{E}] $ 是機率 $ \mathcal{A} $ 贏得比賽。像往常一樣，我們說 $ \mathcal{E} $ 如果對於所有有效的對手，則可以安全地抵禦密鑰恢復攻擊 $ \mathcal{A} $ 優勢 $ \text{KRadv}[\mathcal{A}, \mathcal{E}] $ 可以忽略不計。
證明如果 $ \mathcal{E} $ 在語義上是安全的並且 $ \epsilon = \frac{|K|}{|M|} $ 可以忽略不計，那麼 $ \mathcal{E} $ 對密鑰恢復攻擊是安全的。特別是，表明對於每個有效的密鑰恢復對手 $ \mathcal{A} $ 有一個有效的語義安全對手 $ \mathcal{B} $ ， 在哪裡 $ \mathcal{B} $ 是一個基本的包裝器 $ \mathcal{A} $ , 這樣 $$ \text{KRadv}[\mathcal{A}, \mathcal{E}] ≤ \text{SSadv}[\mathcal{B}, \mathcal{E}] + \epsilon $$
我的嘗試：
我使用以下結構 $ \mathcal{B} $ ：
我們在這裡設置 $ \hat{b}=1 $ 當且僅當 $ D(\hat{k}, c)=m_1 $ .
實驗 $ b=1 $ : 密文 $ c=E(k,m_1) $ ， 所以 $ (m_1, c) $ 是上述密鑰恢復遊戲中的有效對。所以 $ Pr[\hat{b}=1\ |\ b=1]=\text{KRadv}[\mathcal{A}, \mathcal{E}] $ .
實驗 $ b=0 $ ： 這對 $ (m_1, c) $ 根據密鑰恢復遊戲，不再是有效對，因為 $ c=E(k, m_0) $ . 為了 $ \hat{b}=1 $ ，我們需要攻擊者 $ \mathcal{A} $ 輸出 $ \hat{k} $ 這樣 $ D(\hat{k},c)=D(\hat{k}, E(k, m_0))=m_1 $ .
**問：**但是有多少這樣的 $ \hat{k} $ 在那兒？假設有 $ x $ 這樣的鍵，然後會 $ Pr[\hat{b}=1\ |\ b=0]=\frac{x}{|\mathcal{K}|} $ ? 清楚地解釋為什麼這是對或錯的會對我有很大幫助嗎？
回想起來 $$ \text{SSadv}[\mathcal{B}, \mathcal{E}]=|Pr[\hat{b}=1\ |\ b=0]-Pr[\hat{b}=1\ |\ b=1]| $$ 我們會有 $$ \text{SSadv}[\mathcal{B}, \mathcal{E}]=|\text{KRadv}[\mathcal{A}, \mathcal{E}]-\frac{x}{|\mathcal{K}|}|\geq \text{KRadv}[\mathcal{A}, \mathcal{E}]-\frac{x}{|\mathcal{K}|} $$
因此 $ \text{KRadv}[\mathcal{A}, \mathcal{E}] ≤ \text{SSadv}[\mathcal{B}, \mathcal{E}] + \frac{x}{|\mathcal{K}|} $ .
我的方法一般正確嗎？這似乎是錯誤的，尤其是在 $ b=0 $ （不明白在哪裡 $ \frac{|K|}{|M|} $ 適合）。
案件的更新嘗試 $ b=0 $ ：
讓 $ m_1 $ 從 $ \mathcal{M} $ . 在這種情況下 $ c=E(k,m_0) $ . 從任何密文中，我們最多有 $ |\mathcal{K}| $ 我們可以解密的可能消息。讓 $$ S={D(k’, c)\ |\ k’\in \mathcal{K}} $$ 然後 $$ Pr[m_1\in S]\leq\frac{|\mathcal{K}|}{|\mathcal{M}|} $$
如果事件 $ m_1\in S $ 發生，然後攻擊者 $ \mathcal{A} $ 有機率 $ \text{KRadv}[\mathcal{A}, \mathcal{E}] $ 找到一把鑰匙 $ \hat{k} $ 這樣 $ D(\hat{k}, c)=m_1 $ . 否則，當 $ m_1\not \in S $ , 我們有機率 $ 0 $ 找不到這樣的鑰匙，因為不存在。因此
$$ \text{SSadv}[\mathcal{B}, \mathcal{E}]=|\text{KRadv}[\mathcal{A}, \mathcal{E}]-Pr[m_1\in S]\cdot\text{KRadv}[\mathcal{A}, \mathcal{E}] |\geq\text{KRadv}\mathcal{A}, \mathcal{E} $$
這樣我們就完成了。
我相信沒有辦法知道多少 $ \hat{k} $ . 即使我們這樣做了，假設它是不正確的 $ Pr[\hat{b}=1|b=0]=\frac{x}{|K|} $ .
處理分析時 $ b=0 $ 嘗試修復 $ c $ 並查看最大消息數是多少，以便退出密鑰 $ k $ 這樣 $ E(k,m) = c $ . 還要查看消息在此特定集合中的機率。