零知識(shí)證明課件(PPT 25頁)

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

2、讀通信帶合一，但兩個(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ī)的輸出由這一時(shí)刻輸出帶的內(nèi)容決定。 第2頁，共25頁。定義15.3 設(shè)A，B為連接起來的一對(duì)交互圖靈機(jī)，設(shè)對(duì)每一共同輸入，它們的聯(lián)合計(jì)算在有限

3、步終止。記(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ī)變量。定義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|)，則稱圖靈機(jī)A是多項(xiàng)式時(shí)間的。 第3頁，共25頁。定義15.5 一對(duì)連接起來的交互圖靈機(jī)（P，V）稱為語言L成員識(shí)別問題的交互

4、（式省去）證明系統(tǒng)，若V是多項(xiàng)式時(shí)間的，且滿足下列兩個(gè)條件。(1)完全性：對(duì)每個(gè)xL， (15.1）(2)合理性：對(duì)每個(gè)xL和每個(gè)交互圖靈機(jī)B，B與V連接起來， 或 （15.2）其中V的輸出(P,V)(x)和(B,V)(x)表示驗(yàn)證者是否接受xL，輸出1表示接受xL，輸出0表示拒絕xL。 第4頁，共25頁。定理15.1 語言L的成員識(shí)別問題屬于NP，當(dāng)且僅當(dāng)它有一個(gè)交互證明系統(tǒng)具有下列兩個(gè)性質(zhì)。(1)交互是單向的（從證明者到驗(yàn)證者）。(2)證明者和驗(yàn)證者都只用確定性算法（不出錯(cuò)）。 第5頁，共25頁。定義15.6 設(shè)（P，V）為語言L的交互證明系統(tǒng)（參看定義15.5），稱（P，V）為語言L的一

5、個(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ì)算）過程中從V*的隨機(jī)帶讀出的隨機(jī)數(shù)以及V*從P收到的消息，稱為V*的觀察。于是有ViewP,V(x)與m*(x)是相同分布的隨機(jī)變量。M*稱為P與V*交互的完善模擬器。 第6頁，共25頁。定義15

6、.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*交互的模擬器。 第7頁，共25頁。定義15.8 設(shè)（P，V）為語言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)及一

7、切充分大的|x|有。 第8頁，共25頁。定義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ī)變量族 與 是計(jì)算不可區(qū)分的（參看定義6.2）。 第9頁，共25頁。15.2 交互零知識(shí)證明系統(tǒng)的構(gòu)造 （一）無向圖的同構(gòu)問題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) 。2. 重復(fù)執(zhí)行下列36步n次。3. P按等概分布隨機(jī)選擇V2的一個(gè)置換并構(gòu)造圖G=(V，E)，其中，（）；。P將G=(V，

8、E)發(fā)給V。4. V收到P發(fā)送的圖G=(V，E)后，按等概分布隨機(jī)選擇一個(gè)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（拒絕）。第10頁，共25頁。定理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)證

9、者仍用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頁，共25頁。（二）二次剩余問題 1. 共同輸入為N,x，其中N為未知因子分解的N=PQ,P,Q為素?cái)?shù)，x與N互素，xQR(N)2. 重復(fù)執(zhí)行3-6步logN次（N看作二進(jìn)數(shù)表示）。3. P按等概分布從ZN*中隨機(jī)選出一個(gè)v，計(jì)算y=v2(mod N)，P將y發(fā)送給V。4. V 收到P發(fā)送的y后，按等概分布隨機(jī)選擇一個(gè)0,1，V將發(fā)送給

10、P。5. P收到V發(fā)送的后，計(jì)算，其中u為x的一個(gè)模N的平方根，P將z發(fā)送給V。6. 若V收到P發(fā)送的z滿足 ，則V輸出1（接受），否則V輸出0（拒絕）。 第12頁，共25頁。定理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ī)變量，其中，證明者仍用P的程序3和5。 第13頁，共25頁。（三）子群成員問題 1.共同輸入為(N,l,)，其中

