# Definition of indistinguishable schemes

Let $\mathsf{Exp}_{A,\Pi}(\lambda)$ be some indistinguishability experiment that finally outputs 1 if A outputs $b'$ that satisfies $b' = b$, otherwise 0. Then the textbooks often define the security like this:

If for all PPT adversary A, there exists a negligible function $\mathsf{negl}$ satisfies $\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] \leq 1/2 + \mathsf{negl}(\lambda)$, then we say $\Pi$ is a indistinguishable scheme...

However, suppose there is an adversary A that wins the experiment in possibility 0.4, then we can construct another adversary A' that call A as an oracle, and output $b' = 1 - {b'_{A}}$ (where $b'_{A}$ is the output of A), then A' will win the experiment in possiblity 0.6.

So it seems that if $\Pi$ holds the indistinguishability, then there should not exist any adversary A that $\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] < 1/2 + \mathsf{negl}(\lambda)$, for it also means an A' that $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] > 1/2 + \mathsf{negl}(\lambda)$.

Hence my question is, why we don't define the indistinguishability directly via the conditional $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] = 1/2 + \mathsf{negl}(\lambda)$?

• I think you should change the name of the question into something more readable. I suggest something like "Definition of indistinguishable scheme" or something similar. Jun 12 '15 at 19:53
• @cygnusv: Maybe you are right. I've updated the title.
– phan
Jun 12 '15 at 19:59

Note that in the definition you gave, it says that in order for $\Pi$ to be an indistinguishable scheme, then the above inequality must hold for all PPT adversaries.

So it seems that if $\Pi$ holds the indistinguishability, then there should not exist any adversary A that $\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] < 1/2 + \mathsf{negl}(\lambda)$, for it also means an A' that $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] > 1/2 +\mathsf{negl}(\lambda)$.

If there is an adversary $A'$ such that $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] > 1/2 +\mathsf{negl}(\lambda)$, then $\Pi$ cannot be indistinguishable, by definition.

Another way to see it is that the only way $\Pi$ can be indistinguishable is that all adversaries $A$ have probability $1/2 + \epsilon$, at most, of guessing correctly, where $\epsilon \leq \mathsf{negl}(\lambda)$. Then, following your reasoning if you define an adversary $A'$ that simply outputs the opposite than $A$, its probability will be $1 - (1/2 + \epsilon) = 1/2 - \epsilon$, so the scheme is still indistinguishable.

Hence my question is, why we don't define the indistinguishability directly via the conditional $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] = 1/2 + \mathsf{negl}(\lambda)$?

That definition would not be right, as the term $\mathsf{negl}(\lambda)$ is not actually a value, but an undetermined bounded function.

As mentioned in another answer, I personally don't like that definition either, although it is used in some places (see, for example, definition 7.2 in the Lecture Notes on Cryptography, by Goldwasser and Bellare). I also prefer definitions given in terms of the advantage of the adversaries, which is defined as $\mathsf{Adv}_{A,\Pi}(\lambda) = |\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] - 1/2|$. In this case, the definition would be something similar to this:

If for all PPT adversary A, there exists a negligible function $\mathsf{negl}$ that satisfies $\mathsf{Adv}_{A,\Pi}(\lambda) \leq \mathsf{negl}(\lambda)$, then we say $\Pi$ is a indistinguishable scheme...

Your definition seems to be wrong. The correct definition is:

$\left|{\Pr[\textsf{Exp}_{A, \Pi}(\lambda)]-\frac{1}{2}}\right|<\text{negl}(\lambda)$

EDIT: after reading again, your initial definition is also correct (the one you initially quoted). It says for all $A$. So it automatically implies that the probability cannot be too low from 1/2 for any $A$, because if it was, we could then construct another $A'$ like you said and contradict the definition.

However, I prefer the one I gave as its more clear.