1
$\begingroup$

In cryptography, for a polynomial time-bounded adversary $\mathcal{A}$, given a scheme $\Pi$, the success or probability of succeeding $\mathcal{A}$ is the likelihood for $\mathcal{A}$ to break $\Pi$, and its advantage is the absolute value of the difference between its success and a set in stone knowledge. For instance:

  • If the objective is to prove that $\Pi$ satisfies IND-CPA (indistinguishable chosen-plaintext) security, one would design a game where the objective of $\mathcal{A}$ is to differentiate the result produce by $\Pi$ and a truly random function and outputs its answer as a bit $b^\prime$. The success of $\mathcal{A}$ is $\mathrm{Pr}(b^\prime = b)$, and it advantage is $\mathrm{Adv}_{\mathcal{A},\Pi} =|\mathrm{Pr}(b^\prime = b)-\frac{1}{2}|$. Where $b$ is the bit chosen by the challenge. Here, the advantage is given by subtracting the success with $\frac{1}{2}$, which is the probability of a random guess between $0$ and $1$, the distribution of $b$.

How do you establish the advantage when you have to output the actual result?
For instance, if the game is to compute the discrete logarithm in a group $(\mathbb{G},g,p)$, and we assume that the success for $\mathcal{A}$ is $\mathrm{Pr}(x\in \mathbb{Z}^*_p, y=g^x: x \leftarrow \mathcal{A}(y)) = \lambda$, what is its advantage?

  • is it simply equal to its success, i.e., $\mathrm{Adv}_{\mathcal{A}} = \mathrm{Pr}(x\in \mathbb{Z}^*_p, y=g^x: x \leftarrow \mathcal{A}(y)) = \lambda$?

  • or is the advantage the difference between its success and the probability of a successful random guess in the distribution of the output, i.e., $\mathrm{Adv}_{\mathcal{A}} = |\lambda-\frac{1}{\mathrm{order}(\mathbb{G})}|$?

Finally, which concept is better in security proof? computing the advantage or computing the success?

PS: I read the answers to these questions:

But I was not able to get a clear answer. Hence, this new question.

$\endgroup$
3
$\begingroup$

There is nothing special about advantage versus probability of success, and they should be used where it makes sense and improves readability. When considering distinguishing games (like for encryption, PRG, and the like) advantage has the benefit of simplifying notation. Also, it "behaves nicely" in the sense of being able to add advantages and the like (although this should always be checked formally via the distinguishing probability equations). Note that in distinguishing tasks, it is always possible to succeed with probability 1/2. So, it is only interesting to know how much the adversary can succeed beyond 1/2, and this is the advantage. This makes things nice since we can just talk about a negligible or non-negligible advantage.

When considering computational and not distinguishing tasks, advantage no longer makes sense. Here, if the adversary can succeed with non-negligible probability then it's broken. As such, the success probability is all you need to talk about.

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