零知识证明协议研究

张引兵，王 慧

（淮北师范大学 数学科学学院，安徽 淮北 235000）

零知识证明协议研究

张引兵，王 慧

（淮北师范大学 数学科学学院，安徽 淮北 235000）

在当代密码学中，零知识证明占据着重要的位置.已经成为信息安全领域身份认证的关键技术之一,吸引了许多学者的注意，并得到了一系列的重要研究成果.文章首先阐述了零知识证明的主要思想、零知识证明协议的性质以及零知识证明协议所主要基于的几类数学问题.接着，着重研究了零知识证明在相关问题中的应用.最后，对本文进行了总结,以期能够吸引更多的学者在更广泛的领域对零知识证明协议进行研究.

密码学；零知识证明；数独；多项式函数根；身份认证

1 引言

“零知识证明”－zero-knowledge proof，这一概念是由Goldwasser等人[1,2]在20世纪80年代初提出的.从提出到现在已经有30多年的时间了，在零知识证明的研究中，已经取得了许多重要的成果，但仍有许多问题有待进一步的研究，近年来已经成为密码学研究中的热点问题之一.零知识证明的思想是许多密码学协议的基础，在安全协议的设计中有着比较广泛的应用.

2 零知识证明相关概念

2.1 零知识证明的主要思想

零知识证明指的的就是一方(证明者)能够在不向另一方(验证者)提供任何有用的信息的前提下，也能使得另一方能够相信某个论断是正确的.其本质上是一种涉及两方的协议，其中的一方称为证明者，一般用P表示，另一方称为验证者，一般用V表示.在协议的执行过程中，证明者P向验证者V声称其已经掌握了某种信息，证明者P和验证者V通过一系列的交互，使得验证者V或者相信了证明者P的声称，或者拒绝了证明者P的声称，而在这个过程中，验证者V没有获得证明者P声称的所掌握信息的具体内容，这是一种全新的思想.

2.2 零知识证明协议的性质

一般说来，一个零知识证明协议应该下面三个条件：

(1)可行性：如果P对V的声称是真的，则V以一个大的概率接受P的声称.

(2)可靠性：如果P对V的声称是假的，则V以一个大的概率拒绝P的声称.

(3)零知识性：如果P对V的声称是真的，在V没有违反协议的前提下，则无论V采用任何方法，V除了能够接受P的声称外，而无法获有关P所声称内容的任何信息[3].

2.3 零知识证明协议主要基于的几类数学问题

通常零知识证明协议所基于的数学问题，类似于密码学中的公钥密码体制，都是主要基于如下几类数学问题的.

2.3.1 模n平方根问题

设n是一个正整数，若存在一个x，使得x2≡y (modn)，则称x是y的模n平方根.其中：1

2.3.2 大整数分解问题

大整数分解问题是指，给定两个素数p,q，计算乘积p*q=n很容易；但是，反过来给定整数n,求n的素因数p,q使得n=p*q非常困难.大整数的分解问题至今还没有很好的快速分解的方法.在现有的条件下，若n足够大，并且有时间的限制，则想要破解大整数问题将是非常困难的.

2.3.3 离散对数问题

离散对数问题指的是整数中一种基于同余运算和原根的对数运算，也可以按照如下方式进行简单描述：任意给定一个质数p，和有限域Zp上的一个本原元a，对于有限域Zp上整数b，可以找到唯一的一个整数c，使a∧c≡(modp)成立.一般来说，如果选择p恰当，则得到该问题的解是困难的，且至今计算离散对数问题的多项式时间算法还没有找到.为了抵抗已知的攻击，p至少应该是150位的二进制整数，且p-1至少有一个大的素数因子.

3 几种零知识证明协议

3.1 零知识证明的基本协议

