零知识证明课件(PPT 25页)

1、15.1 交互式零知识证明系统的定义 交互图灵机作为证明者和验证者各自的计算模型，将他们各自的交互图灵机连接起来联合计算就构成一问一答的交互协议。 定义15.1 一个交互图灵机是一个（确定性）多带图灵机。它具有下列带：1）一条只读输入带；2）一条只读随机带；3）一条读写工作带；4）一条只写输出带；5）一条只读通信带和一条只写通信带；6）一条仅有一个小方格的读写开关带。 第1页，共25页。定义 15.2 二个交互图灵机连接在一起，若一个图灵机的识别标记为1而另一个图灵机的识别标记为0，它们的输入带合一，开关带合一，一个图灵机的只读通信带与另一图灵机的只写通信带合一，反之前者的只写通信带与后者的只

2、读通信带合一，但两个图灵机的随机带，工作带和输出带是分开的。一对连接起来的交互图灵机在初始时刻有共同的输入，并置开关带的内容为0。它们的联合计算程序是一对形的有限或无限序列，其中一个形序列代表一个图灵机的计算程序。序列中的每一对形总是有一个图灵机（不必是同一个）工作而另一个图灵机休息。第一对形对应于图灵机的初始状态，共同输入和开关带的内容0。若一个图灵机停机了但开关带的内容仍与它的识别标记相等，称这时两个图灵机都已停机了，即计算在这一时刻终止。两个图灵机的输出由这一时刻输出带的内容决定。 第2页，共25页。定义15.3 设A，B为连接起来的一对交互图灵机，设对每一共同输入，它们的联合计算在有限

3、步终止。记(A,B)(x)为共同输入x联合计算终止时B的输出。它是在0,1中取值的随机变量，即在联合计算终止时刻图灵机B的只写头在输出带所写的二进数。由于A，B的随机输入满足随机数约定，故(A,B)(x)为随机变量。定义15.4 一个交互图灵机A称为有时间复杂性 （正整数集），若它与每个交互图灵机B连接起来和对每个共同输入x，它总是在t(|x|)步内停机（与A和B的随机输入无关，只要满足随机数约定即可）。特别若存在一个正多项式p(n)，使图灵机A有时间复杂性p(|x|)，则称图灵机A是多项式时间的。 第3页，共25页。定义15.5 一对连接起来的交互图灵机（P，V）称为语言L成员识别问题的交互

4、（式省去）证明系统，若V是多项式时间的，且满足下列两个条件。(1)完全性：对每个xL， (15.1）(2)合理性：对每个xL和每个交互图灵机B，B与V连接起来， 或 （15.2）其中V的输出(P,V)(x)和(B,V)(x)表示验证者是否接受xL，输出1表示接受xL，输出0表示拒绝xL。 第4页，共25页。定理15.1 语言L的成员识别问题属于NP，当且仅当它有一个交互证明系统具有下列两个性质。(1)交互是单向的（从证明者到验证者）。(2)证明者和验证者都只用确定性算法（不出错）。 第5页，共25页。定义15.6 设（P，V）为语言L的交互证明系统（参看定义15.5），称（P，V）为语言L的一

5、个关于不诚实验证者的交互完全零知识证明系统，若对每个多项式时间的交互图灵机V*，存在一个多项式时间的概率图灵机M*，使对每个xL，下面两个条件成立。1)当M*的输入为x时，它以2-p(|x|)的概率输出一个特殊符号，记作，即，其中p(n)为任一固定的正多项式。2）记m*(x)为一随机变量，其分布为M*(x) 的条件下M*(x)的条件分布，即再记ViewP,V(x)为共同输入x时在P与V*交互（联合计算）过程中从V*的随机带读出的随机数以及V*从P收到的消息，称为V*的观察。于是有ViewP,V(x)与m*(x)是相同分布的随机变量。M*称为P与V*交互的完善模拟器。 第6页，共25页。定义15

