零知识证明及其应用

《网络安全》课程论文

题目零知识证明理论及其应用

学院计算机与信息科学学

软件学院

专业

年级

学号

姓名

指导教师

成绩_____________________

2014年11月16 日

零知识证明理论及其应用

摘要：“零知识证明”－zero-knowledge proof，是由Goldwasser等人在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。本文介绍了零知识证明的概念,并对零知识证明的一般过程进行分析.同时,阐述零知识证明的性质和优点.最后,综述了零知识证明的应用。

关键字：零知识证明身份认证交互式非交互式

一、引言

21世纪是信息时代，信息已经成为社会发展的重要战略资源，社会的信息化已成为当今世界发展的潮流和核心，而信息安全在信息社会中将扮演极为重要的角色，它直接关系到国家安全、企业经营和人们的日常生活。

密码学的出现给这些安全带来了保证，而大量事实证明，零知识证明在密码学中非常有用。Goldwasser等人提出的零知识证明中，证明者和验证者之间必须进行交互，这样的零知识证明被称为“交互零知识证明”。

80年代末，Blum等人进一步提出了“非交互零知识证明”的概念，用一个短随机串代替交互过程并实现了零知识证明。非交互零知识证明的一个重要应用场合是需要执行大量密码协议的大型网络。在零知识证明中,一个人(或器件)可以在不泄漏任何秘密的情况下,证明他知道这个秘密..如果能够将零知识证明用于验证,将可以有效解决许多问题。

二、概念

“零知识证明”－zero-knowledge proof，是由Goldwasser等人在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。

零知识证明分为交互式零知识证明和非交互式零知识证明两种类型。

三、零知识证明的一般过程

证明方和验证方拥有相同的某一个函数或一系列的数值.零知识证明的一般过程如下:

1.证明方向验证方发送满足一定条件的随机值,这个随机值称为"承

诺".[1]

2.验证方向证明方发送满足一定条件的随机值,这个随机值称为"挑

战".[1]

3.证明方执行一个秘密的计算,并将结果发送给验证方,这个结果称

为"响应"。

4)验证方对响应进行验证,如果验证失败,则表明证明方不具有他所

谓的"知识",退出此过程。否则,继续从1)开始,重复执行此过程t次。

如果每一次验证方均验证成功,则验证方便相信证明方拥有某种知识。而且此过程中,验证方没有得到关于这个知识的一点信息。

四、零知识证明的性质

根据零知识证明的定义和有关例子,可以得出零知识证明具有以下三条性质:

1.完备性[2].如果证明方和验证方都是诚实的,并遵循证明过程的每

一步,进行正确的计算,那么这个证明一定是成功的,验证方一定能够接受

证明方。

2.合理性[2].没有人能够假冒证明方,使这个证明成功。

3.零知识性[2].证明过程执行完之后,验证方只获得了"证明方拥有

这个知识"这条信息,而没有获得关于这个知识本身的任何一点信息。

五、零知识证明的优点

根据零知识证明及其有关的协议主要有以下优点[3]:

1.随着零知识证明的使用,安全性不会降级,因为该证明具有零知识

性质。

2.高效性.该过程计算量小,双方交换的信息量少。

3.安全性依赖于未解决的数学难题,如离散对数,大整数因子分解,平

方根等。

4.许多零知识证明相关的技术避免了直接使用有政府限制的加密算

法,这就给相关产品的出口带来了优势。

六、零知识证明身份认证

如果我们把合法用户的个人信息看作是证明方的知识,证明方通过零知识证明向验证方证实自己的身份就是零知识身份认证.零知识身份认证

是零知识证明在身份认证方面的应用.目前的零知识身份认证方案主要有

四种:Fiat—Shamir身份认证,Feige-Piat-Shamir身份认证,Guillo—

Ouisquater身份认证和Schnorr身份认证.其中Fiat—Shamir身份认证

是最早提出的,也是最基础的零知识身份认证方案,其他三种方案是对

