1
$\begingroup$

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) ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$
    – zvisofer
    Commented Jun 13, 2015 at 9:58
  • $\begingroup$ 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. $\endgroup$
    – zvisofer
    Commented Jun 13, 2015 at 12:50
  • 2
    $\begingroup$ 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. $\endgroup$
    – Reid Rankin
    Commented Jun 13, 2015 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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