Pseudo-Random-Generator
以下是PRG嗎？
讓 $ G: {0, 1}^n → {0, 1}^m $ 成為PRG。我們構造一個函式 $ G’: {0, 1}^{m + n} → {0, 1}^{2m} $ 定義如下
$ G’(x || y) = x || (G(y) ⊕ x) $
對所有人 $ x ∊ {0, 1}^m $ 和 $ y ∊ {0, 1}^n $ . （符號 || 在這裡表示二進製字元串的連接。）
是 $ G’ $ 一個PRG？
我相信它不是，但我很容易出錯。
我知道，給定一個長度為 s 的隨機字元串 $ 2m $ （分成等長的字元串 $ s_1 $ 和 $ s_2 $ ）， 那 $ s_1 $ 相當於 $ x $ ， 然後 $ s_2 \oplus x $ 相當於 $ G(y) $ . 但是由於 $ G(y) $ 無法區分 $ U_m $ ，我無法得出矛盾的結論。
我對這一切還是比較陌生，所以任何幫助將不勝感激。
我相信它不是，但我很容易出錯。
…我無法得出矛盾的結論
問題是你不能表現出這種矛盾，因為根本沒有。作為家庭作業問題的經驗法則：如果很明顯您無法證明最初的假設，請考慮您的直覺是錯誤的。
以下是一些提示，您可以如何證明這一點 $ G’ $ 實際上是一個 PRG，在矛盾的證明中：
- 讓我們假設 $ G’ $ 不是PRG，這意味著區分 $ \mathcal{D} $ 存在。
- 輸入為 $ \mathcal{D} $ 是一個均勻隨機或形式為的元素 $ x||(G(y)\oplus x) $ ，然後它有一些不可忽略的優勢 $ \epsilon $ .
- 我們想為 $ G $ . 所以作為輸入，我們得到一個元素，它要麼來自均勻隨機分佈，要麼來自圖像 $ G $ .
- 一般來說，如果 $ a $ 是均勻隨機的，那麼 $ a \oplus b $ 也是均勻隨機的 - 只要這是真的 $ b $ 獨立於 $ a $ . 這包括固定 $ b $ 也 $ b $ 獨立於任何分佈繪製。