如何證明一個函式不是偽隨機的？
我目前正在參加一門密碼學課程，該課程使用的是 Katz 和 Lindell 的書。我正在與要求證明的練習作鬥爭，如下所示：
令 G(k) 是一個帶有 |k| 的 PRG = n，而 G’(k) 將 G(k) 的輸出截斷到前 n 位。證明 $ F_k(x) = G’(k) \oplus x $ 不是偽隨機的。
我唯一能說的是 $ F_k() $ 具有非常特殊的結構，不是隨機選擇的 $ 1/2^n $ .
有什麼提示嗎？
在回答實際問題之前，我將提供一些一般性建議。
- 無論是在課堂上還是您正在閱讀的教科書上，都要注意這一點，這一點很重要。如果學習如何解決這些練習是本課程的一個關鍵目標，那麼這些解決方案很可能已經在課堂上進行了詳細的討論。此外，您的教科書也有證明範例，在這種情況下，它有一個在概念上與您在此處給出的範例相同（其中 $ G’(k) $ 被替換為 $ k $ ).
- 了解和理解您的定義至關重要。在這裡，您想證明某個函式族不是偽隨機函式（即，不滿足偽隨機函式族的定義），但不清楚您是否理解這意味著什麼（您沒有在您的問題）。如果您希望能夠證明某個構造滿足或不滿足它，您必須理解這個定義。
- 從廣義上講，您似乎缺乏通常所說的數學成熟度，這不是對任何特定數學的了解，而是看清如何在假設和結論之間的數學論證中連接點的能力。事實上，一個“數學不成熟”的人的一個明顯跡像是，他們僅僅看到“證明”這個詞就猶豫不決，並且除了陳述假設之外似乎無法取得任何進展。不幸的是，密碼學並不是寫證明的最佳場所，因為它是一項非常複雜的業務（密碼學的大多數結果旨在證明這是不可能的做某事），你很快就會感到不知所措。出於這個原因，抽象代數或實分析是更好的訓練場，即使你不打算為了它們而學習它們。
回到主要問題，我們首先需要知道並理解偽隨機函式族的定義。我們考慮一個函式 $ F $ 映射每對字元串 $ (k,x) $ 與第三個字元串等長 $ y $ 長度與 $ k $ 和 $ x $ . 對於任何字元串 $ k $ 長度 $ n $ ，我們注意到 $ F_k $ 映射的函式 $ n $ -位串 $ x $ 到 $ n $ -位串 $ y $ （即， $ F_k(x) = F(k,x) $ . 字元串 $ k $ 被稱為鑰匙。我只陳述偽隨機函式的定義，沒有冗長的討論（可以在書中找到）。
功能 $ F $ 如果滿足以下兩個條件，則上面定義的為偽隨機。
- **易於計算。**有一個確定性多項式時間算法 $ C $ 這樣 $ C(k,x) = F_k(x) $ 對於任何字元串 $ k $ 和 $ x $ 等長。
- **偽隨機。**對於每個機率多項式時間算法 $ D $ , 每個多項式 $ p $ 並且都足夠大 $ n $ ， 我們有 $$ \left|\mathrm{Pr}[k \gets {0,1}^n : D^{F_k}(1^n) = 1] - \mathrm{Pr}[f \gets \mathrm{Func}_n : D^f(1^n) = 1]\right| < \frac{1}{p(n)}. $$
我的符號如下：
- $ {0,1}^n $ 是所有長度字元串的集合 $ n $ .
- $ \mathrm{Func}_n $ 是所有函式的集合 $ {0,1}^n $ 對自己。
- $ k \gets X $ ， 在哪裡 $ X $ 是一個有限集，意味著 $ k $ 是隨機且均勻地從 $ X $ .
- $ D^f $ 表示算法 $ D $ 當給予 oracle 訪問該功能時 $ f $ . 那是， $ D^f $ 可以獲得 $ f(x) $ , 對於任何 $ x $ 它的選擇，僅以一次操作為代價。
- $ \mathrm{Pr}[A : P(x)] $ 表示機率 $ P(x) $ 執行後保持 $ A $ .
在這裡，您要證明給定函式不是偽隨機的，這意味著它不滿足上述定義。換句話說，它滿足其邏輯否定。由於定義的邏輯否定並非完全無關緊要，因此最好明確說明。通常，會滿足“易於計算”的條件，因此我們只給出偽隨機條件的否定。
一個函式 $ F $ 如上所述，如果存在機率多項式時間算法，那麼容易計算的不是偽隨機的 $ D $ 和一個多項式 $ p $ 這樣對於無限多 $ n $ ， 我們有
$$ \left|\mathrm{Pr}[k \gets {0,1}^n : D^{F_k}(1^n) = 1] - \mathrm{Pr}[f \gets \mathrm{Func}_n : D^f(1^n) = 1]\right| \ge \frac{1}{p(n)}. $$
我們終於可以定義算法了 $ D $ （我們用 $ \mathcal{O} $ oracle 計算的函式）。輸入時 $ 1^n $ , 進行如下。
- 計算 $ y_0 = \mathcal{O}(0^n) $ .
- 計算 $ y_1 = \mathcal{O}(1^n) $ .
- 如果 $ y_0 \oplus y_1 = 1^n $ ， 輸出 $ 1 $ . 否則，輸出 $ 0 $ .
我們必須確定機率 $ D $ 輸出 $ 1 $ 在每種情況下：當 $ \mathcal{O} $ 是 $ F_k $ 對於一個統一選擇的 $ k $ , 當它是一個統一選擇的 $ f $ .
- 在第一種情況下，無論什麼 $ k $ 是，我們有 $ y_0 = G’(k) \oplus 0^n = G’(K) $ 和 $ y_1 = G’(K) \oplus 1^n $ . 因此我們有 $ y_0 \oplus y_1 = G’(k) \oplus G’(k) \oplus 1^n = 1^n $ ， 和 $ D $ 輸出 $ 1 $ 有機率 $ 1 $ .
- 對於第二種情況，我們注意到 $ D $ 輸出 $ 1 $ 當且僅當 $ y_1 = y_0 \oplus 1^n $ . 如果 $ f $ 是一個完全隨機的函式， $ y_1 $ 在所有人中被選中 $ 2^n $ 長度的字元串 $ n $ 一致且獨立於 $ y_0 $ , 所以它等於 $ y_0 \oplus 1^n $ 有機率 $ 1/2^n $ .
因此，我們終於看到了 $ n $ , 定義中大機率表達式的值等於 $ 1-\frac{1}{2^n} $ . 如果 $ n > 0 $ 這至少是 $ \frac{1}{2} $ , 所以我們可以取 $ p $ 為常數多項式 $ 2 $ .