软件学报
JOURNAL OF SOFTWARE
1999年 第1期 No.1 1999



随机归约的五步完美零知识证明系统
臧斌宇　周玉林　熊鹏荣　朱　洪
　　摘要　构造了一个完美零知识的五步交互证明系统,该系统不依赖于任何(复杂性和计算能力)假设,在该系统中,证明者可具有有限或无限的计算能力.
　　关键词　完备性,可靠性,零知识,完美零知识证明系统,随机归约.
　　中图法分类号　TP301
Perfect Zero Knowledge Proof System with Five Moves for Random Reducibility
ZANG Bin-yu1　ZHOU Yu-lin2　XIONG Peng-rong2　ZHU Hong3
　　Abstract　A perfect zero knowledge proof with five moves which doesn't rely on any assumption is constructed in this paper. In this proof system, the prover can have either unlimited or limited computing power.
　　Key words　Completeness, soundness, zero knowledge, perfect zero knowledge proof system, random reducibility.
　　目前,没有任何假设的零知识证明系统是极少的.文献［1］给出了一个没有任何假设的完美零知识五步交互证明系统,该系统是建立在图同构问题上的证明系统,这是目前所见的没有任何假设的交互次数最少的完美零知识证明系统.但该系统要求证明者的计算能力无限.对证明系统没有附加假设这类问题,Tompa和Woll［2］曾给出平均归约的概念使其一般化.目前已有几个四步完美零知识证明系统,但都附加了假设,且缺乏一般性.Sakurai［3］曾给出二次剩余上的零知识四步证明系统,该系统虽然没有任何假设,但它不是语言的证明系统(在xRN时,证明者也能说服验证者接受该语言,即该协议只有在正确的输入下才是完美零知识证明系统).
　　平方剩余是否存在没有附加假设条件的四步完美零知识证明系统这个问题,至今还没有解决,也没有找到其他没有附加条件和假设的四步完美零知识证明系统.
　　本文给出的完美零知识五步证明系统,不需有任何复杂性假设和对证明者附加任何计算能力假设.我们的证明系统中的证明者可具有有限的计算能力,比文献［1］的条件弱(文献［1］中证明者由于计算能力无限,故可据此获得说服验证者的知识就多),比文献［1］适应面广(因为随机归约问题是平方剩余问题、离散对数问题、图同构问题等的一般化).我们的结论适合任何零知识证明机构.
1　协议的描述
　　本文用到的概念有:交互证明系统、完备性、可靠性和完美零知识性,可参阅文献［2,4］,随机归约性概念出自文献［2］. 
　　设R满足下述条件:
　　(1) R是随机自归约的;
　　(2) 存在一概率多项式时间｜N｜O(1)算法,对给定的N,x,y决定(x,y)是否属于RN;
　　(3) 存在一概率多项式时间｜N｜O(1)算法,对输入N,输出随机对(x,y)∈RN,这里,x在RN上为均匀分布,y在RN(x)上为随机的均匀分布,这些条件与文献［2］中相同.
　　在条件(1)～(3)满足的假设下,我们来构造一个五步协议.
　　五步证明协议: 该协议的公共输入是(N,x),证明者的辅助输入是y,(x,y)∈RN,k为安全系数,
　　(1) P:随机地均匀地选择(,)∈RN,i=1,...,k,送α1=(,...,)给V;
　　(2) V:随机地均匀地选择bi∈{0,1},i=1,...,k,
　　　　如果bi=0,则计算ui=A(N,,g),让wi=
　　　　(这里,g是V的随机源,是V在计算ui时消耗掉的g的有限前缀);
　　　　如果bi=1,则随机地、均匀地选择(ui,vi)∈RN,让wi=vi.
　　　　送β1=(u1,...,uk)给P;{V将位元bi掩盖在ui中,用ui提交位bi};
　　(3) P:计算xi=A(N,x,r),设是P在计算xi中消耗掉的P的随机源的有限前缀,
　　　　P根据(N,x,y,)计算xi的某个证据yi,i=1,...,k,送α2=(x1,...,xk)给V;
　　(4) V:送β2=(w1,...,wk)给P;{V揭掩盖};
　　(5) P:根据计算揭掩盖并应答:
　　　　如果ui=A(N,,wi),则得bi=0;如果(ui,wi)∈RN,则得bi=1.
　　　　若bi=0,则令zi=;若bi=1,则令zi=yi,i=1,...,k.
　　　　送α3=(,...,)(z1,...,zk)给V;
　　(6) V:检验P的报文α3的正确性,即:
　　　　检验关系(,)∈RN,
　　　　如果bi=0,则检验等式xi=A(N,x,zi);
　　　　如果bi=1,则检验关系(xi,zi)∈RN,i=1,...,k.
　　　　如果这些条件都满足,则V接受且停机;否则,V拒绝,输出“P欺骗”且停机.
2　协议的证明
　　定理1. 上述协议满足协议的完备性.
　　证明:当x∈LR时,显然,当P以y∈RN(x)为辅助输入,只要P,V按协议执行,则V必接受.　　　□
　　定理2. 上述协议满足协议的可靠性.
　　证明:我们描述一个多项式时间的知识提取器M,该知识提取器在平均时间｜N｜O(1)内停机,且其输出y满足(x,y)∈RN的概率与P′通过交互说服V使V接受的概率最多相差｜x｜-ω(1).
　　我们先分析一下,M怎样才能获得x的一个证据,一个可行的方法是让M获得两轮不同的V能接受的报文,α1-β1-α2-β2-α3与α1-β1-α2-β′2-α′3,其中α1=(,...,),β1=(u1,...,uk),α2=(x1,...,xk),β2=(w1,...,wk),α3=(,...,k)(z1,...,zk),β′2=(w′1,...,w′k),α′3=(,...,)(z′1,...,z′k),设M通过β2,β′2揭开的掩盖位分别是(b1,...,bk),(b′1,...,b′k),且有某个j,使得bj≠b′j,由对称性,不妨设bj=0,b′j=1,则有xi=A(N,x,zi)与(xi,z′i)∈RN同时成立,这样,x的某个证据即可通过(N,x,zi,z′i)算出(随机归约定义中的R2,见文献［2］).
　　为了让M获得两次不同的报文,M必须先得到一“变色龙”β1=(u1,...,uk),然后才能随心所欲地揭开掩盖,以期获得两轮不同的报文.
　　由以上分析,M执行过程可分为3部分:
　　第1部分: 模拟.该部分的目的,是获得(,...,),(,...,),其中(,)∈RN,该部分实际上是使下面的两部分的(u1,...,uk)成为“变色龙”,在该部分中,M模拟诚实的V忠实地执行整个协议,与P′交互(即调用P′作为子程序),若V拒绝则M拒绝,输出P′欺骗,否则M执行第2部分.设M在协议的第(1)句获得(,...,),在协议的第(5)句获得(,...,).
　　第2部分: 获得一组报文α1-β1-α2-β2-α3(其中α1在第1部分已得到).该部分组成如下:
　　REPEAT
　　将P′的工作带、通讯带设置成第1部分模拟时执行完协议的(1)后的状态,即从协议的(2)开始执行,此时,M已有(,...,),(,...,),其中(,)∈RN.
　　(2′) M计算ui=A(N,,g).这里,g是M的随机源,是M在计算ui时消耗掉的g的有限前缀.
　　　　　根据(N,,,)计算vi,使得(ui,vi)∈RN,
　　　　　送β1=(u1,...,uk)给P′{注意,此时(u1,...,uk)已是M掌握的“变色龙”};
　　(3′) 让P′送α2=(x1,...,xk);
　　(4′) M随机地、均匀地选择bi∈{0,1},i=1,...,k,
　　　　　如果bi=0,则让wi=,
　　　　　如果bi=1,则让wi=vi,送β2=(w1,...,wk)给P′;{M随心所欲地揭掩盖};
　　(5′) 让P′送α3=(,...,)(z1,...,zk);
　　(6′) M对P′的报文α3进行检验,即:
　　　　　检验关系(,)∈RN,
　　　　　如果bi=0,则检验xi=A(N,x,zi),
　　　　　如果bi=1,则检验关系(xi,zi)∈RN,i=1,...,k;
　　UNTIL α3通过M的检验.
　　这一部分执行完后,M得到报文α1-β1-α2-β2-α3,且其中的β1=(u1,...,uk)是“变色龙”.现让M进入第3部分.
　　第3部分: 在上述“变色龙”β1=(u1,...,uk)及问题集α2=(x1,...,x3)下找另一组报文α1-β1-α2-β′2-α′3,其中α1-β1-α2是前面已经得到的.该部分内容如下:
　　将P′的工作带、通讯带设置成第2部分执行完(3′)后的状态,即M从协议的(4)开始执行,
　　REPEAT
　　(4″) M随机地选择b′i∈{0,1},i=1,...,k,
　　　　　如果b′i=0,则让w′i=,如果b′i=1,则让w′i=vi,送β′2=(w′1,...,w′k)给P′;
　　(5″) 让P′送α′3=(,...,)(z′1,...,z′k)给M;
　　(6″) M检验P′的报文α3,即:
　　　　　检验关系(,)∈RN,
　　　　　如果bi=0,则检验等式xi=A(N,x,z′i),
　　　　　如果bi=1,则检验关系(xi,z′i)∈RN,i=1,...,k,
　　UNTIL (6)中的α3通过检验或循环将所有的(b1,...,bk)遍历完毕.
　　(7″) 如果所有的(b1,...,bk)被遍历完毕,则M停机,不输出任何东西.
否则,M从成功获得的两组不同的报文中计算x的证据y,M输出x的证据y且停机.
　　当M执行完第3部分后,M要么输出y∈RN(x)后停机,要么停机不输出.下面,我们证明M平均执行的时间是多项式的,然后证明M计算出y∈RN(x)的概率不小于p-2-k.这里,p是M通过第1部分的概率,即设
Prob (VP(N,x,s)(N,x)接受)=p.
　　首先,M在第1部分模拟(P′,V)的时间是多项式的,M模拟之后立即停机的概率为(1-p),因此,M执行后两个部分的概率为p.当M进入第2部分,M反复执行直到M模拟的V再次接受(N,x)为止,因此,M执行第2部分循环的平均次数为1/p.当M进入第3部分时,(,...,)(u1,...,uk)(x1,...,xk)已固定,假设(P′,V)在这些已固定量下接受(N,x)的概率为q,那么M退出第2部分以后,选择这些固定量的概率不超过,这里D是所有的(u1,...,uk)的个数.设q=i1/2k(对q解释,2k为所有可能的(b1,...,bk)的数目,i1为2k个(b1,...,bk)中P′能给予正确应答的数目),那么固定这些量之后,M在第3部分的平均执行次数为(2k-1)/(i1-1)(假设此时i1>1,M在第2部分成功之后,在第3部分重新获得一组P′能正确应答的(b′1,...,b′k)的概率为(i1-1)/(2k-1)),所以M执行第3部分的平均次数不超过.所以,M执行第2部分和第3部分的总的平均次数为p(1/p+2/p)=3,因此,M是平均多项式时间的.
　　如果M模拟成功(其概率为p),那么只有当i1=1,即q=2-k时M才求不出y∈RN(x),而M在退出第1部分时,选择这些固定量的概率不超过,因此,M成功地求出y∈RN(x)的概率不小于p(1-2-k/p)=p-2-k.由于k=ω(log｜x｜),因此M满足条件.　　　　　　　　　　　　　　□
　　至于协议是完美零知识的,其证明几乎与文献［1］相同,在此从略.
　　由上述分析,我们已得:
　　定理3. 上述协议是完美零知识的五步知识证明系统　　　　　　　　　　　　　　　　□
本文研究得到国家自然科学基金资助。
作者介绍：臧斌宇,1963年生,在职博士生,副教授,主要研究领域为并行处理.
　　　　　周玉林,1962年生,讲师,主要研究领域为算法理论.
　　　　　熊鹏荣,1961年生,讲师,主要研究领域为算法分析与设计.
　　　　　朱洪,1939年生,教授,博士生导师,主要研究领域为算法分析与设计.
本文通讯联系人：朱洪,上海 200433,上海复旦大学计算机科学系理论组
作者单位：臧斌宇　复旦大学并行处理中心　上海　200433
　　　　　周玉林　熊鹏荣　江西上饶师范专科学校数学系　上饶　334001
　　　　　朱　洪　复旦大学计算机科学系　上海　200433
E-mail: xjlu@ms.fudan.edu.cn
参考文献
　［1］Bellare M, Micali S, Ostrovsky R. Perfect zero knowledge in constant rounds. In: Gabow H N ed. Proceeding of the 22nd Annual ACM Symposium on the Theory of Computing. New York, NY: ACM Press, 1990. 482～493
　［2］Tompa M, Woll H. Random self-reducibility and zero knowledge interactive proofs of possession of information. In: Leighton F T ed. Proceeding of the 28th Symposium on Foundation of Computer Science. Los Alamitos, CA: IEEE Computer Society, 1987. 427～482
　［3］Sakurai K. On separating proofs of knowledge from proofs of membership of languages and its application to secure identification schemes. Lecture Notes in Computer Science, 1995,(959):496～509
　［4］Feige U, Fiat A, Shamir A. Zero knowledge proofs of identity. In: Aho A V ed. Proceedings of the 19th Annual ACM Symposium on the Theory of Computing. New York, NY: ACM Press, 1987. 210～217
本文1997-05-19收到原稿,1998-01-23收到修改稿
