證明一個函式是PRF？
讓 $ F\colon K×K \rightarrow {0,1}^{128} $ 做一個 $ \mathit{PRF} $ 功能。是 $ F’ $ 一個 $ \mathit{PRF} $ ?
$$ \begin{equation*} F’(x) = \begin{cases} 0^{128} & \quad \text{if $x = 0$} \ F_k(x) & \quad \text{otherwise} \end{cases} \end{equation*} $$ 編輯：
我知道 $ \mathit{PRF} $ 超過 $ (K,X,Y) $ 是一個雙射函式 $ F\colon K×K \rightarrow Y $ 滿足以下性質：
- 效率： $ ∀k ∈ K, x ∈ X, ∃ $ 計算算法 $ F_k(x) $
- 偽隨機性： $ ∀ $ $ \mathit{PPT} $ $ D $ 算法， $ ∃ $ 一個可忽略的函式，因此：
$ |\Pr[D(r) = 1] - \Pr[D(F(.)) = 1]| < \mathit{negl}(n) $ 在哪裡 $ r \leftarrow^R \mathrm{Func}(X,Y), k \leftarrow^RK $
您已經列出了 PRF 的兩個屬性，即效率和偽隨機性。
功能 $ F’ $ 顯然是有效的 $ F $ 高效且 $ F’ $ 來電 $ F $ 在幾乎所有情況下。它不存在的一種情況也是一個非常容易計算的情況。
所以，這就留下了偽隨機性。該屬性基本上是在說假設您有一個黑匣子。您可以為其提供輸入（x 和 k 值）並查看輸出。如果存在機率多項式時間 (PPT) 算法，該算法可以在給定輸出的情況下決定黑盒是否實現 $ F’ $ 與隨機函式相比，您沒有 PRF。另一方面，如果不存在這樣的 PPT 算法，那麼您確實有一個 PRF。
所以，最終，問題是你是否可以建構一個可以區分輸出的 PPT 算法 $ F’ $ 來自隨機函式的輸出。如果您可以建構這樣的算法（在這種情況下相當容易），那麼您已經證明它不是 PRF。
但是，讓我們假設問題的設置方式不同，實際上 $ F’ $ 是一個PRF。你將如何證明這一點？您不能遍歷所有可能的 PPT 算法並表明它無法區分 $ F’ $ 來自隨機函式的輸出。相反，你會假設 $ F’ $ 不是 PRF，並說明這將如何得出以下結論 $ F $ 也不是 PRF。換句話說，矛盾的證明。