PRG 上的合路器
我在問自己以下問題，但我不確定是否是這種方式：
我有第一個 $ PRG $ ： $$ G_1: {0,1}^{\lambda} \rightarrow {0,1}^{\lambda+1} $$
現在我想建構第二個 $ PRG $ 其結構如下：
$$ G: {0,1}^{\lambda} \rightarrow {0,1}^{2\lambda} $$
這樣（ $ || $ 是連接符號，對於 $ x_i $ 我假設它是 $ i^{th} $ 一點 $ x $ ：
$$ G(x) = x_1||x_2||…||x_{\lambda-1}||G_1(x) $$
我需要證明 $ G $ 是一個 $ PRG $ 如果 $ G_1 $ 是。但我在想如果我能展示第三個 $ PRG $ 這樣： $$ G_1 (x)=x_1||x_2||…x_{\lambda/2}||G_2(x_{\lambda/2}||x_{(\lambda/2)+1}||…||x_{\lambda}) $$
現在我的問題是：因為我假設 $ G1 $ 是一個 $ PRG $ ，我不能修改它嗎？我的意思是我不能做我想做的事情 $ G_2 $ ?
如果我繼續踩 $ PRGs $ ( $ G_2, G_3, … $ ) 在實踐中它仍然是一個 $ PRG $ 因為它是 $ x $ 選擇作為函式的輸入與統一但字元串無法區分，對嗎？
我不認為 $ G $ 完全是PRG。考慮以下區分符 $ D $ ，它知道描述 $ G $ , $ G_1 $ , 並給定一個字元串 $ s = x_1||x_2|| …|| x_{2\lambda} $ ：
- 鑑別器計算 $ h = G_1(x_1|| …|| x_{\lambda-1}||0) $ 和 $ h’ = G_1(x_1||…|| x_{\lambda-1}||1) $ .
- $ D $ 輸出 1 如果有的話 $ s = x_1||…||x_{\lambda-1}||h $ 或者 $ s = x_1||…||x_{\lambda-1}||h’ $ , 否則為 0
現在應該違反偽隨機性的性質 $ D $ , 因為一個隨機字元串 $ r \in {0,1}^{2\lambda} $ 應該很少滿足 $ D(r)=1 $ .
Katz & Lindell 關於 PRG 的現代密碼學簡介部分的引述：
**種子及其長度。**偽隨機生成器的種子類似於加密方案使用的密鑰，並且——就像在加密密鑰的情況下一樣——種子 $ s $ 如果我們願意，必須統一選擇，並對任何對手保密 $ G(s) $ 看起來隨機。從上面對暴力攻擊的討論中可以明顯看出，另一個重要的點是 $ s $ 必須足夠長，以便列舉所有可能的種子是不可行的。在漸近意義上，這是通過將種子的長度設置為等於安全參數來解決的，因此對所有可能的種子進行窮舉搜尋需要指數時間。在實踐中，種子長度 n 至少必須足夠大，以使在時間 2n 中執行的蠻力攻擊是不可行的。