零知識證明

15.1交互式零知識證明系統(tǒng)的定義

交互圖靈機(jī)作為證明者和驗(yàn)證者各自的計算模型，將他們各自的交互圖靈機(jī)連接起來聯(lián)合計算就構(gòu)成一問一答的交互協(xié)議。

定義15.1

一個交互圖靈機(jī)是一個（確定性）多帶圖靈機(jī)。它具有下列帶：1）一條只讀輸入帶；2）一條只讀隨機(jī)帶；3）一條讀寫工作帶；4）一條只寫輸出帶；5）一條只讀通信帶和一條只寫通信帶；6）一條僅有一個小方格的讀寫開關(guān)帶。定義15.2

二個交互圖靈機(jī)連接在一起，若一個圖靈機(jī)的識別標(biāo)記為1而另一個圖靈機(jī)的識別標(biāo)記為0，它們的輸入帶合一，開關(guān)帶合一，一個圖靈機(jī)的只讀通信帶與另一圖靈機(jī)的只寫通信帶合一，反之前者的只寫通信帶與后者的只讀通信帶合一，但兩個圖靈機(jī)的隨機(jī)帶，工作帶和輸出帶是分開的。一對連接起來的交互圖靈機(jī)在初始時刻有共同的輸入，并置開關(guān)帶的內(nèi)容為0。它們的聯(lián)合計算程序是一對形的有限或無限序列，其中一個形序列代表一個圖靈機(jī)的計算程序。序列中的每一對形總是有一個圖靈機(jī)（不必是同一個）工作而另一個圖靈機(jī)休息。第一對形對應(yīng)于圖靈機(jī)的初始狀態(tài)，共同輸入和開關(guān)帶的內(nèi)容0。若一個圖靈機(jī)停機(jī)了但開關(guān)帶的內(nèi)容仍與它的識別標(biāo)記相等，稱這時兩個圖靈機(jī)都已停機(jī)了，即計算在這一時刻終止。兩個圖靈機(jī)的輸出由這一時刻輸出帶的內(nèi)容決定。定義15.3

設(shè)A，B為連接起來的一對交互圖靈機(jī)，設(shè)對每一共同輸入，它們的聯(lián)合計算在有限步終止。記(A,B)(x)為共同輸入x聯(lián)合計算終止時B的輸出。它是在{0,1}中取值的隨機(jī)變量，即在聯(lián)合計算終止時刻圖靈機(jī)B的只寫頭在輸出帶所寫的二進(jìn)數(shù)。由于A，B的隨機(jī)輸入滿足隨機(jī)數(shù)約定，故(A,B)(x)為隨機(jī)變量。定義15.4

一個交互圖靈機(jī)A稱為有時間復(fù)雜性（正整數(shù)集），若它與每個交互圖靈機(jī)B連接起來和對每個共同輸入x，它總是在t(|x|)步內(nèi)停機(jī)（與A和B的隨機(jī)輸入無關(guān)，只要滿足隨機(jī)數(shù)約定即可）。特別若存在一個正多項式p(n)，使圖靈機(jī)A有時間復(fù)雜性p(|x|)，則稱圖靈機(jī)A是多項式時間的。定義15.5

