目录
一. 引入
二. 密文与明文
2.1 通俗性理解
2.2 定理
2.3 定理理解
三. 语义安全的第一个版本
3.1 基本理解
3.2 定理
3.3 定理理解
四. 语义安全的第二个版本
4.1 直观解释
4.2 小结
一. 引入
密码学中安全加密要求：敌手（adversary）根据密文（ciphertext）不能推导出关于明文（plaintext）的任何信息。
本文将重点介绍语义安全（semantic security）的理解。
二. 密文与明文
2.1 通俗性理解
密码学的目标：密文不会泄露明文的任何一比特信息。
Enc：加密方案
Dec：解密方案
Gen：产生密钥。在不外加条件的情况下，通常认为Gen算法输出的密钥为n比特的均匀分布。
Message：明文。l比特可写作：
在理想条件下，攻击者在拿到密文后，猜测明文m的第i个比特（可以写做）的概率为1/2.也就等同于胡乱猜测。
2.2 定理
PPT：probabilistic polynomial-time algorithm 概率多项式时间算法
negl：negligible 可忽略函数
假定某对称加密方案的明文是固定长度的，写做：
明文的长度为l，第i位比特。
给定任意的PPT敌手A，以下式子是满足的：
通常认为明文m与密钥k是均匀分布的：
需要注意的是，敌手A是具有随机性的。加密算法Enc也是有随机性的。
2.3 定理理解
证明过程比较繁琐，建议了解的小伙伴略过此部分。
本小节给出一个有意思的安全性归约证明（proofs by reduction）。
对于密文Enc(m)，如果敌手可以确定出明文的第i个比特会发生什么？
换句话说，如果有两个明文m0与m1，这两个明文的第i个比特不一样。敌手就可以区分出这两个明文对应的密文。很明显这违反了我们加密的目标。
密码学需要构造两个敌手A和A'，通过归约证明，来验证安全性。
引入一个PPT的敌手A，以及比特i：
第一个集合I0代表所有第i个比特为0的比特串：
第二个集合I1代表所有第i个比特为0的比特串：
明文m0要么来自于I0，要么来自于I1.而且两者的概率肯定是相等的。由此可得：
两个概率均代表敌手猜对的概率。
接下来我们构建另外一个敌手A'
第一步：均匀选取m0与m1，如下：
第二步：给定密文c。将密文c输入到敌手A的程序中：
如果A输出0，那么b'=0;如果A输出1，那么b'=1.
因为A是多项式时间的，所以A'也是多项式时间的。
对于敌手A'来讲，将其试验的结果表示为：
核心：当A成功时，A'也就成功了。由此可得：
第一个概率代表A'的试验输出1，也就是A'成功的概率；
第二个概率代表A成功的概率；
第三行代表分成两种情况；
第四行代表猜对明文m的第i个比特。
因为密码方案（Enc,Dec）是安全的。所以A'成功的概率是不会优于1/2，也就是：
最终可得敌手A不会猜出明文m的任意1比特信息：
三. 语义安全的第一个版本
3.1 基本理解
更进一步的目标：给定明文m的分布D,我们希望没有PPT敌手可以从密文学习到关于明文m的任意函数f信息。
我们希望给定密文Enc(m)，敌手正确计算f(m)；
敌手根据m的分布，直接计算f(m)；
我们希望这两者的概率是一样的。也就是密文并没有起到任何辅助的作用，这样才能满足密码学的要求。
3.2 定理
(Enc,Dec）:固定明文长度的对称加密方案，其中明文长度为l
明文的分布为D：
A与A'均为PPT算法
函数f定义为：
以下两个概率相减是可忽略的：
第一个概率：明文m是根据分布D选取的，密钥k是n长的均匀分布。算法A与加密Enc本身会引入随机性。
第二个概率：明文m是根据分布D选取的，算法A'会引入随机性。
3.3 定理理解
证明过程比较繁琐，建议了解的小伙伴略过此部分。
假定有两种明文。第一个是从分布D中随机选取，第二个是全为1的比特串，也就是：
如果加密方案是安全的，那么PPT敌手无法区分这两个密文。
接下来我们按密码学的语言来进行解释。
从分布D中选取m0.
确定m1为：
密文c可以是对m0进行加密，也可以是对m1进行加密。
将该密文输入到算法A中。如果A可以输出f(m)，那么试验结果为0.
情况1：给定对m的加密，输出f(m)
情况2：给定对全为1的加密，输出f(m)
这两者其实是相等的。
四. 语义安全的第二个版本
本小节介绍是最全面的版本。
4.1 直观解释
明文为任意分布，可以由某些多项式时间算法产生Samp
可以允许敌手额外获取某些关于明文的信息h(m)。
消息的长度是任意的，该长度敌手可获取。|m|代表明文的长度
综上目前有两个多项式时间可计算的函数f与h
语义安全要求以下表达式是可忽略的：
明文输入依靠算法：
密钥k均匀选取，Enc和A，还有A'本身具有随机性。
第一个概率理解：敌手A拥有密文Enc(m）,外部信息h(m)。尝试猜测f(m)的值
第二个概率理解：A'的目标也是尝试猜测f(m)的值，但只知道m的长度与h(m)的值。
语义安全要求A和A'猜测的概率是相等的。
换句话说，语义安全要求密文Enc(m)不会泄露关于f(m)的任何信息。
4.2 小结
语义安全跟不可区分安全是等效的。
