證明存在不一定是一對一的 PRG
我們假設至少有一個 PRG 。現在證明有一個 PRG 像 $ G:{0,1}^{n} \rightarrow {0,1}^{l(n)} $ 這樣它不一定是一對一的。
認為 $ F \colon \lbrace 0,1 \rbrace^n \to \lbrace 0,1 \rbrace^{\ell(n)} $ 是一個安全的 PRG。創造 $ G \colon \lbrace 0,1 \rbrace^{n+1} \to \lbrace 0,1 \rbrace^{\ell(n)} $ 如下：
$$ G(b ||s) := F(s), \quad b \in \lbrace 0,1 \rbrace, s \in \lbrace 0,1 \rbrace^n. $$ $ G $ 安全 $ F $ ，並且很明顯 $ G(0||s) = G(1 || s) $ .
為了證明*“ $ G $ 安全 $ F $ “部分，考慮以下命題 $ ^ $ :
**主張。**如果存在區分符 $ \mathcal{D} $ 反對 $ G $ ，那麼我們可以創建一個區分器 $ \mathcal{D}’ $ 反對 $ F $ , 這樣
$$ | \Pr[\mathcal{D}’(U_{\ell(n)}, 1^n) = 1] - \Pr[\mathcal{D}’(F(U_n), 1^n) = 1]| > \frac{1}{poly(n)}. $$ *證明。*鑑別器 $ \mathcal{D}’ $ 接收一個字元串作為輸入 $ z \in \lbrace 0,1 \rbrace^{\ell(n)} $ . 然後他簡單地將這個字元串轉發給 $ \mathcal{D} $ 並輸出它輸出的任何東西。自從 $ z $ 分佈與區分遊戲中的完全一樣 $ \mathcal{D} $ 預計，我們特別 $ \Pr[\mathcal{D}’(F(U_n), 1^n) = 1] = \Pr[\mathcal{D}’(G(U_{n+1}), 1^n) = 1] $ ，命題如下。 $ \blacksquare $
請注意，當您意識到位時，上述命題在直覺上是正確的 $ b $ 是獨立的輸出 $ G $ . 也就是說，可以想到 $ G $ 作為第一次執行 $ F $ 在一些輸入 $ s \in \lbrace 0,1 \rbrace^n $ ，然後繪製位 $ b $ . 顯然，這不應降低 $ F $ 作為PRG。或許還應該強調的是 $ G $ 安全_ _ $ F $ , 不是更安全。也就是說，如果 $ F $ 安全級別為 $ n $ 位，然後 $ G $ 還具有安全級別 $ n $ ， 不是 $ n+1 $ 因為更長的種子可能會讓你相信。
$ ^* $ 從技術上講，該命題不成立 $ \ell(n) = n + 1 $ ， 自那時候起 $ G $ 實際上不會是PRG。但我在上面忽略了這一點，只是假設了更典型的情況 $ \ell(n) >> n $ .