安全遊戲預言機查詢
關於私鑰（對稱）IND-CPA 遊戲定義：
- 攻擊者 $ A $ 查詢加密預言多項式的次數。
- $ A $ 發送挑戰者 $ C $ 消息對 $ m_0 $ 和 $ m_1 $ . $ C $ 選擇一個隨機位 $ b $ 並發送回 $ A $ 密文 $ Enc(m_b) $ .
- $ A $ 對加密預言多項式進行進一步查詢次數。
- $ A $ 試圖猜測 $ b $ .
如果出現以下情況，則認為加密系統已損壞 $ A $ 在猜測方面具有不可忽視的優勢 $ b $ .
我的問題是：
- 讓我們將原始遊戲表示為 $ Game_0 $ . 現在我們刪除步驟（3），即 $ A $ 收到挑戰密文後無法查詢預言機。我們稱之為 $ Game_1 $ . 是不是真的，如果 $ A $ 可以打破 $ Game_0 $ ，她一定可以打破 $ Game_1 $ ? 換句話說，是否存在任何加密系統使得 $ A $ 不能斷 $ Game_1 $ , 但可以打破 $ Game_0 $ 收到密文後的額外查詢？
- 同樣，現在我們刪除步驟（1），即 $ A $ 在收到挑戰密文之前無法查詢預言機。我們稱之為 $ Game_2 $ . 是不是真的，如果 $ A $ 可以打破 $ Game_0 $ ，她一定可以打破 $ Game_2 $ ? 換句話說，是否存在任何加密系統使得 $ A $ 不能斷 $ Game_2 $ , 但可以打破 $ Game_0 $ 在收到密文之前有額外的查詢嗎？
我會更多地考慮#1 的證明/反例，但這裡是#2 的反例。
讓 $ \mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec} $ 參考具有消息空間的 CPA 安全加密方案 $ {0,1}^\lambda $ ，並定義以下修改方案：
- $ \mathsf{KeyGen}’ $ ： 跑 $ sk \gets \mathsf{KeyGen} $ 和样品 $ m^* \gets {0,1}^\lambda $ . 關鍵是 $ (sk,m^*) $ .
- $ \mathsf{Enc}’( (sk,m^),m) $ ： 如果 $ m = m^ $ 然後輸出 $ \star $ ; 否則輸出 $ (\mathsf{Enc}(sk,m), m^*) $ .
- $ \mathsf{Dec}’( (sk,m^), c) $ ： 如果 $ c = \star $ 然後輸出 $ m^ $ ; 否則解析 $ c $ 作為 $ (c_1,c_2) $ 並輸出 $ \mathsf{Dec}(sk, c_1) $
這個想法是 $ m^* $ 是一種特殊的消息，其加密很容易區分。但學習的唯一途徑 $ m^* $ 就是查詢加密預言機。
假設您使用挑戰前查詢來玩 CPA 遊戲。進行任何查詢，響應將包括 $ m^* $ . 現在選擇作為你的挑戰 $ m_0 = m^* \ne m_1 $ . 你可以確定 $ b $ 正是通過查看挑戰密文是否為 $ \star $ .
假設您在沒有挑戰前查詢的情況下玩 CPA 遊戲。沒有關於“魔法”明文的資訊 $ m^* $ 你將無法製作 $ m^* $ 挑戰明文之一，除非機率可以忽略不計。所以挑戰密文是一個正則 $ \mathsf{Enc} $ - 加密 $ m_b $ 並且遊戲可以簡化為 CPA 遊戲 $ \mathsf{Enc} $ .
更新： 對於#1，我能做的最好的反例是有狀態的加密方案。這有點自欺欺人，但有人可能會爭辯說，無狀態加密安全的“正確”定義也應該是有狀態加密的“正確”定義。
讓 $ \textsf{Enc} $ 參考標準的 CPA-secure 加密，並使用內部狀態定義以下加密方案 $ st $ , 初始化為 $ \bot $ :
- $ \textsf{Enc}’(sk,m) $ ： 輸出 $ (\textsf{Enc}(sk,m), st) $ ; 更新 $ st = m $ .
每次加密時，還會告訴您之前密文中使用的明文！因此，通過挑戰後查詢打破 CPA 是微不足道的。但是由於沒有挑戰後查詢，事情會降低到 CPA 的安全性 $ \textsf{Enc} $ 以直接的方式（減少已經“知道”用於挑戰前查詢的明文，因此可以適當地添加它們）。