6、.7 设(P，V)为语言L的交互证明系统，称(P，V)为语言L的一个关于不诚实验证者的交互计算零知识证明系统，若对每个多项式时间的交互图灵机V*，存在一个多项式时间的概率图灵机M*，使随机变量族 与 是计算不可区分的（参看定义6.2）。M*称为P与V*交互的模拟器。 第7页，共25页。定义15.8 设（P，V）为语言L的交互证明系统，称（P，V）为语言L的一个关于不诚实验证者的交互统计（几乎完全）零知识证明系统，若对每个多项式时间的交互图灵机V*，存在一个多项式时间的概率图灵机M*，使随机变量族 与是统计接近的，即它们的变差距离（15.3）是|x|的一个可忽略函数，即对每个正多项式p(n)及一

7、切充分大的|x|有。 第8页，共25页。定义15.9 设（P，V）为语言L的交互证明系统，称（P，V）为语言L的一个关于诚实验证者的交互计算零知识证明系统，若存在一个多项式时间概率图灵机M，使随机变量族 与 是计算不可区分的（参看定义6.2）。 第9页，共25页。15.2 交互零知识证明系统的构造 （一）无向图的同构问题1. 共同输入为两个同构的图G1=(V1，E1)和G2=(V2，E2)。设为G1到G2的同构，即为从V1到V2的1-1映射，使(u,v) E1，当且仅当 。2. 重复执行下列36步n次。3. P按等概分布随机选择V2的一个置换并构造图G=(V，E)，其中，（）；。P将G=(V，

8、E)发给V。4. V收到P发送的图G=(V，E)后，按等概分布随机选择一个1,2，V将发送给P，要求P给出到G的同构。5. 若P收到V发送的，则P将发送给V，否则，即2，则P将发送给V。6. 若V收到P发送的消息，记作，是G到G的同构，则V输出1（接受），否则V输出0（拒绝）。第10页，共25页。定理15.2 上面给出的程序GI是语言GI的一个关于不诚实验证者的交互完全零知识证明系统。更确切地说，它满足下列性质。1)若x=（G1，G2）GI（G1与G2同构），则即验证者总是接受x GI。2)若x=（G1，G2）GI（G1与G2不同构），则对每个交互图灵机B即对每一个可能的证明者B与V交互，验证

9、者仍用V的程序4和6，则验证者拒绝xGI的概率至少是1/2。3)对每个多项式时间的交互图灵机V*，存在一个多项式时间的概率图灵机M*，当输入x=（G1，G2）GI时， 与m*(x)是相同分布的随机变量（参看定义15.6），其中，证明者仍用P的程序3和5。 第11页，共25页。（二）二次剩余问题 1. 共同输入为N,x，其中N为未知因子分解的N=PQ,P,Q为素数，x与N互素，xQR(N)2. 重复执行3-6步logN次（N看作二进数表示）。3. P按等概分布从ZN*中随机选出一个v，计算y=v2(mod N)，P将y发送给V。4. V 收到P发送的y后，按等概分布随机选择一个0,1，V将发送给

10、P。5. P收到V发送的后，计算，其中u为x的一个模N的平方根，P将z发送给V。6. 若V收到P发送的z满足 ，则V输出1（接受），否则V输出0（拒绝）。 第12页，共25页。定理15.3 上面给出的程序QR是语言QR的一个关于不诚实验证者的交互完全零知识证明系统。更确切地说，它满足下列性质。1)若 xQR(N)，则2)若 xQR(N)，则对每个交互图灵机B或3)对每个多项式时间的交互图灵机V*，存在一个多项式时间的概率图灵机M*，当输入xQR(N)时， 与m*(x)是相同分布的随机变量，其中，证明者仍用P的程序3和5。 第13页，共25页。（三）子群成员问题 1.共同输入为(N,l,)，其中

11、,ZN*， , 的阶为l。2.重复执行36步logN次（N看作二进数表示）。3.P按等概分布从o,1,l-1中随机选出一个j，计算r= j (mod N)，P将r发送给V。4.V收到P发送的r后，按等概分布随机选择一个0,1，V将发送给P。5.P收到V发送的后，计算h=j+ m(mod N)，其中m=log （的以为底的离散对数），P将h发送给V。6.若V收到P发送的h满足 ，则V输出1（接受），否则V输出0（拒绝）。 第14页，共25页。定理15.4 上面给出的程序SM是语言SM的一个关于不诚实验证者的交互完全零知识证明系统。 第15页，共25页。NP完全类问题的交互零知识证明系统图的3-着

