Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Ilmari Karonen Oct 8 '13 at 20:31
add comment

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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