零知識(shí)證明課件

1、15.1 交互式零知識(shí)證明系統(tǒng)的定義交互式零知識(shí)證明系統(tǒng)的定義 l交互圖靈機(jī)作為證明者和驗(yàn)證者各自的計(jì)交互圖靈機(jī)作為證明者和驗(yàn)證者各自的計(jì)算模型，將他們各自的交互圖靈機(jī)連接起算模型，將他們各自的交互圖靈機(jī)連接起來聯(lián)合計(jì)算就構(gòu)成一問一答的交互協(xié)議。來聯(lián)合計(jì)算就構(gòu)成一問一答的交互協(xié)議。 l定義定義15.1 一個(gè)交互圖靈機(jī)是一個(gè)（確定性）多帶圖靈機(jī)。它具有下列帶：1）一條只讀輸入帶；2）一條只讀隨機(jī)帶；3）一條讀寫工作帶；4）一條只寫輸出帶；5）一條只讀通信帶和一條只寫通信帶；6）一條僅有一個(gè)小方格的讀寫開關(guān)帶。 l 定義定義 15.2 二個(gè)交互圖靈機(jī)連接在一起，若一個(gè)圖靈機(jī)的識(shí)別標(biāo)記為1而另一個(gè)圖

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

3、一時(shí)刻輸出帶的內(nèi)容決定。 l 定義定義15.3 設(shè)A，B為連接起來的一對(duì)交互圖靈機(jī)，設(shè)對(duì)每一共同輸入，它們的聯(lián)合計(jì)算在有限步終止。記(A,B)(x)為共同輸入x聯(lián)合計(jì)算終止時(shí)B的輸出。它是在0,1中取值的隨機(jī)變量，即在聯(lián)合計(jì)算終止時(shí)刻圖靈機(jī)B的只寫頭在輸出帶所寫的二進(jìn)數(shù)。由于A，B的隨機(jī)輸入滿足隨機(jī)數(shù)約定，故(A,B)(x)為隨機(jī)變量。l 定義定義15.4 一個(gè)交互圖靈機(jī)A稱為有時(shí)間復(fù)雜性 （正整數(shù)集），若它與每個(gè)交互圖靈機(jī)B連接起來和對(duì)每個(gè)共同輸入x，它總是在t(|x|)步內(nèi)停機(jī)（與A和B的隨機(jī)輸入無關(guān)，只要滿足隨機(jī)數(shù)約定即可）。特別若存在一個(gè)正多項(xiàng)式p(n)，使圖靈機(jī)A有時(shí)間復(fù)雜性p(|x

4、|)，則稱圖靈機(jī)A是多項(xiàng)式時(shí)間的。 ZZt :l 定義定義15.5 一對(duì)連接起來的交互圖靈機(jī)（P，V）稱為語言L成員識(shí)別問題的交互（式省去）證明系統(tǒng)，若V是多項(xiàng)式時(shí)間的，且滿足下列兩個(gè)條件。(1)完全性：對(duì)每個(gè)xL， (15.1）(2)合理性：對(duì)每個(gè)xL和每個(gè)交互圖靈機(jī)B，B與V連接起來， 或 （15.2）l 其中V的輸出(P,V)(x)和(B,V)(x)表示驗(yàn)證者是否接受xL，輸出1表示接受xL，輸出0表示拒絕xL。 3/21)(VP(Prx），3/20)(VB(Prx），3/11)(VB(Prx），l定理定理15.1 語言L的成員識(shí)別問題屬于NP，當(dāng)且僅當(dāng)它有一個(gè)交互證明系統(tǒng)具有下列兩個(gè)性

5、質(zhì)。(1)交互是單向的（從證明者到驗(yàn)證者）。(2)證明者和驗(yàn)證者都只用確定性算法（不出錯(cuò)）。 l 定義定義15.6 設(shè)（P，V）為語言L的交互證明系統(tǒng)（參看定義15.5），稱（P，V）為語言L的一個(gè)關(guān)于不誠實(shí)驗(yàn)證者的交互完全零知識(shí)證明系統(tǒng)，若對(duì)每個(gè)多項(xiàng)式時(shí)間的交互圖靈機(jī)V*，存在一個(gè)多項(xiàng)式時(shí)間的概率圖靈機(jī)M*，使對(duì)每個(gè)xL，下面兩個(gè)條件成立。1)當(dāng)M*的輸入為x時(shí)，它以2-p(|x|)的概率輸出一個(gè)特殊符號(hào)，記作，即，其中p(n)為任一固定的正多項(xiàng)式。2）記m*(x)為一隨機(jī)變量，其分布為M*(x) 的條件下M*(x)的條件分布，即再記ViewP,V(x)為共同輸入x時(shí)在P與V*交互（聯(lián)合計(jì)算

6、）過程中從V*的隨機(jī)帶讀出的隨機(jī)數(shù)以及V*從P收到的消息，稱為V*的觀察。于是有ViewP,V(x)與m*(x)是相同分布的隨機(jī)變量。M*稱為P與V*交互的完善模擬器。 |)(|*2)(MPrxpx *10)(M|)(MPr)(Pr，xxxml定義定義15.7 設(shè)(P，V)為語言L的交互證明系統(tǒng)，稱(P，V)為語言L的一個(gè)關(guān)于不誠實(shí)驗(yàn)證者的交互計(jì)算零知識(shí)證明系統(tǒng)，若對(duì)每個(gè)多項(xiàng)式時(shí)間的交互圖靈機(jī)V*，存在一個(gè)多項(xiàng)式時(shí)間的概率圖靈機(jī)M*，使隨機(jī)變量族 與 是計(jì)算不可區(qū)分的（參看定義6.2）。M*稱為P與V*交互的模擬器。 LV,P)(*xxViewL*)(Mxxl 定義定義15.8 設(shè)（P，V）為

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

8、變量族 與 是計(jì)算不可區(qū)分的（參看定義6.2）。 LV,P)(xxViewL)(Mxx15.2 交互零知識(shí)證明系統(tǒng)的構(gòu)造交互零知識(shí)證明系統(tǒng)的構(gòu)造 l （一）無向圖的同構(gòu)問題l 1. 共同輸入為兩個(gè)同構(gòu)的圖G1=(V1，E1)和G2=(V2，E2)。設(shè)為G1到G2的同構(gòu)，即為從V1到V2的1-1映射，使(u,v) E1，當(dāng)且僅當(dāng) 。l 2. 重復(fù)執(zhí)行下列36步n次。l 3. P按等概分布隨機(jī)選擇V2的一個(gè)置換并構(gòu)造圖G=(V，E)，其中，（）；。P將G=(V，E)發(fā)給V。l 4. V收到P發(fā)送的圖G=(V，E)后，按等概分布隨機(jī)選擇一個(gè)1,2，V將發(fā)送給P，要求P給出到G的同構(gòu)。l 5. 若P收

9、到V發(fā)送的，則P將發(fā)送給V，否則，即2，則P將發(fā)送給V。l 6. 若V收到P發(fā)送的消息，記作，是G到G的同構(gòu)，則V輸出1（接受），否則V輸出0（拒絕）。2E)(),(vu（)(,),(),(V|V|212uuu|V|2122.,Vuuu2E),(),(),(Evuvu)V),()(1uuul 定理定理15.2 上面給出的程序GI是語言GI的一個(gè)關(guān)于不誠實(shí)驗(yàn)證者的交互完全零知識(shí)證明系統(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)），則對(duì)每個(gè)交互圖靈機(jī)B即對(duì)每一個(gè)可能的證明者B與V交互，驗(yàn)證

10、者仍用V的程序4和6，則驗(yàn)證者拒絕xGI的概率至少是1/2。3)對(duì)每個(gè)多項(xiàng)式時(shí)間的交互圖靈機(jī)V*，存在一個(gè)多項(xiàng)式時(shí)間的概率圖靈機(jī)M*，當(dāng)輸入x=（G1，G2）GI時(shí)， 與m*(x)是相同分布的隨機(jī)變量（參看定義15.6），其中，證明者仍用P的程序3和5。 11)(V,P(Prx2/10)(V,B(Prx)(*V,PxView（二）二次剩余問題 l 1. 共同輸入為N,x，其中N為未知因子分解的N=PQ,P,Q為素?cái)?shù)，x與N互素，xQR(N)l 2. 重復(fù)執(zhí)行3-6步logN次（N看作二進(jìn)數(shù)表示）。l 3. P按等概分布從ZN*中隨機(jī)選出一個(gè)v，計(jì)算y=v2(mod N)，P將y發(fā)送給V。l 4

11、. V 收到P發(fā)送的y后，按等概分布隨機(jī)選擇一個(gè)0,1，V將發(fā)送給P。l 5. P收到V發(fā)送的后，計(jì)算，其中u為x的一個(gè)模N的平方根，P將z發(fā)送給V。l 6. 若V收到P發(fā)送的z滿足 ，則V輸出1（接受），否則V輸出0（拒絕）。 )(modNvuz)(mod2Nyxzl 定理定理15.3 上面給出的程序QR是語言QR的一個(gè)關(guān)于不誠實(shí)驗(yàn)證者的交互完全零知識(shí)證明系統(tǒng)。更確切地說，它滿足下列性質(zhì)。1)若 xQR(N)，則2)若 xQR(N)，則對(duì)每個(gè)交互圖靈機(jī)B或3)對(duì)每個(gè)多項(xiàng)式時(shí)間的交互圖靈機(jī)V*，存在一個(gè)多項(xiàng)式時(shí)間的概率圖靈機(jī)M*，當(dāng)輸入xQR(N)時(shí)， 與m*(x)是相同分布的隨機(jī)變量，其中，

