安全性降低似乎錯誤地表明非 PRF 是 PRF

這是一個眾所周知的練習，甚至已經在這裡發布過。

我理解證明和反駁這兩個論點 $ F’ $ 和 $ \bar{F} $ 是 PRF，正如我在下面解釋的那樣，但是，證明似乎也適用於以下情況 $ \bar{F} $ 不是PRF！

---

認為 $ F $ 是 PRF，那麼我們要證明以下每個函式都是 PRF 或者舉一個反例

1. $ F’_k(x) = F_k(0\mathbin|x) \mathbin| F_k(1\mathbin|x) $
2. $ \bar{F}_k(x) = F_k(0\mathbin|x) \mathbin| F_k(x\mathbin|1) $

（這裡 $ \mathbin| $ 表示串聯）

這 $ \bar{F} $ from (2.) 不是 PRF，因為區分器可以計算 $ \bar{F}_k(00…0) = F_k(000…0) \mathbin| F_k(00…01) $ 和 $ \bar{F}_k(00…1) = F_k(00…01) \mathbin| F_k(00…011) $ 並檢查前半部分的位是否 $ \bar{F}_k(00…1) $ 等於位的後半部分 $ \bar{F}_k(00…0) $ . 對於製服 $ f $ ，這種情況發生的機率可以忽略不計。

現在，對於 $ F’ $ 由(1.)，由於它是一個PRF，我們可以構造一個區分器 $ D $ 為了 $ F $ 給定一個區分符 $ D’ $ 為了 $ F’ $

1. $ D’ $ 發送 $ x $ 至 $ D $
2. $ D $ 查詢兩倍的預言機 $ F $ 要得到 $ f(0\mathbin|x) $ 和 $ f(1\mathbin|x) $ （在哪裡 $ f $ 是統一的或 $ F_k $ )
3. $ D $ 發送 $ f’(x) = f(0\mathbin|x) \mathbin| f(1\mathbin|x) $ 至 $ D’ $
4. $ D’ $ 輸出一點 $ b’ $
5. $ D $ 輸出相同的位

的優勢 $ D $ 反對 $ F $ 是一樣的優點 $ D’ $ 在區分 $ F’ $ （除非我遺漏了什麼），但是 $ \operatorname{Adv}(D’) $ 是不可忽略的假設，所以 $ \operatorname{Adv}(D) $ 是不可忽略的，這與事實相矛盾 $ F $ 是一個PRF。

所以， $ F’ $ 也是 PRF（證明結束）

現在是我感到困惑的地方……似乎如果我們替換上面證明中的步驟（2.）和（3.），那麼 $ D $ 獲得 $ f(0\mathbin|x)\mathbin|f(x\mathbin|1) $ , 那麼我們得到一個證明 $ \bar{F} $ （來自第 (2.) 項）是 PRF，儘管我們知道它不是 PRF！

那麼我錯過了什麼？

或者證明有什麼問題？

的優點 $ D $ 和 $ D’ $ 不一樣。回想一下，區分器的優勢是它在“真實”和“理想”實驗中接受的機率之間的差異，其中它的預言分別是所討論的函式（帶有隨機密鑰）或均勻隨機函式。所以，要分析 $ D $ 的優勢並將其與 $ D’ $ ，你必須考慮這兩種實驗。

在這種情況下，當 $ f $ 是均勻隨機函式 ( $ D $ 的理想實驗）， $ f’ $ 不是均勻隨機函式。的確， $ f’ $ 具有攻擊所尋找的相同屬性（兩個特定函式輸出的兩半相等）。正如您所注意到的，這不太可能適用於隨機函式。所以，在這種情況下 $ D’ $ 沒有義務像在自己的理想實驗中那樣行事。特別是，它可能以與真實實驗相同的機率接受，使得 $ D $ 的優勢為零。（事實上，如果 $ D’ $ 是聲明的攻擊。）

換句話說：雖然提議的減少 $ D $ 確實正確地“模擬”了真實的實驗 $ D’ $ ，它不能正確模擬理想實驗。所以，我們不能斷定 $ D $ 具有相同的優勢 $ D’ $ .

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