Computational indistinguishability is a concept from theoretical computer science and cryptography that describes a relationship between two probability distributions or random variables. Two distributions \( P \) and \( Q \) are said to be computationally indistinguishable if no polynomial-time adversary (or algorithm) can distinguish between them with a significant advantage, that is, if every probabilistic polynomial-time algorithm produces similar outputs when given samples from either distribution.
Articles by others on the same topic
Two indexed families of probability distributions and are computationally indistinguishable when every allowed efficient test has only negligible distinguishing advantage:Here negligible means eventually smaller than for every fixed positive . The probabilities include the sampled input and the test's randomness; the model must specify whether tests are uniform algorithms or nonuniform Boolean circuits.
The claim limits an observer's power. Two distributions can be far apart for an unrestricted observer yet indistinguishable to polynomial-time observers. This is the security goal for a pseudorandom generator: its output should look uniform even though a short seed reaches only a small fraction of all possible outputs.[ref]
Introduction to Theoretical Computer Science by Boaz Barak. Modeling randomized computation, Pseudorandom generators and efficient distinguishing tests