零知識證明技術研究

1 引言

零知識早在70年代提出，到現在已經有40年的時間，在研究零知識證明方面，雖然已經取得了很大的成就，但仍有許多問題需要進一步努力探索，近年來已成為密碼學研究的核心課題。零知識證明的基本理論是當代大部分密碼學協定的基礎，對當代密碼學産生了深遠的影響，在比較廣泛的資訊安全協定的設計中起着很大的作用。零知識證明，通俗的說，就是證明者可以在不給驗證者透露任何自己的資料的前提下，也能讓驗證者相信某個資訊是正确的。它在實質上是一種協定，在這個協定中，一方面關系到驗證者，另一方面關系到證明者。其中的一方，我們稱為證明者，通常用A表示，另一方我們稱為驗證者，通常用B來表示。在協定執行過程中，證明者向驗證者B聲稱已收獲了一些資訊，通過一系列互動驗證A和B，驗證或證明，或拒絕一個聲稱，在這一過程中，驗證者B沒有得到主人的具體内容資訊中說，這是一個新的想法。

2 零知識證明的特征

二十世紀是資訊的時代，資訊已成為關系到社會發展的一種重要的儲備資源，世界的資訊化已成為當今社會發展的核心，在資訊社會中起着非常重要的作用，大到國家安全，小到人民日常生活，密碼學的出現保證了資料資訊的安全性，豐富事實證明零知識證明在密碼學中的應用，是不可忽視的。在由Gold wasser等人提出的零知識證明後，證明者和驗證者之間的聯系必須是“互動的”。“非交的互零知識”的概念是八十年代後期Blum等人提出了。其概念使用一個随機串，用來代替互動的過程，實作了零知識證明系統。基本上，它的應用領域是大型網絡，需要執行大量密碼協定。零知識證明系統中,一個人可以在不洩漏任何資訊的前提下,确定他擁有這個秘密[1]。“零知識證明”是由Goldwasser等人在二十世紀八十年代早期提出的。證明者能在不向驗證者提供任何自己資訊的前提下，使驗證者相信某個結論是正确的，這就是零知識證明的本質。零知識證明本質上是一種涉及兩個或兩個以上當事人的協定，即一個由兩個或兩個以上的當事人完成的一系列步驟。向驗證者證明他或她相信他知道或有消息，但過程不洩露任何有關證明的資料給驗證者。傳統的零知識證明分為，互動的零知識證明系統，和非互動式零知識證明系統。但是它們的本質都是一種協定，就是指多個參與者，使用的一系列特定步驟，目的是為了實作指定的任務。它們大體包括以下三個特征：

（1）該協定是一個有序的過程從開始到結束，每個步驟必須按順序執行，并不能執行下列步驟之前的前一步完成。

（2）該過程需要多個參與者，可以執行一個任務，雖然通過執行一系列的步驟，但是它門不構成某項協定。

（3）必須通過進行該協定能實作一些指令的執行。

在一個零知識證明系統中，一定包含兩個部分，一個部分是證明，另一個部分是驗證。證明者顯示的驗證是正确的，或者說，證明有知識，但沒有透露任何有用的資訊來驗證。

3 零知識證明系統

3.1零知識證明系統的動機

我們指出，最重要的一點是零知識證明是驗證者不能獲得“知識”。我們沒有給出知識的定義，而是給出一個非常公平的例子：沒有知識。這種方法是足夠的加密問題。零知識的定義要求我們必須先考慮A與B之間的一個對話。第一，如果對話是單方面的，同時，這個對話，A隻能說，B隻能聽。是以，我們可以推斷，A在這個對話中并沒有擷取到任何關于B的資訊，因為B很容易确定這個任務的結論；如果B反問A這個圖是不是哈密爾頓圖，是以不管A如何回答，我們能确定B從A回話中擷取了知識。假設，B的判斷能力增加了，那麼我們就說B從對話中得到了資訊，相反，假設B在對話後，對這個圖的判斷能力并沒有改變，我們定論B沒有從這個對話中得到任何資訊。假設系統中的所有使用者都在公共可通路存儲媒體上儲存各自的密鑰加密檔案系統備份。同時，假定在某個時刻，使用者A希望将一個檔案的記錄發送給另一個使用者[2]。最簡單的方法就是簡單地記錄一個發送到B的一個明确的方式，以這種方式B是沒有辦法知道是否一個資訊是真的記錄。通過他的鑰匙給B，一個可以證明他送到B的記錄是正确的，這種方式會讓所有的資訊洩露給B。是以，不僅要讓B相信給了他正确的記錄，也是保障了資訊安全，零知識證明系統是追求“動機不漏的備援資訊”。

