Algebraic Construction for Zero-Knowledge Sets  

作　　者：薛锐 李宁辉 李江滔 

机构地区：[1]The State Key Laboratory of Information Security,Institute of Software,Chinese Academy of Sciences Beijing 100080,China [2]Department of Computer Science,Purdue University,West Lafayette,U.S.A. [3]Software and Solutions Group,Intel Corporation,Hillsboro,U.S.A.

出　　处：《Journal of Computer Science & Technology》2008年第2期166-175,共10页计算机科学技术学报（英文版）

基　　金：This work is supported by NSF of USA under Grant Nos.IIS-0430274, and CCR-0325951, and sponsors of CERIAS;Rui Xue is partially supported by the Fund of the China Scholarship Council, partially by National Natural Science Foundation of China under Grant No.60773029;National Grand Fundamental Research 973 Program of China under Grant No.2007CB311202;the National High Technology Research and Development 863 Program of China under Grant No.2006AA01Z427.

摘　　要：Zero knowledge sets is a new cryptographic primitive introduced by Micali, Rabin, and Kilian in FOCS 2003. It has been intensively studied recently. However all the existing ZKS schemes follow the basic structure by Micali et al. That is, the schemes employ the Merkle tree as a basic structure and mercurial commitments as the commitment units to nodes of the tree. The proof for any query consists of an authentication chain. We propose in this paper a new algebraic scheme that is completely different from all the existing schemes. Our new scheme is computationally secure under the standard strong RSA assumption. Neither mercurial commitments nor tree structure is used in the new construction. In fact, the prover in our construction commits the desired set without any trapdoor information, which is another key important difference from the previous approaches.Zero knowledge sets is a new cryptographic primitive introduced by Micali, Rabin, and Kilian in FOCS 2003. It has been intensively studied recently. However all the existing ZKS schemes follow the basic structure by Micali et al. That is, the schemes employ the Merkle tree as a basic structure and mercurial commitments as the commitment units to nodes of the tree. The proof for any query consists of an authentication chain. We propose in this paper a new algebraic scheme that is completely different from all the existing schemes. Our new scheme is computationally secure under the standard strong RSA assumption. Neither mercurial commitments nor tree structure is used in the new construction. In fact, the prover in our construction commits the desired set without any trapdoor information, which is another key important difference from the previous approaches.

关 键 词：zero knowledge set Merkle tree accumulator strong RSA assumption random oracle 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]