Pseudo-Random-Generator
我如何證明/反駁一個構造產生一個安全的 PRG？
讓 $ G:{0,1}^{} \mapsto {0,1}^{} $ 成為一個安全的 PRG。證明或反駁以下構造也產生安全 PRG。
$$ G’(k) = G(k||0), $$ 在哪裡 $ || $ 表示兩個字元串的連接。 我知道證明/反駁這種結構通常涉及通過簡化或反例來證明。直覺上，我會說 $ G’ $ 是一個安全的 PRG，因為我們只修復了一點輸入，這不應該使輸出可區分（在多項式時間內）。但是，由於某種原因，我找不到合適的減少，因為我不知道如何 $ w \in {0,1}^{*} $ 和一個區分器 $ D’ $ 為了 $ G’ $ 可用於構造區分器 $ D $ 為了 $ G $ .
也是 $ G’ $ 一個安全的 PRG？如果是，我如何構造一個有效的歸約，如果不是，如何區分 $ G’ $ 工作？
我不知道這是否合適，但我更喜歡提示，它指向正確的方向而不是完整的解決方案。
如果存在安全 PRG，則存在安全 PRG，
其輸出的最後一位始終等於其輸入的最後一位。
如果 G 的輸出的最後一位總是等於 G 的輸入的最後一位，那麼按照
問題中所述構造的函式 G’ 將不是安全 PRG。