證明沒有完全 CPA 安全的方案
一個私鑰加密方案 Π = (Gen, Enc, Dec) 在選擇明文攻擊下具有完全不可區分的加密，如果對於所有機率多項式時間對手 A，它認為 Pr$$ PrivK_cpa(n) = 1 $$= 1/2。我需要證明沒有加密方案可以滿足這個定義。
在選擇明文攻擊下無法區分的完美：Pr$$ PrivK_cpa = 1 $$= 1/2
牽連
在竊聽者面前無法區分的完美：Pr$$ PrivK_eav = 1 $$ = 1/2.
這反過來又暗示了完美的保密性：**Pr$$ Enc_K (m) = c $$= 公關$$ Enc_K (m’) = c $$**對於所有 m，m’ 來自 M，c 來自 C。
我的論點在這一點上正確嗎？如果是這樣，請您告訴我，我現在如何才能找到在選擇明文攻擊下完全保密和完全無法區分的方案之間的矛盾？我應該使用完美保密的定義（上面提到的）來發現矛盾，還是應該使用 |K| 的事實？應該 >= |M|?
我看到了這篇文章有沒有完美的 CPA 安全之類的東西？有同樣的問題，但它無濟於事，因為Enc是機率性而不是確定性的事實主要被討論。
在選擇明文攻擊下無法區分的完美：Pr$$ PrivK_cpa = 1 $$= 1/2
我的論點在這一點上正確嗎？
不，因為這個問題沒有詢問“完美的不可區分性”（這將包括計算上無限的對手），只是對機率性多時間對手的不可區分性。
假設對手可以訪問公鑰，那麼這是一個獲得優勢的對手 $ > 1/2 $ :
- 選擇一組隨機硬幣；通過發送他們 $ Gen $ 功能
- 將生成的公鑰與提供的公鑰進行比較
- 如果它們相同，則使用生成的私鑰解密密文並使用生成的明文做出決定。
- 如果它們不相同，請選擇一個隨機位並將其用作輸出。
現在，如果這個過程選擇了一組恰好與原始密鑰生成過程中使用的硬幣相同的隨機硬幣，那麼這總是會得到正確的答案（或者，至少，如果公鑰系統有很高的機率）解密失敗機率小）；如果不是，那麼這會給出至少 1/2 的正確答案（“至少”是因為可能有其他隨機硬幣組會產生相同的公鑰；這些也會給出正確答案）。
因此，如果 $ \lambda $ 密鑰生成過程中使用了隨機硬幣，這給出了正確答案的機率 $ 2^{-\lambda} + 0.5(1 - 2^{-\lambda}) > 1/2 $
這個概念並沒有真正的意義，因為達到完美保密的方式是在給定的密文中沒有足夠的資訊來說明有關消息的任何資訊，因此如果沒有密鑰，攻擊者將一無所知。
這是資訊論的安全性，是無界的。
如果我們侵入一個加密預言機，只要有足夠的時間，對手就會通過嘗試所有方法來找到消息，直到一個成功。
我們可以添加額外的約束，例如製作對手 ppt，但我們不再談論資訊論安全性。