使用先前位的異或將偽隨機生成器擴展一位
是否有可能通過簡單地附加所有先前位的異或來將其輸出擴展 1 位的偽隨機生成器？
我知道偽隨機生成器的輸出與隨機無法區分，那麼附加位是否仍保留其偽隨機屬性？或者這不是偽隨機的，因為最後一位是確定性的？
這允許一個容易區分的攻擊：讓 $ R\colon;{0,1}^n\to{0,1}^m $ 表示一個偽隨機生成器，也就是說，如果 $ x $ 和 $ y $ 是均勻分佈的隨機變數 $ {0,1}^n $ 分別 $ {0,1}^m $ , 沒有多項式時間算法可以區分 $ R(x) $ 從 $ y $ 以不可忽略的機率。
讓 $ R’\colon;{0,1}^n\to{0,1}^{m+1} $ 表示其輸出如問題中指定的那樣擴展的生成器。攻擊者，給定一個黑盒子 $ z $ 包含 $ R’(x) $ （為了 $ x $ 均勻隨機 $ {0,1}^n $ ） 或者 $ y $ （均勻隨機 $ {0,1}^{m+1} $ )，然後可以計算奇偶校驗（異或） $ z $ 的第一個 $ m $ 位並將其與最後一位進行比較 $ z $ . 如果它們匹配，攻擊者會猜到 $ z $ 是 $ R’(x) $ , 否則他猜 $ z $ 是 $ y $ .
很明顯，使用這種策略，攻擊者在給定的情況下總是能正確猜測 $ R’(x) $ . 在另一種情況下，當給定 $ y $ , 該策略的成功機率恰好為 $ \frac12 $ ，因為隨機位串的最後一位也是隨機的，因此可能以相等的機率匹配（在這種情況下攻擊者猜錯）或不匹配（在這種情況下攻擊者猜對）奇偶校驗。
因此，攻擊者的成功機率為
$$ \frac12\cdot1+\frac12\cdot\frac12=\frac34 $$ 在區分 $ R’ $ 從隨機，這是不可忽略的大於 $ \frac12 $ .
一個不太直接的論點是：如果問題中描述的擴展是可能的，則可以多次迭代構造而不會失去偽隨機性屬性。但是，在第一次這樣的擴展之後，輸出的奇偶性始終為零，因此所有進一步附加的位都是零。顯然，輸出總是以一串零結尾的生成器不是偽隨機的。