In game-based security definitions, like for example the one defining IND-CPA security, a given cryptosystem is said to be secure if any probabilistic polynomial time adversary has only a negligible advantage of winning the game, where the advantage is defined to be

$|Pr[b^{\prime}=b] - \frac{1}{2}|$,

being $b$ the attacker guess, and $b^{\prime}$ the challenger flipped coin.

However, sometimes I run into papers, like for example this one, where they write something like this (see page 30):

$Adv^{CPA}(B) \geq \frac{1}{2} Adv^{CCA1}(A)-Adv^P(A).$

Clearly, they seem to be treating the adversary advantage as if it was just a probability, and not as the advantage that follows from the definition I just wrote (and it's also given at the beginning of the paper). Is it correct to mix the terms of advantage and probability in this way? Can you just divide the advantage by $2$, like if it was a probability?

I just mentioned this paper as an example, but I have found many others where the same thing seems to be happening.

  • $\begingroup$ Why do you think you can't divide an advantage by 2? If I can guess $b$ with probability 0.50002, and you can guess it with probability 0.50001, then your advantage is $\frac12$ of mine. $\endgroup$ Commented Oct 8, 2013 at 20:31

1 Answer 1


Advantage and success probability are just words. Their meaning is in practice decided by how the speakers of the language use the words. You have observed that people use the terms advantage and probability in this way. One could probably argue that this is confusing or illogical or something like that, but such is language.

About dividing by two: remember, the advantage is just a number, and numbers can be divided by two and compared to other numbers. Sometimes, we are able to prove that one number is larger than the difference of two other numbers.

(As for the equation you mention, I think two terms are "advantages" and one term is a "probability".)


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.