Reduction zero-knowledge  

作　　者：ZHAOYunlei DENGXiaotie LEEC.H. ZHUHong 

机构地区：[1]DepartmentofComputerScience,FudanUniversity,Shanghai200433,China [2]DepartmentofComputerScience,CityUniversityofHongKong,HongKong,China

出　　处：《Progress in Natural Science:Materials International》2004年第4期350-358,共9页自然科学进展·国际材料（英文版）

基　　金：Supported by the National Natural Science Foundation of China (Grant No. 60273045) ; the Ministry of Science and Technology of China (Grant No. 2001CCA03000)

摘　　要：The nature of zero-knowledge is re-examined and the evidence for the following belief is shown: the classic simulation based definitions of zero-knowledge (simulation zero-knowledge) may be somewhat too strong to include some 'nice' protocols in which the malicious verifier seems to learn nothing but we do not know how to construct a zero-knowledge simulator for it. To overcome this problem a new relaxation of zero-knowledge, reduction zero-knowledge, is introduced. It is shown that reduction zero-knowledge just lies between simulation zero-knowledge and witness indistinguishability. Under the assumption of existence of one-way permutations a 4-round public-coin reduction zero-knowledge proof system for NP is presented and in practice this protocol works in 3 rounds since the first verifier's message can be fixed once and for all.The nature of zero-knowledge is re-examined and the evidence for the following belief is shown: the classic simulation based definitions of zero-knowledge (simulation zero-knowledge) may be somewhat too strong to include some 'nice' protocols in which the malicious verifier seems to learn nothing but we do not know how to construct a zero-knowledge simulator for it. To overcome this problem a new relaxation of zero-knowledge, reduction zero-knowledge, is introduced. It is shown that reduction zero-knowledge just lies between simulation zero-knowledge and witness indistinguishability. Under the assumption of existence of one-way permutations a 4-round public-coin reduction zero-knowledge proof system for NP is presented and in practice this protocol works in 3 rounds since the first verifier's message can be fixed once and for all.

关 键 词：ZERO-KNOWLEDGE non-interactive zero-knowledge bit commitment zap witness indistinguishability. 

分 类 号：TN918.1[电子电信—通信与信息系统]