详解语义安全（semantically secure）
目次一. 引入
二. 密文与明文
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比特可写作：
https://i-blog.csdnimg.cn/direct/0a52b5694197470ca3ba5c6938e91ee4.png
在理想条件下，攻击者在拿到密文后，猜测明文m的第i个比特（可以写做https://latex.csdn.net/eq?m%5Ei）的概率为1/2.也就等同于胡乱猜测。
2.2 定理
PPT：probabilistic polynomial-time algorithm 概率多项式时间算法
negl：negligible 可忽略函数
假定某对称加密方案的明文是固定长度的，写做：
https://i-blog.csdnimg.cn/direct/a06e4a93cb1546ada10fb61ab5142a82.png
明文的长度为l，第i位比特。
给定恣意的PPT敌手A，以下式子是满足的：
https://i-blog.csdnimg.cn/direct/c0cc47845e0649ae823a64e474904b88.png
通常以为明文m与密钥k是均匀分布的：
https://i-blog.csdnimg.cn/direct/4675e0a883f04cc590aacf809f206c35.png
需要注意的是，敌手A是具有随机性的。加密算法Enc也是有随机性的。
2.3 定理理解
证实过程比较繁琐，建议相识的小伙伴略过此部门。
本小节给出一个故意思的安全性归约证实（proofs by reduction）。
对于密文Enc(m)，假如敌手可以确定出明文的第i个比特会发生什么？
换句话说，假如有两个明文m0与m1，这两个明文的第i个比特不一样。敌手就可以区分出这两个明文对应的密文。很明显这违反了我们加密的目标。
密码学需要构造两个敌手A和A'，通过归约证实，来验证安全性。
引入一个PPT的敌手A，以及比特i：
https://i-blog.csdnimg.cn/direct/01f5e05232f944c2801c100e28470ccb.png
第一个聚集I0代表全部第i个比特为0的比特串：
https://i-blog.csdnimg.cn/direct/dff866b32f944b95a5b3bcaf4d146582.png
第二个聚集I1代表全部第i个比特为0的比特串：
https://i-blog.csdnimg.cn/direct/9dfd93ee3b144cc1ab7174d3392d9b3f.png
明文m0要么来自于I0，要么来自于I1.而且两者的概率肯定是相等的。由此可得：
https://i-blog.csdnimg.cn/direct/7e8e839c93d74e09a00350dcb8987d56.png
两个概率均代表敌手猜对的概率。
接下来我们构建另外一个敌手A'
https://i-blog.csdnimg.cn/direct/718c5f8e5e33417c9a39a0190a1f21b4.png
第一步：均匀选取m0与m1，如下：
https://i-blog.csdnimg.cn/direct/05c9af0b23f441c7a323d5031074c78a.png
第二步：给定密文c。将密文c输入到敌手A的步调中：
https://i-blog.csdnimg.cn/direct/504362d047fc4a0c952a51299818d0d1.png
假如A输出0，那么b'=0;假如A输出1，那么b'=1.
因为A是多项式时间的，所以A'也是多项式时间的。
对于敌手A'来讲，将其试验的结果表示为：
https://i-blog.csdnimg.cn/direct/93b62f9db4984864b504af603b33cf20.png
核心：当A成功时，A'也就成功了。由此可得：
https://i-blog.csdnimg.cn/direct/ecfd3d4f5c4346698cd7714f29451034.png
第一个概率代表A'的试验输出1，也就是A'成功的概率；
第二个概率代表A成功的概率；
第三行代表分成两种情况；
第四行代表猜对明文m的第i个比特。
因为密码方案（Enc,Dec）是安全的。所以A'成功的概率是不会优于1/2，也就是：
https://i-blog.csdnimg.cn/direct/5cb1036effed4b33bdbb01c89964aaa2.png
最终可得敌手A不会猜出明文m的恣意1比特信息：
https://i-blog.csdnimg.cn/direct/8740d8fdfc2443e386ef192e30a19610.png
三. 语义安全的第一个版本
3.1 基本理解
更进一步的目标：给定明文m的分布D,我们盼望没有PPT敌手可以从密文学习到关于明文m的恣意函数f信息。
我们盼望给定密文Enc(m)，敌手精确计算f(m)；
敌手根据m的分布，直接计算f(m)；
我们盼望这两者的概率是一样的。也就是密文并没有起到任何辅助的作用，这样才能满足密码学的要求。
3.2 定理
(Enc,Dec）:固定明文长度的对称加密方案，其中明文长度为l
明文的分布为D：
https://i-blog.csdnimg.cn/direct/15876c8c83c24ddd9a64e22d8b612741.png
A与A'均为PPT算法
函数f界说为：
https://i-blog.csdnimg.cn/direct/8707d770802b4960802da752011f3a8a.png
以下两个概率相减是可忽略的：
https://i-blog.csdnimg.cn/direct/3abcfa2495d641afb904127a414fc68d.png
第一个概率：明文m是根据分布D选取的，密钥k是n长的均匀分布。算法A与加密Enc本身会引入随机性。
第二个概率：明文m是根据分布D选取的，算法A'会引入随机性。
3.3 定理理解
证实过程比较繁琐，建议相识的小伙伴略过此部门。
假定有两种明文。第一个是从分布D中随机选取，第二个是全为1的比特串，也就是：
https://latex.csdn.net/eq?Enc_k%28m%29%5Cquad%20Enc_k%281%5El%29
假如加密方案是安全的，那么PPT敌手无法区分这两个密文。
接下来我们按密码学的语言来举行解释。
从分布D中选取m0.
确定m1为：
https://i-blog.csdnimg.cn/direct/6b504555ed094a94ad695cc192ba0ae6.png
密文c可以是对m0举行加密，也可以是对m1举行加密。
将该密文输入到算法A中。假如A可以输出f(m)，那么试验结果为0.
情况1：给定对m的加密，输出f(m)
情况2：给定对全为1的加密，输出f(m)
这两者其实是相等的。
四. 语义安全的第二个版本
本小节先容是最全面的版本。
4.1 直观解释
明文为恣意分布，可以由某些多项式时间算法产生Samp
可以允许敌手额外获取某些关于明文的信息h(m)。
消息的长度是恣意的，该长度敌手可获取。|m|代表明文的长度
综上现在有两个多项式时间可计算的函数f与h
语义安全要求以下表达式是可忽略的：
https://i-blog.csdnimg.cn/direct/74488954e78d4b2b9125db513f278fa6.png
明文输入依赖算法：
https://i-blog.csdnimg.cn/direct/68f7aef734974ebc9866e463ad99ad7a.png
密钥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 小结
语义安全跟不可区分安满是等效的。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]