《网络安全》课程论文
题 目 零知识证明理论及其应用
学 院 计算机与信息科学学
软件学院
专 业 年 级 学 号 姓 名
指 导 教 师 成 绩 _____________________
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
《网络安全》课程论文
题 目 零知识证明理论及其应用
学 院 计算机与信息科学学
软件学院
专 业 年 级 学 号 姓 名
指 导 教 师 成 绩 _____________________
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