Encryption
針對 CPA 攻擊的安全性？
讓 $ \mathcal{E} = (E,D) $ 成為 CPA 安全密碼。
讓我們定義 $ \mathcal{E’} = (E’, D’) $ ， 在哪裡 $ E’(k,m) = E(k, E(k,m)) $ .
我怎樣才能證明 $ \mathcal{E’} $ 將是 CPA 安全，如果 $ \mathcal{E} $ 是？
我的猜測：讓 $ a $ 成為攻擊者的 CPA 優勢 $ \mathcal{E} $ ， 那是， $ \mathrm{CPAadv}[\mathcal{A, E}] = a $ .
作為 $ \mathcal{E} $ CPA 是安全的，那麼 $ a $ 可以忽略不計，因此 $ E(k,m) $ 為一些任意有效的攻擊者提供了可以忽略不計的優勢。
讓 $ E(k,m) = e $ . 如果我重複這個過程 $ E(k,e) $ , $ E $ 應該給攻擊者另一個微不足道的優勢 $ b $ .
那麼，總優勢由 $ E(k,E(k,m)) $ 將會 $ a+b $ ，並且由於它們都可以忽略不計， $ a+b $ 可以忽略不計 $ \mathcal{E’} $ 會很安全。
你可以用反證法來證明這一點。認為 $ \mathcal{E’} $ 不是 CPA-Secure，這意味著存在攻擊者 $ \mathcal{A} $ 誰能以不可忽略的機率打破這個計劃。使用這個攻擊者，我們試圖打破 CPA-Security $ \mathcal{E} $ 具有不可忽略的機率如下：
- 對手 $ \mathcal{B} $ （為了打破 $ \mathcal{E} $ ) 輸出兩個明文 $ m_0 $ 和 $ m_1 $ .
- 一點點 $ b $ 然後隨機均勻地選擇 $ b \leftarrow {0,1} $ 和 $ \mathcal{B} $ 接收加密 $ m_b $ IE， $ c=E(k,m_b) $ .
- 根據 CPA 不可區分性實驗的定義（參見 Katz-Lindell 書中的第 3.5 節），攻擊者仍然可以訪問加密預言機，並且可以在此時查詢該預言機 $ c $ 接收 $ c’=Enc(k,c) $ . （這裡，我們假設明文和密文空間是相同的。）
- $ \mathcal{B} $ 模擬 CPA 不可區分性實驗 $ \mathcal{A} $ 通過發送這個挑戰密文 $ c’ $ 至 $ \mathcal{A} $ .
- $ \mathcal{A} $ 輸出一點 $ b’ $ .
- 最終， $ \mathcal{B} $ 返回相同的輸出位 $ b’ $ 作為 $ \mathcal{A} $ .
現在，很明顯，假設成功機率不可忽略 $ \mathcal{A} $ , 的成功機率 $ \mathcal{B} $ 在打破 $ \mathcal{E} $ 也是不可忽視的。