關於證明偽隨機隨機發生器是單向函式的問題

我一直在“現代密碼學導論”一書中查看這個命題和證明，有點困惑。圖片附在底部）。

為什麼我們不乘 $ 2^{-n} $ 經過 $ \varepsilon $ .

確實，在生成器範圍內的機率是 $ 2^{-n} $ 但即使我們在那裡，A給出正確逆的機會也不 $ 1 $ .

等式不應該是 $ \leq \varepsilon ~ 2^{-n} $ 反而？

之所以這樣分析，是因為要正確得出比這裡寫的要多得多的結論是很棘手的。問題是一個均勻隨機的字元串 $ w $ 在圖像中 $ G $ 不一定像分佈 $ G(x) $ 對於均勻隨機 $ x $ . 我們知道 $ \mathcal{A}(y) $ 成功 $ \varepsilon $ 隨機輸入的機率 $ y=G(x) $ 後一種形式，但這並沒有告訴我們太多關於它在前一種情況下的行為。

更準確地說，條件是 $ w $ 處於形像中 $ G $ ，它在該圖像中是均勻隨機的。這並不一定意味著 $ \mathcal{A}(w) $ 輸出原像集的一個元素 $ G^{-1}(w) = {x : G(x)=w} $ 有機率 $ \varepsilon $ . 例如， $ G $ 可能是高度“不規則的”，這意味著一些原像集比其他原像集大得多。但 $ \mathcal{A} $ 可能只會成功地反轉，比如說，那些 $ y $ 具有非常大的原像集。這會給它很好的反轉機率 $ y=G(x) $ 對於均勻隨機 $ x $ , 但它在統一上反轉的機率 $ w $ 在圖像中 $ G $ 將遠低於 $ \varepsilon $ .

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