PRG 指數擴 展

我剛剛開始閱讀偽隨機生成器，我遇到了 PRG 的這個定義：

$ G_n : {0,1}^n \rightarrow {0,1}^{l(n)}, \quad \text{ where $l(n)$ is a polynomial} $

有沒有理由 $ l(n) $ 必須是多項式的？如果它是指數函式，會不會有更好的安全保證？僅僅因為偽隨機性定義中的對手也是機率多項式時間的對手。

這裡有兩個問題。第一個是，具有指數輸出長度的 PRG 不再是有效的（即多項式時間）算法，因為它甚至需要指數時間來寫入其輸出。

第二個問題是任何這樣的算法都是不安全的。針對 PRG 的區分器接收到一個字元串 $ y\in {0,1}^{\ell(n)} $ ，即 PRG 的輸出，或均勻隨機字元串。它需要高效，即它必須在其輸入長度上按時間多項式執行。如果輸入長度是指數的，說 $ \ell(n)=2^n $ ，那麼它可以在時間多項式中執行 $ 2^n $ . 這足以列舉所有可能的種子值 $ s\in{0,1}^n $ , 計算 $ y’:=G_n(s) $ 並檢查是否 $ y’ = y $ . 因為對於均勻隨機 $ y $ ，這種種子存在的機率（真的）可以忽略不計，這會導致微不足道的區分攻擊。

引用自：https://crypto.stackexchange.com/questions/86269