零知識(shí)證明及其應(yīng)用

1、網(wǎng)絡(luò)安全課程論文題 目 零知識(shí)證明理論及其應(yīng)用 學(xué) 院 計(jì)算機(jī)與信息科學(xué)學(xué) 軟件學(xué)院專(zhuān) 業(yè) 年 級(jí) 學(xué) 號(hào) 姓 名 指 導(dǎo) 教 師 成 績(jī) _ 2014年 11月 16 日 零知識(shí)證明理論及其應(yīng)用摘要：“零知識(shí)證明”zero-knowledge proof，是由Goldwasser等人在20世紀(jì)80年代初提出的。它指的是證明者能夠在不向驗(yàn)證者提供任何有用的信息的情況下，使驗(yàn)證者相信某個(gè)論斷是正確的。本文介紹了零知識(shí)證明的概念,并對(duì)零知識(shí)證明的一般過(guò)程進(jìn)行分析.同時(shí),闡述零知識(shí)證明的性質(zhì)和優(yōu)點(diǎn).最后,綜述了零知識(shí)證明的應(yīng)用。關(guān)鍵字：零知識(shí)證明 身份認(rèn)證 交互式 非交互式一、 引言21世紀(jì)是信息時(shí)

2、代，信息已經(jīng)成為社會(huì)發(fā)展的重要戰(zhàn)略資源，社會(huì)的信息化已成為當(dāng)今世界發(fā)展的潮流和核心，而信息安全在信息社會(huì)中將扮演極為重要的角色，它直接關(guān)系到國(guó)家安全、企業(yè)經(jīng)營(yíng)和人們的日常生活。密碼學(xué)的出現(xiàn)給這些安全帶來(lái)了保證，而大量事實(shí)證明，零知識(shí)證明在密碼學(xué)中非常有用。Goldwasser等人提出的零知識(shí)證明中，證明者和驗(yàn)證者之間必須進(jìn)行交互，這樣的零知識(shí)證明被稱(chēng)為“交互零知識(shí)證明”。80年代末，Blum等人進(jìn)一步提出了“非交互零知識(shí)證明”的概念，用一個(gè)短隨機(jī)串代替交互過(guò)程并實(shí)現(xiàn)了零知識(shí)證明。非交互零知識(shí)證明的一個(gè)重要應(yīng)用場(chǎng)合是需要執(zhí)行大量密碼協(xié)議的大型網(wǎng)絡(luò)。在零知識(shí)證明中,一個(gè)人(或器件)可以在不泄漏任何

3、秘密的情況下,證明他知道這個(gè)秘密.如果能夠?qū)⒘阒R(shí)證明用于驗(yàn)證,將可以有效解決許多問(wèn)題。二、 概念“零知識(shí)證明”zero-knowledge proof，是由Goldwasser等人在20世紀(jì)80年代初提出的。它指的是證明者能夠在不向驗(yàn)證者提供任何有用的信息的情況下，使驗(yàn)證者相信某個(gè)論斷是正確的。零知識(shí)證明實(shí)質(zhì)上是一種涉及兩方或更多方的協(xié)議，即兩方或更多方完成一項(xiàng)任務(wù)所需采取的一系列步驟。證明者向驗(yàn)證者證明并使其相信自己知道或擁有某一消息，但證明過(guò)程不能向驗(yàn)證者泄漏任何關(guān)于被證明消息的信息。零知識(shí)證明分為交互式零知識(shí)證明和非交互式零知識(shí)證明兩種類(lèi)型。三、 零知識(shí)證明的一般過(guò)程證明方和驗(yàn)證方擁有

