安全的偽隨機發生器
假設 $ G : {0,1}^k \rightarrow {0,1}^{2k} $ 是一個安全的偽隨機生成器。描述以下每個嘗試建構偽隨機生成器的問題 $ k $ -位種子和 $ 4k $ -位輸出：（這裡 $ s $ 是種子和 $ \mathbin| $ 表示連接）
$ G_1(s) = G(s) \mathbin| G(0^{k}) $
$ G_2(s) = G(s) \mathbin| G(r) $ 在哪裡 $ r $ 是一個新鮮的隨機 $ k $ -位值；
$ G_3(s) = G(s) \mathbin| (G(s) \oplus 1^{2k}) $
$ G_4(s_{L} \mathbin| s_{R}) = G(s_{L} \mathbin| s_{R}) ,\mathbin|, G(s_{R} \mathbin| s_{L}) $ 在哪裡 $ |s_{L}| = |s_{R}| = \frac{k}{2} $ ;
$ G_5(s_{L} \mathbin| s_{R}) = G(s_{L} \mathbin| 0^{ k \over 2}) ,\mathbin|, G(0^{k \over 2} \mathbin| s_{R}) $ 在哪裡 $ |s_{L}| = |s_{R}| = \frac{k}{2} $ .
這是一種家庭作業和討論問題。我不知道如何或從哪裡開始。我只是想檢查是否存在 PPT 區分器 D 是否有更大的可協商價值。所以它不能是一個偽隨機生成器。指出正確的證明方向（任何提示）會有所幫助。
公式為 $ G_2 $ 甚至沒有定義一個函式（將在不同的呼叫中為相同的種子提供不同的輸出）。
下半場 $ G_1(s) $ 是恆定的，不是很隨機，是嗎？
$ G_3(s) $ 也可以很容易地與隨機區分開來，因為它的後半部分是前半部分的按位補碼。
為了 $ G_1 $ 和 $ G_3 $ 給出一個區分器應該是相當容易的，你只需要分析它在兩種情況下的成功機率。
正如 Henno 已經說過的， $ G_2 $ 根本不滿足 PRG 的定義。
為了 $ G_4 $ 和 $ G_5 $ 使用您基於另一個 PRG 建構的特定 PRG 來實例化構造是有幫助的（您還必須證明您的構造實際上是 PRG，通常通過歸約來證明）。然後你證明這允許你建構一個區分器。提示：嘗試使用將 1 或 2 位種子洩漏到其輸出的 PRG 來實例化它。