建構對消息恢復攻擊安全但在語義上不安全的密碼
我知道這兩種證券的定義（針對消息恢復和語義），但我不知道如何實際建構滿足這些條件的密碼，我的意思是，我不知道如何定義“讓 $ \mathcal{E} = (E,D) $ 在哪裡 $ E(k,m) = ;… $ 你可以看到它對 MR 是安全的，因為 …，但在語義上不安全，因為 …”。
至少，我想知道如何開始建構這樣的密碼。
消息恢復攻擊：
讓 $ \mathcal{E} = (E,D) $ 成為一個密碼。挑戰者隨機選擇一個 $ m $ 來自消息空間 $ \mathcal{M} $ , 一個隨機 $ k $ 從關鍵空間 $ \mathcal{K} $ , 計算隨機 $ c \xleftarrow[]{\text{R}} E(m,k) $ 並發送 $ c $ 給攻擊者。
然後，攻擊者發送 $ \hat{m} $ 回到挑戰者身邊。
如果攻擊者獲勝 $ \hat{m} = m $ . 讓 $ p $ 成為機率 $ Pr[\hat{m} = m] $ .
這種攻擊者的優勢是 $ \Big\vert ; p - \frac{1}{\Vert \mathcal{M} \Vert} ; \Big\vert $
如果這種優勢對於所有有效的攻擊者來說都可以忽略不計，那麼密碼對於 MR 攻擊是安全的。
構造這樣一個密碼的基本思想是利用以下事實（以及定義之間的主要區別！）： $ m $ 從消息空間中均勻隨機採樣以實現消息恢復安全性，並且可以非常具體地選擇用於語義安全性。
這意味著最簡單的解決方案可能為一個特定輸入的加密輸出特例，而對所有其他輸入安全地執行。使用消息恢復安全性，達到這種特殊情況的機會可以忽略不計，但可以通過語義安全性任意提高，從而允許將特殊情況加密與任何其他加密區分開來。
讓 $ \mathcal{M} = {0,1}^{n} $ 然後讓 $ \mathcal{C} = {0,1}^{n} $ ， 然後讓 $ \mathcal{K} = { $ 長度為 n 的奇校驗二進制序列 $ } $ .
密鑰生成： $ k \leftarrow_{\$} \mathcal{K} $ .
E(k,m) = $ m \oplus k $ ，按位。
D(k,c) = $ c \oplus k $ ，按位。
讓 $ \mathcal{E} = (E,D) $ 超過 $ { \mathcal{M}, \mathcal{K}, \mathcal{C} } $ .
讓 $ \mathcal{A} $ 成為任何有效的 MR 對手 $ \mathcal{E} $ .
讓 F 成為挑戰者 $ \mathcal{A} $ ，所以挑戰者 F 計算 $ k \leftarrow_{$} \mathcal{K} $ , $ m \leftarrow_{$} \mathcal{M} $ 和 $ c \leftarrow E(k,m) $ , 並將這個 c 發送到 $ \mathcal{A} $ .
然後讓 $ \mathcal{A} $ 輸出 $ \hat{m} $ 從 F 接收 c 並對其進行分析。
$ MRAdv[\mathcal{A}, \mathcal{E}] $ = |Pr( $ \mathcal{A} $ 獲勝）- $ \frac{1}{|\mathcal{M}|} $ |.
镨( $ \mathcal{A} $ 勝) = Pr( $ \hat{m} $ = m) = Pr(K = $ c \oplus \hat{m} $ ) = [ Pr(K = $ c \oplus \hat{m} $ | $ \hat{m} $ 為偶校驗，c 為偶校驗) Pr( $ \hat{m} $ 是偶數| c 為偶校驗) Pr(c 為偶校驗) + Pr(K = $ c \oplus \hat{m} $ | $ \hat{m} $ 為偶校驗，c 為奇校驗) Pr( $ \hat{m} $ 是偶數| c 奇校驗) Pr(c 奇校驗) + Pr(K = $ c \oplus \hat{m} $ | $ \hat{m} $ 是奇校驗，c 是偶校驗） Pr( $ \hat{m} $ 是奇校驗| c 為偶校驗) Pr(c 為偶校驗) + Pr(K = $ c \oplus \hat{m} $ | $ \hat{m} $ 是奇校驗，c 是奇校驗） Pr( $ \hat{m} $ 是奇校驗| c 是奇校驗) Pr(c 是奇校驗)] $ \leq $ $ \frac{1}{2}[0+\frac{1}{2^{n-1}} + \frac{1}{2^{n-1}} + 0 ] $ = $ \frac{1}{2^{n-1}} = \frac{2}{|\mathcal{M}|} $ .
所以， $ MRAdv[\mathcal{A}, \mathcal{E}] \leq \frac{1}{2^{n-1}}. $
所以 $ \mathcal{E} $ 是 MR 安全的。
現在的說法是 $ \mathcal{E} $ 在語義上不安全。
讓 C 成為 SS 挑戰者，讓我們建構 SS 對手 $ \mathcal{B} $ ，方法如下：
$ \mathcal{B} $ 從消息空間中選擇以下消息 $ m_{0} = 000\cdots00 $ 和 $ m_{1} = 000\cdots01 $ ，並將它們發送給它的挑戰者 C。
然後挑戰者 C 計算 $ b \leftarrow_{$} {0,1} $ 和 $ k \leftarrow_{$} \mathcal{K} $ 和 $ c \leftarrow E(k,m_{b}) $ , 並將這個 c 發送到 $ \mathcal{B} $ .
然後 $ \mathcal{B} $ 計算 $ \hat{b} $ ，方法如下：
$ \hat{b} = 0 $ , 如果 c 是奇校驗，否則 $ \hat{b} = 1 $ .
镨( $ \hat{b} = 1 $ , b = 1) = 1, Pr( $ \hat{b} = 1 $ | b = 0 ) = 0，因為 k 總是奇校驗，我們選擇 $ m_{0} $ 和 $ m_{1} $ 不同的平價。
所以， $ SSAdv[\mathcal{B}, \mathcal{E}] = 1 $ ，這是不可忽略的。所以 $ \mathcal{E} $ 在語義上不安全。