ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



һȨϵͳ֪ʶ*
ٻŸ  
ժҪͼ֪ͬʶ֤ıʶ--ǩϵͳ,һȨķ.ǰķ,Ȼ߶ǻڶܵ𲽱¶ʵֵ,ǰǻͼͬûʵֵ,ǻܹ˼ʵֵ.оȨϵͳİȫʱ,⼶֪ʶԡʵ֪ʶԺͼ֪ʶ.ӦΪЭ֪ʶԵϽ.
ؼʡ֪ʶ֤,ͼͬ,֪ʶ,Ȩϵͳ.
ͼšTP14
One Self-delegation Scheme and the Knowledge Complexity of Problems 
XU Shou-huai ZHANG Gen-du ZHU Hong 
Abstract A solution to the problem of self-delegation using the identification-authentication-signature scheme based on the graph isomorphism problem is proposed in this paper. The major difference from the traditional solutions is that it is based on the graph isomorphism rather than computing numeric theory problem, though they all leak out secret information little by little. The knowledge complexity of problems, the including knowledge complexity, the practical knowledge complexity, and the computing knowledge complexity are also defined. In the authors' opinion, these definitions should be used as the upper bound of knowledge complexity of protocols.
Key wordsZero-knowledge proof, graph isomorphism, knowledge complexity, self-delegation system.
ںܶ,ҪԿ()ڰȫĻ,Կ,ָʱԿ.ƺϷûֶԿ͸ʹأһ,ûһȨʱ,뱩¶йԿĲϢ1,2.
Goldreichף1˽ҪʵֵĿ: ΣС,κһԿʧܶԿɵΣҪС; ɿƵȨ,ÿȨǰԿĲϢй¶.Կй¶ͻ(ֵģʽ)ͽ(ÿй¶ԿЧλ)ַ,˻֪ʶ֤Ľ,֪ʶ֪ʶ֤3ǻɢԵ.
Ļͼ֪ͬʶ֤ıʶ--ǩϵͳ,һµȨϵͳ,佥Ȼ.ڽʽЭж֪ʶԣ4,5ݵ,˻ռ֪ʶԶ,ΪøԽӦЭ֪ʶԽϽ,ɴĿǰϵЭ֪ʶԵͨŸϽ5.
1 ͼ֪ͬʶ֤ıʶ--ǩϵͳ
ͳıʶ--ǩϵͳǻڼе(ɢӷֽ),һһԹͬͼ֪ʶ֤ıʶ--ǩϵͳȨϵͳ.
1. һԹͬͼıʶ--ǩģʽıʶɡݼǩǩ֤4()ʽʱ㷨.
ʶ. İȫ1n,һԪ(o,p,f,{gi}iN),oһԶΪnͬͼ(G0,G1),pG0G1һͬӳ,{gi}iNһ{0,1}i{0,1}iĵû,fΪG1ʩһͬӳ,õûɵ{0,1,...,n-1}ϵûpermu(x),f(,(G0,G1))=(G1).һְȫķ(o,p,f,{gi}iN)ûP,ֻP֪p,Ķǹ.
ݼ. ûPҪûVͨʱ,PͨV֪ʶ֤֪(G0,G1)ͬp.
ǩ. Ըıx,ûP롰ʶɡͬķɦ=permu(x),ټ=(G1),Աx,ûPǩǸæ,xĺ(ҲԲѸǩڱд.Vյĺ,ͬ㷨,õһµĦ¡,Pṩ֪ʶ֤ǹڡG0¡,֤ʹVܡG0¡䡱,˵߱ڴб۸Ķʹæ¡٦¡,Pڵ.ۺԭ,ñĶ).Ȼ,P֪G0ͬ.
ǩ֤. ûV֤ǩʱ,ҪûP֪ʶ֤æG0ͬ.{gi}iNǹ,Vյܱ۸˵ıx,ҡ=permu(x),Ȼ¡=ҡ(G1).'٦,ñ۸Ĺı,,ͨP֪ʶ֤G0ͬ.
ڹ1еıʶɲּһɿĵɱʶɺͷַĹ.ʵ,ҲԲڿŵĵĴ,һİȫ,ÿûԼıʶϢ,Ȼĳ(繫ԿĿ¼)ǼǼ.ⷽоĸµĽ,ķ.
2 ͬͼʶȨϵͳģ
ڻͬͼʶ֪ʶ֤ϵͳ,Ϊʵֿɿɢ,ϷûÿһȨʱ,ͱͬеһż,ʽ3.,ΪȨ,ûܾȫй¶.
2. (һԹͼͼ֪ͬʶ֤ϵͳȨϵͳģ)ϷûӵеĹ˽ԿΪ(sk,pk)*.
Ȩ. ûһԿ(skl,pkl)**,Ȼһɹ֤֤Ĵ±ıtagl,lʾȨһ.taglʹ֤ȷɸúϷûɵ.ʱ,µõĹ˽ԿϵͳваԭԿϢ.
Ȩ֤.һ(skl,pkl)ûʱ,ṩ߽tagl֤Ϸ.֤ȷŸȨǺϷ,ṩ,ƴԪ(skl,pkl,tagl)ǺϷ.
ûͨǷֶεõԪ(skl,pkl,tagl),ڸȨ涨ķΧ(ȨԪЧ)ܷ,ϷûԿȴδ¶.
3 һԹͬͼȨϵͳ
3.1 һԹͬͼȨϵͳ
ڱڸʵ,ʶ--ǩϵͳȻǻһԹͬͼ.
3. (һԹͼͼ֪ͬʶ֤ϵͳȨϵͳ)ϷûѰ1Ӧϵͳ,ӵеĹ˽Կ(sk,pk)ͬ2.(G0,G1)ͬͼԻʶ,ÿͼĶʶΪ0,1,2,...,n-1,nΪ.
Ȩ. lʾȨ±,ʾȨ뱩¶ڸܵͬûG0ıΪlĵӦG1еĵıl.ʽ˵,G1=(G0),(l)=l.Ȼ,ɱȨһ()tagl,ñǹNPԡG0G1ͬû,G1=(G0),Ҧ(l)=l䡱һǽʽ֪ʶ֤.,ûù2һԿ(skl,pkl),pklһͬͼ,䶥ǰȫһ,sklһͼͬû.ԿԽЧԭԿͬĹܺ.
Ȩ֤. һ(skl,pkl)ûʱ,ṩ߽taglʾķǽʽ֪ʶ֤֤Ԫ(skl,pkl,tagl)ǷϷ.
3.2 һԹͬͼȨϵͳȷ
3ȷ֤.
1.(1) κNPԶ֪ʶʽ֤ϵͳ6;(2) κ֪ʶʽ֤ϵͳɱ任ɷǽʽ֪ʶ֤ϵͳ7.
3.3 һԹͬͼȨϵͳʵʰȫ
ͼʱ,ҪжǷͬ,ռΪn!.Stirlingʽ֪,n=128ʱ,ǲе.
Ȼ,֤㹻ĶԿ֤׵ؼϷûԿ.n㹻(n=128)ʱ,¶һ3еĵԲй¶ͬû.ǴĳOracle֪ûĳӦĶΪdʱ,ռn!Ϊd!.(n-d-1)!,,ѡҪ¶ͬûеĵʱ,ҪΣС,ѡеĵ˳ӦԶ.
Ըģͼ,ȫȨĴȡڵʱʵʵļͼ.,ģΪ30ͼͬǿɽܵʱ,һģΪnͼ,ȨĴϽΪ(n-30),ʵýĴΪ(n-60).
4 ԵĺͶ֪ʶ
4.1 Э֪ʶ
Goldwasser8ݵ1985״˽ʽ֤ϵͳ֪ʶԸ.֪ʶǹ֤ͨʱüϵĺôһ,ڽܵõĶ.֪ʶԡϢغͨŸǲͬĲ.ͨŸָ˫ͨȣ5.ڶ֪ʶ,Goldreichˣ5Ϊ:ЭͨŸΪЭ֪ʶԵϽ.ڻͨŸԽǿɼļµõ֪ʶӦλ0,poly(.).
Ŀǰ,Э֪ʶԵʽ3ֲͬĶ.֤Pй¶k(x)ص֪ʶ,ڽ֤Vܼκζ,ͨѯOraclek(x)غ.ڿռȵĸָ,һͼɹģһʵĽӿռһ.ڰʾĸָ,һͼܹЧģһĽʱҪطõСʾĳ.йĶ֪ʶоĲף5.
4.2 ֪ʶ
ĸӦϵͳ漰⼶֪ʶԶЭ鼶֪ʶ,֪ʶΪЭ֪ʶϽǸΪ.
һ,Ϊnͼ,֪ʶйص,ٹ:(1) Ȿ֪ʶǶ٣(2) һOracleǹڴͼͬʱ,ǻõ֪ʶж٣(3)ڹ3ûеһʱ,˶֪ʶ
ͼĶ,0,1,2,...,n-1,1ûֻn.log(n)λȫȷ.n=128ʱ,n.log(n)=896ص֪ʶ.Ǹ:
1. ֪ʶԾǾȷʾĽ̶ƴĳ.
ӷֽ,n=...,piǲͬ,ei0,i=1,2,..,j,֪ʶΪlog(pi).оȷرʾһûn.log(n),õ896ص֪ʶʱ,ĽΨһȷ.ʵ,Ҫ֪ȫn.log(n)ص֪ʶʱ,ܾԼͼͬ.Ϊռ㹻Сʱ,ֱӵõĽ.,Ҫʵ֪ʶ,Ͻ֪ʶ.ռмѶȵģⲻʵļй,ڵ漰Ķ(ͼ)صй.۵״,ͼͬ,3*1032(൱30ͼͬ)ǵǰµĿɼռ,ʱ,ռ䲻ÿռĴС,ڵǰ¿Խ,ӶʱٲѯOracleʱõ֪ʶΪ0.,Oracle֪ʶ,ʹռ𲽼Сÿռʱ,ͻȫ֪ʶ.
2. ʼռΪs0,ǸʱʵʼĿռΪs,һOracleĳ֪ʶ,ռ併Ϊs1s,Ƹʵ֪ʶΪlog(s0),ƴOracleõ֪ʶԼ֪ʶ,Ϊ.
ͼͬ,ʵ֪ʶԵϽΪ֪ʶ,㹻n,nlog(n)log(n!)716.ǴĳOracle֪ûĳӦĶΪdʱ,õ֪ʶԵΪ-log-log=logn.ֱϵ,Ϊǲõ˸õԱĶӦ,õڵĳֶӦϵ.ǴĳOracleõ֪ʶʹռ併Ϊɼʱ,ǴӸOracleõ֪ʶΪ-log716-108=606.
:1512صBlumn=pq,Ӧӷֽ֪ʶΪlogp+logq=512,ͨŸԡlogp+logq=512.ʵ֪ʶԵϽΪlog(.log)=264.
5 ۺ
Ļͼ֪ͬʶ֤ıʶ--ǩϵͳ,һȨķ.ף5ķ,ǰǻͼͬûʵֵ,ǻܹ˼ʵֵ.
оȨϵͳİȫʱ,ǵõһĽ,֪ʶԶ.Ƕ⼶֪ʶԡʵ֪ʶԺͼ֪ʶ.Ϊ,ΪЭ֪ʶԵϽǺ.
оõȻѧ͹863߿ƼĿ.
߽ܣٻ,1970,ʿ,ҪоΪ簲ȫ,ȫ,ӻ.
Ÿ,1937,ڣʿʦ,ҪоΪ,Ϣ̺Ͱȫ.
,1939,,ʿʦ,ҪоΪ㷨ƺͷ,㸴,Ϣȫ.
ͨѶϵ:ٻϺ 200433,ѧѧϵ
עͣ* ʱԿһͬͼ˽Կͼͬ
** ˶ӦõģʽԶԭӦģʽ磬ȻԭĻͼ֪ͬʶ֤ģʽʱԿΪһͼ˽ԿͼͬôͳĹԿģʽRSAʱ,˽ԿĸǴͳϵĶ.
ߵλٻŸ  顡ѧѧϵϺ200433
E-mail: shxu@ms.fudan.edu.cn
ο
1Goldreich O, Pfitmann B, Rivest R L. Self-delegation with Controlled Propagation-or-What if You Lose Your Laptop. http://www.mit.edu, 1997
2Dwork C, Lotspiech J, Naor M. Digital signets: self-enforcing protection of digital information(preliminary version). In: Leighton F T ed. Proceedings of the 28th ACM Symposium on Theory of Computing. New York: ACM Press, 1996. 489498
3Bellare M, Goldreich O. On defining proofs of knowledge. In: Brickell E F ed. Proceedings of the CRYPTO, Lecture Notes in Computer Science 740. Berlin: Springer-Verlag, 1992. 390420
4Goldreich O, Petrank E. Quantifying knowledge complexity. In: Sipser M ed. Proceedings of IEEE Symposium on Foundations of Computer Science. Los Alamitors, California: IEEE Computer Society Press, 1991. 5968
5Goldreich O, Petrank E. Quantifying Knowledge Complexity. http://www.mit.edu, 1997
6Ben-Or M, Goldreich O, Goldwasser S et al. Everything provable is provable in zero-knowledge. In: Goldwasser S ed. Proceedings of CRYPTO, Lecture Notes in Computer Science 403. Berlin: Springer-Verlag, 1988. 3746
7Blum M, Feldman P, Micali S. Non-interactive zero-knowledge and its applications(extended abstract). In: Ullman J D ed. Proceedings of the 20th ACM Symposium on Theory of Computing. New York: ACM Press, 1988. 103112
8Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proofs. In: Pipenger N ed. Proceedings of the 17th ACM Symposium on Theory of Computing. New York: ACM Press, 1985. 291304
1997-12-16յԭ,1998-03-03յ޸ĸ 
