密码学安全归约7 Analysis(Towards A Correct Reduction)
目前郭老师就在B站录了7节课，终于补完啦。学习的思路更清晰了。今后继续先刷完slide，再继续刷书。这个主题的笔记会继续更新，如果今后老师录新课了我会及时跟进，如果没发，就等我自己学完再结合自己的理解更新。要学的东西好多，零知识证明、安全归约、联盟链编程、公链编程、加密货币研究。还有一些需要了解的比如安全多方计算、格密码、AKE......
1 Overview
2 Step 1: Indistinguishable Simulation
2.1 Random and Independent
2.2 Simulation with a General Function
2.3 Simulation with a Linear System
2.4 Simulation with a Polynomial
3 Step 2: Indistinguishable Attack
3.1 Attack Revisited
3.2 Requirements
3.3 Absolutely Hard Problems
4 Correctness of Analysis
1 Overview
正确的安全归约：即使对模拟方案的攻击是由恶意的/无限算力的攻击者发起的，在多项式时间内解决困难问题的优势仍然不可忽略。
正确性分析是为了分析
- 模拟的不可区分性
- 来自恶意的/无限算力的攻击者的攻击对安全归约有用的攻击，且优势不可忽略。
敌手发动成功的攻击之前，模拟必须是不可区分的。但是没必要整个模拟与真实攻击不可区分。whole simulation=simulator完成所有的response之前。
IND simulation分析是为了得到useful attack的第一步。
2 Step 1: Indistinguishable Simulation
满足两个性质：
正确性：模拟器对所有的敌手询问的回复是可以通过验证的。
随机性：模拟器选的随机数必须真的是随机的独立的。
2.1 Random and Independent
真实方案里，群元选取是随机独立的，意味着每个元素都是在空间内均匀分布的。
在模拟方案中，我们必须证明从敌手的角度看来，我们模拟出来的随机数也是随机独立的。
- Random随机：C is equal to any integer in Zp with probability 1/p.
- Independent独立：C cannot be computed from A and B.
假设仅给敌手A和B。那么敌手在猜测C时没有任何优势，只能以1 / p的概率正确地猜测C，即使敌手的无限计算能力的。
主要有三种方法证明模拟过程中的随机独立。
2.2 Simulation with a General Function
通用函数形式
引理：真实方案随机选取(A,B,C)。模拟方案使用随机数(w,x,y,z)通过函数F(w,x,y,z)生成(A,B,C)。
假设敌手从归约算法中知道函数F，但不知道(w,x,y,z)。如果对于任何给定的(A,B,C)，两个方案满足 F(w,x,y,z)=(A,B,C)的解的个数是相同的，则两个方案不可区分 。意味着在模拟方案中，将以相同的概率生成(A,B,C)。
这个例子4是不可区分的。
三个输出，四个输入，不一定是不可区分的，还得仔细分析。
随便给(A,B,C),倒推出多个不同的输入。
2.3 Simulation with a Linear System
线性方程组形式
引理：真实方案真随机产生(A1,A2,...,An)。模拟方案的(A1,A2,...,An)通过系数矩阵a以及模拟器随机选择的(x1,x2,...,xn)产生。
假设敌手知道矩阵a但是不知道x列向量，只要矩阵a的行列式不等于0，产生的(A1,A2,...,An)依然是随机的，两个方案不可区分。
2.4 Simulation with a Polynomial
多项式形式 。
q-1次多项式，q个系数（还有a0）。假设模拟器随机选择ai，f(x)对敌手来说未知。
引理：
真实方案随机选取(A1,A2,...,An)。模拟方案的(A1,A2,...,An)是通过
产生的。(m1,m2,...,mn)是n个不同的整数。
假设敌手知道(m1,m2,...,mn)但是不知道f(x)，产生的(A1,A2,...,An)仍然是随机的，两个方案不可区分。
原理同线性方程组。
3 Step 2: Indistinguishable Attack
主要是看敌手能否区分useful attack 和useless attack。
参考密码学安全归约5 Difficulties in Security Reduction
根据能否解决困难问题分类：
- Useless Attack.无用的攻击。敌手的攻击，不能归约为解决困难问题。
- Useful Attack.有用的攻击。敌手的攻击，可以归约为解决困难问题。
3.1 Attack Revisited
一个重要的签名案例。先去看教材的6.2 Gentry Scheme。
归约关系如下。作者也给出了详细的证明。就是这套思路。
假如这么模拟，α=a, β=f(a)。无穷算力的敌手对消息m*进行签名的伪造。
Adaptive（抛硬币概率可能不是1/2）= Unpredictable。
敌手用不同的r进行签名，可以看作不同的攻击。有n个数，敌手到底选了哪个是不知道的。
假如敌手最后选择的数是r*，用来伪造m*的签名。
当r*=f(m*)时，模拟器自己都可以计算等式右边的值。即敌手的攻击没办法转化为解决困难问题。
当r*!=f(m*)时，模拟器无法自己算等式右边的值。而且模拟器可以利用这个值把它转化为困难问题的解。
这里的困难问题是q-SDH。
给你上面一串，计算下面这对儿还是困难的，注意敌手是不知道a的。
补充一个柯西中值定理：
3.2 Requirements
安全归约要做到，再怎么狡猾的敌手也不能区分useful attack和useless attack。
3.3 Absolutely Hard Problems
绝对困难问题：即使无限计算能力的敌手也没有优势能解决。
如何证明一个计算问题的绝对困难的？problem instance a,f(a)和problem solution f(m*)都是随机且独立的。
随机独立的两个用法：1.证明真实方案和模拟方案不可区分。2.证明绝对难的困难问题。
六个例子
敌手不知道x和c。
总结：
敌手：发动useless attack必须知道c
布局：通过敌手已知(g,h,Z)计算c是一个绝对困难问题。
方法：c和敌手已知的所有信息是随机且独立的。
4 Correctness of Analysis
正确性分析：
- 不可区分模拟。模拟成功时，模拟不可区分。
- 模拟成功和useful attack的概率。分析解决困难问题的成功概率。
- 优势和时间成本。分析解决困难问题的优势和时间成本。