一對連接起來的交互圖靈機(jī)（P，V）稱為語言L成員識別問題的交互（式省去）證明系統(tǒng)，若V是多項式時間的，且滿足下列兩個條件。(1)完全性：對每個x∈L， (15.1）(2)合理性：對每個x∈L和每個交互圖靈機(jī)B，B與V連接起來， 或 （15.2）其中V的輸出(P,V)(x)和(B,V)(x)表示驗(yàn)證者是否接受x∈L，輸出1表示接受x∈L，輸出0表示拒絕x∈L。定理15.1

語言L的成員識別問題屬于NP，當(dāng)且僅當(dāng)它有一個交互證明系統(tǒng)具有下列兩個性質(zhì)。(1)交互是單向的（從證明者到驗(yàn)證者）。(2)證明者和驗(yàn)證者都只用確定性算法（不出錯）。定義15.6

設(shè)（P，V）為語言L的交互證明系統(tǒng)（參看定義15.5），稱（P，V）為語言L的一個關(guān)于不誠實(shí)驗(yàn)證者的交互完全零知識證明系統(tǒng)，若對每個多項式時間的交互圖靈機(jī)V*，存在一個多項式時間的概率圖靈機(jī)M*，使對每個x∈L，下面兩個條件成立。

1)當(dāng)M*的輸入為x時，它以2-p(|x|)的概率輸出一個特殊符號，記作⊥，即 ，其中p(n)為任一固定的正多項式。

2）記m*(x)為一隨機(jī)變量，其分布為M*(x)≠⊥的條件下M*(x)的條件分布，即 再記ViewP,V’(x)為共同輸入x時在P與V*交互（聯(lián)合計算）過程中從V*的隨機(jī)帶讀出的隨機(jī)數(shù)以及V*從P收到的消息，稱為V*的觀察。 于是有ViewP,V’(x)與m*(x)是相同分布的隨機(jī)變量。

M*稱為P與V*交互的完善模擬器。定義15.7

設(shè)(P，V)為語言L的交互證明系統(tǒng)，稱(P，V)為語言L的一個關(guān)于不誠實(shí)驗(yàn)證者的交互計算零知識證明系統(tǒng)，若對每個多項式時間的交互圖靈機(jī)V*，存在一個多項式時間的概率圖靈機(jī)M*，使隨機(jī)變量族 與 是計算不可區(qū)分的（參看定義6.2）。

M*稱為P與V*交互的模擬器。定義15.8

設(shè)（P，V）為語言L的交互證明系統(tǒng)，稱（P，V）為語言L的一個關(guān)于不誠實(shí)驗(yàn)證者的交互統(tǒng)計（幾乎完全）零知識證明系統(tǒng)，若對每個多項式時間的交互圖靈機(jī)V*，存在一個多項式時間的概率圖靈機(jī)M*，使隨機(jī)變量族與 是統(tǒng)計接近的，即它們的變差距離 （15.3） 是|x|的一個可忽略函數(shù)，即對每個正多項式p(n)及一切充分大的|x|有 。定義15.9

設(shè)（P，V）為語言L的交互證明系統(tǒng)，稱（P，V）為語言L的一個關(guān)于誠實(shí)驗(yàn)證者的交互計算零知識證明系統(tǒng)，若存在一個多項式時間概率圖靈機(jī)M，使隨機(jī)變量族 與 是計算不可區(qū)分的（參看定義6.2）。15.2交互零知識證明系統(tǒng)的構(gòu)造

（一）無向圖的同構(gòu)問題1.共同輸入為兩個同構(gòu)的圖G1=(V1，E1)和G2=(V2，E2)。設(shè)Φ為G1到G2的同構(gòu)，即Φ為從V1到V2的1-1映射，使(u,v)∈E1，當(dāng)且僅當(dāng) 。2.重復(fù)執(zhí)行下列3－6步n次。3.P按等概分布隨機(jī)選擇V2的一個置換并構(gòu)造圖G’=(V’，E’)，其中 ，（ ）； 。P將G’=(V’，E’)發(fā)給V。4.V收到P發(fā)送的圖G’=(V’，E’)后，按等概分布隨機(jī)選擇一個σ∈{1,2}，V將σ發(fā)送給P，要求P給出到G’的同構(gòu)。5.若P收到V發(fā)送的σ，則P將π發(fā)送給V，否則，即σ≠2，則P將 發(fā)送給V。6.若V收到P發(fā)送的消息，記作ψ，是Gσ到G’的同構(gòu)，則V輸出1（接受），否則V輸出0（拒絕）。定理15.2

