1、网络安全课程论文题 目 零知识证明理论及其应用学 院 计算机与信息科学学 软件学院专 业 年 级 学 号 姓 名 指 导 教 师 成 绩 _2014 年 11 月 16 日 零知识证明理论及其应用摘要：“零知识证明”zero-knowledge proof，是由 Goldwasser等人在 20世纪 80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。本文介绍了零知识证明的概念,并对零知识证明的一般过程进行分析.同时,阐述零知识证明的性质和优点.最后,综述了零知识证明的应用。关键字：零知识证明 身份认证 交互式 非交互式一、 引言21世纪是
2、信息时代，信息已经成为社会发展的重要战略资源，社会的信息化已成为当今世界发展的潮流和核心，而信息安全在信息社会中将扮演极为重要的角色，它直接关系到国家安全、企业经营和人们的日常生活。密码学的出现给这些安全带来了保证，而大量事实证明，零知识证明在密码学中非常有用。Goldwasser 等人提出的零知识证明中，证明者和验证者之间必须进行交互，这样的零知识证明被称为“交互零知识证明” 。80 年代末，Blum 等人进一步提出了“非交互零知识证明”的概念，用一个短随机串代替交互过程并实现了零知识证明。非交互零知识证明的一个重要应用场合是需要执行大量密码协议的大型网络。在零知识证明中,一个人(或器件)可
3、以在不泄漏任何秘密的情况下,证明他知道这个秘密.如果能够将零知识证明用于验证,将可以有效解决许多问题。二、 概念“零知识证明”zero-knowledge proof，是由 Goldwasser等人在20世纪 80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。零知识证明分为交互式零知识证明和非交互式零知识证明两种类型。三、 零知识证明的一般过程
4、证明方和验证方拥有相同的某一个函数或一系列的数值.零知识证明 的一般过程如下: 1.证明方向验证方发送满足一定条件的随机值,这个随机值称为“承诺“.1 2.验证方向证明方发送满足一定条件的随机值,这个随机值称为“挑战“.1 3.证明方执行一个秘密的计算,并将结果发送给验证方,这个结果称为“响应“。4)验证方对响应进行验证,如果验证失败,则表明证明方不具有他所谓的“知识“,退出此过程。否则,继续从 1)开始,重复执行此过程 t次。如果每一次验证方均验证成功,则验证方便相信证明方拥有某种知 识。而且此过程中,验证方没有得到关于这个知识的一点信息。四、 零知识证明的性质根据零知识证明的定义和有关例子
5、,可以得出零知识证明具有以下三条性质: 1.完备性2.如果证明方和验证方都是诚实的,并遵循证明过程的每一步,进行正确的计算,那么这个证明一定是成功的,验证方一定能够接受证明方。2.合理性2.没有人能够假冒证明方,使这个证明成功。 3.零知识性2.证明过程执行完之后,验证方只获得了“证明方拥有这个知识“这条信息,而没有获得关于这个知识本身的任何一点信息。五、 零知识证明的优点根据零知识证明及其有关的协议主要有以下优点3: 1.随着零知识证明的使用,安全性不会降级,因为该证明具有零知识性质。2.高效性.该过程计算量小,双方交换的信息量少。3.安全性依赖于未解决的数学难题,如离散对数,大整数因子分解
6、,平方根等。4.许多零知识证明相关的技术避免了直接使用有政府限制的加密算 法,这就给相关产品的出口带来了优势。六、 零知识证明身份认证如果我们把合法用户的个人信息看作是证明方的知识,证明方通过零知识证明向验证方证实自己的身份就是零知识身份认证.零知识身份认证是零知识证明在身份认证方面的应用.目前的零知识身份认证方案主要有四种:FiatShamir 身份认证,Feige-Piat-Shamir 身份认证,GuilloOuisquater身份认证和 Schnorr身份认证.其中 FiatShamir身份认证是最早提出的,也是最基础的零知识身份认证方案,其他三种方案是对FiatShamir的改进.下
7、面仅就 FiatShamir方案做一个介绍,并证明其完备性,合理性和零知识性. （一）FiatShamir 身份认证协议过程 协议概要:A 在 t次迭代过程中向 B证明他的身份。1.一次建立3 该阶段主要完成以下两项任务,且在 t次迭代过程之前一次完成。 （1）一个可信中心 T选择并发布一个类似于 RSA的随机模数n,n=pXq. P,q为两个大素数,可信中心对 P和 q保密。（2）申请者 A选择一个和 12互素的秘密值 S,1sn 一 1.计算=mod.并向可信中心 T注册 v做为他的公钥。 2.协议消息3 t轮中的每一轮会产生如下三条信息: （1）AB:x=,mod. （2）BA:e0,1
8、. （3）AB:y=r?rood. 3.协议执行34 以下步骤迭代 t轮,轮与轮之间是连续进行的而且是相互独立的.如 果这 t轮都成功了,则 B就接受 A的身份. （1）A 选择一个承诺随机数 r,1rn 一 1.计算 x=rmodn,发送给 B. （2）B 随机选择一个挑战比特位 e,e0,1,发送给 A。 （3）A 如果收到 e=O,则计算 y=r.如果收lJe=l,则计算 Y=modn。 然后向 B发送响应 Y。 （4）B 验证 y2=?v.modn.如果验证成功,则接受 A的响应,否则拒绝。（二）FiatShamir 身份认证协议的完备性,合理性和零知识性证明 1.完备性证明 （1）当
9、 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 的身份认证将是正确的.PFiatShamir 身份认证协议满足完备性。2.合理性证明 假设第三方要假冒 A.首先该第三方能够顺利通过 FiatShamir协议的第一步.然后在第三步中,因为 e是随机产生的,Ue=0 或 e=l的概率都是 1/2. （1）当 e=0时,y=r.此时
10、该第三方只要把他第一步中产生的随机数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.因此 FiatShamir身份认证协议满足合理性.3.零知识性证明 s是秘
11、密值,只有 A知道,因此 S就是 A的身份信息.在此协议执行过程中,验证方 B没有得到关于 S本身的任何一点信息.B 虽然知道 v,y和 X的值,但都不能求出正确的 S值.原因是求解模 n的平方根问题是数学难题。因此 Fiat-Shamir身份认证协议满足零知识性。七、 零知识证明协议（一） 基本的零知识证明协议假设 P知道一部分信息而且这个信息是一个难题的解法,基本的零知识协议由下面几轮组成。Step1:P用他的信息和一个随机数将这个难题转变成另一个难题,新的难题和原来的难题同构。然后他用他的信息和随机数解这个新的难题。Step2:P利用位承诺方案递交这个新难题的解法。Step3:P向 V透
12、露这个新难题。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 无法利用这些新难题得到原问题
13、或其解法的任何信息。Step4:对这 n个问题中的每一个,V 要求 P: 1.向他证明新、旧难题是同构，或者： 2.公开他在第 2步中提交的解法,并证明是新难题的解法。Step5:P对这 n个新难题中的每一个都表示同意。在实际应用中这个协议似乎是安全的,但是没有人知道怎么证明它。在某些环境下,针对某些问题的某些协议可以并行运行，并同时保留它们的零知识性质。（三） 非交互式的零知识证明协议早在 1988年,人们就已经发明了非交互式零知识的证明。非交互式的零知识证明6协议不需要任何交互,证明者 P可以公布协议,从而向任何花时间对此进行验证的人证明协议是有效的。这个基本协议类似于并行零知识证明,不过
14、只是用单向散列函数代替了 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步中的解法都公之于众。Ste
15、p6:V或者其他感兴趣的人,可以验证第 1步至第 5步是否能被正确执行。这个协议起作用的原因在于单向散列函数扮演一个无偏随机位发生器的角色。如果 P要进行欺骗,他必须能预测这个单向散列函数的输出。但是,他没有办法强迫这个单向散列函数产生哪些位或猜中它将产生哪些位。这个单向散列函数在协议中实际上是 V的代替物在第 4步中随机的选择两个证明中的一个。八、 结语零知识证明提供了一种能向别人证明拥有某知识但不透漏该知识的一种方法。零知识证明过程不但在身份认证中有重要应用,而且在 NP问题4中也有广泛的应用。同时微软提出的新一代安全计算平台 NGSCB也应用到了与零知识证明相关的技术。零知识证明理论是一
16、个非常重要的理论，另外,数字签名,水印检测,密钥交换和电子现金也为零知识证明的应用提供了新的方向。参考文献：1安全协议曹天杰,张永平,汪楚娇.北京:北京邮电大学出版社,2009,113122. 2A.Menezes,P.vanOorschot,S.Vanstone.Handbook of Applied Crypt Ography.BocaRaton:CRCPress,1996.405409. 3浅析零知识证明 赵晓柯4零知识与国防部-通信保密苏珊?兰道,1991,1:2734. 5What are in teractire proof sand zero Knowledge proofs? RSA Laboratories6基于零知识证明的图论问题和网络安全的研究 朱洪武，8-9
