1
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – cygnusv Jun 12 '15 at 19:53
  • $\begingroup$ @cygnusv: Maybe you are right. I've updated the title. $\endgroup$ – phan Jun 12 '15 at 19:59
3
$\begingroup$

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...

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.