是F(ķ,f(ķ,x))F(ķ,F(ķ,X))f(K, f(K, x))偽隨機函式？
給定一個 PRF $ f : {0, 1}^n \times {0, 1}^n \rightarrow {0, 1}^n $ ， 是 $ f(K, f(K, x)) $ PRF，也是？
我的預感是建構一個類似於 Feistel 密碼但具有屬性的 PRP $ f(K, f(K, x)) = x $ , 並用 PRP/PRF 切換引理反駁該陳述。但是，我還沒有找到具有上述所需屬性的具體實例。
任何人都可以分享一些提示嗎？謝謝！
我正在回复：
“如果 B 訪問的預言機是真正隨機的，如何證明預言機 B 為 A 構造的也是真正隨機的？” 我想知道是否存在解決（或避免）這個問題的方法。
這是一個“好”的東西，因為它不是你可以推到地毯下的東西。具體來說，讓 $ f_k(\cdot) $ 是一個隨機函式，所以對於任何 $ x_i $ ，你有那個 $ y_i = f_k(x_i) $ 是均勻隨機的（並且獨立於任何其他 $ y_j $ ）。如果我們知道 $ z_i = f_k(y_i) $ 也是均勻隨機的，並且獨立於所有其他 $ z_j $ 的，我們就完了！
是這樣嗎？答案差不多。具體來說，只要 $ \forall i : y_i\neq y_j $ ，不難證明所有 $ z_i $ 是統一隨機的（並且是獨立的），所以一切都很順利。
直覺地說，一個隨機函式可以表示為一個查找表（這是最簡潔的表達方式），因此計算 $ f_k(0) $ 我們查找一些值 $ U_0 $ . 此表中的條目是均勻隨機的自變數。我們可以考慮使用這個查找表 $ f_k $ 計算 $ f_k\circ f_k $ 通過進行兩次查找（如此精確地按照您期望的方式）。
現在考慮計算 $ q $ 價值觀 $ ((f_k\circ f_k)(1),\dots, (f_k\circ f_k)(q)) $ . 這將是統一的隨機值，但存在它們之間存在某種依賴關係的風險。具體來說，如果 $ f_k(i) = f_k(j) $ 為了 $ i\neq j $ , 然後我們就有了 $ (f_k\circ f_k)(i) = (f_k\circ f_k)(j) $ , 所以隨機變數 $ (f_k\circ f_k)(i) $ 和 $ (f_k\circ f_k)(j) $ 將是相關的（因此不是獨立的）。根據我們的查找表類比，事件 $ f_k(i) = f_k(j) $ 發生意味著我們的查找表 $ f_k\circ f_k $ 最終擁有 $ i $ 和 $ j $ 指向查找表中的相同“槽” $ f_k $ ，這就是問題的原因。
所以，我們想限制機率 $ \Pr[\exists (i,j)\in[q]^2\setminus{(i,i)\mid i\in[q]} : f_k(i) = f_k(j)] $ . 這可以通過生日界限來完成（如果你不熟悉它，你應該查找它），並且可以通過 $ q^2/2^n $ ，這就是評論中提到的術語的來源。