Statistical closeness implies computational indistinguishability was recently posed. It revolves around a numeric value $\Delta(n)$ of the statistical difference between a pair of distribution ensembles, as:-

$$ \Delta(n) = 1/2 \sum_{\alpha}|\mathbb{P}[X_n = \alpha] - \mathbb{P}[Y_n = \alpha]| $$

But statistical distances can also be measured via other techniques such as Pearson's chi-squared test, Kolmogorov-Smirnov & Anderson–Darling tests and Kullback–Leibler. There are many other exotic tests as well. My four examples are non parametric tests too that produce a numeric test statistic. And they are also used in many aspects of cryptography.

Is the $\Delta(n)$ formula specific to cryptography, and if so, why?


What we call "statistical distance" in cryptography is called total variation distance by statisticians. So it certainly exists outside of cryptography.

I can't speak to its applications within statistics. But it certainly is the most natural metric for cryptography because it has an equivalent formulation in terms of distinguishing two source distributions given a sample, which is how we state many security properties. Restricting the distinguisher to be polynomial-time leads to natural and useful generalizations.

  • $\begingroup$ Not clear as to how it's "most natural". In non-distinguish ability was aim for a negligible $\Delta(n)$. But those other tests also tend to zero when the distributions are very very similar. Not sure that it's any more sensitive either... $\endgroup$
    – Paul Uszak
    Sep 7 '19 at 3:05
  • 2
    $\begingroup$ It's "most natural" in precisely the way I stated: it it equivalent to the maximum advantage of a distinguisher. $\endgroup$
    – Mikero
    Sep 7 '19 at 18:02

In the cryptographic context, the $\Delta(X;Y)$ formula(i.e the statistical distance) seems to be the most 'natural' because of the way we define security in terms of a distinguishing advantage. i.e $$\Delta^D(X;Y) = |Pr^{DY}[D(Y) = 1] - Pr^{DX}[D(X) = 1]$$.

As mentioned here here, this definition implies that the statistical distance is an upper bound on the distinguishing advantage of any distinguisher(computationally bounded or not). In other words, as consequence of the definition, the statistical distance is 'The metric' for security. Now why is this definition of advantage the most natural? I have no idea...

Talking about metrics, the distinguising advantage can be shown to also be a pseudo-metric. Which is not the case for all distance measure.

At Swiss Crypto Day Maurer gave an intringuing talk titled 'Adversaryless cryptography'. The main insight was that by essentially using the statistical distance, one can make security claims without the need of explicitly speaking of an adversary, this would potentially simplify our security proofs and help gain more insight into the security claims that we make. I am curious to see where this goes ;).

Looking at the specific case of Pearson's $\chi^2$, i don't know of many indistinguishability proofs based on that.

The only one I could find was in the paper Information-theoretic Indistinguishability via the Chi-squared Method by Dai and al. The insight of the paper was that the new method could be a potentially simpler framework to make security claims based on statistical distance, since the classical proof frameworks seem to be error-prone.

But ironically, this paper seems to show that the proof by Dai and al. had some mistakes furthermore they show ways to fix the proof. So it seems that an exiting advancement but we still have a long way to go...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.