第5講零知識證明

零知識證明1概念“零知識證明”－zero-knowledgeproof，是由Goldwasser等人在20世紀80年代初提出的。它指的是證明者能夠在不向驗證者提供任何有用的信息的情況下，使驗證者相信某個論斷是正確的。

21）A要向B證明自己擁有某個房間的鑰匙，假設(shè)該房間只能用鑰匙打開鎖，而其他任何方法都打不開。這時有2個方法：（一）A把鑰匙出示給B，B用這把鑰匙打開該房間的鎖，從而證明A擁有該房間的正確的鑰匙。（二）B確定該房間內(nèi)有某一物體，A用自己擁有的鑰匙打開該房間的門，然后把物體拿出來出示給B，從而證明自己確實擁有該房間的鑰匙。后面這個方法屬于零知識證明。好處在于在整個證明的過程中，B始終不能看到鑰匙的樣子，從而避免了鑰匙的泄露。3零知識證明實質(zhì)上是一種涉及兩方或更多方的協(xié)議，即兩方或更多方完成一項任務(wù)所需采取的一系列步驟。零知識證明必須包括兩個方面，一方為證明者P，另一方為驗證者V。證明者試圖向驗證者證明某個論斷是正確的，或者證明者擁有某個知識，卻不向驗證者透露任何有用的消息。零知識證明目前在密碼學(xué)中得到了廣泛的應(yīng)用，尤其是在認證協(xié)議、數(shù)字簽名方面。

4在Goldwasser等人提出的零知識證明中，證明者和驗證者之間必須進行交互，這樣的零知識證明被稱為“交互零知識證明”。80年代末，Blum等人進一步提出了“非交互零知識證明”的概念，用一個短隨機串代替交互過程并實現(xiàn)了零知識證明。非交互零知識證明的一個重要應(yīng)用場合是需要執(zhí)行大量密碼協(xié)議的大型網(wǎng)絡(luò)。大量事實證明，零知識證明在密碼學(xué)中非常有用。5Quisquater-Guillon零知識協(xié)議1990年，Quisquater和Guillon提出一種形象的基本零知識協(xié)議的例子。如下圖所示，該圖表示一個簡單的迷宮，只有知道秘密口令的人才能打開C和Ｄ之間的密門。現(xiàn)在，P希望向V證明P能夠打開此門，但是又不愿意向V泄漏P掌握的秘密口令。為此，P采用了所謂的“分隔與選擇”技術(shù)實現(xiàn)一個零知識協(xié)議。6分隔與選擇（cutandchoose）協(xié)議A將蛋糕分成兩半；B為自己選擇其中的一半；A得到剩下的一半。這是一種公平協(xié)議，A如果分割不均勻，B總能選擇對自己有利的一半。這個協(xié)議為交互零知識證明的雛形。7ABCD81)V站在Ａ點。

(2)P一直走到迷宮深處，隨即選擇Ｃ點或者Ｄ點。

(3)在P消失后，V走到Ｂ點。

(4)V向P喊叫，要她：從左通道出來，或者從右通道出來。

(5)P答應(yīng)了，如果有必要她就用秘密口令打開密門。

P和V重復(fù)第(1)至第(5)步n次。

