1
$\begingroup$

I'm currently studying a paper (Sequences of Games: A Tool for Taming Complexity in Security Proofs) on proving semantic security using the Game Hopping technique by Victor Shoup.

On pages 9-11, he is using a sequence of three games, $Game 1$, $Game 2$, and $Game 3$ to deduct the semantic security of Hashed ElGamal to DDH and entropy smoothing assumptions. How does he combine the three probabilities equations, namely $(1 )$, $(2)$, $(3)$ to derive the last one, $|Pr[S_0]-1/2| \le ε_{ddh} + ε_{es}$?

$\endgroup$

1 Answer 1

4
$\begingroup$

The three equations you reference are (we'll just take them as truth - their proof can be found in the PDF):

$$ \begin{align} |Pr[S_0] - Pr[S_1]| & = \epsilon_{\text{ddh}} & \text{ (1)} \\ |Pr[S_1] - Pr[S_2]| & = \epsilon_{\text{es}} & \text{ (2)} \\ Pr[S_2] & = \frac{1}{2} & \text{ (3)} \\ \end{align} $$

Then: $$ \begin{align} \epsilon_{\text{ddh}} + \epsilon_{\text{es}} & = |Pr[S_0] - Pr[S_1]| + |Pr[S_1] - Pr[S_2]| & \text{(1) + (2)} \\ & \geq |Pr[S_0] - Pr[S_1] + Pr[S_1] - Pr[S_2]| & \text{Triangle inequality} \\ & = |Pr[S_0] - Pr[S_2]| \\ & = \left|Pr[S_0] - \frac{1}{2}\right| & \text{(3)} \end{align} $$

$\endgroup$

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.