不可預測的 PRG 是安全的（Theorem Yao'82）
在 Mr Boneh 的線上課程中陳述了以下定理：
讓 $ G:K \to {0,1}^n $ 成為PRG。
“Thm”：如果 $ \forall i \in {0, … ,n-1} $ PRG $ G $ 在 pos 是不可預測的。 $ i $ ， 然後 $ G $ 是一個安全的 PRG。
而且，按照他的說法，證明這只是一個“謎題”來證明，但實際上我並沒有那麼容易看到，我現在唯一的想法就是在爭論，如果你無法預測下一點一些偽隨機字元串，那麼您無法區分該偽隨機字元串和在該位置與真正隨機字元串連接的偽隨機字元串，這是一個不錯的開始，但我不知道如何利用它。有人可以幫我參與論證嗎？非常感謝你。
PS： 在這裡您可以找到我們使用的不可預測的、安全的 PRG的定義和定理本身（儘管在我看來，從數學的角度來看，這些定義並不令人滿意）。
本講座 （PDF）在第 3 節中有解決方案。
這是我對證明的非正式解釋：
我們有一個不可預測的 PRG $ G $ . 我們想證明 $ G $ 是安全的，或者換句話說，與 $ R $
=（在餘下的證明中提到兩個分佈時， 我會用它來表示無法區分）。使用表示法 $ G_k R_{n-k} $ 意味著獲得第一個 $ k $ 位使用 $ G $ 並生成最後一個 $ n-k $ 位完全隨機，這足以表明 $ G_{i-1} R_{n-i+1} = G_{i} R_{n-i} \ \forall i $ ， 自那時候起 $ G_n = G_{n-1} R_1 = G_{n-2} R_2 … = R_n $ 通過一個簡單的歸納，和 $ G_n $ 是 $ G $ , $ R_n $ 是 $ R $ 根據定義。
所以我們想向所有人展示 $ 0 \le i \le n-1 $ , $ G_{i-1} R_{n-i+1} = G_{i} R_{n-i} $ .
為了矛盾起見，假設這對某些人不成立 $ i $ . 這意味著有一些統計測試 $ A $ 哪個可以區分 $ G_{i-1} R_{n-i+1} $ 從 $ G_{i} R_{n-i} $ ，或優勢不可忽略的統計測試。這意味著要麼 $ A $ 更可能等於 $ 1 $ 使用時 $ G_{i} R_{n-i} $ ，或更可能等於 $ 0 $ 使用時 $ G_{i} R_{n-i} $ ，不失一般性，讓我們說 $ 1 $ . 所以隨便挑一個 $ b $ 並執行 $ A(G_{i-1} b R_{n-i}) $ .
如果它返回 $ 1 $ ，那麼我們會猜到 $ b = g_i $ （自從 $ A $ 更可能等於 $ 1 $ 當第一個 $ i $ 位來自 $ G $ ); 如果它返回 $ 0 $ , 我們猜 $ b \neq g_i $ . 這只是一個猜測，但由於存在不可忽略的優勢，我們猜測正確的機率大於 $ \frac 1 2 $ 由相同的不可忽略的因素。這意味著我們可以預測 $ i $ 從第一個開始 $ i-1 $ 位，這與我們的假設相矛盾 $ G $ 是不可預測的。