為什麼這個 PRF 不安全？

所以，我在 Coursera 上學習 Dan Boneh 的 Cryptography I，我在解決練習時正在查看 PRF 的安全性定義，我在 Dan Boneh 為 2020 年冬季課程的家庭作業中偶然發現了這個問題。表示 F1 不是一個安全的 PRF，但我無法理解它。

如果 $ k_1 $ 和 $ k_2 $ 來自同一個密鑰空間，我假設它們是獨立選擇的，為什麼這個 PRF 不安全？是不是因為我們可以假設 $ k_1 $ 可能等於 $ k_2 $ ? 然後查詢 $ x = y = 0^n $ , 這樣我們就可以爭論如下：

• 收到 $ z = G((k_1,k_2),(x,y)) $ ， 在哪裡 $ G $ 或者是 $ F_1 $ 或隨機函式。
• 輸出 $ b = 1 $ 如果 $ z = 0^n $ 和 $ 0 $ 否則，那麼

$ F_1((k_1,k_2),(0^n,0^n)) = F(k_1, 0^n) ⊕ F(k_2,0^n) = 0^n $

這將帶來不可忽視的優勢 $ (1-2^{-n}) $ ?

對不起，如果它沒有意義，這是一個我仍在努力理解的概念。

這是攻擊： 您查詢：

• $ F_1((k_1,k_2),a,b) $ 並得到 $ y1 $
• $ F_1((k_1,k_2),c,b) $ 並得到 $ y2 $
• $ F_1((k_1,k_2),a,d) $ 並得到 $ y3 $

現在你可以計算

• $ F_1((k_1,k_2),c,d) = y_1 \oplus y_2 \oplus y_3 $

但是如果 PRF 是安全的，這個值應該是不可預測的：

證明：

• $ y_1 \oplus y_2 \oplus y_3= (F(k_1,a)\oplus F(k_2,b))\oplus( F(k_1,c)\oplus F(k_2,b))\oplus( F(k_1,d)\oplus F(k_2,b))= F(k_1,c)\oplus F(k_2,d)=F_1((k_1,k_2),c,d) $

x1 和 x2 沒有正確混合在一起，您可以預測組合的輸出。特別是我們得到了這個（只有 2 個查詢）

$ F_1((0,0),(0,1)) = F_1((0,0),(1,0)) $

但是如果你使用不同的隨機Ks仍然沒有多大幫助，你仍然有一個問題可以查詢一些相關點並預測一個新點，即提示中的4個點，我將停止完整的解決方案。

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