Fiat—Shamir的改进.下面仅就Fiat—Shamir方案做一个介绍,并证明其

完备性,合理性和零知识性.

（一）Fiat—Shamir身份认证协议过程

协议概要:A在t次迭代过程中向B证明他的身份。

1.一次建立[3]

该阶段主要完成以下两项任务,且在t次迭代过程之前一次完成。

（1）一个可信中心T选择并发布一个类似于RSA的随机模数n,n=pXq.

P,q为两个大素数,可信中心对P和q保密。

（2）申请者A选择一个和12互素的秘密值S,1≤s≤n一1.计算=mod.

并向可信中心T注册v做为他的公钥。

2.协议消息[3]

t轮中的每一轮会产生如下三条信息:

（1）AB:x=,mod.

（2）BA:e∈{0,1}.

（3）AB:y=r?'rood.

3.协议执行[3][4]

以下步骤迭代t轮,轮与轮之间是连续进行的而且是相互独立的.如果这t轮都成功了,则B就接受A的身份.

（1）A选择一个承诺随机数r,1≤r≤n一1.计算x=rmodn,发送给 B.

（2）B随机选择一个挑战比特位e,e∈{0,1},发送给A。

（3）A如果收到e=O,则计算y=r.如果收~lJe=l,则计算Y=modn。

然后向B发送响应Y。

（4）B验证y2=?v.modn.如果验证成功,则接受A的响应,否则拒绝。

（二）Fiat—Shamir身份认证协议的完备性,合理性和零知识性证明

1.完备性证明

（1）当e=O时,y=r,.~lJy2=r2.又=rmod,所以?vx=rmod. 故

Y=?vroodn.此时B验证成功。

（2）当e=1时,Y=rsmodny2=rSmodn.?ye=XoP=rs..所以y2=? vmodn.

此时B也能验证成功。

因此,只要A和B都是真实的.并遵循协议计算正确,则B对A的身份认证将是正

确的.~PFiat—Shamir身份认证协议满足完备性。

2.合理性证明

假设第三方要假冒A.首先该第三方能够顺利通过Fiat—Shamir协议的第一步.然后在第三步中,因为e是随机产生的,~Ue=0或e=l的概率都是1/2.

（1）当e=0时,y=r.此时该第三方只要把他第一步中产生的随机数r发送给B即可通过验证,此次过程假冒成功.

（2）但当e=l时,Y=rsmod.此时该第三方要想计算出正确的Y发送给 B,则其首先要正确的计算出s的值.但s2=vmodn.要想由v求出s,其困难性和分解大整数n.因此第三方得到正确的s值的概率几乎为0.即当e=l时,第三方冒充A会失败

由（1）和（2）可知,协议执行一次,第三方假冒A成功的概率是1/2.

则执行t次,第三方假冒A成功的概率为.当t很大时,第三方假冒A成功的概率可以认为是0.因此Fiat—Shamir身份认证协议满足合理性.

3.零知识性证明

s是秘密值,只有A知道,因此S就是A的身份信息.在此协议执行过程中,验证方B没有得到关于S本身的任何一点信息.B虽然知道v,y和X 的值,但都不能求出正确的S值.原因是求解模n的平方根问题是数学难

题。因此Fiat-Shamir身份认证协议满足零知识性。

七、零知识证明协议

（一）基本的零知识证明协议

假设P知道一部分信息而且这个信息是一个难题的解法,基本的零知识协议由下面几轮组成。

Step1:P用他的信息和一个随机数将这个难题转变成另一个难题,新的难题和原来的难题同构。然后他用他的信息和随机数

解这个新的难题。

Step2:P利用位承诺方案递交这个新难题的解法。

Step3:P向V透露这个新难题。V不能用这个新难题得到原难题或其解法的任何信息。

Step4:V要求P：

1.

2.公开他在第2步中提交的解法并证明是新难题的解法。

Step5:P同意V的要求。

Step6:P和V重复第1步至第5步n次。

（二）并行的零知识证明协议