上面給出的程序GI是語言GI的一個關(guān)于不誠實(shí)驗(yàn)證者的交互完全零知識證明系統(tǒng)。更確切地說，它滿足下列性質(zhì)。1)若x=（G1，G2）∈GI（G1與G2同構(gòu)），則 即驗(yàn)證者總是接受x∈GI。2)若x=（G1，G2）∈GI（G1與G2不同構(gòu)），則對每個交互圖靈機(jī)B

即對每一個可能的證明者B與V交互，驗(yàn)證者仍用V的程序4和6，則驗(yàn)證者拒絕x∈GI的概率至少是1/2。3)對每個多項式時間的交互圖靈機(jī)V*，存在一個多項式時間的概率圖靈機(jī)M*，當(dāng)輸入x=（G1，G2）∈GI時， 與m*(x)是相同分布的隨機(jī)變量（參看定義15.6），其中，證明者仍用P的程序3和5。（二）二次剩余問題1.共同輸入為N,x，其中N為未知因子分解的N=PQ,P,Q為素數(shù)，x與N互素，x∈QR(N)2.重復(fù)執(zhí)行3-6步「logN」次（N看作二進(jìn)數(shù)表示）。3.P按等概分布從ZN*中隨機(jī)選出一個v，計算y=v2(modN)，P將y發(fā)送給V。4.V收到P發(fā)送的y后，按等概分布隨機(jī)選擇一個σ∈{0,1}，V將σ發(fā)送給P。5.P收到V發(fā)送的σ后，計算 ，其中u為x的一個模N的平方根，P將z發(fā)送給V。6.若V收到P發(fā)送的z滿足 ，則V輸出1（接受），否則V輸出0（拒絕）。定理15.3

上面給出的程序QR是語言QR的一個關(guān)于不誠實(shí)驗(yàn)證者的交互完全零知識證明系統(tǒng)。更確切地說，它滿足下列性質(zhì)。1)若x∈QR(N)，則2)若x∈QR(N)，則對每個交互圖靈機(jī)B

或3)對每個多項式時間的交互圖靈機(jī)V*，存在一個多項式時間的概率圖靈機(jī)M*，當(dāng)輸入x∈QR(N)時， 與m*(x)是相同分布的隨機(jī)變量，其中，證明者仍用P的程序3和5。（三）子群成員問題1.共同輸入為(N,l,α,β)，其中α,β∈ZN*，α≠β,α的階為l。2.重復(fù)執(zhí)行3－6步「logN」次（N看作二進(jìn)數(shù)表示）。3.P按等概分布從{o,1,…,l-1}中隨機(jī)選出一個j，計算r=αj(modN)，P將r發(fā)送給V。4.V收到P發(fā)送的r后，按等概分布隨機(jī)選擇一個σ∈{0,1}，V將σ發(fā)送給P。5.P收到V發(fā)送的σ后，計算h=j+σm(modN)，其中m=logαβ（β的以α為底的離散對數(shù)），P將h發(fā)送給V。6.若V收到P發(fā)送的h滿足 ，則V輸出1（接受），否則V輸出0（拒絕）。定理15.4上面給出的程序SM是語言SM的一個關(guān)于不誠實(shí)驗(yàn)證者的交互完全零知識證明系統(tǒng)。NP完全類問題的交互零知識證明系統(tǒng)——圖的3-著色問題

1.共同輸入為一可3-著色的圖G=(V，E)。2.重復(fù)執(zhí)行下列3－6步|E|2次。3.設(shè)ψ為圖G的一個3-著色。P按等概分布隨機(jī)選擇{1,2,3}的一個置換π，并構(gòu)造 ，即Φ為圖G的一個隨機(jī)3-著色（顏色的標(biāo)記1，2，3是隨機(jī)的）。P用|V|個保險箱，每個保險箱里放一個Φ(u),u∈V，將所有|V|個保險箱都發(fā)送給V（驗(yàn)證者）。4.V（驗(yàn)證者）按等概分布從E中隨機(jī)選出一條邊(u,v)，將它發(fā)送給P，要求檢查u和v的著色。5.P收到V發(fā)送的(u,v)后，將放有Φ(u)和Φ(v)的兩個保險箱的密碼發(fā)送給V。6.V打開這兩個保險箱，若他看到的是{1,2,3}中兩個不同的數(shù)，則V輸出1（接受），否則V輸出0（拒絕）。15.3非交互零知識證明系統(tǒng)理論

