ѧ
JOURNAL OF SOFTWARE
1999 1 No.1 1999



Լ岽֪ʶ֤ϵͳ
갱֡١졡
ժҪһ֪ʶ岽֤ϵͳ,ϵͳκ(Ժͼ),ڸϵͳ,֤߿ɾ޻޵ļ.
ؼʡ걸,ɿ,֪ʶ,֪ʶ֤ϵͳ,Լ.
ͼšTP301
Perfect Zero Knowledge Proof System with Five Moves for Random Reducibility
ZANG Bin-yu1ZHOU Yu-lin2XIONG Peng-rong2ZHU Hong3
AbstractA 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 wordsCompleteness, soundness, zero knowledge, perfect zero knowledge proof system, random reducibility.
Ŀǰ,ûκμ֪ʶ֤ϵͳǼٵ.ף1ݸһûκμ֪ʶ岽֤ϵͳ,ϵͳǽͼͬϵ֤ϵͳ,ĿǰûκμĽٵ֪ʶ֤ϵͳ.ϵͳҪ֤ߵļ.֤ϵͳûиӼ,TompaWoll2ƽԼĸʹһ㻯.ĿǰмĲ֪ʶ֤ϵͳ,˼,ȱһ.Sakurai3ʣϵ֪ʶĲ֤ϵͳ,ϵͳȻûκμ,Ե֤ϵͳ(xRNʱ,֤Ҳ˵֤߽ܸ,Эֻȷ²֪ʶ֤ϵͳ).
ƽʣǷûиӼĲ֪ʶ֤ϵͳ,ûн,ҲûҵûиͼĲ֪ʶ֤ϵͳ.
ĸ֪ʶ岽֤ϵͳ,κθԼͶ֤߸κμ.ǵ֤ϵͳе֤߿ɾ޵ļ,ף1ݵ(ף1֤ڼ,ʿɾݴ˻˵֤ߵ֪ʶͶ),ף1Ӧ(ΪԼƽʣ⡢ɢ⡢ͼͬȵһ㻯).ǵĽʺκ֪ʶ֤.
1Э
õĸ:֤ϵͳ걸ԡɿԺ֪ʶ,ɲף2,4,ԼԸף2. 
R:
(1) RԹԼ;
(2) һʶʽʱNO(1)㷨,ԸN,x,y(x,y)ǷRN;
(3) һʶʽʱNO(1)㷨,N,(x,y)RN,,xRNΪȷֲ,yRN(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=
(,gVԴ,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. ЭЭ걸.
֤:xLRʱ,Ȼ,PyRN(x)Ϊ,ֻҪP,VЭִ,Vؽ.
2. ЭЭĿɿ.
֤:һʽʱ֪ʶȡM,֪ʶȡƽʱNO(1)ͣ,y(x,y)RNĸPͨ˵VʹVܵĸx-(1).
ȷһ,Mܻxһ֤,һеķMֲͬVܽܵı,1-1-2-2-31-1-2-¡2-3,Ц1=(,...,),1=(u1,...,uk),2=(x1,...,xk),2=(w1,...,wk),3=(,...,k)(z1,...,zk),¡2=(w1,...,wk),3=(,...,)(z1,...,zk),Mͨ2,¡2ҿڸλֱ(b1,...,bk),(b1,...,bk),ĳj,ʹbjbj,ɶԳ,bj=0,bj=1,xi=A(N,x,zi)(xi,zi)RNͬʱ,,xĳ֤ݼͨ(N,x,zi,zi)(Լе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) Mui=A(N,,g).,gMԴ,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) MPıĦ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)ǡɫ.M3.
3: ɫ1=(u1,...,uk)⼯2=(x1,...,x3)һ鱨Ħ1-1-2-¡2-3,Ц1-1-2ǰѾõ.ò:
PĹͨѶóɵ2ִ(3)״̬,MЭ(4)ʼִ,
REPEAT
(4) Mѡbi{0,1},i=1,...,k,
bi=0,wi=,bi=1,wi=vi,ͦ¡2=(w1,...,wk)P;
(5) Pͦ3=(,...,)(z1,...,zk)M;
(6) MPıĦ3,:
ϵ(,)RN,
bi=0,ʽxi=A(N,x,zi),
bi=1,ϵ(xi,zi)RN,i=1,...,k,
UNTIL (6)еĦ3ͨѭе(b1,...,bk).
(7) е(b1,...,bk),Mͣ,κζ.
,Mӳɹõ鲻ͬıмx֤y,Mx֤yͣ.
Mִ3ֺ,MҪôyRN(x)ͣ,Ҫôͣ.,֤MƽִеʱǶʽ,Ȼ֤MyRN(x)ĸʲСp-2-k.,pMͨ1ֵĸ,
Prob (VP(N,x,s)(N,x))=p.
,Mڵ1ģ(P,V)ʱǶʽ,Mģ֮ͣĸΪ(1-p),,MִкֵĸΪp.M2,MֱִMģVٴν(N,x)Ϊֹ,,Mִе2ѭƽΪ1/p.M3ʱ,(,...,)(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ȷӦ(b1,...,bk)ĸΪ(i1-1)/(2k-1)),Mִе3ֵƽ.,Mִе2ֺ͵3ֵܵƽΪp(1/p+2/p)=3,,Mƽʽʱ.
Mģɹ(Ϊp),ôֻеi1=1,q=2-kʱM󲻳yRN(x),M˳1ʱ,ѡЩ̶ĸʲ,,MɹyRN(x)ĸʲСp(1-2-k/p)=p-2-k.k=(logx),M.
Э֪ʶ,֤ף1ͬ,ڴ˴.
,ѵ:
3. Э֪ʶ岽֪ʶ֤ϵͳ
оõȻѧ
߽ܣ갱,1963,ְʿ,,ҪоΪд.
,1962,ʦ,ҪоΪ㷨.
,1961,ʦ,ҪоΪ㷨.
,1939,,ʿʦ,ҪоΪ㷨.
ͨѶϵˣ,Ϻ 200433,Ϻѧѧϵ
ߵλ갱ѧдġϺ200433
֡١ʦרѧУѧϵġ334001
졡顡ѧѧϵϺ200433
E-mail: xjlu@ms.fudan.edu.cn
ο
1Bellare 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. 482493
2Tompa 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. 427482
3Sakurai 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):496509
4Feige 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. 210217
1997-05-19յԭ,1998-01-23յ޸ĸ