基本的零知识证明协议包括P和V之间的n次交换，可以把它们全部并行完成：

Step1:P使用他的信息和n个随机数把这个难题变成n个不同的同构难题,然后用他的信息和随机数解决这n个新难题。

Step2:P提交这n个新难题的解法。

Step3:P向V透露这n个新难题。V无法利用这些新难题得到原问题或其解法的任何信息。

Step4:对这n个问题中的每一个,V要求P:

1.

2.公开他在第2步中提交的解法,并证明是新难题的

解法。

Step5:P对这n个新难题中的每一个都表示同意。

在实际应用中这个协议似乎是安全的,但是没有人知道怎么证明它。在某些环境下,针对某些问题的某些协议可以并行运行，

并同时保留它

（三）非交互式的零知识证明协议

早在1988年,人们就已经发明了非交互式零知识的证明。非交互式的零知识证明[6]协议不需要任何交互,证明者P可以公布

协议,从而向任何花时间对此进行验证的人证明协议是有效的。

这个基本协议类似于并行零知识证明,不过只是用单向散列函数代替了V:

Step1:P使用他的信息和n个随机数把这个难题变换成n个

不同的同构难题,然后用他的信息和随机数解决这n个新难题。

Step2:P提交这n个新难题的解法。

Step3:P把所有这些提交的解法作为一个单向散列函数的输入,然后保存这个单向散列函数输出的头n个位。

Step4:P取出在第3步中产生的n个位，针对第i个新难题依次取出这n个位中的第i个位,并且:

1.如果它是0,则证明新旧问题是同构的,或者:

2.如果它是1,则公布他在第2步中提交的解法,并证明

它是这个新问题的解法。

Step5:P将第2步中的所有约定及第4步中的解法都公之于众。

Step6:V或者其他感兴趣的人,可以验证第1步至第5步是否能被正确执行。

这个协议起作用的原因在于单向散列函数扮演一个无偏随机位发生器的角色。如果P要进行欺骗,他必须能预测这个单向

散列函数的输出。但是,他没有办法强迫这个单向散列函数产生

哪些位或猜中它将产生哪些位。这个单向散列函数在协议中实际

上是V的代替物——在第4步中随机的选择两个证明中的一个。

八、结语

零知识证明提供了一种能向别人证明拥有某知识但不透漏该知识的一种方法。零知识证明过程不但在身份认证中有重要应用,而且在NP问题

[4]中也有广泛的应用。同时微软提出的新一代安全计算平台NGSCB也应

用到了与零知识证明相关的技术。零知识证明理论是一个非常重要的理论，另外,数字签名,水印检测,密钥交换和电子现金也为零知识证明的应用提供了新的方向。

参考文献：

[1]《安全协议》曹天杰,张永平,汪楚娇.北京:北京邮电大学出版社,2009,113—122.

[2]《A.Menezes,P.vanOorschot,S.Vanstone.Handbook of Applied Crypt Ography》. BocaRaton:CRCPress,1996.405—409.

[3]《浅析零知识证明》赵晓柯

[4]《零知识与国防部-通信保密》苏珊?兰道,1991,1:27—34.

[5]《What are in teractire proof sand zero— Knowledge proofs?》 RSA Laboratories

[6]《基于零知识证明的图论问题和网络安全的研究》朱洪武，8-9

零知识证明是零信任吗