3.2 零知識證明的一般過程

證明方以及驗證方同時包含某個函數，這個函數是相同的，或一系列的數值。零知識證明的一般過程如下:

（1）證明者必須向驗證者發送随機值，這個随機值必須滿足一定條件，是以，這個随機值也稱為“承諾”。

（2）驗證者向證明者發送必須滿足指定條件的随機值，是以，這個随機值也被稱為“挑戰”。

（3）證明者在執行這個秘密的計算,并将這個資訊傳達給驗證者,這個資訊也被稱為“響應”。

（4）驗證者并對響應進行判斷，一旦驗證不成功，就表明證明者不具備他所知道的“知識”，傳回這個過程。相反，繼續從第一步開始,連續進行這個過程多次。

如果每次驗證成功，就可以友善地相信當事人有一定的知識。在這個過程中，驗證者自始至終，都沒有得到任何關于知識的資訊。

3.3 零知識證明的優點

根據一系列的零知識證明協定，其具備的優點主要有以下幾點:

（1）使用零知識證明，安全性不會退化，因為它具有零知識屬性。

（2）具備高效性，整個過程中計算量比較小，雙方交換的資訊同樣少。

（3）目前，大部分零知識證明相關技術，通常避免直接應用于有政府限制的加密系統，同時這也給相關産品的出口帶來了很大的機遇。

4零知識證明協定

4.1 基本的零知識證明協定

零知識的數學分析，需要使用分割技術來實作，假設證明了資訊的一部分，而這個資訊是一個非常困難的問題，解決基本零知識協定包括以下步驟 ：

（1）一個新的解決方案是證明者利用位承諾方案來送出。

（2）驗證者不能由新難題得到關于舊難題的所有資訊，并且證明者向驗證者透漏這個新的難題。

（3）驗證者問者要向他證明，新老問題是同構的，即上一步的解決必須解決的新問題。

（4）證明者同意。

（5）驗證者和證明者重複執行上面幾步。

這種證明的操作背景極其複雜，應慎重選擇問題和随機變化，使問題在多次疊代後無法得到原始問題的任何資訊。

4.2并行的零知識證明協定

基層的零知識系統證明包含A和B之間的多次交換資訊，可以把它們合并完成：

（1）A利用其資訊和多個随機數将問題轉化為多個不同的同構問題，然後利用其資訊和随機數求解多個問題。 A送出這多個新難題的解法。

（2）A向B透露這n個新難題。B無法在這些新問題中得到任何關于原問題或其解法的所有資訊。

（3）對每一個問題,B要求A向他證明新舊問題是同構的，并且他在第2步中使用的解法,并判定這就是新難題的方案。

（4）A對多個新問題中的任何一個都表示通過。

是以，這個協定似乎在實踐中是安全的，因為沒有人知道如何證明它。在某些環境中，某些協定的某些問題可以并行運作，同時，必須保持其零知識屬性 [3]。

4.3 非互動式的零知識證明協定

二十世紀八十年代,那時候人們已經發明了非互動類型的零知識的證明系統。非互動式零知識證明協定不需要任何互相作用，并證明可以釋出協定，證明該協定是有效的任何人誰需要時間來驗證它。此基本協定類似于并行零知識證明，但隻使用單向散列函數代替B ：

(1)A隻是利用他的資訊和多個随機數，并把這個問題轉化成多個不同的同構問題,然後根據他的資訊以及随機數處理多個新難題。

(2)A呈交多個新問題的解決方案。

(3)A作為一個特定的單向散列函數的輸入,把所有這些送出的解決方法，儲存到這個單向散列函數。

(4)A提出在第3步中生成的多個位，針對某個新難題依次取出多個位中的第i個位,假設它是0,我們就能斷定新舊問題是同構的,假設它是1,則斷定他在第2步中送出的解決方案,并證明它就是這個新問題的解決方法。

(5)A必須将第2步中的任何協定及第4步中的解決方案都公開。

（6）B以及其他人,都可以判斷從第1步到第5步，是否都能被順利進行。

