Sequences of Games
关于《Sequences of Games: A Tool for Taming Complexity in Security Proofs∗》的总结和疑问
咨询可证明安全的学习建议时，沛公和Tover师傅推荐读这篇论文（还有《Introduction to Modern Cryptography 》，有空再看T-T）
PS：最近一两个月给我的感觉，臭打CTF的，密码学压根没入门23333，还有好多好多要学的，计算复杂性、可证明安全、UC等等，总之任重道远，进入正题。
介绍
总的来说，关于安全规约有两种方式，基于游戏的和基于模拟的安全，这篇文章主要是介绍如何使用基于游戏的安全证明来保证一个方案是安全的，其基本方法是假设一堆游戏，Game 0, Game 1, ... , Game n, 其中Game 0是关于对手和方案的原始攻击游戏，并定义\[S_0, S_1, ... ,S_n\]为Game中的事件。随后，通过一步步推导，得到\[\text{Pr}[S_0]\]和之后的事件差距很小（negligibly close）或相等，最后说明\[\text{Pr}[S_n]\]与一个目标概率相等或可忽略不计，则可证明是安全的。
为了让证明尽可能简洁，连续游戏之间的变换有三种类型：
- Transitions based on indistinguishability
- Transitions based on failure events
- Bridging steps
基于不可区分的过渡
假定有一个很小的改变在连续的游戏之间，如果被敌手所检测到，就说明存在一个高效的算法能区分两个不可区分的分布。例如：
假设\[P_1\]和\[P_2\]是两个不可区分的分布，为了证明\[|\text{Pr}[S_i] - \text{Pr}[S_{i+1}]|\]是忽略不计的，假定存在一个区分算法（distinguishing algorithm）\[ D\] 插入在Game i和Game i+1之间，当输入为取自分布\[ P_1\] 的元素时，D输出1的概率为\[ \text{Pr}[S_i]\] ；当输入为取自分布\[ P_2\] 的元素时，D输出1的概率为\[ \text{Pr}[S_{i+1}]\] ，于是不可区分性就证明了\[|\text{Pr}[S_i] - \text{Pr}[S_{i+1}]|\]是忽略不计的。
基于失败事件的过渡
在这种情况下，Game i 和Game i+1完全相同除非事件\[F\]发生。为了尽可能简洁，最好要让两个Game定义在两个相同的概率空间，唯一的不同是计算某些随机变量。所以有： \[ S_i\land F \Longleftrightarrow S_{i+1} \land F \] 也就是说\[S_i\land F 和\] \[S_{i+1} \land F\]相同，证明也不困难，利用Difference Lemma(其实非常trivial)
所以只需要证明\[\text{Pr}[F]\]是可忽略不计的就可以得到结论，通常这又是基于一个安全假设（例如当F发生时，敌手发现了一个哈希碰撞或者伪造了一个MAC）。
---------------------------------------下面这两段没太懂------------------------------
比如第一段的最后一句，通常其中某个game会更适合分析得出清晰的证明，难道不需要分析F和二者之间吗？
以及第二段的第二句开始到最后都不太懂。
桥接步骤
这个我觉得是最玄乎的方式，以相同的方式重述某些量的计算，改变是完全概念上的，就可以得到\[\text{Pr}[S_i] = \text{Pr}[S_{i+1}]\]
后面也只介绍了为什么要引入这个方式：如果没有它某些证明就会很麻烦0.0.