由Quisquater等人[4]最先给出了有关零知识证明解释的通俗例子，如图1所示,在位置C与位置D之间有一个秘密的通道，而这个秘密通道只有知道相应咒语的人才可以通过.如果证明者P知道通过秘密通道的咒语，他如何在不泄露咒语的前提下向验证者V证明他知道咒语呢？可以按照如下协议的步骤执行：

图1 零知识洞穴

协议：

(1)首先让验证者V走到A处；

(2)接着让证明者P进入洞穴，走到图中的C处或D处；

(3)然后验证者V再走到图中的B处；

(4)验证者V要求证明者P或者从左侧通道出来或者从右侧通道出来；

(5)证明者P按照验证者V的要求从相应的通道出来(若有必要，可以用咒语打开通道)；

(6)证明者P和验证者V可以反复执行(1)～(5) n轮.

在上述的零知识洞穴的例子中，若P没有掌握秘密通道的咒语，则他只能从他原来进入通道的一侧出来.若P靠猜测，在整个协议执行的n轮过程中，P在每一轮中均能按照V的要求从相应的一侧出来的概率只有.经过16轮后，P只有65536分之一的机会猜中.若进过16轮的验证，P在每一轮中均能按照V的要求从相应的一侧出来，那么V就可以得出结论，P一定掌握了通过秘密通道的咒语.

3.2 游戏中的零知识证明—数独的零知识证明协议

数独顾名思义——每个数字只能出现一次.数独盘面是个九宫，每一宫又分为九个小格，一共是九行九列，共八十一个小格.数独问题就是在这八十一个小格中首先给出一些已知的数字和相关的解题条件，利用逻辑和推理的方式，在其余空余的空格上填入1-9中相应的数字.使得1-9中所有的数字在每一行，每一列，每一个宫中都出现一次，且仅出现一次.数独游戏能够全面考察做题的人的观察能力、逻辑推理与判断的能力，虽然规则不复杂，做题也不是太难，但1-9相应的数字的排列却是千变万化的，有许多教育家认为数独是一种训练孩子思维逻辑的一种不错的形式.在数独问题中，任一道合格的数独谜题都有唯一确定的答案，逻辑推理过程也是以此为基础的，所有无解或多解的数独谜题都是不合要求的.下面给出的是一种基于比特承诺的零知识证明方案.

协议：数独的零知识证明协议[5]

证明者：

(1)证明者随机选择一个置换σ:{1,2,…,9}a{1,2,…,9}；

(2)对于每个单元(i,j)的值v，证明者发送σ(v)给验证者；

验证者：

验证者随机选择下列可能性中的一种:或者一行、或者一列、或者一个子网格,或直接打开已经填充好的一个单元格,并要求证明者公开相应的承诺.当验证者做出回应后,如果验证者选择了一行、一列或一个子网格,验证者检查其中的所有的值是否确实是不同的.如果验证者选择的是直接打开已经填充好的一个单元格，验证者将所填充的单元格中的数据与证明者所发送的数据做比较，与原来相同的现在仍然相同，与原来不同的现在仍然不同，这样就可以说明σ的确是单元格中所填充数字的一种置换.

3.3 多项式函数根的零知识证明协议

多项式函数是数学中许多重要研究内容之一,在计算机科学中，多项式函数的研究也有着举足轻重的作用.假如P已经知道了某个整系数高次f(x)的一个整数根x0,现在他想向V证明自己已经知道了多项式函数f(x)的某一个根,但又不想让V了解有关x0的任何相关信息，这个问题就是多项式函数根的零知识证明问题.假设某整系数高次多项式函数其主要证明过程如下：

协议：多项式函数根的零知识证明协议[6]

