證明 CPA-security 意味著針對明文恢復的安全性

考慮以下實驗：

1. $ k = Gen(1^n) $
2. $ m \stackrel{u}{\in} {0,1}^{l(n)} $
3. $ c = Enc_k(m) $
4. $ m’ = B(1^n,c) $

將獲勝事件定義為 $ m’ = m $ . 我想證明，如果加密方案 $ Enc $ 每個 PPT 算法都是 CPA 安全的 $ B $ 在上述實驗中，只能以可忽略的機率成功。

提議

這是我自己想出的解決方案：

您的解決方案幾乎是正確的。只是不要忘記考慮以下兩種情況：1） $ m_0 $ 和 $ m_1 $ 可能是一樣的，那麼 $ A $ 將不得不猜測秘密位 $ b $ 盲目地；2) $ B $ 可能會返回其他消息，例如， $ B $ 碰巧回來 $ m_1 $ 給予時 $ E_k(m_0) $ ， 然後 $ A $ 的輸出將是錯誤的。請注意，1) 和 2) 僅以可忽略的機率發生。

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