How are probabilities combined in the game hopping proof technique?

JAAAY

3/8/23, 2:09 PM

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}$?

227

0 + 0

provable-security

semantic-security

probability

game

Score:4

Crypto

Morrolan

3/8/23, 3:04 PM

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} $$

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How are probabilities combined in the game hopping proof technique?

TH: ความน่าจะเป็นถูกรวมเข้าด้วยกันอย่างไรในเทคนิคการพิสูจน์การกระโดดของเกม

RO: Cum sunt combinate probabilitățile în tehnica jocului de proba de salt?

RU: Как вероятности комбинируются в методе доказательства скачкообразной игры?

VI: Xác suất được kết hợp như thế nào trong kỹ thuật chứng minh nhảy trò chơi?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.