為什麼這個函式是偽隨機的（PRF）？
首先，我想澄清這不是家庭作業。我在學習即將進行的測試時遇到了這個問題（這裡如何證明函式 F 不是偽隨機函式？ ）。
- $ F’_k(x) = F_k(0||x) || F_k(1||x) $
- $ F’_k(x) = F_k(0||x) || F_k(x||1) $
（這裡 $ || $ 代表串聯， $ F $ 是 PRF）。
我知道第二個功能不是 PRF，我自己想出了一個對手。
至於第一個功能，我閱讀評論說它是 PRF，但我找不到正式證明這一點的方法。我知道證明這類問題的方法。
我應該通過矛盾假設 $ F’_K $ 不是 PRF，即它有一個對手 $ D’ $ 區分 $ F’_K $ 和一個隨機函式 $ f’ $ 以不可忽略的機率。使用 $ D’ $ , 我應該構造一個對手 $ D $ 區分 $ F_K $ 和一個隨機函式 $ f $ 具有不可忽略的機率 - 這是一個矛盾。
我想到了以下減少構造 $ D $ :
給定一個輸入 $ x $ , 和一個 oracle 訪問 $ O $ （為了 $ F_K $ ), $ D $ 執行 $ D’ $ 上 $ O(0||x)||O(1||x) $ . 然後， $ D $ 回答什麼 $ D’ $ 答案。
- 如果 $ O=F_k $ ， 然後 $ D $ 的區分機率等於 $ D’ $ 的。
- 如果 $ O=f $ （隨機函式） -好吧，我在這里卡住了。
這不完全是你的方式，但我發現它是一種更容易處理這種結構的方法。首先，我們切換到資訊論設置，然後回到具體構造。這與證明計數器模式加密的安全性非常相似。
首先，我們替換 $ F_k $ 通過一個真正的隨機函式 $ G $ . 每一個新的輸入 $ G $ 導致均勻隨機輸出 $ G(x) \in {0,1}^{n} $ . 現在我們有了對應的
$$ G’(x) = G(0|x)|G(1|x),. $$ 由於每次呼叫 $ F_k’ $ 給你兩個免費電話 $ F_k $ ， 我們有 $$ \mathbf{Adv}^{\mathrm{prf}}{F_k’}(D) \le \mathbf{Adv}^{\mathrm{prf}}{F_k}(D’) + |\mathbf{Pr}[D(G’) = 1] - \mathbf{Pr}[D($) = 1]| ,, $$ 對於區分者 $ D’ $ 最多執行 $ 2q $ 查詢，通過三角不等式（第一項是 $ \Delta_D(F_k’, G’) $ ，第二個是 $ \Delta_D(G’, $) $ . $ $ $ 表示理想的隨機函式）。 我們現在的目標是區分 $ G’ $ 從一個均勻隨機函式 $ {0,1}^{n-1} $ 至 $ {0,1}^{2n} $ , 來確定上述不等式的第二項。請注意，輸入 $ G $ 適當的域分離：之間永遠不會有任何衝突 $ 0|x $ 和 $ 1|x $ 對於任何不同的 $ x $ .
更具體地說，採用任何一組（不同的）查詢 $ ((x_1, y_1), (x_2, y_2), \dots, (x_q, y_q)) $ ， 在哪裡 $ y_i = \mathcal{O}(x_i) $ . 的機率 $ G’(x_1) = y_1 $ , $ G’(x_2) = y_2 $ , $ \dots $ , $ G’(x_q) = y_q $ 是 $ \left(\frac{1}{2^{n}}\frac{1}{2^{n}}\right)^q = 2^{-2nq} $ . 隨機函式的機率也是 $ 2^{-2nq} $ ，因為每個輸出都有獨立的機率 $ 2^{-2n} $ .
優勢的定義是
$$ |\mathbf{Pr}[D(F) = 1] - \mathbf{Pr}[D($) = 1]|,, $$ 對於任何區分器 $ D $ . 由此我們得出結論，任何攻擊者的優勢 $ G’ $ 是 $ 0 $ ，因為它具有與隨機函式完全相同的機率分佈。所以我們得出結論 $$ \mathbf{Adv}^{\mathrm{prf}}{F_k’}(D) \le \mathbf{Adv}^{\mathrm{prf}}{F_k}(D’) + 0 ,. $$
構造區分器 $ D $ 為了 $ F $ 從區分者 $ D’ $ 為了 $ F’ $ . $ D $ 執行 $ D’ $ . 什麼時候 $ D’ $ 要求在字元串上呼叫它的神諭 $ x $ , $ D $ 在弦上呼叫它的神諭 $ 0||x $ 和 $ 1||x $ ，連接答案，並將結果字元串提供給 $ D’ $ 作為它的答案。最後 $ D $ 輸出什麼 $ D’ $ 輸出。
很清楚
- $ D $ 如果在多時間內執行 $ D’ $ 做;
- 如果 $ D $ 的神諭工具 $ F $ ，其成功機率與 $ D’ $ 當它的神諭實現 $ F’ $ ; 和
- 如果 $ D $ 的預言機實現了一個隨機函式，其成功機率與 $ D’ $ 當它的神諭也這樣做時。
PS：區分符沒有給出任何輸入字元串，只有安全參數。它根據其定義選擇輸入字元串。