Computational indistinguishability

in computer science, relationship between two families of distributions

Uses your system voice; voice and rate in settings.

Q5157322Snapshot

≈ 2 min read

Names in other languages

  • EnglishComputational indistinguishability
  • Portuguêsindistinguibilidade computacional
  • Françaisindistinguabilité calculatoire
  • slračunalniška nerazločljivost
  • 日本語計算上区別できない
  • 中文計算不可辨

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 \scriptstyle\{ D_n \}_{n \in \mathbb{N}} and \scriptstyle\{ 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) = \left| \Pr_{x \gets D_n}[ A(x) = 1] - \Pr_{x \gets E_n}[ A(x) = 1] \right|. denoted D_n \approx E_n . In other words, every efficient algorithm As behavior does not significantly change when given samples according to D n or E n in the limit as n\to \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.

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. 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.

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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368546528 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot computational-indistinguishability-587640-4a443b3ed4a72f2d · hash 4a443b3ed4a72f2d379f805581366feae05c1af825e2bf121400a9c404485243 · captured 2026-08-09 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Computational indistinguishability”, snapshot computational-indistinguishability-587640-4a443b3ed4a72f2d. https://encyclopegia.org/a/computational-indistinguishability

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.