該協定工作的原因是單向散列函數作為一個公正随機位發生器。如果一個是欺騙，他必須能夠預測單向散列函數的輸出。但是，它是不可能強制散列函數或猜測它會有什麼位置 [4]。這種單向散列函數實際上是B在協定中的替代品--在第四步中随機選取了兩個證明之一。

5  零知識的身份證明應用案例

假設，我們把合法的個人資訊當成是證明者的知識，證明者必須通過零知識證明向驗證者确定自己的身份資訊，這個過程就是就是零知識身份認證。所謂的零知識身份認證就是零知識證明在身份認證領域的一些應用。目前的完善的零知識身份認證大體有四種。由于篇幅有限，下面僅對Fiat—Shamir這個案例做進一步解釋說明，并對其具有的完備性，合理性和零知識性一系列特性進行合理的證明[5]。

Fiat—Shamir身份的認證協定程序協定主要是:A在多次疊代程序中向B送出他的身份。

 （1）一次建立階段，該階段必須完成以下兩個任務,并且在多次疊代程序之前一次完成。 

①信任中心T選擇和釋出随機模拟子產品的N，N = PXQ。p，Q為兩個大素數，可信中心的P和Q機密性（RSA）。

②申請人A選擇一個和12互素的秘密值S，1小于等于S小于等于n一1。計算=MOD，最後向可信中心T申請v做他的公鑰。

（2）協定資訊。t輪中的任何一輪會産生以下三條通訊:

①AB:x=mod。

②BA:e∈{0,1}。

③AB:y=r? rood. 

（3）協定執行。 以下程序在疊代了t輪之後，輪與輪之間是斷斷續續進行的并且必須互相獨立的。假設這t輪都成功了，則B就确定了A的身份。

①A确定一個随機數r，1小于r小于n一1。計算x=r mod n,發送給 B。

②B随機的确定一個挑戰比特位W，W∈{0,1},發送給A。

③假設A收到W=O,則運作y=r。假設收l J W=l,則計算Y等于mod n。然後向B發送響應Y。

④B驗證y2=?v.mod n.如果檢驗成立,則B可以接受A的申請,否則就會拒絕。

身份認證系統協定的完備性,合理性和零知識性證明。

（1）完備性證明：

①當W=O時,y=r,.lJy2等于r2.又等于r mod,是以?v x=r mod。 故Y等于v rood n。此時B驗證提示成功。

②當W=1時,Y=rsmodny2=r S mod n。?y e=X o P=r s。是以y2=? V mod n。此時B也能确定驗證是成功的。是以,一旦A和B都是真實的，并按照協定計算無誤，則B對A的身份認證将是成功的，是以Fiat—Shamir身份認證系統必須滿足完備性。

1. 合理性證明：

①如果第三方要欺騙B。首先第三方可以悄悄的通過Fiat—Shamir認證協定的第一步驟。然後，在第三步中，~U W=0或W=l的機率都是一半，是由于W是随機産生的。

②當W=0時,y=r。此時第三方一旦把他第一步中産生的随機數r，轉發給B即可經過驗證，此次過程冒充勝利。

③但當W=l時,Y=r s mod。此時，第三方為了計算Y的正确發送給B，首先要正确計算S的值。但s2等于v mod n。為了由v求出s的資訊，困難性和分解大整數n的困難性是相同的。是以，第三方得到正确的s值的機率基本為0。是以，當W=l時，第三方假裝A會不會成功。由1）和2）可以得出，程序執行一次，第三方冒充A正确的機率是一半。則執行t次，第三方假冒A成功的機率為1/2的t次方。是以說，在t很大時，第三方冒充A正确的機率近乎是0。是以說，Fiat—Shamir身份認證協定必須要滿足其自身合理性[6]。

（3）零知識證明：S是一個秘密值，隻有一個知道，是以S是A的身份知識。在這個協定的執行，B沒有得到任何關于S本身的資訊。即使B知道V，y和x的值，但是找不到正确的s值。 原因是N的平方根本身是個難題。是以，菲亞特夏米爾認證協定滿足零知識。 認為佩吉有一定的知識（如一些不解決長期問題的解決方法），零知識證明是在不披露知識的内容的前提下，驗證者維克多在佩吉 和維克多證明他們有知識。首先，讓我們看一看佩吉和維克多之間的對話：佩吉：“我可以解密的密文C”維克多：“我不相信。請證明。”佩吉：“關鍵是K，你可以看到解密到M的消息。”維克多：“那麼我現在也知道了密鑰以及資訊。”在這裡，雖然佩吉證明了他有一定的知識（重點K和明文M），但要披露維克多的知識。一個更好的對話是：佩吉：“我可以解密加密的C消息。”維克托：“我不相信。請你開始證明。”佩吉：“讓我們使用一零知識協定，我将證明我的知識在任何高機率（但不會透露任何有關情況的資訊給你）。”維克托：“好的”。佩吉和維克托通過零知識證明協定，可以解釋使用零知識洞穴的例子，有一個C和D之間的門，隻有人們知道咒語打開。佩吉知道咒語，并試圖證明給維克托，但他不想透露它 [7]。步驟如下：

