建設的必要條件nnn至p(n)p(n)p(n)偽隨機發生器nnn至n+1n+1n+1發電機？
給定多項式時間確定性算法 $ G_1:{0,1}^n \rightarrow {0,1}^{n+1} $ , 考慮函式 $ G:{0,1}^n \rightarrow {0,1}^{p(n)} $ 構造如下：
- 讓 $ s \in {0,1}^n $ 是輸入種子並表示 $ s =s_0 $ .
- 對於每一個 $ i = 1,\ldots,p(n) $ , 計算 $ (s_i,\sigma_i) = G_1(s_{i-1}) $ .
- 輸出 $ (\sigma_1,\ldots,\sigma_{p(n)}) $ .
現在，我們知道如果 $ G_1 $ 是一個偽隨機生成器，那麼 $ G $ 也是一個偽隨機生成器 - 即為了建構 $ G $ 產生一個偽隨機發生器就足夠了 $ G_1 $ 成為一個偽隨機生成器。
我的問題如下：是否也有必要 $ G_1 $ 是偽隨機發生器？換句話說，是不是真的 $ G $ 是一個偽隨機生成器當且僅當 $ G_1 $ 是一個偽隨機生成器——即是否有可能證明如果 $ G_1 $ 不是偽隨機生成器，那麼 $ G $ 不是偽隨機生成器嗎？
更一般地說，如果上述情況不正確，則給定 $ G_1 $ ，有沒有辦法構造一個確定性的多時間算法 $ G:{0,1}^n \rightarrow {0,1}^{2n} $ 這樣 $ G $ 是一個偽隨機生成器當且僅當 $ G_1 $ 是偽隨機發生器？
或者，如果這是不可能的，給定一個排列 $ f:{0,1}^n \rightarrow {0,1}^n $ , 是否可以構造確定性多項式時間算法 $ G:{0,1}^n \rightarrow {0,1}^{2n} $ 這樣 $ G $ 是一個偽隨機生成器當且僅當 $ f $ 是單向排列嗎？
對於上下文：我正在從單向函式完成偽隨機函式的經典構造的每一步：
OWF $ \rightarrow $ 硬核謂詞 $ \rightarrow $ $ n+1 $ PRG $ \rightarrow $ $ 2n $ PRG $ \rightarrow $ PRF
我們知道，如果 $ f $ 是單向排列，那麼這種構造產生一個偽隨機函式。我想了解是否有必要 $ f $ 是這種構造起作用的單向函式 - 即，如果給我一個反轉對手 $ f $ ，我可以為上述構造給出的偽隨機函式構造一個對手嗎？更一般地，給定一個排列 $ f $ ，我想構造一個偽隨機函式，當且僅當 $ f $ 是單向排列，我很好奇偽隨機函式的典型構造是否具有此屬性。
沒必要，那 $ G_1 $ 是一個PRG。
讓 $ G_2: {0,1}^{n-1} \rightarrow {0,1}^n $ 是一個 PRG，定義 $ G_1: {0,1}^n \rightarrow {0,1}^{n+1} $ 作為 $$ \begin{align*} G_1(s_1||\ldots||s_n) := 1||G_2(s_2||\ldots||s_n). \end{align*} $$ 並考慮區分器 $ \mathcal{D}1 $ ，它返回第一位 $ w_1 $ ，當給定 $ n+1 $ 位串 $ w := w_1||\ldots||w{n+1} $ 作為輸入。
為了 $ s_1 \leftarrow {0,1}^n $ 和 $ r_1 \leftarrow {0,1}^{n+1} $ 我們有 $$ \begin{align*} \Big|\text{Pr}[\mathcal{D}_1(G_1(s_1))=1] - \text{Pr}[\mathcal{D}_1(r_1)=1]\Big| = \Big|1 - \frac{1}{2}\Big| = \frac{1}{2} > \mathsf{negl}(n), \end{align*} $$ 這意味著 $ G_1 $ 不是PRG。
儘管如此，我們仍然可以證明， $ G $ 是一個 PRG，通過對“現代密碼學導論”中定理 6.20 的 Katz’ 和 Lindell 的證明稍作修改。（我假設您熟悉它，因為您使用的是完全相同的符號。）
我們構造一個區分器 $ \mathcal{D}_2 $ 為了 $ G_2 $ 使用另一個區分符 $ \mathcal{D} $ 為了 $ G $ ， 和 $$ \begin{align*} \Big|\text{Pr}[\mathcal{D}(G(s))=1] - \text{Pr}[\mathcal{D}(r)=1]\Big| =: \epsilon(n). \end{align*} $$
讓 $ \mathcal{D}_2 $ 行為如下，當給定一個 $ w := w_1 || \ldots || w_n \in {0,1}^n $ 作為輸入。
- $ i \leftarrow {0, \ldots, p(n) - 1} $
- $ r \leftarrow {0,1}^i $
- $ p := G(1||w) $
- 構造位串 $ w’ $ 作為的串聯 $ r $ , $ w_{n} $ 和第一個 $ p(n) - i - 1 $ 位 $ p $ .
- 輸出 $ \mathcal{D}(w’) $
您可以輕鬆驗證以下兩個語句：
- 如果 $ i = 0 $ 和 $ w = G_2(s_2) $ 為了 $ s_2 \in {0,1}^{n-1} $ ， 然後 $ w’ = G(s) $ 為了 $ s = b||s_2 $ 和 $ b \in {0,1} $ .
- 如果 $ i = p(n) -1 $ 和 $ w = r_2 \leftarrow {0,1}^n $ ， 然後 $ w’ \leftarrow {0,1}^{p(n)} $ .
使用與 Katz 和 Lindell 相同的論點，我們得到 $$ \begin{align*} \mathsf{negl}(n) \geq \frac{\epsilon(n)}{p(n)} && \Longrightarrow && \mathsf{negl}(n) \geq \epsilon(n), \end{align*} $$ 意思就是 $ G $ 是一個PRG。
類似的論點適用於您的其他兩個問題。