使用 CPA 和 CCA 進行安全雙重加密

你介意給我任何提示，連結或想法關於如何通過使用CPA遊戲和CCA遊戲來提高雙重正常加密和解密的安全性，這聽起來很有趣，我還在和我的同學討論這個問題。鑑於以下資訊，

密鑰生成算法 $ (PK, SK) \leftarrow Gen(1^λ) $ :

• 計算 $ (pk, sk) \leftarrow gen(1^λ) $
• 計算 $ (pk’, sk’) \leftarrow gen’(1^λ) $
• 放 $ PK := (pk, pk’) $ 和 $ SK := (sk, sk’) $

加密算法 $ C \leftarrow Enc(m) $ :

• 計算 $ c \leftarrow enc(m) $
• 計算 $ C \leftarrow enc’(c) $

解密算法 $ \tilde{m} \leftarrow Dec(C) $ :

• 計算 $ \tilde{c} \leftarrow dec’(C) $
• 計算 $ \tilde{m} \leftarrow dec(\tilde{c}) $

如果兩者 $ \pi $ 是 CPA 安全的，那麼新方案將 $ \Pi $ 是 CPA 安全的嗎？如果有，請證明。如果不是，請反駁。與 CCA 相同。親切的問候

對於 CPA 安全來說，第一個方案實際上就足夠了，即 $ \pi = (gen, enc, dec) $ 是 CPA 安全的。

讓我們定義一個通用方案的 CPA 遊戲 $ \pi = (Gen, Enc, Dec) $ 對抗對手 $ A $ 如下：

1. 我們採樣 $ (pk, sk) \leftarrow Gen(1^\lambda) $ ， 並且寄出 $ pk $ 到 $ A $ .
2. $ A $ 輸出消息 $ m_0 $ 和 $ m_1 $ .
3. 我們採樣 $ b \leftarrow {0,1} $ （一個隨機位），和 $ c \leftarrow Enc(pk,m_b) $ （這裡我將公鑰作為參數添加到 $ Enc $ , 使密鑰明確）
4. $ A $ 輸出一點 $ b’ $ .

我們說 $ A $ 贏，如果 $ b = b’ $ ，並且該方案是 IND-CPA 安全的，如果 $ A $ 至多具有微不足道的優勢。

現在，讓 $ \Pi = (Gen, Enc, Dec) $ , $ \pi = (gen, enc, dec) $ 和 $ \pi’ = (gen’, enc’, dec’) $ 成為您在問題中建議的方案。假設存在對手 $ A $ 具有不可忽視的優勢 $ \Pi $ （即證明 $ \Pi $ 不是 IND-CPA 安全的）。然後我們可以構造一個對手 $ B $ 反對 $ \pi $ 如下：

1. 輸入時 $ pk $ 來自 CPA 遊戲 $ B $ 樣品 $ (pk’, sk’) \leftarrow gen’(1^\lambda) $ , 並發送 $ PK = (pk, pk’) $ 到 $ A $ .
2. 什麼時候 $ A $ 輸出 $ m_0 $ , $ m_1 $ $ B $ 將這些消息轉發給 CPA 遊戲。
3. 輸入時 $ c $ 來自 CPA 遊戲 $ B $ 樣品 $ C \leftarrow Enc’(pk’, c) $ 並發送 $ C $ 到 $ A $ .
4. 什麼時候 $ A $ 輸出 $ b’ $ $ B $ 輸出相同的位。

現在你看到了 $ B $ 在 CPA 比賽中獲勝 $ \pi $ 當且僅當 $ A $ 會贏得相應的比賽 $ \Pi $ . 這意味著由於 $ A $ 具有不可忽視的優勢 $ \Pi $ 和 $ B $ 提供了 $ A $ 與 CPA 遊戲中的消息完全相同 $ \Pi $ ， 它遵循 $ B $ 還必須具有不可忽視的優勢 $ \pi $ . 然而，這與 $ \pi $ IND-CPA 是安全的，所以沒有這樣的 $ A $ 可以存在。IE， $ \Pi $ 也是 CPA 安全的。

注意安全性 $ \pi’ $ 這裡真的無所謂。

對於 CCA 安全性，類似的證明可能是可能的，但我沒有嘗試過。

引用自：https://crypto.stackexchange.com/questions/20647