12、色问题 1. 共同输入为一可3-着色的图G=(V，E)。2. 重复执行下列36步|E|2次。3. 设为图G的一个3-着色。P按等概分布随机选择1,2,3的一个置换，并构造，即为图G的一个随机3-着色（颜色的标记1，2，3是随机的）。P用|V|个保险箱，每个保险箱里放一个(u),uV，将所有|V|个保险箱都发送给V（验证者）。4. V（验证者）按等概分布从E中随机选出一条边(u,v)，将它发送给P，要求检查u和v的着色。5. P收到V发送的(u,v)后，将放有(u)和(v)的两个保险箱的密码发送给V。6. V打开这两个保险箱，若他看到的是1,2,3中两个不同的数，则V输出1（接受），否则V输出0

13、（拒绝）。 第16页，共25页。15.3 非交互零知识证明系统理论 定义15.10 一对概率图灵机（P，V）称为语言L的非交互证明系统，若V是多项式时间的，且满足下列两个条件。1）完全性：对每个xL， （15.4）其中，x为（P，V）的共同输入；R为（P，V）的共同参考序列，它是在0,1p(|x|)中等概分布的随机序列，p(n)为任一固定的正多项式；P(x,R)为P发送给V的消息（P的输出和V的输入）。2）合理性：对每个L和每个交互图灵机B或 (15.5)其中， 表示验证者接受L， 表示验证者拒绝L。 第17页，共25页。定义15.11 一个语言L的非交互证明系统（P，V）称为是计算零知识的，

14、若存在一正多项式p(n)和一个多项式时间概率图灵机M，使随机变量族与 是计算不可区分的。 第18页，共25页。定义15.12 一对概率图灵机（P，V）称为语言L的隐比特证明系统，若V是多项式时间的，且满足下列两个条件。1)完全性：对每个xL，其中， 为P发送给V的消息（P的输出和V的输入），Cer称为证明书， 为的指定位置集，称为泄漏的比特位置集，x为（P，V）的共同输入，R=r1,rt是在0,1p(|x|)中等概分布的随机序列，为R在指定位置集I上的子序列，称为泄漏的比特序列。2)合理性：对每个xL和每个概率图灵机B或其中， 是B发送给V的消息（B的输出和V的输入）。 第19页，共25页。定

15、义15.13 一个语言L的隐比特证明系统（P，V）称为是计算零知识的，若存在一个多项式时间概率图灵机M，使随机变量族与 是计算不可区分的。 第20页，共25页。构造一个语言L的非交互证明系统（P，V） 1. 共同输入x0,1n。2. 共同参考序列为s=s1,sm，其中每个si0,1n。3. 证明者（记作P）的程序。1)对每个i1,m，计算。2)向P要。3)输出 （P 发送给V的消息），其中， ，。4. 验证者（记作V）的程序1) 输入P输出的 后，对每个ijI，检验 是否成立。若发现有一个不成立，则V停止和拒绝。2) 计算，记。3) 向V要输出作为V的输出，即V接受当且仅当V接受。 第21页，

16、共25页。语言HC的隐比特零知识证明系统1. 共同输入= G=(V，E)HC，其中|V|=n。2. 共同参考序列看作一个n3n3矩阵M，其元素为1的概率为n-5，元素为0的概率为1-n-5。3. 证明者（记作P）的程序。设C为G中的一个哈密尔顿圈。1) 证明者考察矩阵M，分如下两种情况。情况一：M为有用。记H为M中的哈密尔顿nn子矩阵，CH为H对应的哈密尔顿圈。2）证明者泄漏M中除H以外的所有n6-n2个元素。3）证明者计算出(1,2)，其中1为V到H的行的1-1映射，2为V到H的列的1-1映射，使G中的哈密尔顿圈C上的边映射到H中的元素1，即将任一有序顶点对(u,v),u,vV，映射到H的1(u)行2(v)列的元素。若(u.v) C，则H的1(u)行2(v)列的元素为1，即映射(1,2)是C到CH的一个同构。 第22页，共25页。4）证明者泄漏所有(u,v) E对应的H的1(u)行2(v)列的个元素。5）证明者输出(I,Cer)，MI（P发送给V（验证者）的消息），其中，Cer= (1,2) ，I为P泄漏的M中所有n6-|E|个元素的位置，MI为P泄漏的M中所有n6-|E|个元素，都是0。情况二： M不为有用。6）证明者只输出（I，MI）（没有