4、相同的某一個(gè)函數(shù)或一系列的數(shù)值.零知識(shí)證明 的一般過(guò)程如下: 1.證明方向驗(yàn)證方發(fā)送滿足一定條件的隨機(jī)值,這個(gè)隨機(jī)值稱(chēng)為承諾.1 2.驗(yàn)證方向證明方發(fā)送滿足一定條件的隨機(jī)值,這個(gè)隨機(jī)值稱(chēng)為挑戰(zhàn).1 3.證明方執(zhí)行一個(gè)秘密的計(jì)算,并將結(jié)果發(fā)送給驗(yàn)證方,這個(gè)結(jié)果稱(chēng)為響應(yīng)。4)驗(yàn)證方對(duì)響應(yīng)進(jìn)行驗(yàn)證,如果驗(yàn)證失敗,則表明證明方不具有他所謂的知識(shí),退出此過(guò)程。否則,繼續(xù)從1)開(kāi)始,重復(fù)執(zhí)行此過(guò)程t次。如果每一次驗(yàn)證方均驗(yàn)證成功,則驗(yàn)證方便相信證明方擁有某種知 識(shí)。而且此過(guò)程中,驗(yàn)證方?jīng)]有得到關(guān)于這個(gè)知識(shí)的一點(diǎn)信息。四、 零知識(shí)證明的性質(zhì)根據(jù)零知識(shí)證明的定義和有關(guān)例子,可以得出零知識(shí)證明具有以下三條性質(zhì):

5、 1.完備性2.如果證明方和驗(yàn)證方都是誠(chéng)實(shí)的,并遵循證明過(guò)程的每一步,進(jìn)行正確的計(jì)算,那么這個(gè)證明一定是成功的,驗(yàn)證方一定能夠接受證明方。2.合理性2.沒(méi)有人能夠假冒證明方,使這個(gè)證明成功。 3.零知識(shí)性2.證明過(guò)程執(zhí)行完之后,驗(yàn)證方只獲得了證明方擁有這個(gè)知識(shí)這條信息,而沒(méi)有獲得關(guān)于這個(gè)知識(shí)本身的任何一點(diǎn)信息。五、 零知識(shí)證明的優(yōu)點(diǎn)根據(jù)零知識(shí)證明及其有關(guān)的協(xié)議主要有以下優(yōu)點(diǎn)3: 1.隨著零知識(shí)證明的使用,安全性不會(huì)降級(jí),因?yàn)樵撟C明具有零知識(shí)性質(zhì)。2.高效性.該過(guò)程計(jì)算量小,雙方交換的信息量少。3.安全性依賴于未解決的數(shù)學(xué)難題,如離散對(duì)數(shù),大整數(shù)因子分解,平方根等。4.許多零知識(shí)證明相關(guān)的技術(shù)避

6、免了直接使用有政府限制的加密算 法,這就給相關(guān)產(chǎn)品的出口帶來(lái)了優(yōu)勢(shì)。六、 零知識(shí)證明身份認(rèn)證如果我們把合法用戶的個(gè)人信息看作是證明方的知識(shí),證明方通過(guò)零知識(shí)證明向驗(yàn)證方證實(shí)自己的身份就是零知識(shí)身份認(rèn)證.零知識(shí)身份認(rèn)證是零知識(shí)證明在身份認(rèn)證方面的應(yīng)用.目前的零知識(shí)身份認(rèn)證方案主要有四種:FiatShamir身份認(rèn)證,Feige-Piat-Shamir身份認(rèn)證,GuilloOuisquater身份認(rèn)證和Schnorr身份認(rèn)證.其中FiatShamir身份認(rèn)證是最早提出的,也是最基礎(chǔ)的零知識(shí)身份認(rèn)證方案,其他三種方案是對(duì)FiatShamir的改進(jìn).下面僅就FiatShamir方案做一個(gè)介紹,并證明其

7、完備性,合理性和零知識(shí)性. （一）FiatShamir身份認(rèn)證協(xié)議過(guò)程 協(xié)議概要:A在t次迭代過(guò)程中向B證明他的身份。1.一次建立3 該階段主要完成以下兩項(xiàng)任務(wù),且在t次迭代過(guò)程之前一次完成。 （1）一個(gè)可信中心T選擇并發(fā)布一個(gè)類(lèi)似于RSA的隨機(jī)模數(shù)n,n=pXq. P,q為兩個(gè)大素?cái)?shù),可信中心對(duì)P和q保密。（2）申請(qǐng)者A選擇一個(gè)和12互素的秘密值S,1sn一1.計(jì)算=mod.并向可信中心T注冊(cè)v做為他的公鑰。 2.協(xié)議消息3 t輪中的每一輪會(huì)產(chǎn)生如下三條信息: （1）AB:x=,mod. （2）BA:e0,1. （3）AB:y=r?rood. 3.協(xié)議執(zhí)行34 以下步驟迭代t輪,輪與輪之間是

