給出一個區分器來區分 PRP 和 RPO

我已經理解了證明 PRP 是 PRF 的證據，除了可以忽略不計的機率 $ \frac{q(n)^2}{2^{-l(n)}} $ . 我的計算表明，同樣的論點，可能帶有少量數學細節，可以表明 PRF 可以被視為 PRP（如果我們忘記了 PRP 需要是 DPT 可計算排列而 PRF 不需要的事實）。

現在我偶然發現了這個問題：

證明有一個 PPT 對手將 PRP F 與 RFO 區分開來，具有可忽略不計但非零的優勢。

我的問題是在區分端給出程式碼。讓我來形容一下：

1. 愛麗絲挑選 $ b \stackrel{u}{\in} {0,1} $ . 如果 $ b = 0 $ 將 RFO 發送給 Eve，如果 $ b = 1 $ 將 PRP 發送給 Eve $ F $ .
2. 這裡我需要描述一下區分器是什麼 $ D $ 做。

我想我應該做 $ D $ 查詢他收到多項式次數的預言機 $ q(n) $ 由其效率界限定義。但是施工的細節是什麼？

詞彙表

1. PRP = 偽隨機排列
2. PRF = 偽隨機函式
3. RFO = 隨機函式預言機
4. RPO = 隨機排列預言機

從某種意義上說，RFO 本質上應該生成一個隨機函式，即當一個新輸入（以前從未見過）時，它將為該輸入分配一個隨機輸出。RPO 與此構造類似，但確保輸出之前沒有用於其他輸入，因此生成的函式是單射的。

由於您沒有指定函式的域是什麼，我將假設我們正在討論表單的函式 $ f:{0,1}^n \to {0,1}^n $ .

區分器的工作原理如下：

1. 讓 $ q(n) $ 是一些多項式。
2. 選擇 $ q(n) $ 許多不同的元素 $ {0,1}^n $ . 給他們打電話 $ x_1,\dots,x_q $ .
3. 查詢每個 $ x_i $ 到 oracle 並將結果記錄為 $ y_i $ .
4. 如果存在任何 $ y_i=y_j $ 和 $ i\neq j $ ， 輸出 $ 0 $ , 否則輸出 $ 1 $ .

如果預言機是一個 PRP，那麼根據定義它是一個排列（即沒有衝突）並且因為 $ x_i\neq x_j $ 對所有人 $ i\neq j $ 區分器輸出 $ 1 $ 有機率 $ 1 $ .

如果預言機是一個真正的隨機函式，那麼每個 $ y_i $ 是均勻且獨立分佈的。至少發生一次碰撞的機率 $ q(n) $ 隨機抽樣的元素 $ {0,1}^n $ 是$$ 1-\prod_{i=1}^{q(n)}\frac{2^n-i}{2^n} \geq 1 $$因此區分器將輸出 $ 1 $ 有機率 $ 1-\varepsilon(n) $ 對於一些 $ \varepsilon(n)\geq0 $ .

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