Pseudo-Random-Generator
PRG - 理解定義
說 $ G $ 是一個 $ PRG $ 將其輸入擴展一位，因此我們定義：
$$ G’(x_1||x_2)=G(x_1)||G(x_2) $$ 練習表明證明 $ G’ $ 也是一個PRG。
現在這是我的困惑。 $ PRGs $ 被定義為隨機種子作為輸入。
但作為對手我知道 $ G $ . 因此對於 $ x\in{0,1}^* $ 我總是可以輸入 $$ x||x $$ 現在，我可以檢查兩半是否 $ G’(x||x)=G(x)||G(x) $ 是平等的，並且知道這不是隨機的。
在解決方案中，他們假設 $ x_1,x_2 $ 也必須隨機選擇。但是，對手的意義何在？
不得允許對手選擇種子。 （否則，定義將無法滿足，因為攻擊者可以檢查返回的字元串是否為 $ G(x) $ 為他們選擇的種子 $ x $ .)
這背後的基本原理是 PRG 的種子被理解為（某種）密鑰，攻擊者在任何威脅模型中都不能知道或選擇它。（畢竟，這就是密鑰是secret的原因。請注意，當攻擊者拿到密鑰時，任何密碼術都會輕易破壞。）
根據定義，函式 $ G\colon {0,1}^n\to{0,1}^{\ell(n)} $ 和 $ \ell(n)>n $ 如果任何多項式時間的對手無法區分真正隨機的 $ y\in{0,1}^{\ell(n)} $ 和偽隨機字元串 $ G(x) $ 對於隨機種子 $ x\in{0,1}^n $ 除了可以忽略的機率。
直覺地說，這意味著 PRG 的輸出在使用足夠隨機的種子初始化時，與真正的隨機字元串“一樣好”。