1

Consider a PPT distinguisher $D$. Now if I give it an input (a bit string) $x$, it outputs 1 if $x$ ends with $1$ and $0$ otherwise. We know such a distinguisher exists and is often given as an example many times.

Now consider another distinguisher strategy, where on input $x$, it checks if $x$ is $0^n$ or $1^n$. If yes, it outputs $0$. Otherwise it tosses a coin. If the result is heads, it outputs $1$, else it outputs $0$.

My question is - Is such a distinguisher valid according to the assumptions we make in cryptography?

I think it should be valid as our distinguisher being PPT, has access to a random number generator (hence the coin tosses). Can someone please confirm.

user185887
  • 177
  • 5

1 Answers1

3

Such a distinguisher is certainly valid. In fact, in many proofs of security, we use this strategy. In particular, assume that there is some event that can be detected by $D$ with some non-negligible probability $\epsilon=\epsilon(n)$ when $D$ is given distribution $X$, but not when given distribution $Y$. You can use this to build a distinguisher but the problem is that the distinguisher needs to distinguish with probability non-negligibly greater than $1/2$ over all possible samples. In order to bridge this gap, we typically have $D$ output 1 if the detected value is received and output a random bit otherwise. This means that $D$ outputs 1 on distribution $X$ with probability $\epsilon \cdot 1 + (1-\epsilon)\cdot\frac12 = \frac12 + \frac\epsilon2$. If this detected event never happens on distribution $Y$, then $D$ will output 1 with probability $\frac12$ on random, and so it distinguishes with non-negligible probability $\frac\epsilon2$. Note that sometimes the detected event does happen on distribution $Y$ as well. But if it is with negligible probability then it's still OK. Letting $\mu=\mu(n)$ be a negligible function, we would have that $D$ outputs 1 on distribution $Y$ with probability $\frac12 + \frac\mu2$ (using the same computation as above) and the distinguishing probability is $\frac\epsilon2 - \frac\mu2$. Since $\epsilon$ is non-negligible and $\mu$ is negligible, this is still a non-negligible probability.

Yehuda Lindell
  • 27,820
  • 1
  • 66
  • 83
  • Short summary for the OP: the algorithm in the question fits the definition of a distinguisher: But it's not one that gives a non-negligible advantage in any standard experiment as used in cryptography. Thus, as is, it is not useful. – fgrieu Feb 14 '21 at 09:29