A two-round honest-verifier zero-knowledge protocol  

作　　者：LIU HanWu LIN DongDai 

机构地区：[1]The State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China [2]Graduate University of the Chinese Academy of Sciences, Beijing 100049, China

出　　处：《Science China(Information Sciences)》2010年第5期954-963,共10页中国科学（信息科学）（英文版）

基　　金：supported by the National Natural Science Foundation of China (Grant Nos. 60673069, 60803128);the National High-Tech Research & Development Program of China (Grant No. 2007AA01Z447)

摘　　要：Since the concept of zero-knowledge protocols was introduced, it has attracted a lot of attention and in turn showed significant effect on the development of cryptography, complexity theory and other areas. The round complexity of a zero-knowledge protocol is a very important efficiency consideration, and it is required to be as small as possible. Generally, it is desirable to have zero-knowledge protocols with constant numbers of rounds. Goldreich and Oren proved that only languages in BPP have one-round and two-round zero-knowledge protocols. Moreover, they also showed that only languages in BPP have one-round honest-verifier zero-knowledge protocols. The notion of honest-verifier zero-knowledge protocols is highly non-trivial and fascinating itself, and has many other uses. Thus, the problem as to whether there exist two-round honest-verifier zero-knowledge protocols becomes an important open problem. In this paper, we introduce a new simulation technique and present a two-round honest-verifier zero-knowledge protocol for any language in N P under a standard complexity assumption based on this technique.

关 键 词：proof system argument system ZERO-KNOWLEDGE witness indistinguishability BLACK-BOX one-way permutation commitment scheme zap 

分 类 号：TP309[自动化与计算机技术—计算机系统结构] TP393[自动化与计算机技术—计算机科学与技术]