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

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

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

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

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

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

7、 FiatShamir 方案做一個介紹,并證明其完備性,合理 性和零知識性.（一）FiatShamir身份認(rèn)證協(xié)議過程協(xié)議概要：A在t次迭代過程中向B證明他的身份。1。一次建立3該階段主要完成以下兩項任務(wù)，且在t次迭代過程之前一次完成。（1）一個可信中心T選擇并發(fā)布一個類似于RSA的隨機(jī)模數(shù)n ,n = pXq. P，q為兩 個大素數(shù)，可信中心對P和q保密。（2 ）申請者A選擇一個和12互素的秘密值S , 1sn 一 1.計算二mod.并向可信中 心T注冊v做為他的公鑰.2.協(xié)議消息3t 輪中的每一輪會產(chǎn)生如下三條信息:AB：x=,mod。BA:ee 0,1 oAB:y=r？rood.3.協(xié)議

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

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

10、要想計算出正確的Y發(fā)送給B,則其首先要正確的計算出s的值。但s2=vmodn.要想由v求出s ,其困難性和分解大整數(shù)n的困難(完整word版)零知識證明及其應(yīng)用性是 樣的。因此第三方得到正確的s值的概率幾乎為0.即當(dāng)e=l時，第三方冒充A會 失敗由(1)和(2 )可知，協(xié)議執(zhí)行一次，第三方假冒A成功的概率是1/2。則執(zhí)行t次， 第三方假冒A成功的概率為。當(dāng)t很大時，第三方假冒A成功的概率可以認(rèn)為是0.因此 FiatShamir身份認(rèn)證協(xié)議滿足合理性.3。零知識性證明s是秘密值，只有A知道，因此S就是A的身份信息。在此協(xié)議執(zhí)行過程中，驗證方 B沒有得到關(guān)于S本身的任何一點信息。B雖然知道v,y和

11、X的值,但都不能求出正確的 S值.原因是求解模n的平方根問題是數(shù)學(xué)難題。因此FiatShamir身份認(rèn)證協(xié)議滿足 零知識性。七、零知識證明協(xié)議(一)基本的零知識證明協(xié)議假設(shè)P知道一部分信息而且這個信息是一個難題的解法，基本的零知識協(xié)議 由下面幾輪組成。Step1:P用他的信息和一個隨機(jī)數(shù)將這個難題轉(zhuǎn)變成另一個難題，新的難題和 原來的難題同構(gòu)。然后他用他的信息和隨機(jī)數(shù)解這個新的難題.Step2 : P利用位承諾方案遞交這個新難題的解法.Step3 : P向V透露這個新難題。V不能用這個新難題得到原難題或其解法的 任何信息。Step4:V 要求 P :1。向他證明新、舊難題是同構(gòu)，或者：公開他在第

12、2步中提交的解法并證明是新難題的解法。Step5:P同意V的要求。Step6 : P和V重復(fù)第1步至第5步n次。（二）并行的零知識證明協(xié)議基本的零知識證明協(xié)議包括P和V之間的n次交換，可以把它們?nèi)坎⑿型?成：Step1:P使用他的信息和n個隨機(jī)數(shù)把這個難題變成n個不同的同構(gòu)難題， 然后用他的信息和隨機(jī)數(shù)解決這n個新難題。Step2 : P提交這n個新難題的解法.Step3 : P向V透露這n個新難題。V無法利用這些新難題得到原問題或其 解法的任何信息.Step4:對這n個問題中的每一個，V要求P:向他證明新、舊難題是同構(gòu),或者：公開他在第2步中提交的解法，并證明是新難題的解法。Step5:P

13、對這n個新難題中的每一 都表示同意。在實際應(yīng)用中這個協(xié)議似乎是安全的,但是沒有人知道怎么證明它。在某些環(huán) 境下，針對某些問題的某些協(xié)議可以并行運行，并同時保留它們的零知識性質(zhì)。（三）非交互式的零知識證明協(xié)議早在1988年人們就已經(jīng)發(fā)明了非交互式零知識的證明。非交互式的零知識 證明6協(xié)議不需要任何交互，證明者P可以公布協(xié)議，從而向任何花時間對此進(jìn) 行驗證的人證明協(xié)議是有效的.這個基本協(xié)議類似于并行零知識證明，不過只是用單向散列函數(shù)代替了 V:Step1:P使用他的信息和n個隨機(jī)數(shù)把這個難題變換成n個不同的同構(gòu)難題，然后用他的信息和隨機(jī)數(shù)解決這n個新難題。Step2:P提交這n個新難題的解法。St

14、ep3:P把所有這些提交的解法作為一個單向散列函數(shù)的輸入,然后保存這個 單向散列函數(shù)輸出的頭n個位。Step4 : P取出在第3步中產(chǎn)生的n個位,針對第i個新難題依次取出這n個 位中的第i個位,并且：如果它是0,則證明新舊問題是同構(gòu)的,或者：2。如果它是1,則公布他在第2步中提交的解法，并證明它是這個新問 題的解法。Step5 : P將第2步中的所有約定及第4步中的解法都公之于眾。Step6:V或者其他感興趣的人，可以驗證第1步至第5步是否能被正確執(zhí)行。 這個協(xié)議起作用的原因在于單向散列函數(shù)扮演一個無偏隨機(jī)位發(fā)生器的角 色。如果P要進(jìn)行欺騙，他必須能預(yù)測這個單向散列函數(shù)的輸出.但是，他沒有辦法

15、 強(qiáng)迫這個單向散列函數(shù)產(chǎn)生哪些位或猜中它將產(chǎn)生哪些位。這個單向散列函數(shù)在 協(xié)議中實際上是V的代替物在第4步中隨機(jī)的選擇兩個證明中的一個。八、結(jié)語零知識證明提供了一種能向別人證明擁有某知識但不透漏該知識的一種方法。零知識 證明過程不但在身份認(rèn)證中有重要應(yīng)用,而且在NP問題4中也有廣泛的應(yīng)用.同時微軟 提出的新一代安全計算平臺NGSCB也應(yīng)用到了與零知識證明相關(guān)的技術(shù)。零知識證明理 論是一個非常重要的理論，另外，數(shù)字簽名，水印檢測，密鑰交換和電子現(xiàn)金也為零知識證 明的應(yīng)用提供了新的方向。參考文獻(xiàn):1安全協(xié)議曹天杰，張永平，汪楚嬌.北京：北京郵電大學(xué)出版社,2009，113122。2A。Menezes ,