8、連續(xù)進(jìn)行的而且是相互獨(dú)立的.如 果這t輪都成功了,則B就接受A的身份. （1）A選擇一個(gè)承諾隨機(jī)數(shù)r,1rn一1.計(jì)算x=rmodn,發(fā)送給 B. （2）B隨機(jī)選擇一個(gè)挑戰(zhàn)比特位e,e0,1,發(fā)送給A。 （3）A如果收到e=O,則計(jì)算y=r.如果收l(shuí)Je=l,則計(jì)算Y=modn。 然后向B發(fā)送響應(yīng)Y。 （4）B驗(yàn)證y2=?v.modn.如果驗(yàn)證成功,則接受A的響應(yīng),否則拒絕。 （二）FiatShamir身份認(rèn)證協(xié)議的完備性,合理性和零知識(shí)性證明 1.完備性證明 （1）當(dāng)e=O時(shí),y=r,.lJy2=r2.又=rmod,所以?vx=rmod. 故Y=?vroodn.此時(shí)B驗(yàn)證成功。（2）當(dāng)e=1

9、時(shí),Y=rsmodny2=rSmodn.?ye=XoP=rs.所以y2=? vmodn.此時(shí)B也能驗(yàn)證成功。因此,只要A和B都是真實(shí)的.并遵循協(xié)議計(jì)算正確,則B對(duì)A的身份認(rèn)證將是正確的.PFiatShamir身份認(rèn)證協(xié)議滿足完備性。2.合理性證明 假設(shè)第三方要假冒A.首先該第三方能夠順利通過(guò)FiatShamir協(xié)議的第一步.然后在第三步中,因?yàn)閑是隨機(jī)產(chǎn)生的,Ue=0或e=l的概率都是1/2. （1）當(dāng)e=0時(shí),y=r.此時(shí)該第三方只要把他第一步中產(chǎn)生的隨機(jī)數(shù)r發(fā)送給B即可通過(guò)驗(yàn)證,此次過(guò)程假冒成功. （2）但當(dāng)e=l時(shí),Y=rsmod.此時(shí)該第三方要想計(jì)算出正確的Y發(fā)送給 B,則其首先要正確

10、的計(jì)算出s的值.但s2=vmodn.要想由v求出s,其困難性和分解大整數(shù)n的困難性是樣的.因此第三方得到正確的s值的概率幾乎為0.即當(dāng)e=l時(shí),第三方冒充A會(huì)失敗 由（1）和（2）可知,協(xié)議執(zhí)行一次,第三方假冒A成功的概率是1/2.則執(zhí)行t次,第三方假冒A成功的概率為.當(dāng)t很大時(shí),第三方假冒A成功的概率可以認(rèn)為是0.因此FiatShamir身份認(rèn)證協(xié)議滿足合理性.3.零知識(shí)性證明 s是秘密值,只有A知道,因此S就是A的身份信息.在此協(xié)議執(zhí)行過(guò)程中,驗(yàn)證方B沒(méi)有得到關(guān)于S本身的任何一點(diǎn)信息.B雖然知道v,y和X的值,但都不能求出正確的S值.原因是求解模n的平方根問(wèn)題是數(shù)學(xué)難題。因此Fiat-Sh

11、amir身份認(rèn)證協(xié)議滿足零知識(shí)性。 七、 零知識(shí)證明協(xié)議（一） 基本的零知識(shí)證明協(xié)議假設(shè)P知道一部分信息而且這個(gè)信息是一個(gè)難題的解法,基本的零知識(shí)協(xié)議由下面幾輪組成。Step1:P用他的信息和一個(gè)隨機(jī)數(shù)將這個(gè)難題轉(zhuǎn)變成另一個(gè)難題,新的難題和原來(lái)的難題同構(gòu)。然后他用他的信息和隨機(jī)數(shù)解這個(gè)新的難題。Step2:P利用位承諾方案遞交這個(gè)新難題的解法。Step3:P向V透露這個(gè)新難題。V不能用這個(gè)新難題得到原難題或其解法的任何信息。Step4:V要求P：1.向他證明新、舊難題是同構(gòu)，或者：2.公開(kāi)他在第2步中提交的解法并證明是新難題的解法。Step5:P同意V的要求。 Step6:P和V重復(fù)第1步至第

