通過組合兩個給定方案構造IND-CPA安全加密方案
我有兩種加密方案 $ \Pi_0, \Pi_1 $ ，其中至少有一個是 IND-CPA 安全的，但我不知道是哪一個。任務是建構一個方案 $ \Pi $ 保證是 CPA 安全並為此提供證明。
儘管閱讀了q1，q2我仍然不明白建構該方案的最佳方式以及如何充分證明其安全性。
任何通往正確方向的想法或提示都值得讚賞！
第一個評論是密碼系統與獨立密鑰一起使用。這很重要，否則通常很難證明任何事情。
簡單的解決方案
現在，正如評論和連結問題中提到的那樣，簡單的解決方案是將您的消息秘密共享為兩個共享，並分別加密每個共享。最終的密文由這兩個密文組成。（這也可以用“一次性”加密來表述，但最好將其視為秘密共享，因為將其推廣到您擁有兩個以上密碼系統的情況是微不足道的。 )
證明策略是直截了當的。為了了解有關消息的任何資訊，對手需要（相同的部分）兩個共享。如果至少有一個密碼系統是 IND-CPA 安全的，那麼攻擊者就無法了解至少其中一個共享的資訊。IND-CPA-安全性如下。
基於遊戲的證明可能首先使用實數或隨機數（RoR-CPA，相當於 IND-CPA）作為安全加密方案來加密隨機字元串而不是秘密共享。完成此操作後，秘密共享的屬性可確保對手無法了解有關消息的任何資訊。
至於秘密分享，最簡單的通常是最好的。如果您的消息是 $ m $ , 選擇一個隨機字元串 $ r $ 長度相同。隨機字元串是您的第一個共享。然後計算異或 $ m $ 和 $ r $ ，這是第二次分享。（這通過選擇更多隨機字元串以明顯的方式推廣到更多共享。）
作品
如果您嘗試組合密碼系統，即首先使用一個系統加密消息，然後使用另一個系統加密生成的密文，則會發生更複雜的事情。
如果您首先使用安全系統進行加密（成為第一的重要性！），一切都很好。第二次加密所做的任何事情，對手都可以做，所以第二次加密不能破壞安全的內部加密。
如果您首先使用不安全的系統進行加密呢？直覺是外部系統（現在是安全的）應該隱藏不安全的密文，這將使組合變得安全。但這不是真的，您的直覺問題是密碼系統僅將消息隱藏到message length。可能發生的情況是，不安全的密碼系統會產生長度取決於消息的密文。該長度（包含有關消息的資訊）可能會通過安全密碼系統洩漏並導致不安全的構造。
但是，如果您將注意力限制在某種“保留長度”的密碼系統上，其中密文長度僅是消息長度的函式，而不是消息的確切內容，那麼您的直覺應該再次起作用。