PRF XORed 與它的密鑰仍然是 PRF 嗎？（總是）
$ \forall k \in {0,1}^n,m \in \mathbb{M},F_k(m) $ 定義如下： $ F_k(m) = F’_k(m) \oplus k $ . 眾所周知 $ F’_k $ 是一個PRF。注意：𝕄 是消息空間，假設密鑰 $ k $ 是由一些 Gen 算法以隨機方式生成的。
必須 $ F_k(m) $ 也是PRF？
我有一種直覺，答案是肯定的，因為它不想改變輸出的分佈，但任何類型的減少都需要密鑰才能模擬 $ F $ 並以某種方式陷入矛盾（達到我的知識水平-該主題的Ba學生第一門課程）。所以我想也許答案實際上是否定的，但可能超出我的知識……這裡有什麼好的方法？
不。
讓 $ || $ 表示串聯。讓 $ F’’ $ 成為域上的 PRF $ \mathbb{M} \times {0,1} $ . 修復任何“特殊消息” $ m^* \in \mathbb{M} $ . 考慮以下結構 $ F’ $ : 的關鍵 $ F’ $ 是 $ k_0 || k_1 $ ， 在哪裡 $ k_0 $ 是一個隨機密鑰 $ F’’ $ ， 和 $ k_1 $ 是一個相同長度的隨機字元串。輸入時 $ m \in \mathbb{M} $ , $ F’{k_0||k_1}(m) $ 輸出 $ F’’{k_0}(m||0) || k_1 $ 如果 $ m = m^* $ ， 和 $ F’’{k_0}(m||0) || F’’{k_0}(m||1) $ 否則。
首先，觀察 $ F’ $ 仍然是PRF。它直接來自於安全性 $ F’’ $ ，並通過觀察 $ k_1 $ 是真正隨機的，並且只使用一次，在特殊輸入上 $ m = m^* $ .
二、讓 $ F_{k_0||k_1}: m \rightarrow F’{k_0||k_1}(m) \oplus (k_0 || k_1) $ . 這顯然不是 PRF，因為 $ F{k_0||k_1}(m^*) $ 是一串零（隨機函式不太可能發生）。
（我忽略了關於我們對密鑰長度的假設的一些小細節，因為處理它並不難，只是有點乏味）。