Example of not computationally indistinguishable

Question

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?

Answer 1

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.