密碼學的復(fù)雜性理論基礎(chǔ)

1、1,第3章 密碼學的復(fù)雜性理論基礎(chǔ),2,密碼技術(shù)和算法復(fù)雜性,計算復(fù)雜性 ：研究密碼分析對于計算量的需求和密碼分析的困難程度 ，從而得出這些密碼技術(shù)和算法在現(xiàn)有可行的條件下是否具有足夠的安全性： 算法復(fù)雜性；問題復(fù)雜性。密碼協(xié)議、方案和體制的安全性證明：零知識證明理論。,3,問題（problem）,即需要回答的一般性提問:它通常含有若干個參數(shù)。對于一個問題進行描述應(yīng)該包括兩方面的內(nèi)容：必須對問題的所有給定參數(shù)給出一般性描述

2、；必須描述該問題的答案（或解）應(yīng)該滿足的性質(zhì)。當問題的所有參數(shù)都有了確定的取值時，我們稱得到了該問題的一個實例（instance）。,4,算法（algorithm）,即求解某個問題的一系列具體步驟（通常被理解為求解所需的通用計算程序）。算法總是針對具體問題而言的，求解一個問題的算法通常不止一個。當某個算法能夠回答一個問題的任何實例時，我們稱該算法能夠回答這個問題。當一個問題至少有一個能夠回答該問題的算法時，我們稱該問題可解（re

3、solvable），否則稱該問題不可解（unresolvable）。,5,算 法 復(fù) 雜 性,即度量該算法所需的計算能力 ，包括：時間復(fù)雜性T（time complexity）；空間復(fù)雜性S（space complexity）； 隨機位數(shù)目；信道帶寬；數(shù)據(jù)總量； ……,6,算 法 復(fù) 雜 性,計算復(fù)雜性的表示符號為“ O ”（稱為“大O ”），表示計算復(fù)雜性的數(shù)量級 好處：使算法復(fù)雜性度量與處理器的運行速度和指令運行時間

4、無關(guān)； 明確地揭示了輸入的數(shù)據(jù)長度對算法復(fù)雜性的影響。,,,,7,算 法 復(fù) 雜 性,算法的分類及其運行時間,,,,,,,,,,,,,,,,,,運算次數(shù),,,,,,,,,,宇宙年齡的,8,問 題 復(fù) 雜 性,研究問題的內(nèi)在復(fù)雜性，即在圖靈機上解決最難的問題實例所需的最小時間和空間條件。,9,圖靈機,圖靈機是一種具有無限讀寫存儲帶的有限狀態(tài)機，可以被當作一個實際可用的計算模型 。確定性圖靈機。 非確定性圖靈機 ：能夠進行猜測。求解

5、一個問題分兩個階段：猜測階段和驗證階段。,10,問題分類,易處理的（tractable） ：確定性圖靈機上能夠在多項式時間內(nèi)得到處理的問題。稱易處理問題的全體為“多項式時間可解類”，記為P。 非確定性圖靈機上能夠在多項式時間內(nèi)得到處理的問題被稱為“非確定性多項式時間可解問題”，簡稱NP問題。NP問題的全體被稱為“非確定性多項式時間可解類”，記為NP。,11,NP問題,意義：能夠通過非確定性的多項式時間算法對許多對稱密鑰算法和所有公鑰

6、算法進行攻擊。 NP完全問題 ：指NP中的任何一個問題都可以通過多項式時間轉(zhuǎn)化為該問題 。NP完全問題的全體被記為NPC 。NP完全問題是NP問題中最難的問題。,12,零知識證明,證明者能夠在不向驗證者提供任何有用的信息的情況下，使驗證者相信某個論斷是正確的。實質(zhì)上是一種涉及兩方或更多方的協(xié)議，即兩方或更多方完成一項任務(wù)所需采取的一系列步驟。,13,零知識“洞穴”,14,零知識“洞穴”,（1）V站在A處； （2）P走進洞穴，到達

7、C處或D處；（3）當P消失在洞穴中時，V走到B處；（4）V呼叫P，要求P：（a）從左通道出來；或者（b）從右通道出來；（5）P答應(yīng)V的呼叫，并在有必要的情況下用咒語打開C與D之間的秘密之門；（6）重復(fù)步驟（1）~（5）次。,15,基本的零知識協(xié)議過程,假設(shè)P知道一部分信息，并且該信息是一個難題的解法 ：（1）P用自己的信息和一個隨機數(shù)將這個難題轉(zhuǎn)變?yōu)榕c之同構(gòu)的新難題，然后用自己的信息和這個隨機數(shù)這個新難題；（2）P利用位承諾

8、方案提交對于這個新難題的解法；（3）P向V透漏這個新難題，V無法通過新難題得到關(guān)于原難題或其解法的任何信息；（4）V要求P：（a）證明新、舊難題同構(gòu)；或者（b）公布P在（2）中提交解法并證明該解法的確為新難題的解法；（5）P答應(yīng)V的要求；（6）重復(fù)步驟（1）~（5）次。,16,交互與非交互,交互零知識證明 ：證明者和驗證者之間必須進行交互 。由Goldwasser等人在20世紀80年代初提出 GMR模型； FFS模型。 非

9、交互零知識證明 ：用一個短隨機串代替交互過程并實現(xiàn)了零知識證明 。 20世紀80年代末，Blum等人進一步提出 成員（或定理）的非交互零知識證明系統(tǒng)； 知識（或身份）的非交互零知識證明系統(tǒng)。,17,交互圖靈機,交互圖靈機指的是一個具有一條只讀輸入帶、一條工作帶、一條隨機帶、一條只讀通信帶和一條只寫通信帶的圖靈機。其中，隨機帶上包含一條無限長的隨機比特序列，并且只能從左向右讀入?！耙粋€交互圖靈機投一個硬幣”指該圖靈機從自己的隨機帶上讀

10、取1bit。,18,交互協(xié)議,即滿足以下兩個條件的有序圖靈機（A,B），其中，A具有無限的計算能力，B具有多項式時間的計算能力： （a）A與B共享同一輸入帶； （b）B的只寫通信帶是A的只讀通信帶，同時，B的只讀通信帶是A的只寫通信帶。,19,GMR模型,假設(shè)證明者具有無限的計算能力，并且驗證者具有多項式時間的計算能力。 對于輸入I和語言L，判斷I∈L是否成立。由于這一過程向驗證者泄露了1b信息（即I∈L），所以基于

11、GMR模型的零知識證明并非真正的零知識證明。這種交互零知識證明通常被稱為“成員（或定理）的零知識證明（zero knowledge proofs of membership or theorem）。,20,FFS模型,假設(shè)證明者與驗證者具有多項式時間的計算能力。 證明者向驗證者證明的不是I∈L成立與否，而是證明自己知道輸入I關(guān)于語言L的狀況。由于在這個證明過程中，驗證者相信這個證明，但是又無法得知任何信息（包括I∈L是否成立）。 基

12、于FFS模型的零知識證明是真正的零知識證明。這種交互零知識證明通常被稱為“知識（或身份）的零知識證明（zero knowledge proofs of knowledge or identity）”。,21,成員（或定理）的非交互零知識證明系統(tǒng),兩個階段預(yù)處理階段 ：建立證明者和驗證者所擁有的某些共同信息及其各自擁有的秘密信息，允許證明者和驗證者進行交互。 定理證明階段 ：證明者選擇并向驗證者證明自己所知道的定理，這個階段是非交互的