Pseudo-Random-Generator
如果GGG是PRG，是F(小號)=G(小號)||克（s¯)F(s)=G(小號)||G(s¯)F(s)=G(S)||G(bar{s})一定是PRG？
讓 $ G $ 是一個偽隨機生成器，並且 $ F(s)=G(s)||G(\bar{s}) $ （在哪裡 $ \bar{s} $ 表示的按位補碼 $ s $ ）， 是 $ F $ 一定是PRG？
我的直覺說這是一個 PRG，很明顯 $ G(s) $ 和 $ G(\bar{s}) $ 本身就是 PRG，將它們連接起來不應該影響隨機性，而是只會增加擴展因子（輸出長度）。但是，我覺得存在一個反例 $ G(s) $ 和 $ G(\bar{s}) $ 本身是安全的，但將它們連接起來會失去一些隨機性，即使它們可預測（因為 $ F(s) $ 和 $ F(\bar{s}) $ 應該看起來很相似）。我想了一些例子 $ G(s)=H(s) \oplus H(\bar{s}) $ ， 在哪裡 $ H(s) $ 是一個 PRG（並且 $ G(s) $ 這裡也仍然是 PRG），但我不確定這是否會導致 $ F(s) $ 不是PRG。任何想法將不勝感激！
$ F(s)=G(s)\mathbin|G(\bar{s}) $ 不一定是PRG。我們將建構一個反例。
認為 $ H(t) $ 是一個PRG。
現在定義 $ G(t\mathbin|0)=H(t) $ 和 $ G(t\mathbin|1)=H(\bar t) $ . 這 $ G(s) $ 因此定義的是一個帶有輸入寬度的 PRG $ |t|+1 $ . 然而 $ F(s)=G(s)\mathbin|G(\bar s) $ 不是 PRG，因為它的兩半總是相等的。