Pseudo-Random-Function
證明一個函式不是PRF？
讓 $ G $ $ PRG $ 和 $ G’(s) $ 等於第一個 $ n $ -位 $ G(s) $ ， 在哪裡 $ |s| = n $ . 顯示 $ F_k(x) = G’(k) ⊕ x $ 不是一個 $ PRF $ .
我的嘗試：
讓我們假設一個 $ k $ 和 2 條消息 $ x_1 $ 和 $ x_2 $ . 因此對於 $ x_1 $ 我有 $ F_k(x_1) = G’(k) ⊕ x_1 $ ， 為了 $ x_2 $ 我們有 $ F_k(x_2) = G’(k) ⊕ x_2 $ . 如果攻擊者這樣做 $ F_k(x_1) ⊕ F_k(x_2) $ 他得到 $ x_1 ⊕ x_2 $ . 然後他可以簡單地 $ XOR $ 那是 $ x_1 $ 或者 $ x_2 $ 然後從中獲取消息。
我不知道這是否是證明這一點的正確方法。如果這是表明函式不是的正確方法，你能給我任何提示嗎 $ PRF $ ，也許我必須做一個矛盾的證明？
編輯：
我也知道一個 $ PRG $ 一定是不可預測的，如果是的話那就不好了，所以對於函式 $ F $ 使用 $ G’ $ 作為 $ PRG $ 這總是第一個 $ n $ -位 $ G $ 這不好，因為它違反了偽隨機性屬性。我不知道這是否正確或有幫助。
對於要成為 PRF 的東西，機率多項式時間算法必須不可能將其與隨機函式區分開來。您在嘗試中註意到的區分符是正確的，因為隨機函式不具有該屬性（異或兩次呼叫具有相同的鍵但不同的 x 值，您得到兩個 x 值的異或）。
作為旁注，這些筆記在 PRF 方面非常好。尤其是 3.3 和 3.4。