證明 IND$-CPA 意味著 IND-CPA？
我最近閱讀了幾篇論文，這些論文在選擇的明文攻擊下使用了一種稱為“與隨機位/字元串不可區分”的安全概念，也稱為 IND $ -CPA。參見例如http://pdf.aminer.org/000/217/279/nonce_based_symmetric_encryption.pdf。認證的加密模式“OCB”也使用這個概念來證明。這與我更熟悉的概念不同，例如 Left-Or-Right (LOR) 或 Real-Or-Random (ROR)，它們通常被稱為 IND-CPA。這些論文都聲稱“很容易驗證 IND $ -安全性概念隱含 IND-概念，並且通過嚴格的簡化”，但忽略了提供該隱含的證明。那麼任何人都可以提供這個證據嗎？
這是 IND-CPA 的經典 LOR 定義，來自http://www.cs.ucdavis.edu/~rogaway/papers/sym-enc.pdf，也在這裡更全面地解釋：http: //cseweb.ucsd.edu /~mihir/cse107/w-se.pdf。
一種對稱加密方案 $ \mathcal{S} $ 是一組三個算法， $ {\mathcal{K}, \mathcal{E}, \mathcal{D}} $ . 隨機密鑰生成算法， $ \mathcal{K} $ , 從 Key-Space 中均勻隨機選擇一個密鑰K，由 security 參數定義 $ k $ – 鍵空間 = $ {0, 1}^k $ . 加密算法 $ \mathcal{E} $ 獲取密鑰K和明文M並輸出密文C或符號 $ \bot $ （表示明文不在 $ \mathcal{S} $ ）。在這個階段我不限制什麼樣的算法 $ \mathcal{E} $ 必須是——它可以是隨機的（如 CBC 模式），或有狀態的（如 CTR 模式），或確定性和無狀態的（如 ECB 模式，儘管很容易證明任何非有狀態或隨機的加密算法都是非常不安全的）。解密算法 $ \mathcal{D} $ 是確定性和無狀態的，並獲取密鑰K和密文C並輸出明文M或符號 $ \bot $ （表示送出的密文不在 $ \mathcal{S} $ ). $ \mathcal{D} $ 是的倒數 $ \mathcal{E} $ , 這樣 $ D_K(E_K(M)) = M $ 對於域中的所有M $ \mathcal{S} $ 以及 Key-Space 中的所有鍵。
IND-CPA 遊戲
這種安全性概念可以根據對手之間的博弈來定義 $ \mathcal{A} $ 和正在實施加密方案的挑戰者 $ \mathcal{S} $ . 挑戰者贈款 $ \mathcal{A} $ 訪問左或右加密“神諭” $ E_K(\mathcal{LR}(\cdot, \cdot, b)) $ ，它接受形式的查詢 $ (M_0, M_1) $ 並返回 $ E_K(M_b) $ 或符號 $ \bot $ 如果 $ |M_0| \neq |M_1| $ （即，如果消息的長度不同）。
以下是遊戲的步驟：
- 挑戰者選擇一個安全參數 $ k $ 和用途 $ \mathcal{K} $ 從該安全參數定義的密鑰空間中選擇一個密鑰*K。*挑戰者然後發送參數 $ k $ 到 $ \mathcal{A} $ . 如果安全參數是固定的並且是公開的，那麼挑戰者不需要選擇它或將它發送到 $ \mathcal{A} $ .
- 挑戰者選擇一個值 $ b $ 從集合中均勻隨機地 $ {0, 1} $ （例如，擲一枚公平的硬幣）。該位定義了加密預言機在遊戲的其餘部分中的行為方式——要麼是“左預言機”（如果 $ b = 0 $ ) 或“正確的 Oracle”（如果 $ b = 1 $ ）。挑戰者贈款 $ \mathcal{A} $ 訪問現在定義的 oracle，但不告訴 $ \mathcal{A} $ 的價值 $ b $ （神諭是左神諭還是右神諭是秘密）。
- $ \mathcal{A} $ 向表單的 oracle 送出查詢 $ (M_0, M_1) $ , 並收到回复，要麼是留下的消息的加密， $ M_0 $ ，或正確的資訊， $ M_1 $ ， 根據 $ b $ . $ \mathcal{A} $ 允許彌補 $ q_e $ 此類查詢，總消息長度最多 $ \mu $ 位，並且可以根據較早的答案自適應地選擇查詢（這是一種“自適應”選擇明文攻擊）。
- 在進行了它想要和/或可以的所有查詢之後， $ \mathcal{A} $ 輸出一點， $ b’ $ ，這是它對值的最佳猜測 $ b $ . 如果 $ b’ = b $ 然後 $ \mathcal{A} $ 贏得比賽，但如果 $ b’ \neq b $ 然後 $ \mathcal{A} $ 輸了。
任何對手的優勢 $ \mathcal{A} $ 玩這個遊戲被定義為機率 $ \mathcal{A} $ 獲勝減去機率 $ \mathcal{A} $ 輸了。
$ Adv^{lor-cpa}_{\mathcal{S}, \mathcal{A}} = P(\mathcal{A} \textit{ wins}) - P(\mathcal{A} \textit{ loses}) $
通常在安全證明中，我們試圖證明一個上限，以證明任何對手的優勢最多 $ q_e $ 查詢，最多總計 $ \mu $ 位，最大執行時間為 $ t $ （算法的執行時間 $ \mathcal{A} $ 用於設計查詢，然後決定做出什麼猜測），以及給定的安全參數 $ k $ . 如果證明的上限對於“合理”值來說是“小” $ k, t, q_e $ 和 $ \mu $ 那麼加密方案 $ \mathcal{S} $ 被認為是“可證明安全的”。
IND $ -CPA 遊戲
這種安全性的概念類似地定義為之間的博弈 $ \mathcal{A} $ 和挑戰者實施 $ \mathcal{S} $ . 有一個關鍵區別：
挑戰者再次隨機選擇 $ b $ ，但這次不是定義左 Oracle 或右 Oracle，而是這個位 $ b $ 確定挑戰者將實施“真實”預言機還是“假”預言機。Real Oracle 接受以下形式的查詢 $ M $ 並返回 $ E_K(M) $ （即查詢不是成對的等長消息）。Fake Oracle 接受形式的查詢 $ M $ 並返回從集合中獨立且均勻隨機選擇的字元串 $ {0, 1}^{|M|+s} $ ， 在哪裡 $ |M| $ 是查詢的長度 $ M $ 和 $ s $ 是“伸展”的 $ \mathcal{E} $ （加密算法擴展與相關聯的密文的數量 $ M $ ，例如 CBC 如何填充不能被密碼的塊大小整除的消息）。
對手 $ \mathcal{A} $ 因此不是試圖區分加密的 $ M_0 $ 和 $ M_1 $ ，而是試圖區分加密 $ M $ 來自相同長度的隨機字元串。和以前一樣，對手的優勢被定義為它正確猜測比特的機率 $ b $ 減去它做出錯誤猜測的機率。和以前一樣，如果總體上的最大優勢 ( $ k, t, q_e, \mu $ )-limited Adversaries 對於這些參數的合理值來說足夠小，那麼加密方案是“可證明安全的”。
這是我想出的證據。如果您發現它有任何問題，請告訴我…
證明聲明：如果加密方案在 IND $ -CPA 意義上是安全的，那麼它在 IND-CPA 意義上也是安全的。即IND $ -CPA $ \Rightarrow $ 註冊會計師
對立式更容易證明： $ \neg $ 註冊會計師 $ \Rightarrow $ $ \neg $ IND $ -CPA。這個陳述是以下引理的一個微不足道的結果：
引理 1. 任何具有以下優勢的有效 (LOR) IND-CPA 對手 $ \epsilon $ 可以轉化為具有多項式相似效率和優勢的 IND $ -CPA 對手 $ \frac{\epsilon}{2} $ .
因此，如果 IND-CPA 的優勢很大（意味著加密方案在這個意義上是不安全的），那麼 IND $ -CPA 的優勢也會很大（意味著它在這個意義上也是不安全的）。
為了證明引理 1，我將使用歸約論點。讓 $ \mathcal{A}{\mathcal{LOR}} $ 成為具有優勢的 LOR 對手 $ \epsilon $ ， 然後讓 $ \mathcal{A}$ $ 成為 IND $ -CPA 的對手。 $ \mathcal{A}$ $ 可以充當“包裝器”，冒充 LOR 挑戰者 $ \mathcal{A}{\mathcal{LOR}} $ , 並在$ -Challenger 和 $ \mathcal{A}_{\mathcal{LOR}} $ 以下列方式：
- $ \mathcal{A}_$ $ 拋硬幣， $ b’ $ ，並將該值用於遊戲的其餘部分；
- $ \mathcal{A}{\mathcal{LOR}} $ 傳輸表單的請求 $ (x_0, x_1) $ 到 $ \mathcal{A}$ $ , 誰選 $ x_{b’} $ 並將其傳輸給$ -Challenger，然後將來自$ -Challenger 的響應傳回給 $ \mathcal{A}_{\mathcal{LOR}} $ ;
- 後 $ q_e $ 查詢， $ \mathcal{A}{\mathcal{LOR}} $ 做出猜測， $ b^* $ , 至於價值 $ b’ $ 並將猜測發送給 $ \mathcal{A}$ $ ;
- $ \mathcal{A}$ $ 檢查是否 $ b’ = b^* $ . 如果是的話，那麼 $ \mathcal{A}$ $ 猜想 $ b = 0 $ （即$ -Challenger oracle 是真正的 Oracle），如果 $ b’ \neq b^* $ 然後 $ \mathcal{A}_$ $ 猜想 $ b = 1 $ （即$ -Challenger oracle 是一個隨機字元串 Oracle）。
優勢定義： $ Adv(\mathcal{A}) = P(\mathcal{A} $ 猜對了 $ ) - P(\mathcal{A} $ 猜錯了 $ ) $
讓 $ \mathcal{A}$\Rightarrow x $ 平均對手 $ \mathcal{A}$ $ 猜想 $ b = x $ .
所以， $ Adv(\mathcal{A}$) = [P(\mathcal{A}$\Rightarrow 0|b = 0)P(b = 0) + P(\mathcal{A}$\Rightarrow 1 | b = 1)P(b = 1)] - [P(\mathcal{A}$\Rightarrow 0 | b = 1)P(b = 1) + P(\mathcal{A}_$\Rightarrow 1 | b = 0)P(b = 0)] $
自從 $ \mathcal{A}_$\Rightarrow 0 $ （它猜測$ -Challenger 正在實例化一個 Real Oracle）當且僅當 $ b^* = b’ $ ， 然後：
$ Adv(\mathcal{A}_$) = [P(b^* = b’|b = 0)P(b = 0) + P(b^* = b’ | b = 1)P(b = 1)] - [P(b^* \neq b’| b = 1)P(b = 1) + P(b^* \neq b’ | b = 0)P(b = 0)] $
$ -Challenger從 $ {0, 1} $ ， 所以 $ P(b = 0) = P(b = 1) = \frac{1}{2} $ ，因此：
$ Adv(\mathcal{A}_$) = P(b^* = b’|b = 0)\frac{1}{2} + P(b^* = b’ | b = 1)\frac{1}{2} - P(b^* \neq b’| b = 1)\frac{1}{2} - P(b^* \neq b’ | b = 0)\frac{1}{2} $
在這一點上，我需要另一個引理…
引理 2。 $ P(b^* = b’| b = 1) = P(b^* \neq b’| b = 1) = \frac{1}{2} $ .
這是因為當 $ b = 1 $ 然後$ -Challenger 正在實例化一個隨機字元串 Oracle，因此 $ \mathcal{A}{\mathcal{LOR}} $ 只看到響應其查詢的均勻隨機字元串序列，與什麼值無關 $ \mathcal{A}$ $ 被選為 $ b’ $ . 因此，就正確猜測而言，它永遠不會比隨機猜測做得更好（或更差） $ b’ $ .
這個引理在手，兩個 $ b = 1 $ 前面的優勢方程中的項抵消了，留下我們，
$ Adv(\mathcal{A}_$) = P(b^* = b’|b = 0)\frac{1}{2} - P(b^* \neq b’ | b = 0)\frac{1}{2} $ ,
$ = \frac{1}{2}[P(b^* = b’|b = 0) - P(b^* \neq b’ | b = 0)] $ .
什麼時候 $ b = 0 $ 那麼整個遊戲本質上就是一個 LOR 遊戲，而當 $ \mathcal{A}_{\mathcal{LOR}} $ 其實是在玩LOR遊戲，它的優勢是，
$ Adv(\mathcal{A}{\mathcal{LOR}}) = P(\mathcal{A}{\mathcal{LOR}} $ 猜對了 $ ) - P(\mathcal{A}_{\mathcal{LOR}} $ 猜錯了 $ ) $ ,
或者明確地包括它正在玩 LOR 遊戲的條件，
$ Adv(\mathcal{A}{\mathcal{LOR}}) = P(\mathcal{A}{\mathcal{LOR}} $ 猜對了 | 遊戲 = LOR $ ) - P(\mathcal{A}_{\mathcal{LOR}} $ 猜錯 | 遊戲 = LOR $ ) $ .
為了 $ \mathcal{A}_{\mathcal{LOR}} $ 正確猜測，這意味著 $ b^* = b’ $ , 然後讓它猜錯 $ b^* \neq b’ $ . 所以：
$ P(\mathcal{A}_{\mathcal{LOR}} $ 猜對了 | 遊戲 = LOR $ ) = P(b^* = b’|b = 0) $
$ P(\mathcal{A}_{\mathcal{LOR}} $ 猜錯 | 遊戲 = LOR $ ) = P(b^* \neq b’ | b = 0) $ .
$ \therefore $ $ Adv(\mathcal{A}$) = \frac{1}{2}[Adv(\mathcal{A}{\mathcal{LOR}})] $
就“效率”而言 $ \mathcal{A}$ $ （它的執行時間），這基本上是計算成本 $ \mathcal{A}{\mathcal{LOR}} $ 連同“包裝器”成本，它應該很小。唯一的“每個查詢”操作 $ \mathcal{A}$ $ 必須執行的是： a) 接收 $ (x_0, x_1) $ 查詢來自 $ \mathcal{A}{\mathcal{LOR}} $ , b) 決定是否 $ x_{b’} $ 等於 $ x_0 $ 或者 $ x_1 $ , c) 將其發送給$ -Challenger，並且 d) 將響應發送回至 $ \mathcal{A}{\mathcal{LOR}} $ . 唯一的“每場比賽”操作 $ \mathcal{A}$ $ 必須執行的是隨機選擇一個值 $ b’ $ 開始，然後在最後決定是否 $ b^* = b’ $ 或者 $ b^* \neq b’ $ 並輸出其對值的猜測 $ b $ 因此。所以如果運營成本 $ \mathcal{A} $ 是 $ C_{\mathcal{A}} $ ， 然後：
$ C_{\mathcal{A}$} = A(C{\mathcal{A}_{\mathcal{LOR}}}) + B $ ， 在哪裡 $ A $ 和 $ B $ 很小。
因此是引理 1，因此是語句 IND $ -CPA $ \Rightarrow $ IND-CPA，證明。或者我相信。想法？