是否存在 CPA 安全的確定性私鑰加密方案？
我假設不可能有這樣的方案，因為 CPA 安全性等同於多重加密的 CPA 安全性，並且對手可以區分 $ (\mathsf{Enc}_k(m_0),\mathsf{Enc}_k(m_0)) $ 和 $ (\mathsf{Enc}_k(m_0),\mathsf{Enc}_k(m_1)) $ 如果 Enc 是確定性的，則不存在 CPA 安全的確定性對稱加密方案。
但是，我看不出對手如何僅將一種加密與另一種加密區分開來。
CPA 不可區分性實驗 $ \mathsf{PrivK}_{\mathcal A,\Pi}^{\mathsf{cpa}}(n) $ :
讓 $ \Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec}) $ 是任何加密方案， $ \mathcal A $ 任何對手，以及 $ n $ 安全參數。
- 關鍵 $ k $ 是通過執行生成的 $ \mathsf{Gen}(1^n) $ .
- 對手 $ \mathcal A $ 給定輸入 $ 1^n $ 和 oracle 訪問 $ \mathsf{Enc}_k(\cdot) $ ，並輸出一對消息 $ m_0 $ , $ m_1 $ 長度相同。
- 一個統一的位 $ b \in {0, 1} $ 被選中，然後是密文 $ c \leftarrow \mathsf{Enc}_k(m_b) $ 被計算並給予 $ \mathsf A $ .
- 對手 $ \mathcal A $ 繼續擁有 oracle 訪問權限 $ \mathsf{Enc}_k(\cdot) $ , 並輸出一點 $ b’ $ .
- 實驗定義為 $ 1 $ 如果 $ b’ = b $ ， 和 $ 0 $ 否則。
CPA-安全的定義：
一種私鑰加密方案 $ \Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec}) $ 在選擇明文攻擊下具有不可區分的加密，或者是CPA 安全的，如果對於所有機率多項式時間的對手 $ \mathcal A $ 有一個可以忽略的函式 $ \mathsf{negl} $ 這樣 $$ \text{Pr}[\mathsf{PrivK}_{\mathcal A,\Pi}^{\mathsf{cpa}}(n) = 1] \leq \frac{1}{2} + \mathsf{negl}(n), $$ 其中機率取代了使用的隨機性 $ \mathcal A $ ，以及實驗中使用的隨機性。
總結 fkraiem 的評論，CPA-secure 加密方案不能是確定性的。
原因很簡單：攻擊者面臨的挑戰是區分加密的 $ m_0 $ 和 $ m_1 $ ，但他也可以訪問加密預言機（他可以根據他想要的任何輸入查詢預言機！）。如果加密方案每次在相同的明文上查詢時都會產生相同的密文，那麼攻擊者可以簡單地向 oracle 請求加密 $ m_0 $ 和加密 $ m_1 $ ，並比較哪一個等於給定的挑戰密文。