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

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

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

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

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

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

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

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

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

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

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

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

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