定義15.10

一對概率圖靈機(jī)（P，V）稱為語言L的非交互證明系統(tǒng)，若V是多項式時間的，且滿足下列兩個條件。1）完全性：對每個x∈L，（15.4）其中，x為（P，V）的共同輸入；R為（P，V）的共同參考序列，它是在{0,1}p(|x|)中等概分布的隨機(jī)序列，p(n)為任一固定的正多項式；P(x,R)為P發(fā)送給V的消息（P的輸出和V的輸入）。2）合理性：對每個L和每個交互圖靈機(jī)B

或 (15.5)其中， 表示驗(yàn)證者接受L， 表示驗(yàn)證者拒絕L。定義15.11

一個語言L的非交互證明系統(tǒng)（P，V）稱為是計算零知識的，若存在一正多項式p(n)和一個多項式時間概率圖靈機(jī)M，使隨機(jī)變量族 與是計算不可區(qū)分的。定義15.12

一對概率圖靈機(jī)（P，V）稱為語言L的隱比特證明系統(tǒng)，若V是多項式時間的，且滿足下列兩個條件。1)完全性：對每個x∈L， 其中， 為P發(fā)送給V的消息（P的輸出和V的輸入），Cer稱為證明書， 為的指定位置集，稱為泄漏的比特位置集，x為（P，V）的共同輸入，R=r1,…rt是在{0,1}p(|x|)中等概分布的隨機(jī)序列， 為R在指定位置集I上的子序列，稱為泄漏的比特序列。2)合理性：對每個x∈L和每個概率圖靈機(jī)B

或 其中， 是B發(fā)送給V的消息（B的輸出和V的輸入）。定義15.13

一個語言L的隱比特證明系統(tǒng)（P，V）稱為是計算零知識的，若存在一個多項式時間概率圖靈機(jī)M，使隨機(jī)變量族 與是計算不可區(qū)分的。構(gòu)造一個語言L的非交互證明系統(tǒng)（P’，V’）1.共同輸入x∈{0,1}n。2.共同參考序列為s={s1,…,sm}，其中每個si∈{0,1}n。3.證明者（記作P’）的程序。

1)對每個i∈{1,…,m}，計算 。

2)向P要 。

3)輸出 （P’發(fā)送給V’的消息），其中，， 。4.驗(yàn)證者（記作V’）的程序

1)輸入P’輸出的 后，對每個ij∈I，檢驗(yàn)是否成立。若發(fā)現(xiàn)有一個不成立，則V’停止和拒絕。

2)計算 ，記 。

3)向V要輸出 作為V’的輸出，即V’接受當(dāng)且僅當(dāng)V接受。語言HC的隱比特零知識證明系統(tǒng)1.共同輸入=G=(V，E)HC，其中|V|=n。2.共同參考序列看作一個n3×n3矩陣M，其元素為1的概率為n-5，元素為0的概率為1-n-5。3.證明者（記作P）的程序。設(shè)C為G中的一個哈密爾頓圈。

1)證明者考察矩陣M，分如下兩種情況。情況一：M為有用。記H為M中的哈密爾頓n×n子矩陣，CH為H對應(yīng)的哈密爾頓圈。

2）證明者泄漏M中除H以外的所有n6-n2個元素。

3）證明者計算出(Φ1,Φ2)，其中Φ1為V到H的行的1-1映射，Φ2為V到H的列的1-1映射