哪些功能是 PRF？

假使，假設 $ F: {0,1 }^n \rightarrow {0,1 }^n $ 是PRF。檢查以下函式是否是 PRF：

$$ \begin{align}

1. , F_1(k,x) &= F(k,x) \oplus x \
2. , F_2(k,x) &= F\left(F(k,0^n), x\right) \
3. , F_3(k,x) &= F\left(F(k,0^n), x\right)|| F(k,x) \end{align} $$

在哪裡 $ || $ 表示連接。

---

試圖：

為了 $ 1. $ 一個標準的區別是： $ x_1 \oplus x_2 == y_1 \oplus y_2 $ ， 在哪裡 $ x_1, x_2 $ 是兩個輸入和 $ y_1, y_2 $ 分別是它們的輸出。所以 $ F_1 $ 不是 PRF。

為了 $ 2. $ 我相信 $ F(k,0^n) = k’ $ 充當鑰匙，所以 $ F_2(k’,x) = F(k’,x) $ 應該仍然是PRF。

為了 $ 3. $ 我會說兩個 PRF 的串聯仍然是一個 PRF，因為您將兩個偽隨機輸出組合在一起以產生 $ F_3 $ 的輸出。

你能驗證我的結果嗎？

不幸的是，我沒有時間詳細介紹每一個細節，但也許它足以讓你走上正軌。

1.是PRF。

證明構想：

假設我們有一個區分器 $ \mathcal{D}_{F_1} $ 區分 $ F_1 $ 來自具有不可忽略機率的隨機函式。然後我們可以構造一個區分器 $ \mathcal{D}_F $ 區分 $ F $ 來自具有不可忽略機率的隨機函式。

$ \mathcal{D}_F $ 被授予訪問預言機的權限 $ f(\cdot) $ 那要麼 $ F(k, \cdot) $ 或隨機函式 $ g(\cdot) $ .

$ \mathcal{D}F $ 執行 $ \mathcal{D}{F_1} $ 並且可以回答它的詢問。什麼時候 $ \mathcal{D}{F_1} $ 要求 $ x $ , $ \mathcal{D}{F} $ 查詢 $ f $ 上 $ x $ 並返回 $ f(x) \oplus x $ 至 $ \mathcal{D}{F_1} $ . 這模擬 $ \mathcal{D}{F_1} $ 的查詢：何時 $ f $ 是 $ F(k, \cdot) $ 我們返回 $ F(k, x) \oplus x $ , 這正是 $ F_1(k, x) $ .

什麼時候 $ \mathcal{D}_{F_1} $ 完成後，我們複製它的輸出：當它說它正在與 $ F_1 $ （輸出 = 1）， $ \mathcal{D}_F $ 輸出相同。當它說它正在與一個隨機函式（輸出 = 0）交談時， $ \mathcal{D}_F $ 輸出相同。

您現在必須證明優勢： $ |\Pr[\mathcal{D}_F^{F(k, \cdot)}(1^n)=1] - \Pr[\mathcal{D}_F^{g(\cdot)}(1^n) = 1]| $ 的 $ \mathcal{D}F $ 是不可忽略的，使用假設的優勢 $ \mathcal{D}{F_1} $ 是不可忽略的。

最後一部分通常是最難的部分，錯誤可能會悄無聲息地出現，所以要小心跳過步驟或做出無效的假設。

是一個PRF。

直覺上，這是否是 PRF 的問題似乎歸結為對手是否可以預測 $ F(k, 0^n) $ . 但是，對於不可忽略的許多人來說，這是可能的功能 $ k $ 不是 PRF。

不是PRF。

我們可以構造一個區分器 $ \mathcal{D} $ 具有不可忽視的優勢。 $ \mathcal{D} $ 被授予訪問權限 $ f(\cdot) $ , 要麼是 $ F_3(k, \cdot) $ 或隨機函式。我表示前半部分 $ z $ 作為 $ z_L $ 和下半場 $ z $ 作為 $ z_R $ .

1. $ \mathcal{D} $ 查詢 $ y^0 = f(0) $
2. $ \mathcal{D} $ 計算 $ y^1 = F(y^0_R, x) $ 對於一些隨機的 $ x $ .
3. $ \mathcal{D} $ 查詢 $ y^2 = f(x) $
4. 如果 $ y^1 = y^2_L $ , $ \mathcal{D} $ 輸出 $ f $ 是 $ F_3 $ .
5. 否則， $ \mathcal{D} $ 輸出 $ f $ 是一個隨機函式。

$ \mathcal{D} $ 具有不可忽視的優勢：如果 $ f $ 是 $ F_3 $ ， 然後 $ y^1 = y^2_L $ :

$ y^1 = F(y^0_R, x) = F(f(0^n), x) = F(F(k, 0^n), x) $

$ y^2_L = f(x)_L = F_3(k, x)_L = F(F(k, 0^n), x) $

這在什麼時候成立的機率 $ f $ 是一個隨機函式，可以忽略不計。

希望我能幫上忙！

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