零知识证明是零信任吗 导语 虽然零知识证明和零信任这两个词，都带有“零”，都与“信任”有关，但并不是一回事。两者本质上都要增强「信任」，但在增强「信任」的过程中，零知识证明强调不泄露知识；零信任强调不要过度授权。简单说，零知识是为了隐藏知识；零信任是为了控制信任。零知识证明解决了信任与隐私的矛盾：既通过「证明」提升「信任」，又通过「零知识」保护「隐私」。是两全其美的方案。探索零知识证明的过程，可以探索到安全的本质。安全之终极定义，不是启发式的CIA三性，而是采用形式化验证的可证明安全——上帝（“模拟者”）与科学（数学、计算复杂度）完美结合的推演过程。 一、了解零知识证明 1、零知识证明的定义 零知识证明（ZKP，Zero-Knowledge Proof）的定义为：证明者（prover）能够在不向验证者（verifier）提供任何有用信息的情况下，使验证者（verifier）相信某个论断是正确的。根据定义，零知识证明具有以下三个重要性质： (1)完备性（Completeness）： 只要证明者拥有相应的知识，那么就能通过验证者的验证，即证明者有足够大的概率使验证者确信。 （关于这里提到的“概率”，详见后面的“色盲游戏”）

(2)可靠性（Soundness）： 如果证明者没有相应的知识，则无法通过验证者的验证，即证明者欺骗验证者的概率可以忽略。 (3)零知识性（Zero-Knowledge）： 证明者在交互过程中仅向验证者透露是否拥有相应知识的陈述，不会泄露任何关于知识的额外信息。 从定义中，还可以提取到两个关键词：“不泄露信息”+“证明论断有效”。再浓缩一下就是：隐藏+证明。所以，零知识证明的核心目的是：隐藏并证明需要它隐藏的各类秘密。（感觉很矛盾是吧） 2、零知识证明的源头 零知识证明是1984年由Goldwasser、Micali、Rackoff三个人提出，论文题目是《The Knowledge Complextiy of Interactive Proof Systems》（《交互式证明系统中的知识复杂性》）。 这篇论文其实发表在1989年。原因在于这篇论文的思想太过超前，以至于从1984年写出初稿到1989年正式被采纳发表，经历了整整五年时间。正是由于零知识证明这项开创性工作，Goldwasser和Micali两人在2012年分享了图灵奖——计算机领域最高奖项，也有“计算机界的诺贝尔奖”之称。 3、零知识证明的核心价值：消灭可信第三方 当互联?电?商务和在线交易蓬勃发展到今天，可信第三方（TTP，Trusted Third Party）几乎不可或缺。但大家体会不到的事实是，可信第三方引入了巨大的「信任成本」。对第三方的过度信任，会带来严重的「隐私泄露」、「单点失效」、「个?信息滥?」等问题。虽然学术界也提出“半可信第三方”（Semi-trusted

零知识证明及其应用

《网络安全》课程论文 题目零知识证明理论及其应用 学院计算机与信息科学学 软件学院 专业 年级 学号 姓名 指导教师 成绩_____________________ 2014年11月16 日

零知识证明理论及其应用 摘要：“零知识证明”－zero-knowledge proof，是由Goldwasser等人在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。本文介绍了零知识证明的概念,并对零知识证明的一般过程进行分析.同时,阐述零知识证明的性质和优点.最后,综述了零知识证明的应用。 关键字：零知识证明身份认证交互式非交互式 一、引言 21世纪是信息时代，信息已经成为社会发展的重要战略资源，社会的信息化已成为当今世界发展的潮流和核心，而信息安全在信息社会中将扮演极为重要的角色，它直接关系到国家安全、企业经营和人们的日常生活。 密码学的出现给这些安全带来了保证，而大量事实证明，零知识证明在密码学中非常有用。Goldwasser等人提出的零知识证明中，证明者和验证者之间必须进行交互，这样的零知识证明被称为“交互零知识证明”。 80年代末，Blum等人进一步提出了“非交互零知识证明”的概念，用一个短随机串代替交互过程并实现了零知识证明。非交互零知识证明的一个重要应用场合是需要执行大量密码协议的大型网络。在零知识证明中,一个人(或器件)可以在不泄漏任何秘密的情况下,证明他知道这个秘密..如果能够将零知识证明用于验证,将可以有效解决许多问题。 二、概念 “零知识证明”－zero-knowledge proof，是由Goldwasser等人在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。 零知识证明分为交互式零知识证明和非交互式零知识证明两种类型。 三、零知识证明的一般过程 证明方和验证方拥有相同的某一个函数或一系列的数值.零知识证明的一般过程如下: 1.证明方向验证方发送满足一定条件的随机值,这个随机值称为"承 诺".[1] 2.验证方向证明方发送满足一定条件的随机值,这个随机值称为"挑 战".[1]

