從一個長度加倍的偽隨機數中構造一個特定的長度加倍的偽隨機數發生器
讓 $ G $ 是一個長度加倍的偽隨機生成器（即，對於任何 $ n\in \mathbb{N} $ 並且對於任何 $ s\in{0, 1}^n $ 它認為 $ G(s)\in{0, 1}^{2n} $ ）。你能構造一個長度加倍的偽隨機生成器嗎 $ H $ 這樣 $ H(0^n)= 0^{2n} $ 對於任何 $ n\in \mathbb{N} $ ?
定義 $ \forall s\in {0,1}^{n} \ : H(s)=G(s)\oplus G(0^n)\implies H(0^n)=G(0^n)\oplus G(0^n)=0^{2n} $
現在，我們將通過反證法證明 $ H $ 確實是一個偽隨機生成器。
假設我們不知道存在一個對手 D（PPT 算法），因此對於每個多項式 p(n)：
$ |Pr_{s\leftarrow{0,1}^n}[D(H(s))=1]-Pr_{r\leftarrow{0,1}^n}[D(r)=1]|>1/p(n) $
現在，定義對手 $ D’(v):=v\oplus G(0^n) $ 對於 PRG" $ G $ “，我們差不多完成了： $ |Pr_{s\leftarrow{0,1}^n}[D’(G(s))=1]-Pr_{r\leftarrow{0,1}^n}[D’(r)=1]|= $ $ |Pr_{s\leftarrow{0,1}^n}[D(G(s)\oplus G(0^n))=1]-Pr_{r\leftarrow{0,1}^n}[D((r)\oplus G(0^n)=1]|= $ $ |Pr_{s\leftarrow{0,1}^n}[D(H(s))=1]-Pr_{r\leftarrow{0,1}^n}[D(r)=1]|>1/p(n) $
$ \blacksquare $