是GGG一個安全的 PRG？
以下功能是安全 PRG 嗎？
給定 $ F $ 是一個安全的 PRG 並且 $ k $ 從密鑰空間中隨機選擇 $ K $ .
$$ G(x) = F(k,x) \oplus F(k,x \oplus 1^s) $$
我的解決方案是 $ x \oplus 1^s = x’ $ 所以 $ G(x) $ 變成 $ f \oplus f’ $ 和 $ f = F(k,x) $ 和 $ f’ = F(k,x’) $ . 清楚地 $ f $ 和 $ f’ $ 是PRG，即生成隨機字元串；和 $ \oplus $ 其中將是隨機的。
如果我錯了，請糾正我。
為了給這個問題一個應得的答案，我將重複Ricky Demer在他的評論中指出的內容：
$$ G(x \oplus 1^s) = F(k,x \oplus 1^s) \oplus F(k,x \oplus 1^s \oplus 1^s) \ \downarrow \ F(k,x \oplus 1^s) \oplus F(k,x \oplus 1^s \oplus 1^s) = F(k,x \oplus 1^s) \oplus F(k,x \oplus 0^s) \ \downarrow \ F(k,x \oplus 1^s) \oplus F(k,x \oplus 0^s) = F(k,x \oplus 1^s) \oplus F(k,x) \ \downarrow \ F(k,x \oplus 1^s) \oplus F(k,x) = F(k,x) \oplus F(k,x \oplus 1^s) \ \downarrow \ F(k,x) \oplus F(k,x \oplus 1^s) = G(x) $$ 正如tylo 評論的那樣：這表明 G 不是一個安全的 PRG。
如果，正如可以從問題中合理推斷的那樣，一個新的隨機 $ k $ 在每次呼叫時選擇 $ G $ ， 然後 $ G $ 不是偽隨機生成器，因為它不是確定性的。（根據定義，偽隨機生成器是一種確定性算法。）
如果 $ k $ 是固定的，那麼將需要更多資訊。例如，是 $ k $ 總是一樣的，或者是不同的 $ k $ 根據長度使用 $ x $ （即，是 $ G $ 實際上是一系列算法）？