在 CPA 中，單消息安全性如何隱含多消息安全性？

我正在學習現代密碼學，最近我們達到了 CPA 機制。

在 CPA 遊戲設置中，A 向 C 發送兩條消息，然後 C 隨機選擇一條消息並將其加密並將加密文本發送回 A，然後 A 將確定兩條消息中的哪一條被 C 選擇。

但是，如果 A 向 C 發送兩條相同的消息，比如“m”，A 肯定會通過 C 的返回文本知道加密的“m”。然後，A 第二次可以發送“m”和任何其他消息消息給C，則如果C的返回文本與輸入’m’時返回的文本相同，則C選擇的消息為’m’，否則為其他任何消息。這使得 A 能夠以 1 的機率猜測 C 選擇的消息。

所以，單消息安全似乎並不意味著多消息安全，即使在單消息安全方案中，如果從 A 發送的兩條消息相同，A 仍然有 1 的機率猜測選擇的一個C.

誰能幫助我理解這一點？

謝謝你的回答！

對於 CPA 遊戲，我們進行以下實驗

1. 生成密鑰 $ k $ 帶有安全參數 $ n $
2. 對手 $ \mathcal{A} $ 被賦予 $ n $ ，oracle訪問加密oracle $ Enc_k(\cdot) $
3. $ \mathcal{A} $ 輸出兩條消息 $ m_1 $ 和 $ m_2 $ 長度相同（這裡沒有限制 $ m_0 \neq m_1 $ )
4. 選擇了一個隨機位 $ b \overset{R}\leftarrow {0,1} $ 密文 $ c = Enc_k(m_b) $ 被計算並傳輸到 $ \mathcal{A} $ . 這稱為挑戰密文。
5. $ \mathcal{A} $ 訪問加密預言機 $ Enc_k(\cdot) $ （甚至在送出之前）
6. 最後， $ \mathcal{A} $ 送出 $ b’ $ 作為他們的候選人
7. 實驗的輸出定義為 $ 1 $ 如果 $ b’ = b $ 和 $ 0 $ 否則。如果輸出是 $ 1 $ ，我們也說 $ \mathcal{A} $ 成功。

然後我們可以定義 $ Ind\text{-}CPA $ 作為;

加密方案是 $ Ind\text{-}CPA $ 如果對於所有機率多項式時間對手 $ \mathcal{A} $ 優勢可以忽略不計 $ negl(n) $

筆記：

1. 可忽略不計取決於安全參數 $ n $
2. 送出相同的消息沒有限制。對手必須找到正確的 $ b $ .
3. 如果您發送兩條相同的消息，則沒有任何優勢，因為對手不會學到任何東西。
4. C PA 安全需要隨機加密。像 ECB 模式這樣的確定性加密不能具有 CPA 安全性。
5. 該實驗還需要一個好的隨機數發生器。
6. 在公鑰密碼學中，加密預言 $ Enc_k(\cdot) $ 免費。人們可以隨時訪問，考慮使用 RSA 的公鑰進行加密。
7. 在實驗過程中密鑰是固定的（步驟 1）

但是，如果 A 向 C 發送兩條相同的消息，比如“m”，A 肯定會通過 C 的返回文本知道加密的“m”。然後，A 第二次可以發送“m”和任何其他消息消息給C，則如果C的返回文本與輸入’m’時返回的文本相同，則C選擇的消息為’m’，否則為其他任何消息。這使得 A 能夠以 1 的機率猜測 C 選擇的消息。

• 你知道 $ m $ 但是哪個 $ b’ $ 你會送出贏得比賽嗎？
• 第二次加密 $ m $ 由於 CPA 遊戲需要隨機加密，因此會發生變化，換句話說，任何 CPA 安全加密方案都必須是機率性的。其中，隨機投擲硬幣以確保同一消息的兩次加密不同。

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