零知识证明

零知识证明 “零知识证明”－zero-knowledge proof，是由Goldwasser等人在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。在Goldwasser等人提出的零知识证明中，证明者和验证者之间必须进行交互，这样的零知识证明被称为“交互零知识证明”。80年代末，Blum等人进一步提出了“非交互零知识证明”的概念，用一个短随机串代替交互过程并实现了零知识证明。非交互零知识证明的一个重要应用场合是需要执行大量密码协议的大型网络。大量事实证明，零知识证明在密码学中非常有用。 在零知识证明中,一个人(或器件)可以在不泄漏任何秘密的情况下,证明他知道这个秘密..如果能够将零知识证明用于验证,将可以有效解决许多问题.. 这是我前几天在网络上看到得，觉得很有意思，但现的问题是：要怎么做? 诸位发表点看法： 附相关零知识证明材料： 零知识证明不是证明在条款的数学感觉因为有一个固定的可能性p 在任一零知识证明Peggy 能提供对挑战的正确反应即使她不知道钥匙。但是如果测试被重覆n 计时欺诈被减少Peggy 的可能性p n , 和由增加测试胜者的数字可能使Peggy 的可能性降低欺诈到一个任意水平。 例子战略 Peggy 的公开密钥是一张大图表, 我们将称G。Peggy 被组建的G 某时从前,和广泛然后出版它。由于她特别地制造了它为目的, Peggy 知道一个汉密尔顿的周期在G。Peggy 将证明她的身份对胜者由证明, 她知道一个汉密尔顿的周期在G。即使G 是公开信息, 没人可能做这, 因为没人知道G 的一个汉密尔顿的周期, 并且发现汉密尔顿的周期在图表是一个困难的问题(参见NP 完整性) 。 但是, Peggy 不能简单地显露汉密尔顿的周期对胜者, 胜者(或偷听者) 从那以后能在将来扮演Peggy 。Peggy 不能显露任何信息在所有周期, 因为偷听者也许收集信息关于几个不同的场合和装配它入足够的信息能扮演Peggy 。 证明她的身份, Peggy 和胜者扮演以下比赛的几个圆: Peggy 标记G 端点以随机号。边缘可能然后代表作为一对这些数字。她列出G 边缘, 和编成密码各个边缘以一个另外密钥。她然后寄发被编成密码的边缘到胜者。 胜者翻转硬币。 * 如果硬币过来头, Peggy 向随机号投降密钥和测绘从端点。胜者解码边缘和然后核实, 被编成密码的边缘被派在步骤1 实际上做graph.g 和没有某一其它图表。 * 如果硬币过来尾巴, Peggy 投降密钥只为实际上形成汉密尔顿的周期的边缘。胜者解码这些边缘和核实, 他们的确形成正确长度的周期。

零知识证明