12、證明者仍用P的程序3和5。 11)(V,P(Prx2/10)(V,B(Prx2/11)(VP(Prx），)(*V,PxView（三）子群成員問題 l 1.共同輸入為(N,l,)，其中,ZN*， , 的階為l。l 2.重復(fù)執(zhí)行36步logN次（N看作二進(jìn)數(shù)表示）。l 3.P按等概分布從o,1,l-1中隨機(jī)選出一個(gè)j，計(jì)算r= j (mod N)，P將r發(fā)送給V。l 4.V收到P發(fā)送的r后，按等概分布隨機(jī)選擇一個(gè)0,1，V將發(fā)送給P。l 5.P收到V發(fā)送的后，計(jì)算h=j+ m(mod N)，其中m=log （的以為底的離散對(duì)數(shù)），P將h發(fā)送給V。l 6.若V收到P發(fā)送的h滿足 ，則V輸出1（接受）

13、，否則V輸出0（拒絕）。 )(modNrhl定理定理15.4 上面給出的程序SM是語言SM的一個(gè)關(guān)于不誠實(shí)驗(yàn)證者的交互完全零知識(shí)證明系統(tǒng)。 NP完全類問題的交互零知識(shí)證明系統(tǒng)圖的3-著色問題 l 1. 共同輸入為一可3-著色的圖G=(V，E)。l 2. 重復(fù)執(zhí)行下列36步|E|2次。l 3. 設(shè)為圖G的一個(gè)3-著色。P按等概分布隨機(jī)選擇1,2,3的一個(gè)置換，并構(gòu)造，即為圖G的一個(gè)隨機(jī)3-著色（顏色的標(biāo)記1，2，3是隨機(jī)的）。P用|V|個(gè)保險(xiǎn)箱，每個(gè)保險(xiǎn)箱里放一個(gè)(u),uV，將所有|V|個(gè)保險(xiǎn)箱都發(fā)送給V（驗(yàn)證者）。l 4. V（驗(yàn)證者）按等概分布從E中隨機(jī)選出一條邊(u,v)，將它發(fā)送給P，

14、要求檢查u和v的著色。l 5. P收到V發(fā)送的(u,v)后，將放有(u)和(v)的兩個(gè)保險(xiǎn)箱的密碼發(fā)送給V。l 6. V打開這兩個(gè)保險(xiǎn)箱，若他看到的是1,2,3中兩個(gè)不同的數(shù)，則V輸出1（接受），否則V輸出0（拒絕）。 V),()(uuu15.3 非交互零知識(shí)證明系統(tǒng)理論非交互零知識(shí)證明系統(tǒng)理論 l 定義定義15.10 一對(duì)概率圖靈機(jī)（P，V）稱為語言L的非交互證明系統(tǒng)，若V是多項(xiàng)式時(shí)間的，且滿足下列兩個(gè)條件。l 1）完全性：對(duì)每個(gè)xL， （15.4）l 其中，x為（P，V）的共同輸入；R為（P，V）的共同參考序列，它是在0,1p(|x|)中等概分布的隨機(jī)序列，p(n)為任一固定的正多項(xiàng)式；P

15、(x,R)為P發(fā)送給V的消息（P的輸出和V的輸入）。l 2）合理性：對(duì)每個(gè)L和每個(gè)交互圖靈機(jī)B或 (15.5)l 其中， 表示驗(yàn)證者接受L， 表示驗(yàn)證者拒絕L。 3/21),(P,(VPrRxRx3/20),(B,(VPrRxRx3/11),(B,(VPrRxRx1),(B,(VRxRx0),(B,(VRxRxl定義定義15.11 一個(gè)語言L的非交互證明系統(tǒng)（P，V）稱為是計(jì)算零知識(shí)的，若存在一正多項(xiàng)式p(n)和一個(gè)多項(xiàng)式時(shí)間概率圖靈機(jī)M，使隨機(jī)變量族與 是計(jì)算不可區(qū)分的。 L|)(|)(|),(P,(xxpxpUxUxL)(Mxxl 定義定義15.12 一對(duì)概率圖靈機(jī)（P，V）稱為語言L的隱

16、比特證明系統(tǒng)，若V是多項(xiàng)式時(shí)間的，且滿足下列兩個(gè)條件。1)完全性：對(duì)每個(gè)xL，其中， 為P發(fā)送給V的消息（P的輸出和V的輸入），Cer稱為證明書， 為的指定位置集，稱為泄漏的比特位置集，x為（P，V）的共同輸入，R=r1,rt是在0,1p(|x|)中等概分布的隨機(jī)序列，為R在指定位置集I上的子序列，稱為泄漏的比特序列。2)合理性：對(duì)每個(gè)xL和每個(gè)概率圖靈機(jī)B或其中， 是B發(fā)送給V的消息（B的輸出和V的輸入）。 3/21),(VPrCerIRxI),(P),(RxCerI|)(|, 2 , 1,1xpiiIiiIrrR13/20),(VPrCerIRxI3/11),(VPrCerIRxI),(B

17、),(RxCerIl定義定義15.13 一個(gè)語言L的隱比特證明系統(tǒng)（P，V）稱為是計(jì)算零知識(shí)的，若存在一個(gè)多項(xiàng)式時(shí)間概率圖靈機(jī)M，使隨機(jī)變量族與 是計(jì)算不可區(qū)分的。 LL),(),(P,(xIxICerIRxRxRxL)(Mxx構(gòu)造一個(gè)語言L的非交互證明系統(tǒng)（P，V） l 1. 共同輸入x0,1n。l 2. 共同參考序列為s=s1,sm，其中每個(gè)si0,1n。l 3. 證明者（記作P）的程序。1)對(duì)每個(gè)i1,m，計(jì)算。2)向P要。3)輸出 （P 發(fā)送給V的消息），其中， ，。l 4. 驗(yàn)證者（記作V）的程序1) 輸入P輸出的 后，對(duì)每個(gè)ijI，檢驗(yàn) 是否成立。若發(fā)現(xiàn)有一個(gè)不成立，則V停止和拒絕

18、。2) 計(jì)算，記。3) 向V要輸出作為V的輸出，即V接受當(dāng)且僅當(dāng)V接受。 )(1iisfbr),(),(P1CerIrrxm),(IpCerIiiI,1）ppsfsfpiiI111()()(1),(IpCerI)(jipfsj, 1),(ipbrii),(1rrr),(VCerIrx語言HC的隱比特零知識(shí)證明系統(tǒng)l 1. 共同輸入= G=(V，E)HC，其中|V|=n。l 2. 共同參考序列看作一個(gè)n3n3矩陣M，其元素為1的概率為n-5，元素為0的概率為1-n-5。l 3. 證明者（記作P）的程序。設(shè)C為G中的一個(gè)哈密爾頓圈。1) 證明者考察矩陣M，分如下兩種情況。l 情況一：M為有用。記H為M中的哈密