9在上述協(xié)議中，如果P不知道秘密口令，他只能從來路返回到B點，而不能走另外一條路。此外，P每一次猜對V要求他走哪一條路的概率是1/2。因此，每一輪協(xié)議P能夠欺騙V的概率是1/2。執(zhí)行n輪協(xié)議后，P成功欺騙V的概率是1/2n。嘉定n=16，則執(zhí)行16輪協(xié)議后，P成功欺騙V的概率是1/216=1/65536。于是，如果P能夠16次按V的要求路線返回，V即能證明P確實知道秘密口令。同時，V無法從上述證明過程中獲取絲毫有關(guān)P的秘密口令的消息。所以，這是一個零知識協(xié)議。10Hamilton回路零知識協(xié)議許多計算上困難的問題可以用來構(gòu)造零知識協(xié)議。在圖論中，圖G中的回路是指始點和終點相重合的路徑，若回路通過圖的每個頂點一次且僅一次，則稱圖G為哈密爾頓回路，構(gòu)造圖G的哈密爾頓回路是NPC問題。11假定P知道圖G的哈密爾頓回路，并希望向V證明這一事實，可采用如下協(xié)議：(1)P隨機地構(gòu)造一個與圖G同構(gòu)的圖W。并將W交給V。(2)V隨機地要求P做下述兩件工作之一：證明圖G和圖W同構(gòu)；指出圖W的一條哈密爾頓回路。12(3)P根據(jù)要求做下述兩件工作之一：證明圖G和圖W同構(gòu)，但不指出圖G或圖W的哈密爾頓回路；指出圖W的哈密爾頓回路，但不證明圖G和圖W同構(gòu)。(4)P和V重復(fù)以上過程n次。13協(xié)議執(zhí)行完后，V無法獲得任何信息使自己可以構(gòu)造圖G的哈密爾頓回路，因此該協(xié)議是零知識證明協(xié)議。事實上，如果P向V證明圖G和圖W同構(gòu)，這個結(jié)論對V并沒有意義，因為構(gòu)造圖G的哈密爾頓回路和構(gòu)造圖W的哈密爾頓回路同樣困難。如果P向V指出圖W的一條哈密爾頓回路，這一事實也無法向V提供任何幫助，因為求兩個圖之間的同構(gòu)并不比求一個圖的哈密爾頓回路容易。在協(xié)議的每一輪中，P都隨機地構(gòu)造一個與圖G同構(gòu)的新圖，因此不論協(xié)議執(zhí)行多少輪，V都得不到任何有關(guān)構(gòu)造圖G的哈密爾頓回路的信息。14Goldwasser等人提出的零知識證明是交互式的，也就是證明者和驗證者之間必須進行雙向?qū)υ挘拍軐崿F(xiàn)零知識性，因而稱為交互零知識證明。15在交互零知識證明的研究中，目前受到關(guān)注的有兩種基本模型。一種是GMR模型，在這種模型中，證明者具有無限的計算能力，驗證者具有多項式時間的計算能力。需要證明的是語言成員問題，即輸入I是否是語言L中的一個成員。GMR模型不是真正的零知識證明，這是因為在證明中，證明者向驗證者揭露了有關(guān)知識的1比特信息，即I∈L是否成立。但除此之外，再沒有其他任何附加的信息泄露給驗證者，通常稱這種交互零知識證明為成員零知識證明或定理零知識證明。16另一種是FFS模型，在這種模型中，證明者和驗證者均具有多項式時間的計算能力，證明者的目的不是向驗證者證明I∈L，而是證明他知道I是否屬于L。FFS模型是真正的零知識證明，因為在證明中，驗證者沒有得到任何信息，他連I∈L還是IL都不知道，但他相信這個證明，通常稱這種交互零知識證明為知識零知識證明或身份零知識證明。17從實用角度考慮，要保證用戶身份識別的安全性，識別協(xié)議至少要滿足以下條件：識別者A能夠向驗證者B證明他的確是A。在識別者A向驗證者B證明他的身份后，驗證者B沒有獲得任何有用的信息，B不能模仿A向第三方證明他是A。18Feige-Fiat-Shamir身份識別協(xié)議在一個安全身份識別協(xié)議中，我們希望識別者Alice能向驗證者Bob電子地證明他的身份，而又沒有向Bob泄露他的識別信息，這十分類似于零知識的思想。1986年，F(xiàn)eige，F(xiàn)iat和Shamir基于零知識的思想設(shè)計了一個零知識身份識別協(xié)議，這就是著名的Feige-Fiat-Shamir零知識身份識別協(xié)議。該協(xié)議的目的是證明者P向驗證者V證明他的身份，且事后V不能冒充P。19簡化的Feige-Fiat-Shamir身份鑒別方案

在發(fā)放私人密鑰之前，仲裁方隨機選取一個模數(shù)n，n為兩個大素數(shù)之積。實際中，n應(yīng)至少為512位長，盡量接近1024位。n值可在一組證明者之間共享。20212223Feige-Fiat-Shamir身份鑒別方案24其他身份識別協(xié)議25Schnorr鑒別協(xié)議

262728攻擊身份的零知識證明例子象棋大師問題一個有預(yù)謀的用戶A想使其他人相信她是一個象棋高手，她可以通過這樣的方法來實現(xiàn)：她找到兩位世界頂尖級象棋界高手B和C，向他們提出挑戰(zhàn)，并定于同一時間，在同一地點的不同房間和他們進行比賽。在比賽的過程中，每當B或C下一步棋，A就跑到隔壁的房間如法炮制，走同一步棋。也就是說，盡管B和C以為他們都在和A對弈，但實際的情況是B和C在彼此對弈。無論最后是B和C哪個贏，A總會是某一局棋的得勝者，從而向其他人證明她的確是一名象棋高手。該過程是對身份的零知識證明的一種攻擊。29黑手黨騙局A正在B(黑手黨)的餐廳吃飯。此時C（黑手黨）按照計劃來到一