阿里巴巴的零知识证明--淘自科学松鼠会 战争中你被俘了，敌人拷问你情报。你是这么想的：如果我把情报都告诉他们，他们就会认为我没有价值了，就会杀了我省粮食，但如果我死活不说，他们也会认为我没有价值而杀了我。怎样才能做到既让他们确信我知道情报，但又一丁点情报也不泄露呢？ 这的确是一个令人纠结的问题，但阿里巴巴想了一个好办法，当强盗向他拷问打开山洞石门的咒语时，他对强盗说：“你们离我一箭之地，用弓箭指着我，你们举起右手我就念咒语打开石门，举起左手我就念咒语关上石门，如果我做不到或逃跑，你们就用弓箭射死我。” 强盗们当然会同意，因为这个方案不仅对他们没有任何损失，而且还能帮助他们搞清楚阿里巴巴到底是否知道咒语这个问题。阿里巴巴也没损失，因为处于一箭之地的强盗听不到他念的咒语，不必担心泄露了秘密，而且他确信自己的咒语有效，也不会发生被射死的杯具。 强盗举起了右手，只见阿里巴巴的嘴动了几下，石门果真打开了，强盗举起了左手，阿里巴巴的嘴动了几下后石门又关上了。强盗还是有点不信，说不准这是巧合呢，他们不断地换着节奏举右手举左手，石门跟着他们的节奏开开关关，最后强盗们想，如果还认为这只是巧合，自己未免是个傻瓜，那还是相信了阿里巴巴吧。 “零知识证明”说的是示证者向验证者表明他知道某种秘密，不仅能使验证者完全确信他的确知道这个秘密，同时还保证一丁点秘密也不泄露给验证者。阿里巴巴的这个方案，就是认证理论“零知识证明”的一个重要协议。 除了被俘后如何靠情报保命这个问题，零知识证明在社会领域中还有着很多应用场合。例如你证明了一个世界级的数学难题，但在发表出来之前，总是要找个泰斗级的数学家审稿吧，于是你将证明过程发给了他，他看懂后却动了歪心思，他把你的稿子压住，把你的证明用自己的名义发表，他名利双收，你郁闷至死，你去告他也没用，因为学术界更相信的是这位泰斗，而不是你这个无名之辈。 这并不是天方夜谭，而是学术界常见的难题，前些年有个博士生告他的泰斗级导师剽窃他的成果，但除了令师生关系恶化外没有任何效果，最后他使出了撒手锏，称他在给导师审阅的论文的关键公式中，故意标错了一个下标，而这会导致整个推导失败。学术委员会一查果真如此，但还是有倾向于泰斗的声音，有人说那是泰斗的笔误，只不过让你发现了而矣，并不能证明那公式就是你推导出来的。 这个博士生故意标错下标，不能说他没有心眼，但他没有把“零知识证明”理论用好，以致于落到这种地步。“零知识证明”早在1986年就被A.Fiat和A.Shamir用数学的方法给出了解决方案，并在同年申请了美国专利，但由于该理论可能被用于军事领域，专利局被军方密令搁置，6个月后，军方命令：“该申请发表后会有害于国家安全……所有美国人的研究未经许可而泄露将会被判刑罚款”。看来军方认为作者肯定是美国人了，但作者实际上是在美国申请专利的以色列人，研究也是在以色列的大学里做的，军方这个命令摆了个大乌龙，虽然两天后撤消了，但已经成为了学术界的笑柄。 这个笑柄也说明了一个问题，即“零知识证明”非常重要。基于数学的推理虽然非常复杂，但思路却很简单，上述的阿里巴巴方案就是其中之一。其它的一些方案，也都是像这样遵循着分割和选择（Cut and Chose）协议的。

零知识身份认证

4．零知识身份认证 零知识证明（zero-knowledge proof）的思想是：证明者Peggy拥有某些知识（如某些长期没有解决的难问题的解决方法），零知识证明就是在不将该知识的内容泄露给验证者Victor的前提下，Peggy向Victor证明自己拥有该知识。首先，我们看下面Peggy和Victor之间的一段对话： Peggy：“我可以对密文为C的消息进行解密。” Victor：“我不相信。请证明。” Peggy（糟糕的回答）：“密钥是K，您可以看到消息解密成了M。” Victor：“哈哈！现在我也知道了密钥和消息。” 这里，Peggy虽然证明了自己拥有某些知识（密钥K及明文M），却向Victor 泄露了这些知识。一个更好的对话是： Peggy：“我可以对加密为C的消息进行解密。” Victor：“我不相信。请证明。” Peggy（好的回答）：“让我们使用一个零知识协议，我将以任意高的概率证明我的知识（但是不会将关于消息的任何情况泄露给您）。” Victor：“好”。 Peggy 和 Victor 通过该协议…… 可以使用洞穴例子来解释零知识，C和D之间存在一个密门，并且只有知道咒语的人才能打开。Peggy知道咒语并想对Victor证明，但证明过程中不想泄露咒语。

