如何從 PRF 建構週期性 PRF？
這個問題可能與這個有關，儘管結構不同。
讓我們考慮一個 PRF $ f $ . 我們定義 $ g_k $ 作為 $ g_k(x)=f(x)\oplus f(x\oplus k) $ . 是 $ g_k $ 一個 PRF，假設 $ k $ 是隨機選擇的？
我試圖證明這一點如下。讓我們考慮一個對手 $ \mathcal{A} $ 能夠區分 $ g_k $ 以及具有不可忽略優勢的 PRF。讓 $ \mathcal{R} $ 是一個可以訪問的歸約 $ \mathcal{A} $ 並想破壞 PRF 的安全性 $ f $ . 在這兩場比賽中， $ b=0 $ 表示現實世界和 $ b=1 $ 隨機世界，其中應用了真正的隨機函式，而不是 $ f $ 或者 $ g_k $ .
在遊戲開始時， $ \mathcal{R} $ 事物 $ k $ 隨機。什麼時候 $ \mathcal{A} $ 查詢 $ x $ , $ \mathcal{R} $ 查詢 $ x $ 和 $ x\oplus k $ , 異或結果並將其發送回 $ \mathcal{A} $ . 什麼時候 $ \mathcal{A} $ 返回它的猜測 $ b’ $ , $ \mathcal{R} $ 返回相同的位。
為了證明 $ \mathcal{R} $ 有一個不可忽視的優勢，我們只需要證明它完美地模擬了一個預言機實現 $ g_k $ . 在這種情況下 $ b=0 $ , 是這樣，沒有什麼區別 $ \mathcal{R} $ 從一個預言機實現 $ g_k $ . 如果 $ b=1 $ 然而， $ \mathcal{A} $ 期望得到 $ \pi(x) $ 對於隨機函式 $ \pi $ , 而它接收 $ \pi(x)\oplus\pi(x\oplus k) $ . $ \pi(x) $ 是均勻隨機的，並且根據隨機函式的定義，與 $ \pi(x\oplus k) $ ， 所以呢 $ \mathcal{R} $ 返回 $ \mathcal{A} $ 也是均勻隨機的。需要指出的是，現在 $ \pi $ 已定義在 $ x $ 和上 $ x\oplus k $ , $ \mathcal{A} $ 可以預測加密的值 $ x\oplus k $ 因為這將與 $ x $ 的。自從 $ \mathcal{A} $ 不知道 $ k $ ，這不是一個可行的策略。因此， $ \mathcal{A} $ 無法區分這些情況。
這個證明正確嗎？困擾我的是這個新的 PRF 有很多碰撞，這對於 PRF 來說是相當令人驚訝的，但我認為除非對手了解，否則無法找到它們 $ k $ .
你寫的是正確和準確的直覺。不“猜測”，對手確實無法分辨 $ k $ . 這可以形式化，而您的文章似乎缺少這種形式化。
這是一個傳統的基於遊戲的安全性證明的草圖。不失一般性，假設對手從不重複查詢。
真正的混合動力車：
- 隨機選擇 $ k $ 和一個隨機函式 $ \pi $
- 對於每個對手查詢 $ x $ , 回應 $ \pi(x) \oplus \pi(k \oplus x) $
混合1：
- 隨機選擇 $ k $ 和一個隨機函式 $ g $
- 對於每個對手查詢 $ x $ , 如果之前有查詢 $ x \oplus k $ 然後返回 $ g(x \oplus k) $ ; 否則返回 $ g(x) $
理想的混合動力車：
- 隨機選擇 $ k $ 和一個隨機函式 $ g $
- 對於每個對手查詢 $ x $ ， 返回 $ g(x) $
這裡完成證明的觀察：
- 真正的混合動力車和混合動力車#1 的分佈相同。遵循真正混合的邏輯：如果沒有事先查詢 $ x \oplus k $ , 那麼兩者 $ \pi(x) $ 和 $ \pi(x \oplus k) $ 到目前為止，它們與對手的觀點無關，因此結果完全一致。否則，結果正是來自查詢的響應 $ x\oplus k $ . 這完全符合 Hybrid #1 的邏輯。
- 在 Hybrid #1 和理想的混合中，將“壞事件”定義為對手查詢的情況 $ x $ 在先前查詢之後 $ x \oplus k $ . 請注意，兩個混合器執行完全相同的操作（給出統一/獨立的響應），直到發生此不良事件。因此，這兩個混合體在Bellare & Rogaway的術語中是“相同的直到壞的” 。根據 Bellare-Rogaway 的“基本引理”，對手的區分機率受壞事件發生在理想混合體中的機率的限制。
- 理想混合體中壞事件的機率是多少？這種混合的一個好處是對手的觀點顯然獨立於 $ k $ — 它不會改變任何想像 $ k $ 在對手完成所有查詢後被選中。如果 $ k $ 在對手的查詢之後選擇，然後我們看到如果存在查詢，就會發生錯誤事件 $ x_i, x_j $ 這樣 $ k = x_i \oplus x_j $ . 和 $ q $ 最多在那裡查詢 $ q^2 $ 的可能值 $ x_i \oplus x_j $ ， 所以 $ \Pr[bad] \le q^2/2^n $ ， 在哪裡 $ n $ 是的長度 $ x $ 的。
總體而言，對手的顯著優勢受限於 $ q^2/2^n $ .