了解 PRG 的區分符

鑑於以下偽隨機生成器的定義，我無法理解“鑑別器”D 究竟輸出了什麼，什麼時候輸出？

$ D $ 輸出一點 $ b \in \lbrace 0,1 \rbrace $ . 什麼時候 $ b = 0 $ ， 代表著 $ D $ 猜測它給出的字元串是從 $ \lbrace 0 , 1 \rbrace^{\ell(n)} $ ， 當……的時候 $ b = 1 $ ， 代表著 $ D $ 相信它給出的字元串是由 PRG 產生的 $ G $ （或相反亦然）。

如前所述，區分器D輸出一點。

我想補充一點，優點是衡量區分器的表現。假設您有兩個在計算上無法區分的分佈，那麼 $ adv_D $ 接近 0 可以忽略不計。另一方面，如果兩個分佈易於區分，則 $ adv_D $ 將接近 1。

在您的公式中， D 的優勢是：

$$ adv_D = |Pr(D(X)=1) - Pr(D(Y)=1)| $$. 如果分佈無法區分，則區分器無法成功完成其工作，即區分兩個分佈。然後，無論輸入是分佈 X 還是分佈 Y，D 的輸出都是相同的。

如果您需要進一步閱讀，我強烈建議您閱讀 Rogaway 的論文“On the Role of Definitions in and Beyond Cryptography”。在那裡他清楚地解釋了區分器的概念。

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