11、,ZN*， , 的階為l。2.重復(fù)執(zhí)行36步logN次（N看作二進(jìn)數(shù)表示）。3.P按等概分布從o,1,l-1中隨機(jī)選出一個(gè)j，計(jì)算r= j (mod N)，P將r發(fā)送給V。4.V收到P發(fā)送的r后，按等概分布隨機(jī)選擇一個(gè)0,1，V將發(fā)送給P。5.P收到V發(fā)送的后，計(jì)算h=j+ m(mod N)，其中m=log （的以為底的離散對(duì)數(shù)），P將h發(fā)送給V。6.若V收到P發(fā)送的h滿足 ，則V輸出1（接受），否則V輸出0（拒絕）。 第14頁，共25頁。定理15.4 上面給出的程序SM是語言SM的一個(gè)關(guān)于不誠實(shí)驗(yàn)證者的交互完全零知識(shí)證明系統(tǒng)。 第15頁，共25頁。NP完全類問題的交互零知識(shí)證明系統(tǒng)圖的3-著

12、色問題 1. 共同輸入為一可3-著色的圖G=(V，E)。2. 重復(fù)執(zhí)行下列36步|E|2次。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)證者）。4. V（驗(yàn)證者）按等概分布從E中隨機(jī)選出一條邊(u,v)，將它發(fā)送給P，要求檢查u和v的著色。5. P收到V發(fā)送的(u,v)后，將放有(u)和(v)的兩個(gè)保險(xiǎn)箱的密碼發(fā)送給V。6. V打開這兩個(gè)保險(xiǎn)箱，若他看到的是1,2,3中兩個(gè)不同的數(shù)，則V輸出1（接受），否則V輸出0

13、（拒絕）。 第16頁，共25頁。15.3 非交互零知識(shí)證明系統(tǒng)理論 定義15.10 一對(duì)概率圖靈機(jī)（P，V）稱為語言L的非交互證明系統(tǒng)，若V是多項(xiàng)式時(shí)間的，且滿足下列兩個(gè)條件。1）完全性：對(duì)每個(gè)xL， （15.4）其中，x為（P，V）的共同輸入；R為（P，V）的共同參考序列，它是在0,1p(|x|)中等概分布的隨機(jī)序列，p(n)為任一固定的正多項(xiàng)式；P(x,R)為P發(fā)送給V的消息（P的輸出和V的輸入）。2）合理性：對(duì)每個(gè)L和每個(gè)交互圖靈機(jī)B或 (15.5)其中， 表示驗(yàn)證者接受L， 表示驗(yàn)證者拒絕L。 第17頁，共25頁。定義15.11 一個(gè)語言L的非交互證明系統(tǒng)（P，V）稱為是計(jì)算零知識(shí)的，

14、若存在一正多項(xiàng)式p(n)和一個(gè)多項(xiàng)式時(shí)間概率圖靈機(jī)M，使隨機(jī)變量族與 是計(jì)算不可區(qū)分的。 第18頁，共25頁。定義15.12 一對(duì)概率圖靈機(jī)（P，V）稱為語言L的隱比特證明系統(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的輸入）。 第19頁，共25頁。定

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

16、共25頁。語言HC的隱比特零知識(shí)證明系統(tǒng)1. 共同輸入= G=(V，E)HC，其中|V|=n。2. 共同參考序列看作一個(gè)n3n3矩陣M，其元素為1的概率為n-5，元素為0的概率為1-n-5。3. 證明者（記作P）的程序。設(shè)C為G中的一個(gè)哈密爾頓圈。1) 證明者考察矩陣M，分如下兩種情況。情況一：M為有用。記H為M中的哈密爾頓nn子矩陣，CH為H對(duì)應(yīng)的哈密爾頓圈。2）證明者泄漏M中除H以外的所有n6-n2個(gè)元素。3）證明者計(jì)算出(1,2)，其中1為V到H的行的1-1映射，2為V到H的列的1-1映射，使G中的哈密爾頓圈C上的邊映射到H中的元素1，即將任一有序頂點(diǎn)對(duì)(u,v),u,vV，映射到H的1(u)行2(v)列的元素。若(u.v) C，則H的1(u)行2(v)列的元素為1，即映射(1,2)是C到CH的一個(gè)同構(gòu)。 第22頁，共25頁。4）證明者泄漏所有(u,v) E對(duì)應(yīng)的H的1(u)行2(v)列的個(gè)元素。5）證明者輸出(I,Cer)，MI（P發(fā)送給V（驗(yàn)證者）的消息），其中，Cer= (1,2) ，I為P泄漏的M中所有n6-|E|個(gè)元素的位置，MI為P泄漏的M中所有n6-|E|個(gè)元素，都是0。情況二： M不為有用。6）證明者只輸出（I，MI）（沒有