給定 PRNG克（秒）G(s)G(s)， 為什麼是G(秒)||G(小號+1)G(s)||G(s+1)G(s) || G(s+1)不是PRNG？
我給了一個偽隨機生成器 $ G(s) $ , $ |s|=n $ 誰的擴張 $ l(n) $ 是 $ >2n $ . 我也知道 $ G^\prime(s) := G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor}) $ 是一個偽隨機生成器。現在函式
$ \begin{equation}L(s) := G(s) ~||~ G(s+1)\end{equation} $
和 $ || $ 串聯應該不是偽隨機生成器，我很難證明這一點。直覺上，我會認為，因為 $ L $ 將兩個不同的種子傳遞給 $ G $ 和 $ G $ 是偽隨機的， $ L $ 也必須是偽隨機的。 $ G(s+1) $ 應該與 $ G(s+1) $ 對於PRNG，不應該嗎？有人能指出我正確的方向嗎？
$ L $ 不一定是偽隨機生成器，但它可能是。因此，沒有希望證明 $ L $ 不是給定的偽隨機生成器。相反，您必須展示一個偽隨機生成器 $ G $ 這樣 $ L $ 不是偽隨機生成器。這是具有擴展因子的規範範例 $ n+1 $ .
讓 $ f $ 是一個單向排列（即，一個單射的、保持長度的單向函式）。那麼就知道下面是一個帶有擴展因子的偽隨機生成器 $ n+1 $ :
- 統一選擇種子 $ s $ 等長 $ s_1s_2\dots s_{2n} $ .
- 計算 $ b = \sum_{i=1}^n s_is_{n+i} $ （算術在 $ \mathbf{F}_2 $ ).
- 輸出 $ f(s_1s_2\dots s_n)s_{n+1}s_{n+2}\dots s_{2n}b $ .
現在，如果 $ s $ 是一致選擇的，有機率 $ 1/2 $ 它的最後一點是 $ 0 $ ， 意思是 $ s+1 $ 將只是 $ s $ 最後一點（ $ s_{2n} $ ) 翻轉，反過來這意味著 $ G(s+1) $ 將等於 $ G(s) $ 除了可能在最後兩位。因此，區分器可以檢查其輸入字元串的後半部分是否等於第一個，而不管每個字元串的最後兩位。如果字元串是 $ G(s)G(s+1) $ ，這至少有機率發生 $ 1/2 $ ，而如果字元串是真正隨機的，這很有可能發生 $ 1/2^{n-2} $ .
我想改進@fkraiem 的答案（即給出一個更簡單的結構）：
you must exhibit a pseudorandom generator G such that L is not a pseudorandom generator.取任何偽隨機數生成器 $ PRG : {0,1}^{n-1} \rightarrow {0,1}^{l(n)} $ . 現在定義 $ G : {0,1}^n \rightarrow {0,1}^{l(n)} $ 成為 $ G(x_1 | x_2 … | x_n) = PRG(x_1 | x_2 … | x_{n-1}) $ .
是的 $ G $ 忽略最後一個輸入位並將截斷的密鑰傳遞給 $ PRG $ .
$ G $ 是一個偽隨機數生成器，但是 $ L = G(s)|G(s+1) $ 不是：
讓我們構造一個區分器 $ D $ 給定一個數字 $ x = x_1 | x_2 | … | x_{2l(n)} $ 告訴它是隨機均勻採樣的，還是從 $ L $ :
# our distinguisher fun D(x): if the first half of x equals to the second half of x: return 1 else return 0如果 $ x = r $ 是一個真正的隨機數，那麼 $ \Pr[D(r) = 1] = 2^{-l(n)} $
如果 $ x = L(s) $ 是使用生成的 $ L $ 從隨機密鑰 $ s = s_1|s_2|…|s_n $ ，那麼至少有一半的時間 G(s) 與 G(s+1) 相同（因為一半的時間最後一位 $ s_n = 0 $ ) 所以至少有一半的時間是區分符 $ D $ 輸出 1，因此差異
$ |\Pr[D(G(s)) = 1] - \Pr[D(r) = 1]| \geq \frac{1}{2} - 2^{-l(n)} $ 是不可忽略的。