區分器是什麼有正式的定義嗎？

我經常在書籍或論文中閱讀（多項式有界）區分符。儘管從名稱和直覺來看，區分器是什麼和做什麼都有些清楚，但我問自己是否有一個具體的正式定義。儘管這個概念被頻繁使用，但我找不到一個。

區分器是任意算法。事實上，我們不想形式化任何關於區分器的東西（除了它的輸出是一個位，儘管我們甚至不需要這樣做）。在定義中，我們要求任何區分器都不能以不可忽略的機率成功。因此，這應該適用於任何算法。

當然，我們確實指定了區分器的複雜度等級（機率多項式時間或非均勻多項式時間）。

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

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