1
$\begingroup$

I'm doing sequence-of-game formal security analysis for key exchange protocol. It confuses me a lot how to calculate the adversary's semantic secure (SS) advantage. In Shoup's tutorial "sequences of games: a tool for taming complexity in security proofs", SS-advantage = |Pr[S0]-1/2|; while in other papers like ""Security proofs for an efficient password-based key exchange", SS-advantage= |2Pr[S0]-1|. Can someone explain me which is correct? Is it because in key-exchange protocols, there are two parties that the adversary can steal key from, so the SS-advantage = 2|Pr[S0]-1/2|?

$\endgroup$

1 Answer 1

3
$\begingroup$

$|\Pr[S] - \frac12|$ is a number between 0 and 1/2.

$|2\Pr[S] - 1|$ is a number between 0 and 1.

Some people just like the elegance of having 1 be the highest possible advantage, so they normalize the advantage to be between 0 and 1. That's the only difference.

You can use either one, it really doesn't matter. There is no case that I know of in cryptography where a factor of two difference changes whether something is deemed secure or not. Usually we just care whether the advantage is a negligible function of the security parameter.

$\endgroup$
1
  • $\begingroup$ Thanks a lot!!! $\endgroup$
    – Chandler
    Commented Feb 21, 2022 at 8:07

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.