# Distinguishing between two probabilities and the uniform probability

Say I have a polynomial adversary $A$ that can distinguish with a non-negligible adventage between $x$ generated from a probability $X$ and $y$ generated from a probability $Y$.

Obviously, this implies that it is possible to either efficiently distinguish between $X$ and the uniform distribution, or between $Y$ and the uniform distribution (or both).

How can this be proven?

Can $A$ be directly used to construct another adversary that distinguishes between $X$ and uniform (or $Y$ and uniform) ?

## 1 Answer

Perhaps a proof by contradiction? Either they are both indistinguishable from uniform or not. If so, they are indistinguishable from each other. Since that contradicts the premise, at least one must be distinguishable from uniform.

• That's fine, but how can it be formally proven that indistinguishability is transitive? i.e. $X$ indistinguishable from $Z$ and $Y$ indistinguishable from $Z$ implies $X$ indistinguishable from $Y$? Jun 13, 2015 at 9:58
• nevermind, got it. The way is to simply express Pr[A(X) = 1] − Pr[A(Z) = 1] as Pr[A(X) = 1] − Pr[A(Y ) = 1] + Pr[A(Y ) = 1] − Pr[A(Z) = 1], and then use the standard triangle inequality |a+b| ≤ |a|+|b| to conclude that if both |Pr[A(X) = 1]−Pr[A(Y ) = 1]| ≤ epsilon and |Pr[A(Y ) = 1] − Pr[A(Z) = 1]| ≤ epsilon, then |Pr[A(X) = 1] − Pr[A(Z) = 1]| ≤ 2*epsilon. Jun 13, 2015 at 12:50
• For those of you following along at home, statistical indistinguishability is based on the concept of statistical distance, which just like any other metric follows the triangle inequality by definition. Jun 13, 2015 at 22:54