Statistically close

The variation distance of two distributions ${\displaystyle X}$ and ${\displaystyle Y}$ over a finite domain ${\displaystyle 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 ${\displaystyle 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