1、零知识证明的概念 设P表示掌握某些信息，并希望证实这一事实的实体，设V是证明这一事实的实体。n某个协议向V证明P的确掌握某些信息，但V无法推断出这些信息是什么，我们称P实现了最小泄露证明。n如果V除了知道P能够证明某一事实外，不能够得到其他任何知识，我们称P实现了零知识证明，相应的协议称作零知识协议。零知识证明的概念n在最小泄露协议中满足下述两个性质：n(1)P无法欺骗V。换言之，若P不知道一个定理的证明方法，则P使V相信他会证明定理的概率很低。（正确性）n(2)V无法欺骗P。换言之，若P知道一个定理的证明方法，则P使V以绝对优势的概率相信他能证明。（完备性）n在零知识协议中，除满足上述两个条
2、件以外，还满足下述性质：n(3)V无法获取任何额外的知识。（零知识性）零知识洞穴n设P知道咒语，可打开C和D之间的秘密门，不知道者则走向死胡同。现在来看P如何向V出示证明使其相信他知道这个秘密，但又不告诉V有关咒语。n协议1：洞穴协议n V站在A点；nP进入任一点C或D；n当P进洞之后，V走向B点；nV叫P：(a)从左边出来，或(b)从右边出来 nP按照要求实现（有咒语）；nP和V重复执行(1)(5)共n次。零知识洞穴n若P不知道咒语，则在B点，只有50%的机会猜中V的要求，协议执行n次，则只有2 n次机会完全猜中。此洞穴问题可以转化为数学问题，P知道解决某个难题的秘密信息，而V通过与P交互作
3、用验证其真伪。CDBA5零知识证明可以向另一方证明自己拥有某种信息而无需暴露该信息给对方。交互式零知识证明 证明者和验证者共享输入证明者和验证者共享输入(函数或者是值函数或者是值)如果验证者检查，对于每一个挑战的响应都是正确的，这个协议才输如果验证者检查，对于每一个挑战的响应都是正确的，这个协议才输出出Accept，否则，输出，否则，输出 RejectP证明者证明者V验证者验证者承诺承诺挑战挑战响应响应Repeats trounds输入输入输入输入平方根问题的零知识 n令N=P Q，P、Q为两个大素数，Y是mod N的一个平方，且gcd(Y,N)=1，注意找到mod N的平方根与分解N等价。n
4、Peggy声称他知道Y的一个平方根S，但他不愿意泄露S，Vector想证明Peggy是否真的知道。下面给出了这个问题的一个解决方案。nPeggy选择两个随机数R1和R2，满足gcd(R1,N)=1，R2=S R11，R1 R2=S(mod N)。Peggy计算X1=R12(mod N)，X2=R22(mod N)，并将X1、X2发送给Vector。nVector检验X1 X2=Y(mod N)，然后Vector随机选择X1（或X2）让Peggy提供它的一个平方根，并检验Peggy是否提供的是真的平方根。n重复上面的过程直至Vector相信。n这里，Peggy不知道Y的平方根，虽然他可能知道X1
5、、X2的一个平方根，但不是全部。离散对数问题的零知识证明 Peggy试图向Vector证明他知道离散对数x，x=loggY mod p，Y=gx mod plogmod,(Ymod)xgxYpgppgRZttqRmod*qRZuquxtwmodpYgRuwmod?RuwCommitmentChallengeResponseProverVerifierPeggy试图向Vector证明两个离散对数相等而不泄露x，Y=gx，Z=cx，loggY=logc ZZYcZgYcgxxloglog,pcRpgRZtttqRmodmod21*qRZuquxtwmodpZcRpYgRuwuwmodmod?2?1
6、uwCommitmentChallengeResponseProverVerifier21,RR离散对数问题的零知识证明证明ElGamal解密的正确性比如，Peggy试图证明他的ElGamal解密是正确的。n明文是m而不泄露他的私钥x。Peggy的私钥为Y=gx mod p；nElGamal加密为m (U,V)，nElGamal解密为V/Ux mnPeggy只需证明下面的两个离散对数相等即可：Y=gx，V/m=Ux，logg Y=logU(V/m)。pmYVpgUrrmodmodn使用 Fiat-Shamir Heuristic的非交互零知识证明(NIZK)非交互零知识证明 logmod,(Y
7、mod)xgxYpgpquxtwRYHupgRZttqRmod),(mod*pYgRRYHuuwmod),(?),(wRProverVerifier身份鉴别方案 n在一个安全的身份认证协议中，我们希望被认证者P能向验证者V电子地证明他的身份，而又不向P泄露他的认证信息nFeige-Fiat-Shamir身份鉴别方案 nGuillo-Quisquater身份鉴别方案 nSchnorr身份鉴别方案 简化的Feige-Fiat-Shamir身份鉴别方案 n可信赖仲裁方选定一个随机模数n=p1 p2，p1、p2为两个大素数。实际中n至少为512比特，尽量长达1024比特。仲裁方可实施公钥和私钥的分配。
8、他产生随机数v（v为对模n的二次剩余）。n换言之，选择v使得x2=v mod n有一个解并且v1 mod n 存在。以v作为被验证方的公钥，而后计算最小的整数s：s sqrt(v 1)mod n，将它作为被验方P的私人密钥而分发给他。简化的Feige-Fiat-Shamir身份鉴别方案n实施身份证明的协议如下：(1)用户P取随机数r（r m），计算x=(x2)mod n，送给验证方V：(2)V将随机比特b送给P；(3)若b=0，则P将r送给V；若b=1，则将y=r s mod n送给V；(4)若b=0，则V验证x=r2 mod n，从而证明P知道sqrt(x)；若b=1，则V验证x=y2 v
9、mod n，从而证明P知道s。n这是一轮认证，P和V可将此协议重复t次，直到V确信P知道s为止。BA)(mod 2nrx proof.therejects otherwise,proof;theaccepts then),(mod and 0 If2B Bnvxyye1 0,e)(mod ns ry e简化的Feige-Fiat-Shamir身份鉴别方案简化的Feige-Fiat-Shamir身份鉴别方案n安全性讨论如下：nP欺骗V的可能性。P不知道s，他也可选取随机数r，将x=r 2 mod n发给V，V发送随机比特b给P，P可将r送出。当b=0时，则V让P通过检验而受骗；当b=1时，则V可
10、发现P不知道s。V受骗的概率为1/2，但连续t次受骗的概率将仅为21。nV伪装P的可能性。V和其他验证者W开始一个协议。第一步他可用P用过的随机数r，若W所选的b值恰与以前发给P的一样，则V可将在第(3)步所发的r或y重发给W，从而可成功的伪装P。但W可能随机地选b为0或1，故这种工具成功的概率为1/2，执行t次，则可使其将为2t。n可信赖仲裁方选n=p1 p2，p1、p2为两个大素数，并选k个不同的随机数v1,v2,vk，各vi是mod n的平方剩余，且有逆。以v1,v2,vk为被验证方P的公钥，计算最小正整数si，使si=mod n，将s1,s2,sk作为P的私人密钥。Feige-Fiat
11、-Shamir身份鉴别方案 1/ivFeige-Fiat-Shamir身份鉴别方案 n协议如下：(1)P选随机数r（r m），计算x=r2 mod n并发送给验证方V；(2)V选k比特随机二进制串b1,b2,bk传送给P；(3)P计算y=r (s1b1 s2b2 skbk)mod n，并送给V；(4)V验证x=y2 (v1b1 v2b2 vkbk)mod n。n此协议可执行t次，直到V相信P知道s1,s2,sk，P欺骗V的机会为2 k t。Feige-Fiat-Shamir身份鉴别方案AB)(mod 2nrx proof.therejects otherwise,proof;theaccept
12、s then,and)0(mod If12B Bxznvyzjjeej 1 0,),.,(1ikeee)(mod 1nsryjejGuillo-Quisquater身份鉴别方案 nGuillo和Quisquater给出一种身份认证方案，这个协议需要三方参与、三次传送，利用公钥体制实现。n可信赖仲裁方T先选定RSA的秘密参数p和q，生成大整数模n=p q。公钥指数有e 3，其中gcd(,e)=1，=(p 1)(q 1)。计算出秘密指数d=e1 mod ，公开(e,n)，各用户选定自己的参数。n用户A的唯一性身份IA，通过散列函数H变换得出相应散列值JA=H(IA)，I JA 2160，元素g为q
13、阶元素，l g p 1。令a为GF(p)的生成元，则得到g=a(p 1)/q mod q。由可信赖的第三方T向各用户分发系统参数(p,q,g)和验证函数（即T的公钥），用此验证T对消息的签字。Schnorr身份鉴别方案n对每个用户给定惟一身份I，用户A选定秘密密钥s，0 s q 1，并计算v=gs mod p；A将IA和v可靠地送给T，并从T获得证书，CA=(IA,v,ST(IA,v)。n协议如下：n（1）选定随机数r，1 r q 1，计算x=g r mod p，这是预处理步骤，可在B出现之前完成；n（2）A将(CA,x)送给B；n（3）B以T的公钥解ST(IA,v)，实现对A的身份IA和公钥
14、v认证，并传送一个介于0到2 t 1之间的随机数e给A；n（4）A验证1 e 2 t，计算y=(s e+r)mod q，并将y送给B；n（5）B验证x=gy ve mod p，若该等式成立，则认可A的身份合法。n安全性基于参数t，t要选得足够大以使正确猜对e的概率2t足够小。Schnorr建议t为72位，p大约为512位，q为140位。n此协议是一种对s的零知识证明，在认证过程中没有暴露有关s的任何有用信息。Schnorr身份鉴别方案BA,(mod)rACxypIf (mod),then accepts the proof;otherwise,rejects the proof.yexgvxp
15、 BBqeet21 where,(mod)ys erq 复杂性理论 n在计算机学科中，存在多项式时间的算法的一类问题，称之为P类问题；而向旅行商问题、命题表达式可满足问题这类，至今没有找到多项式时间算法解的一类问题，称之为NP类问题。nNP问题中最难的称之为NP完全问题 n（1）旅行商问题n（2）三方匹配问题n（3）三方满足问题NP与零知识证明 n每一个NP问题都存在一个零知识证明nGMR(Goldwasser,Micali,Rackoff)n“The knowledge complexity of interactive-proof systems”,Proc.of 17th ACM Sym.on Theory of Computation,pp.291-304,1985n“The knowledge complexity of interactive-proof systems”,Siam J.on Computation,Vol.18,pp.186-208,1989(revised version)n 图同构G0PG1PG0G1PG0G1PG0G1PG0G1G0G10TG0G1HC=0G0G1HX=TorX=T*P (X=T*P)-1G0G1X=?G0t轮
