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:
- What is adversary's advantage in cryptography and why we use it?
- Advantage of attacker in CPA secure IBE
But I was not able to get a clear answer. Hence, this new question.
