證明以下私鑰加密方案不是 CPA-secure
考慮以下私鑰加密方案：共享密鑰為 k $ \in $ {0,1} n。加密消息 m $ \in $ {0,1} n，選擇隨機 r $ \in $ {0,1} n和輸出 $ (r, F_r(k)\oplus \overline{m}) $ ， 在哪裡 $ F $ 是分組密碼並且 $ \overline{m} $ 是 m 的逐位補碼。這個方案CPA安全嗎？
在這個問題中按位恭維的重要性是什麼？
此外，該方案似乎確實是 CPA 安全的，因為它正在執行 $ \oplus $ 一個消息字元串和一個隨機字元串（當我們為每個 m 選擇一個隨機 r 時，它會隨著每條消息而改變）
正如 aventurin 所指出的，所寫的方案不是 CPA 安全的。
正如 poncho 的評論所指出的，它甚至無法抵禦已知的明文攻擊：
認識任何一對 $ (m,c) $ 和 $ c = (c_1,c_2) = (r,F_r(k)\oplus \bar{m}) $ 給攻擊者 $ k $ 直接地：
$$ k = F^{-1}_{c_1}(c_2 \oplus \bar{m}) $$
在這個問題中按位恭維的重要性是什麼？
沒有什麼。按位補碼是一個固定的雙射映射，每個人都可以對每個輸入和任一方向進行評估。關於安全性，（在這種情況下）這與身份功能一樣有用。
在你寫的評論中：
.. $ F $ 作為OWF … PRF，道歉…
在原來的問題 $ F $ 是一個分組密碼。如果我們考慮 $ F $ 作為 PRP（分組密碼的通用模型），上述內容仍然成立：PRP 上的攻擊者通常會同時獲得兩者的預言機 $ F(x) $ 和 $ F^{-1}(x) $ .
然而，如果我們假設一個 PRF，攻擊者不會得到預言機 $ F^{-1} $ ，因此上述攻擊不再起作用。但是構造也不能簡化為 PRF 的安全定義：通常您會假設您的方案有攻擊者，然後表明該攻擊者也可以破壞 PRF 屬性。但：
- 在 PRF 遊戲中，攻擊者可以在任意輸入上查詢函式 $ x $ 為了 $ F(x) $ . 答案總是來自真正的隨機函式或 $ F_k(x) $ 對於一個固定的 $ k $ .
- 在您的方案中，攻擊者可以為同一個請求多個密文 $ k $ ，但這會導致以下形式的多個查詢 $ F_r(x) $ 和 $ x = k $ 固定的。
那是不合適的，而且我們不太可能證明或反駁這種說法——不做進一步的假設。
如果我們考慮 $ k $ 和 $ x $ 作為函式的兩個輸入，隨機函式不使用 $ k $ ，則標準 PRF 僅允許對第二個輸入進行查詢。在您的情況下，您需要的是雙重 PRF，其中攻擊者可以訪問兩個輸入中的更改。您可以找到有關此的更多資訊：
- 如何構造具有特定屬性的偽隨機數（在 crypto-SE 上）
- 來自標准假設的對稱和對偶 PRF：HMAC 假設的通用驗證（Bellare 和 Lysyanskaya，2015 年）