2
$\begingroup$

All the examples that I see for proving that two distributions are not computationally indistinguishable involve a pattern: choose a Distinguisher $D(\cdot)$ such that $D(x)$ is $1$ if $x$ satisfies some certain properties.

For example, consider the distribution $X$ such that it contains all the binary strings in $\{0,1\}^k$ such that they end with 1 and distribution $Y$ uniformly spread over all strings in $\{0,1\}^k$. Now I can choose my distinguisher to be $D(x) = 1$, if $x$ ends with $1$.

However, if there is no such pattern in our distributions, how can we prove that the given distributions are (not) computationally indistinguishable?

$\endgroup$

1 Answer 1

2
$\begingroup$

The usual way of proving that two distributions are distinguishable is by devising an attack such as the one you mentioned. Finding an attack may not be easy or even doable. In general, you should assume that two distributions are distinguishable unless you can prove otherwise. To prove indistinguishability, you can often use the technique of reduction to map the distributions in question to other ones that are known to be indistinguishable from random.

$\endgroup$
1
  • $\begingroup$ if the OP cannot think of a pattern or structural property that one distribution has, then he cannot think of what reduction map to use. $\endgroup$
    – kodlu
    Feb 13, 2021 at 22:08

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.