2

Sequence of games by Victor Shoup
引理 1 Difference Lemma：
假设 事件A 和 事件B基本是一致的（computationally indistingui****le），唯独当事件F也发生的时候，才可以区分两个事件。也就是说 A & not F <==> B & not F，那么 | Pr[A] - Pr[B] | <= Pr[F] 。
==============================================
证明：| Pr[A] - Pr[B] | = | Pr[A & F] + Pr[A & not F] - Pr[B & F] - Pr[B & not F] | …… （1）
= | Pr[A & F] - Pr[B & F] | ……（2）
<= | Pr[F] | ……（3）
其中（2）成立是因为由条件得两个事件不可区分；
（3）成立是因为Pr[A & F]和Pr[B & F]都在[ 0, Pr[F] ]中。
============================================
举例：
比如协议安全性证明中，Game1是模拟了hash的随机预言。
而Game2则排除了hash中的碰撞情况。
则 | Pr[Succ1] - Pr[Succ2] | = (Qsend + Qexecute)^2 / 2*|H|
也就是说如果在Game2中不发生碰撞，那么Game1和Game2是不可区分的，
而发生碰撞的概率由生日问题（birthday paradox）的平方近似法（Square approximation）可以计算得到。
-----------------------------------
p(n,d) = n^2 / 2d，其中n是生日问题中的人数，而d是生日可选的365天范围，那么p(n, d)表示n个人中至少有2个人生日相同（同等于至少存在生日发生碰撞）的概率。