密碼學安全歸約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的機率。分析解決困難問題的成功機率。
- 優勢和時間成本。分析解決困難問題的優勢和時間成本。