(3)V要求p证明他拥有一个数x0，使得(modp),(i=1,2,…,n）；

(6)重复执行(1)～(5)k轮.

3.4 图论中的零知识证明—图的同构的零知识证明协议

图的同构问题：有两个图G0(V0,E0)和G1(V1,E1)，其中这两个图的顶点数和边数都相同，并且存在一个置换π，当(u,v)∈E0时，(π(u),π(v))∈E1，则称图G0和图G1同构，记作G1=πG0.

协议：图的同构的零知识证明协议[7]

公共输入：初始化数据：两个图G0(V0,E0)和G1(V1,E1)，并且G0=φ(G1)使用独立的随机掷币协议执行如下4步m轮. (1)P随机选择一个置换π生成图G0的一个置换图H，即：H=π(G0),并将H发送给V；

(2)V随机选择α∈{0,1}，并将α发送给P；

(3)如果α=0，P将置换π发送给V;否则，如果α≠0，P将置换π·φ-1发送给V;

(4)V验证H=ψ(Gα)(其中当α=0时，ψ=π；当α≠0时，ψ=π·φ-1)是否成立，若成立则继续，否则，拒绝P的声称.

如果如上协议成功执行了m轮，V则接受P的证明.

在上述协议中，若P确实掌握了图G0和图G1的同构关系G1=φ(G0)，则对所有的置换πφ总有H=π(G0)=π(φ(G1))，又因为置换π是随机选择的，所以整个过程中没有泄露有关置换ø的任何信息.又因为V要求证明H与图G0同构或与图G1同构是随机的，所以P只有掌握了置换φ才能或者证明(H,G0)同构或者证明(H,G1)同构.

3.5 身份认证中的零知识证明—F-S身份认证协议

在密码学中，零知识证明最早是作为实体认证的一种方法进行应用的.Fiat和Shamir在1986年首先给出了这种身份认证的零知识证明方法，也就是F-S认证协议.F-S认证协议一般不单独应用于现在的认证系统中，但它当今应用的零知识证明身份认证系统的基础，像Feige-Fiat-Shamir和Guillou-Quisquater中，都用到了F-S认证协议.

在F-S认证协议中，首先找一个证明者和验证者两方都信任的第三方，第三方选取两个大的素数p和q，然后计算n=p×q，其中n的值是公开的，而p和q的值是不公开的.P选取一个私钥s(1≤s≤n-1)，接着计算v=smod n，将v作为公钥由可信的第三方保存.V可以按照如下步骤对P进行认证：

协议：F—S身份认证协议[8]

(1)P从0到n-1中随机选取一个数r，并计算x=r2modn；

(2)P将x发送给V；

(3)V将c发送给P，其中c为0或1；

(4)P计算y=rsc，其中r是在(1)中P选取的一个随机数，s是P的私钥；

(5)P将y再发送给V，从而证明其知道其所声称的私钥s；

(6)V计算y2modn和xvc，如果y2modn=xvc，则P或者知道s的值(P是诚实的)或者P已经用其他的方法计算出了y的值(P是不诚实的)，因为:

如上六步构成一轮，每一轮让c为0或1，重复执行若干轮后，P只有每一轮都通过验证，才能通过V的验证；如果在某一轮的执行过程中，P没有通过验证，则整个认证过程终止，P没有通过认证.

3.6 云存储中的零知识证明

由于云存储能够提供安全、可靠和实用的存储服务，使得其得到更广泛的应用.为了得到用户的信任，云存储的服务提供商必须为用户提供可恢复性证明POR(proof of retrievability)[9]，证明数据的完整性和安全性.

对于可恢复性证明的安全性，这里主要从如下两点来进行说明：

(1)在认证过程中，怎样才能防止证明者通过篡改数据进行欺骗？

(2)对于公开可验证的POR协议，如何避免在应答的过程中恶意的验证者通过分析而存储相关数据？

基于以上两类安全问题，在POR协议中，可以考虑使用零知识证明协议来完成.零知识证明的完整性和可靠性可满足第一点要求，零知识证明的零知识性可满足第二点要求.在文献[10]中，作者所提出的零知识数据可恢复性证明协议模型，可以防止证明者欺骗或者是泄露相关的认证数据.而整个思想主要是依据双线性映射群s=(p,G,GT,e),其中G, GT为群p中两个有序的随机大素数，并且需要验证数据文件F备份到一个分区每个子块的秘密数据{mi,j}由随机数λj∈Zp保护，{σi}由随机数γ∈Zp保护.同时，为了避免恶意验证者获得{λ}和γ，证明者可以利用承诺的方法通过Hλ和

j1)来保护这些数据，其中β是属于Zp的随机数，h是一个防碰撞散列函数，是属于Zp的随机数，且i=1，…s，e为双线性映射的群映射群系统[11].

