安全 PRF 的錯誤證明
免責聲明，這不是家庭作業；我在這裡找到了問題陳述：此 PRF 的安全性
重申問題：
給定 $ F $ 具有輸入大小的安全 PRF $ \lambda $ . 定義 $ F’ $ 作為 $ F’(k,x\mathbin|x’) = F(k, 0\mathbin|x)\oplus F(k, 1\mathbin|x’) $ 和 $ x $ 和 $ x’ $ 的 $ \lambda-1 $ 位。是 $ F’ $ 一個安全的 PRF？
給出的答案是否定的，很明顯 PRF $ F’ $ 不安全。但我試圖提供一個虛假的證據 $ F’ $ 是安全的（但不是）並且看不到證明出錯的步驟。
首先，重述反例：
更具體地說，為了簡單起見，讓 $ F’_k $ 成為一個鍵控 PRF $ F’ $ 帶鑰匙 $ k $ 來自無鍵 PRF 家族 $ {F’ : {0, 1}^{2(\lambda - 1)} \times {0, 1}^{2(\lambda - 1)} \to {0, 1}^{\lambda - 1} } $ 並考慮以下 $ \mathsf{PPT} $ 對手 $ \mathcal{A} $ . $ \mathcal{A} $ 要求對預言機進行評估 $ \mathcal{O} $ 上 $ x_0 \mathbin| x_1 $ , $ x_0 \mathbin| x_2 $ , $ x_1 \mathbin| x_2 $ ， 和 $ x_1 \mathbin| x_1 $ . 然後 $ \mathcal{A} $ 計算前三個 oracle 輸出的 XOR，並檢查 XOR 是否等於第四個 oracle 輸出。觀察如果 $ \mathcal{A} $ 被授予 oracle 訪問權限 $ F’_k $ ， 然後 $ \mathcal{A} $ 收到$$ \begin{align*} F’_k (x_0 \mathbin| x_1) &= F_k (0 \mathbin| x_0) \oplus F_k (1 \mathbin| x_1)\ F’_k (x_0 \mathbin| x_2) &= F_k (0 \mathbin| x_0) \oplus F_k (1 \mathbin| x_2)\ F’_k (x_1 \mathbin| x_2) &= F_k (0 \mathbin| x_1) \oplus F_k (1 \mathbin| x_2)\ F’_k (x_1 \mathbin| x_1) &= F_k (0 \mathbin| x_1) \oplus F_k (1 \mathbin| x_1) \end{align*} $$ 並且前三個的 XOR 正好等於第四個並且 $ \mathcal{A} $ 給定預言機的這種情況，以機率 1 正確猜測。在隨機情況下， $ \mathcal{O} $ 等於某個真正的隨機函式 $ U $ 並收到 $ U(x_0 \mathbin| x_1) \oplus U (x_0 \mathbin| x_2) \oplus U (x_1 \mathbin| x_2) $ 不太可能等於 $ U (x_1 \mathbin| x_1) $ ，即機率可以忽略不計。因此 $ \mathcal{A} $ 是區分符。
這是我試圖證明陳述的“虛假證明” $ F’ $ 是一個安全的 PRF”，我非常感謝您澄清哪些步驟不正確。
認為 $ F_k’ $ 不是 PRF。那麼存在一個 $ \mathsf{PPT} $ 區分器 $ \mathcal{A}’ $ 和一個常數 $ c $ 和自然數 $ n \in \mathbb{N} $ 這樣 $ \mathcal{A}’ $ 區分 $ F_k’ $ 來自具有顯著優勢的真正隨機函式 $ \geq \frac{1}{n^c} $ . 我們現在建構一個區分器 $ \mathcal{A} $ （一台可以訪問的預言機 $ \mathcal{O} $ 來自 PRF 家族 $ {F} $ 或真正的隨機函式 $ {U} $ ） 為了 $ F $ 如下。 $ \mathcal{A} $ 執行 $ \mathcal{A}’ $ . $ \mathcal{A}’ $ 要求查詢表格 $ x_0 \mathbin| x_1 $ 如上所述和 $ \mathcal{A} $ 然後查詢oracle $ \mathcal{O} $ 和 $ 0 \mathbin| x_0 $ 和 $ 1 \mathbin| x_1 $ , 計算異或 $ \mathcal{O}(0 \mathbin| x_0) \oplus \mathcal{O}(1 \mathbin| x_1) $ ，並將其發送到 $ \mathcal{A}’ $ . $ \mathcal{A}’ $ 將多次查詢多項式 $ \mathcal{A}’ $ 的輸入長度所以 $ \mathcal{A} $ 將不得不製造兩倍的數量，即 $ O((2(\lambda-1))^l) $ 查詢一些常數 $ l $ ，這仍然是多項式 $ \lambda $ . 最後， $ \mathcal{A} $ 將輸出任何內容 $ \mathcal{A}’ $ 輸出。然後注意 $ \Pr[\mathcal{A}^{{F}}(1^{\lambda}) = 1] = \Pr[\mathcal{A}’^{{F’}}(1^{2(\lambda -1)}) = 1] $ 自建造以來 $ \mathcal{A} $ 有效模擬預言機訪問 $ {F’} $ 什麼時候 $ \mathcal{O} = F_k $ 對於一些 $ k $ . 如果 $ \mathcal{O} = {U} $ 對於真正的隨機函式 $ U $ ， 然後 $ \Pr[\mathcal{A}^{{U}}(1^{\lambda}) = 1] = \Pr[\mathcal{A}’^{{U}}(1^{2(\lambda -1)}) = 1] $ 因為 $ U(0 \mathbin| x_0) \oplus U(1 \mathbin| x_1) $ 仍然是真正隨機的。然後是新對手的顯著優勢 $ \mathcal{A} $ 也是不可忽略的，因此 $ F $ 不是安全的 PRF。
同樣，我在這個“虛假證明”中哪裡出錯了？
問題在於最後一個等式： $$ Pr[\mathcal{A}^{{U}}(1^{\lambda})=1]=Pr[\mathcal{A’}^{{U}}(1^{\lambda})=1] $$
它不成立，因為 $ \mathcal{A}^{{U}} $ 是結果 $ \mathcal{A}’ $ 使用 $ U $ 代替 $ F_k $ . 這實際上相當於 $ F’ $ 並將通過 $ \mathcal{A}’ $ ，所以我們得到 $$ Pr[\mathcal{A}^{{U}}(1^{\lambda})=1]=Pr[\mathcal{A’}^{{F’(U)}}(1^{\lambda})=1]\neq Pr[\mathcal{A’}^{{U}}(1^{\lambda})=1] $$