Computational indistinguishability

Template:Short description In computational complexity and cryptography, two families of distributions are computationally indistinguishable if no efficient algorithm can tell the difference between them except with negligible probability.

Formal definition

Let $\{D_n{\}}_{n\in \mathbb{N}}$ and $\{E_n{\}}_{n\in \mathbb{N}}$ be two distribution ensembles indexed by a security parameter n (which usually refers to the length of the input); we say they are computationally indistinguishable if for any non-uniform probabilistic polynomial time algorithm A, the following quantity is a negligible function in n:

$\delta (n)=|\underset{x\leftarrow D_n}{Pr}[A(x)=1]-\underset{x\leftarrow E_n}{Pr}[A(x)=1]|.$

denoted $D_n\approx E_n$. In other words, every efficient algorithm A's behavior does not significantly change when given samples according to D_n or E_n in the limit as $n\to \mathrm{\infty }$. Another interpretation of computational indistinguishability is that polynomial-time algorithms actively trying to distinguish between the two ensembles cannot do so: that any such algorithm will only perform negligibly better than if one were to just guess.

Related notions

Implicit in the definition is the condition that the algorithm, $A$, must decide based on a single sample from one of the distributions. One might conceive of a situation in which the algorithm trying to distinguish between two distributions, could access as many samples as it needed. Hence two ensembles that cannot be distinguished by polynomial-time algorithms looking at multiple samples are deemed indistinguishable by polynomial-time sampling.Template:Rp If the polynomial-time algorithm can generate samples in polynomial time, or has access to a random oracle that generates samples for it, then indistinguishability by polynomial-time sampling is equivalent to computational indistinguishability.Template:Rp

Quantum computational indistinguishability

The notion of computational indistinguishability has been generalized to quantum information, where the objects being distinguished are quantum states rather than classical probability distributions. A pair of efficiently preparable quantum states is said to be computationally indistinguishable if no quantum polynomial-time (QPT) algorithm can distinguish them with non-negligible advantage, even though the states may be distinguishable in principle by computationally unbounded measurements. This notion, known as an efficiently indistinguishable (EFI) pair, provides a quantum analogue of classical computational indistinguishability.

Quantum computational indistinguishability has become a central concept in quantum cryptography and quantum complexity theory. It underlies several modern quantum cryptographic primitives, including one-way state generators (OWSGs), pseudorandom quantum state generators (PRSGs), quantum commitments, and computational quantum money (see also Quantum cryptography).

External links

• 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