12、5步n次。（二） 并行的零知識(shí)證明協(xié)議基本的零知識(shí)證明協(xié)議包括P和V之間的n次交換，可以把它們?nèi)坎⑿型瓿桑篠tep1:P使用他的信息和n個(gè)隨機(jī)數(shù)把這個(gè)難題變成n個(gè)不同的同構(gòu)難題, 然后用他的信息和隨機(jī)數(shù)解決這n個(gè)新難題。Step2:P提交這n個(gè)新難題的解法。Step3:P向V透露這n個(gè)新難題。V無(wú)法利用這些新難題得到原問(wèn)題或其解法的任何信息。Step4:對(duì)這n個(gè)問(wèn)題中的每一個(gè),V要求P: 1.向他證明新、舊難題是同構(gòu)，或者： 2.公開(kāi)他在第2步中提交的解法,并證明是新難題的解法。Step5:P對(duì)這n個(gè)新難題中的每一個(gè)都表示同意。在實(shí)際應(yīng)用中這個(gè)協(xié)議似乎是安全的,但是沒(méi)有人知道怎么證明它。在某

13、些環(huán)境下,針對(duì)某些問(wèn)題的某些協(xié)議可以并行運(yùn)行，并同時(shí)保留它們的零知識(shí)性質(zhì)。（三） 非交互式的零知識(shí)證明協(xié)議早在1988年,人們就已經(jīng)發(fā)明了非交互式零知識(shí)的證明。非交互式的零知識(shí)證明6協(xié)議不需要任何交互,證明者P可以公布協(xié)議,從而向任何花時(shí)間對(duì)此進(jìn)行驗(yàn)證的人證明協(xié)議是有效的。這個(gè)基本協(xié)議類(lèi)似于并行零知識(shí)證明,不過(guò)只是用單向散列函數(shù)代替了V:Step1:P使用他的信息和n個(gè)隨機(jī)數(shù)把這個(gè)難題變換成n個(gè)不同的同構(gòu)難題,然后用他的信息和隨機(jī)數(shù)解決這n個(gè)新難題。Step2:P提交這n個(gè)新難題的解法。Step3:P把所有這些提交的解法作為一個(gè)單向散列函數(shù)的輸入,然后保存這個(gè)單向散列函數(shù)輸出的頭n個(gè)位。Ste

14、p4:P取出在第3步中產(chǎn)生的n個(gè)位，針對(duì)第i個(gè)新難題依次取出這n個(gè)位中的第i個(gè)位,并且: 1.如果它是0,則證明新舊問(wèn)題是同構(gòu)的,或者: 2.如果它是1,則公布他在第2步中提交的解法,并證明它是這個(gè)新問(wèn)題的解法。Step5:P將第2步中的所有約定及第4步中的解法都公之于眾。Step6:V或者其他感興趣的人,可以驗(yàn)證第1步至第5步是否能被正確執(zhí)行。這個(gè)協(xié)議起作用的原因在于單向散列函數(shù)扮演一個(gè)無(wú)偏隨機(jī)位發(fā)生器的角色。如果P要進(jìn)行欺騙,他必須能預(yù)測(cè)這個(gè)單向散列函數(shù)的輸出。但是,他沒(méi)有辦法強(qiáng)迫這個(gè)單向散列函數(shù)產(chǎn)生哪些位或猜中它將產(chǎn)生哪些位。這個(gè)單向散列函數(shù)在協(xié)議中實(shí)際上是V的代替物在第4步中隨機(jī)的選擇兩個(gè)證明中的一個(gè)。八、 結(jié)語(yǔ)零知識(shí)證明提供了一種能向別人證明擁有某知識(shí)但不透漏該知識(shí)的一種方法。零知識(shí)證明過(guò)程不但在身份認(rèn)證中有重要應(yīng)用,而且在NP問(wèn)題4中也有廣泛的應(yīng)用。同時(shí)微軟提出的新一代安全計(jì)算平臺(tái)NGSCB也應(yīng)用到了與零知識(shí)證明相關(guān)的技術(shù)。零知識(shí)證明理論是一個(gè)非常重要的理論，另外,數(shù)字簽名,水印檢測(cè),密鑰交換和電子現(xiàn)金也為零知識(shí)證明的應(yīng)用提供了新的方向。參考文獻(xiàn)：1安全協(xié)議曹天杰,張永平,汪楚嬌.北京:北京郵電大學(xué)出版社,2009,113122. 2A.Menezes,P.va