①維克多站在A點。

②佩吉開始走并走進洞内，到達C點或者D點。

③當佩吉消失在洞中的時候，Victor走到B點。

④維克多可以指定左轉或者右轉，要求佩吉從該通道出來。

⑤佩吉從維克多要求的通道出來，如果有必要就用咒語打開密門。

⑥佩吉和維克多重複步驟1）至5）n次。 

如果佩吉不知道這個魔咒，那麼隻出了一條路，如果你是按的要求在每輪Peggy Peggy的通道中達成一緻的話，那麼所有n時間的猜測機率是1 / 2N。經過兩輪，佩吉隻有一個65536分的機會來猜測。是以，維克托可以假設，如果所有16次佩吉的是正确的，那麼她必須知道門點之間的C點和D點如何打開。讓我們看一個零知識證明的例子。如果圖是同構的，很難判斷兩個圖是否同構于一個非常大的圖，這是一個NP完全問題。對于圖G1和G2，如果有一個一一對應的函數f，定義域是頂點集的G1，f的範圍是G2的頂點集。當且僅當[ G1，G2 ]是G1的一側，[ F（G1），F（G2）]是G2的一側，表示G1和G2同構。如果，佩吉明白G1和G2之間是同構的，佩吉要使用零知識列協定向使維克多證明G1和G2是同構的[8]：

①佩吉變換G1産生另一個圖H，并且使得H和G1同構。由于佩吉知道G1和H同構，也等同于知道了H和G2是同構的。

②佩吉把H送給維克多。

③對于下面兩個問題，維克多可以選擇其中的一個，要求佩吉向其證明。然而，維克多不能要求兩者都證明。

④佩吉按照維克多指定的要求證明。

⑤佩吉和維克多重複以上步驟多次。

這裡假設佩吉不知道G1和G2之間的同構性，佩吉隻能建立一個圖或同構到G1或同構到G2。每一輪佩吉都有一半的機會猜測維克托的選擇。由于佩吉在每個回合的協定産生一個新的H，是以無論多少回合後，協定維克多沒有收到任何關于佩吉的資訊，他不能了解的同構G1和G2從佩吉的回答。在這裡，我們引入了一個簡化的方案為知名菲戈菲亞特-夏米爾零知識認證協定。信任仲裁指定了一個随機兩個大素數的乘積n，實際上最少達到512或高達1024。仲裁員産生一個随機數V，使X2等于 V mod n，即模N的V的平方，和v-1mod N.存在。佩吉的公鑰是V，然後，運算出的最小整數：S 的那個呀SQRT（V-1）mod n作為佩吉的私人密。實施身份證的協定如下 ：

①使用者佩吉取随機數r，這裡r＜m，計算x= r2 mod m，把x送給維克多。

②維克多把一個随機位b送給佩吉。

③若b=0，則佩吉将r送給維克多；若b=1，則佩吉将y=r s 送給維克多

④若b=0，則維克多驗證x=r2 mod m ，進而證明佩吉知道sqrt(x)

如果b=1，那麼維克多需要驗證x=y2.v mod m，進一步證明佩吉是知道s的。這本身就是一項驗證，直到維克多相信佩吉知道s，佩吉和維克多可以将此協定重複多次[9]。

6 總結

零知識證明技術是近年來各個應用領域資訊安全加密的重點研究對象。但由于應用領域環境的特殊性,傳統的加密技術并不能直接應用于目前的複雜環境。本論文主要讨論了零知識證明的一般過程和技術特點，總結了零知識證明系統的特征和優點。但是加密技術是一項新型且複雜的技術，涉及的應用範圍比較廣泛，我們國外的一些零知識證明研究不是太深。想要更深入的了解研究零知識證明，還需要全體從事研究人員做進一步的研究。