Distinguishers

Distinguishers are algorithms used in cryptography to decide whether a given sample comes from one distribution or from another. They are central to formalizing what it means for a cryptographic construction to be secure, by testing whether an observer can tell apart the real object from an ideal or random reference.

Formally, a distinguisher A is given access to a sample that is drawn either from distribution D0 or from distribution D1. A outputs a bit indicating which distribution it thinks the sample came from. The distinguishing advantage of A is defined as the absolute difference between the probability that A correctly identifies the source and the probability of random guessing (usually 1/2). In practical security definitions, A is assumed to run in time polynomial in the security parameter, and the advantage is required to be negligible.

Distinguishers come in several flavors. Computational distinguishers run in efficient time and reflect what an attacker could feasibly do. Statistical distinguishers may have unlimited time and focus on whether two distributions differ in a statistical sense. Distinguishers are often used in conjunction with security games and reductions: if a distinguisher can tell apart a real object from a simulated one with non-negligible advantage, one can typically transform that into an algorithm that breaks an underlying hard problem or breaks a cryptographic scheme.

In cryptography, practical applications include testing pseudorandom generators (a generator is secure if no efficient distinguisher can tell its output from uniform randomness), and validating encryption schemes under chosen-plaintext or chosen-ciphertext attacks. Distinguishers thus provide a precise, objective way to quantify and compare security properties such as indistinguishability and semantic security.

---