在游戏跳跃验证技术中，概率是如何组合的？

Question

我目前正在研究一篇关于使用维克托·舒普的游戏跳跃技术证明语义安全的论文(游戏序列:一种安全证明复杂性的驯服工具)。

在9-11页中，他使用三个游戏序列( Game 1、Game 2和Game 3 )来推断哈希ElGamal到DDH和熵平滑假设的语义安全性。他如何结合三个概率方程，即(1 )，(2)，(3)，导出最后一个方程|Pr[S_0]-1/2| \le ε_{ddh} + ε_{es}？

Answer 1

您所引用的三个方程是(我们将它们作为真理-它们的证明可以在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}

然后：

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