Statistically close

The variation distance of two distributions $X$ and $Y$ over a finite domain $D$, (often referred to as statistical difference ^[1] or statistical distance^[2] in cryptography) is defined as

${\displaystyle \Delta (X,Y)={\frac {1}{2}}\sum _{\alpha \in D}|\Pr[X=\alpha ]-\Pr[Y=\alpha ]|}$.

We say that two probability ensembles ${\displaystyle \{X_{k}\}_{k\in \mathbb {N} }}$ and ${\displaystyle \{Y_{k}\}_{k\in \mathbb {N} }}$ are statistically close if ${\displaystyle \Delta (X_{k},Y_{k})}$ is a negligible function in $k$.

References

1. Goldreich, Oded (2001). Foundations of Cryptography: Basic Tools (1st ed.). Berlin: Cambridge University Press. p. 106. ISBN 0-521-79172-3.
2. Reyzin, Leo. (Lecture Notes) Extractors and the Leftover Hash Lemma

See also

• Zero-knowledge proof
• Randomness extractor