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|?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
$|\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.
