Negligible functions and indistinguishability

A function is negligible if it vanishes faster than every inverse polynomial, and two distribution ensembles are statistically indistinguishable if their statistical distance is negligible. They are computationally indistinguishable if every efficient distinguisher’s advantage is negligible — GM84, Yao82a.

Negligible functions

A function is negligible, written , if for every there is such that for all . It is noticeable if there is with for all sufficiently large , and overwhelming if is negligible. A function that is not negligible need not be noticeable: it may exceed for infinitely many and equal for infinitely many others. The sum of two negligible functions and the product of a polynomial and a negligible function are negligible — standard.

Advantage

For a game in which guesses a uniform bit and the game outputs ,

since . The bit-guessing advantage used throughout this site is therefore the distinguishing advantage between world 0 and world 1 — standard.

Statistical distance

The statistical distance between random variables and over a countable set is

Every distinguisher, of unbounded running time, has advantage at most in telling a sample of from a sample of , and the maximizing set attains it — standard. For every randomized function , ; satisfies the triangle inequality; and for independent samples — standard. Ensembles and are statistically indistinguishable if is negligible.

The min-entropy of is .

Computational indistinguishability

Ensembles and are computationally indistinguishable, , if for all efficient ,

is negligible — GM84, Yao82a. With efficient read as probabilistic polynomial time the notion is uniform; read as a family of polynomial-size circuits, equivalently probabilistic polynomial time with polynomial advice, it is non-uniform (uniform and non-uniform adversaries), and non-uniform indistinguishability implies uniform indistinguishability — Gol01. An ensemble is pseudorandom if it is computationally indistinguishable from the uniform ensemble over the same lengths; a PRG’s output is pseudorandom yet statistically far from uniform — standard.

Statistical indistinguishability implies computational indistinguishability — standard. Computational indistinguishability is preserved under efficient post-processing and, by the hybrid argument, under chains of polynomially many steps when, for each efficient distinguisher, one negligible function bounds its advantage at every step — standard. It extends from one sample to polynomially many independent samples when both ensembles are efficiently sampleable, and for non-uniform distinguishers without that condition, since the advice can fix the samples outside the hybrid step — Gol01.