承接上文，本文主要从2个方面介绍安全归约的正确性分析
不可区分性模拟实验
不可区分的攻击
正确的安全归约：将敌手攻破方案转换为困难问题。在安全归约的过程中，面对具有无限计算能力的敌手，在多项式时间内必须具有不可忽略的优势去解决困难问题。正确性分析：
模拟方案是与真实方案是否不可区分
敌手的攻击是否存在不可忽略优势的有效攻击。
1、证明不可区分的模拟
回顾前面对不可区分性的定义：
模拟方案能够正确响应敌手的询问
所有模拟的随机数都是随机且独立的
在模拟阶段，可以对每个响应做正确性分析，只要每个响应都是正确的，那么在证明“不可区分模拟”的时候，只需要分析随机性和独立性即可。
随机数在密钥生成、签名、加密等密码方案中常常用到，假设一个数是随机的，那么该数在数据空间上就是随机独立的，且均匀分布。
在模拟方案中，如果用函数模拟生成随机数，就必须证明该随机数在敌手看来确实是随机独立的。
用生成函数模拟随机数
一个重要的引理：在真实方案中选取随机数与模拟方案中生成随机数是不可区分的，只要模拟方案生成的随机数与真实方案选取的随机数看起来相同。
由模拟方案生成的随机数，是通过函数计算而来，函数的输入是一个随机数元组，这个元组敌手不知道的。由模拟方案输出的随机数与真正方案选取的随机数个数相同，敌手也就不能区分到底是谁输出的随机数。
案例分析：由模拟方案生成随机数，有的随机数是可区分的。
在这个案例中，输出的随机数是可区分的，因为只有满足A+B=C，x、y才有唯一解，如果不满足该条件，x、y就无解，所以ABC三者不是独立的。
在这个案例中，ABC三者是独立的，不管ABC是什么值，x、y、z的解都是唯一的。
这个案例与前一个案例类似，不管ABC为何值，x、y、z的解唯一。
这个案例与前一个案例类似，不管ABC为何值，w、x、y、z的解唯一。
用线性方程模拟随机数
线性方程组可以用矩阵的形式表示，只要方程组的行列式不等于0（即方程组有唯一解），那么输出的随机数就是随机独立的。
案例分析：由线性方程生成随机数
在这个案例中，方程组的行列式等于0，那么x1、x2、x3有无数组解，解不唯一，所以输出的随机数是可区分的。
用多项式模拟随机数
这里设置的多项式，其系数是随机选取的，所以敌手是不允许知道该多项式的。
只要敌手不知道多项式f(x)，即使知道多项式的输入（输入各不相同），敌手也是不能区分输出是不是真实方案的随机数。
案例分析：多项式生成随机数
系数矩阵是范德蒙德矩阵，其行列式为非零。
2、不可区分的攻击
以一个签名方案为例：敌手不可区分到底是有效攻击，还是无效攻击。
在这个签名方案中，私钥有两部分，在证明的时候，模拟器设私钥a=α，f(a)=β。
敌手具有无穷计算能力，并可以发起签名询问。假设敌手用不同的随机数对消息m*进行伪造攻击，将可以发起n个攻击（每个随机数r都不相同）。（敌手知道私钥，不知道f(x)，模拟器知道私钥和f(x)）
我们希望敌手不可区分有效攻击和无效攻击，证明攻击不可区分要求：在敌手发起的所有攻击中，敌手没有分辨无效攻击的优势。
在上面这个案例中，如何证明敌手没有任何优势分辨发起的是有效攻击还是无效攻击呢？
对于上述案例，要证明敌手不能区分发起的是否为有效攻击，就是证明敌手没有计算f(x)的优势，f(x)对于敌手来说，就是一个随机数。对应的分析方法就是绝对难的困难问题。
绝对难的困难问题：即使敌手具有无限计算能力，也没有解决该问题的优势。
回到上述案例，要证明敌手没有任何优势分辨发起的是有效攻击还是无效攻击，转换成绝对困难问题的解，再转换成实例与解的随机独立。
实例分析
案例一，如果a,c,x都是随机独立的，不管c选何值，a+x或者x都是随机独立的值，敌手能够分辨的概率都是1/2.
如果敌手知道c，那么敌手就能够计算a+x，也就是发起了无效攻击。因此，要把c隐藏起来。
案例二，因为a和x都是随机值，那么a+x也是随机值。
如果敌手知道a，那么敌手就能计算Z，也就是发起了无效攻击。因此，需要把a隐藏起来。
案例三，因为x随机，所以f(x)随机，敌手通过f(x)猜中x的概率为1/p。
如果敌手知道x*，那么就能计算f(x*)，也就是发起了无效攻击。因此，需要将x*隐藏起来。
案例四，Z1...Zn构成一个n元一次多项式组，且系数矩阵的行列式不等于0。给出系数矩阵以及Z1...Zn-1，敌手能够计算出Zn的概率为1/p，因为Z1...Zn随机且独立。由Z1...Zn-1可以得到n组解，猜中正确解的概率为1/p。
案例五，即使敌手有无穷计算能力，正确猜中(x,y)的概率为1/p（也就是空间大小）。类似于解决DL问题，如果能够计算出一个指数，马上就可以得到另一个指数。
如果敌手知道x或者y，将会发起无效攻击，敌手就可以计算出另一个值。所以把x和y放在一个困难问题里面，让敌手发起有效攻击。
案例六，因为g,h,Z,c都是随机独立的，所以敌手能区分g^x和g^xh的概率为1/2。
如果敌手知道c，那么就是一个无效攻击，敌手就可以区分g^x和g^xh。因此，为了让敌手发起有效攻击，在设计方案的时候，就需要把c隐藏起来，也就是通过一个困难问题把c隐藏起来，让敌手计算c是一个绝对困难的问题。
安全证明的正确性分析
正确性分析包括三方面：
不可区分性模拟：分析模拟方案与真实方案是不可区分的
分析成功模拟的概率和成功攻击的概率
根据前面分析的概率，得到敌手攻击成功的优势，也就是解决困难问题的优势
在分析过程中，一定要有不可区分模拟和解决困难问题的优势不可忽略。
indistinguishable simulation and non-negligible advantage of solving problem must be analyzed.
本文从不可区分模拟实验和不可区分攻击两个方面介绍了安全归约证明的正确性分析。
欢迎留言讨论。
联系客服
