計算不可區分性

在演算法分析和密碼學中，如果沒有高效的演算法可以區分兩個分布族之間的差異（或區分出兩者的概率可以忽略），那麼兩個分布族被稱為是計算不可區分（英語：computationally indistinguishable）的。

正式定義

令$\scriptstyle \{D_{n}\}_{n\in \mathbb {N} }$和$\scriptstyle \{E_{n}\}_{n\in \mathbb {N} }$ 是兩個分布集合，下標n（通常指輸入的長度）是安全參數。如果對於任意的非均勻概率多項式時間演算法 A，以下值是一個n上的可忽略函式，則我們說它們在計算上是不可區分的：

$\delta (n)=\left|\Pr _{x\gets D_{n}}[A(x)=1]-\Pr _{x\gets E_{n}}[A(x)=1]\right|$

記為$D_{n}\approx E_{n}$。 換言之，在$n\to \infty$時，每個高效的演算法A的行為在D_n和E_n上不會有明顯變化。對計算不可區分性的另一種解釋是，主動嘗試區分這兩個集合的多項式時間演算法不能實現目標：任何這樣的演算法的表現與單純猜測相比，優勢可以忽略不計。

相關概念

定義中隱含的條件是演算法$A$必須根據其中一個分布的單個樣本中決定。有人可能會設想這樣一種情況，即演算法為了區分兩個分布，可以根據需要訪問儘可能多的樣本。因此，兩個分布無法由多項式時間演算法通過觀察多個樣本區分的情形，被稱為無法通過多項式時間採樣區分（英語：indistinguishable by polynomial-time sampling）。 如果多項式時間演算法可以在多項式時間內生成樣本，或者可以訪問為其生成樣本的隨機預言機，那麼多項式時間採樣的不可區分性等同於計算不可區分性。

外部連結

• Yehuda Lindell. Introduction to Cryptography （頁面存檔備份，存於網際網路檔案館）
• Donald Beaver and Silvio Micali and Phillip Rogaway, The Round Complexity of Secure Protocols (Extended Abstract), 1990, pp. 503–513
• Shafi Goldwasser and Silvio Micali. Probabilistic Encryption. JCSS, 28(2):270–299, 1984
• Oded Goldreich. Foundations of Cryptography: Volume 2 – Basic Applications. Cambridge University Press, 2004.
• Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007

本條目含有來自PlanetMath《computationally indistinguishable》的內容，著作權遵守創用CC協定：署名-相同方式共享協定。