图7.13 零知识洞穴 步骤如下： （1）Victor站在A点； （2）Peggy一直走进洞穴，到达C点或者D点； （3）在Peggy消失在洞穴中之后，Victor走到B点； （4）Victor随机选择左通道或者右通道，要求Peggy从该通道出来； （5）Peggy从Victor要求的通道出来，如果有必要就用咒语打开密门； （6）Peggy和Victor重复步骤（1）至（5）n次。 如果Peggy不知道这个咒语，那么只能从进去的路出来，如果在协议的每一轮中Peggy都能按Victor要求的通道出来，那么Peggy所有n次都猜中的概率是1/2n。经过16轮后，Peggy只有65536分之一的机会猜中。于是Victor可以假定，如果所有16次Peggy的证明都是有效的，那么她一定知道开启C点和D 点间的密门的咒语。 我们来看一个零知识证明的例子。图是否同构是NP完全问题，对于一个非 常大的图，判断两个图是否同构是非常困难的。对于图G 1和G 2 ，如果存在一个 一一对应的函数F：F的定义域是G 1的顶点集。F的值域是G 2 的顶点集。当且仅 当[g1,g2]是G 1中的一条边，[F(g1),F(g2)]才是G 2 中的一条边，称G 1 和G 2 同构 的。 假设Peggy知道图G 1和G 2 之间同构，Peggy使用下面的协议将使Victor相 信G 1和G 2 同构： （1）Peggy随机置换G 1 产生另一个图H，并且H和G 1 同构。因为Peggy知 道G 1和H同构，也就知道了H和G 2 同构。 （2）Peggy把H送给Victor。 （3）对如下两个问题Victor选择其中的一个，要求Peggy证明。但是，Victor 不要求两者都证明。 证明G 1 和H同构，或者 证明G 2 和H同构。 （4）Peggy按Victor的要求证明。 （5）Peggy和Victor重复步骤（1）至（4）n次。

5零知识证明

零知识证明

零知识证明的概念 设P表示掌握某些信息，并希望证实这一事实的实体，设V是证明这一事实的实体。 体设是明这事实的实体 某个协议向V证明P的确掌握某些信息，但V无法推断出这些信息是什么，我们称P实现了最小泄露证明。 这些信息是什么我们称实现了最小泄露证明 如果V除了知道P能够证明某一事实外，不能够得到其他任何知识，我们称P实现了零知识证明，相应的协议称作任何知识我们称实现了零知识证明相应的协议称作 零知识协议。

零知识证明的概念 在最小泄露协议中满足下述两个性质： (1)P换言之若不知道个定理的证 (1) P无法欺骗V。换言之，若P不知道一个定理的证 明方法，则P使V相信他会证明定理的概率很低。 （正确性） (2) V无法欺骗P。换言之，若P知道一个定理的证明 方法，则P使V以绝对优势的概率相信他能证明。 （完备性） 在零知识协议中，除满足上述两个条件以外，还满足下述性质： 还满足下述性质 (3) V无法获取任何额外的知识。（零知识性）

零知识洞穴 设P知道咒语，可打开C和D之间的秘密门，不知道者则走向死胡同。现在来看P如何向V出示证明使其相信他知道这个秘密，但又不告诉V有关咒语。 协议1：洞穴协议 V站在A点； P进入任一点C或D； 进洞之后点 当P进洞之后，V走向B点； V叫P：(a)从左边出来，或(b)从右边出来 P按照要求实现（有咒语）； P和V重复执行(1)~(5)共n次。

零知识洞穴 A B C D 若P不知道咒语，则在B点，只有50%的机会猜中V的要求，协议执行n次，则只有50% n次机会完全猜中。 要求协议执行次则只有50%次机会完全猜中此洞穴问题可以转化为数学问题，P知道解决某个难题的秘密信息，而V通过与P交互作用验证其真伪。