1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Commented Feb 14, 2021 at 9:29

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.