4 结束

在零知识证明过程中，证明者使验证者相信某个断言或定理是真实的，而除此之外，验证者没有获得有关断言或定理的任何有用信息.零知识证明的思想是许多密码学协议的基础，在安全协议的设计中有着比较广泛的应用.本文在介绍零知识证明协议相关知识的基础上，对零知识证明的相关应用进行了研究，但没有涉及一些最近发展起来的高级课题.近年来，国内许多学者在零知识证明理论研究方面取得了一系列国际领先的研究成果[12]-[14]，希望通过本文，能够吸引更多的学者在更广泛的领域对零知识证明进行研究.

〔1〕Goldwasser S,M icali S,Rackoff C.The know ledge complexity of interactive proofsystems, Proceedingsof the17th ACM [C],Symposium on the theory ofComputing,1985:291-304.

〔2〕Goldwasser S,M icali S,Rackoff C.The know ledge complexity of interactive proof systems,SIAM J.Comput,18(1989):186-208.

〔3〕李顺东，王道顺．现代密码学：理论、方法与研究前沿[M]．北京：科学出版社，2009.157-192.

〔4〕王育民，刘建伟.通信网的安全——理论与技术[M]．西安：西安电子科技大学出版社，1999.309-319.

〔5〕Ronen Gradwohl,Moni Naor,Benny Pinkas, Guy N.Rothblum.Cryptographic and Physical Zero-Know ledge Proof Systems for Solutions of Sudoku Puzzles. Theory Comput Syst (2009)44:245–268.

〔6〕李曦,王道顺．多项式函数根的零知识证明协议[J].清华大学学报，2009, 49（7）:1015-1018.

〔7〕Oded Goldreich,Silvio M icali,Avi W igderson. Proofs that yield nothing but their validity. Journal of the ACM[C],volume 38,issue 3, July 1991:690-728.

〔8〕Feige U,Fiat A,Sham ir A.Zero-know ledge proofs of identity. Proceedings of the nineteenth annual ACM conference on Theory of computing[C],1987:210-217.

〔9〕Juels A,Kaliski-Jr B S.Pors. Proofs of retrievability for large files.Proceedings of the 2007 ACM Conference on Computer and Communications Security [C],CCS 2007. Alexandria:ACM,2007:584-597.

〔10〕Zhu y,W ang HX,Hu ZX,Ahn GJ,Hu HX.Zero-know ledge proofs of retrievability. Science China-Information Sciences[J].54(8), 2011:1608-1617.

〔11〕W Huqing,S Zhixin;Research on Zero-Know ledge Proof Protocol.IJCSI International Journal of Computer Science Issues[J],Vol. 10,Issue 1,No 1,January 2013:194-200.

〔12〕Deng Yi,Lin Dongdai.Instance-Dependent Verifiable Random Functions and Their Application to Simultaneous Resettability[C]. EUROCRYPT 2007:148-168.

〔13〕Deng Yi, Giovanni Di Crescenzo, Lin Dongdai,Feng Dengguo.Concurrently Nonmalleable Black Box Zero Know ledge in the Bare Public-Key M odel[C].CSR 2009:80-91.

〔14〕Deng Yi,Vipul Goyal,Am it Sahai.Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy [C].FOCS 2009:251-260.

TP393.08

A

1673-260X（2014）04-0006-04

2011年安徽省高校省级自然科学研究项目(KJ2011Z332)；2012年淮北师范大学青年科学研究项目（2012xq54）