Special Issue: Artificial Intelligence and Pattern Recognition

• Articles •     Next Articles

Algebraic Construction for Zero-Knowledge Sets

Rui Xue1, Ning-Hui Li2, and Jiang-Tao Li3   

  1. 1The State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences Beijing 100080, China 2Department of Computer Science, Purdue University, West Lafayette, U.S.A. 3Software and Solutions Group, Intel Corporation, Hillsboro, U.S.A.
  • Revised:2008-01-03 Online:2008-03-15 Published:2008-03-10

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 {\it 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.

Key words: data compression; genetic algorithm; cellular automaton; parallel processing;

[1] Micali S, Rabin M, Kilian J. Zero-knowledge sets. In -\it Proc. the 44th Annual IEEE Symposium on Foundations of Computer Science $($FOCS$)$}, Cambridge, MA, USA, 2003, p.80.

[2] Merkle R C. A certified digital signature. In -\it Proc. Advances in Cryptology----CRYPTO}'89}, Brassard G (ed.), Santa Barbara, California, United States, -\it Lecture Notes in Computer Science}, Vol. 435, Springer-Verlag, 1990, 20--24 Aug., 1989, pp.218--238.

[3] Pedersen T P. Non-interactive and information-theoretic secure verifiable secret sharing. In -\it Proc. Advances in Cryptology --- -CRYPTO}'91}, Santa Barbara, California, USA, 1992, pp.129--140.

[4] Chase M, Healy A, Lysyanskaya A, Malkin T, Reyzin L. Mercurial commitments with applications to zero-knowledge sets. In -\it Proc. Advances in Cryptology ---EUROCRYPT}'05}, Aarhus, Denmark, 2005, pp.422--439.

[5] Liskov M. Updatable zero-knowledge databases. In -\it Proc. Advances in Cryptology ---ASIACRYPT}'05}, Chennai, India, 2005, pp.174--198.

[6] Ostrovsky R, Rackoff C, Smith A. Efficient consistency proofs for generalized queries on a committed database. In -\it Proc. ICALP}, Turku, Finland, 2004, pp.1041--1053.

[7] Catalano D, Dodis Y, Visconti I. Mercurial commitments: Minimal assumptions and efficient constructions. In -\it Proc. Theory of Cryptography --TCC'06}, -\it Lecture Notes in Computer Science}, Vol.3876, New York, Springer-Verlag, 2006, pp.120--144.

[8] Gennaro R, Micali S. Independent zero-knowledge sets. In -\it Proc. ICALP $(2)$}, Venice, Italy, 2006, pp.34--45.

[9]Benaloh J C, de Mare M. One-way accumulators: -A} decentralized alternative to digital signatures. In -\it Proc. Advances in Cryptology ---EUROCRYPT}'93}, Lofthus, Norway, 1994, pp.274--285.

[10] Bari\'c N, Pfitzmann B. Collision-free accumulators and fail-stop signature schemes without trees. In -\it Proc. Advances in Cryptology ---EUROCRYPT}'97}, Konstanz, Germany, 1997, pp.480--494.

[11] Camenisch J, Lysyanskaya A. Dynamic accumulators and application to efficient revocation of anonymous credentials. In -\it Advances in Cryptology ---CRYPTO}'02}, Santa Barbara, California, USA, 2002, pp.61--76.

[12] Goodrich M T, Tamassia R, Hasic J. An efficient dynamic and distributed cryptographic accumulator. In -\it Proc. the 5th International Conference on Information Security}, London, UK, 2002, pp.372--388.

[13] Li J T, Li N H, Xue R. Universal accumulators with efficient nonmembership proofs. In -\it Proc. %the 5th International Conference on %Applied Cryptography and Network Security $($ACNS07$)$}, -\it Lecture Notes in Computer Science}, Vol. 4521, Zhuhai, China, Springer-Verlag, 2007, pp.253--269.

[14] Prabhakaran M, Xue R. Statistically Hiding Sets. Submitted to -\it ICALP 2008}, 2007.

[15] Camenisch J, Stadler M. Efficient group signature schemes for large groups. In -\it Proc. Advances in Cryptology ---CRYPTO}'97}, Santa Barbara, California, USA, 1997, pp.410--424.

[16] Gennaro R, Halevi S, Rabin T. Secure hash-and-sign signatures without the random oracle. In -\it Proc. Advances in Cryptology --- -EUROCRYPT}'99}, Prague, Czech Republic, 1999, pp.123--139.

[17] Fujisaki E, Okamoto T. Statistical zero knowledge protocols to prove modular polynomial relations. In -\it Proc. Advances in Cryptology ---CRYPTO}'97}, Santa Barbara, California, Aug. 1997, pp.16--30.

[18] Cramer R, Shoup V. Signature schemes based on the strong -RSA} assumption. In -\it Proc. the 6th -ACM} Conference on Computer and Communications Security $($CCS$)$}, Singapore, Nov. 1999, pp.46--51.

[19] Shamir A. On the generation of cryptographically strong pseudorandom sequences. \it ACM Transactions on Computer Systems, \rm 1983 1(1): 38.

[20] Bellare M, Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols. In -\it Proc. ACM Conference on Computer and Communications Security}, Alexandria, VA, USA, 1993, pp.62--73.

[21] Fiat A, Shamir A. How to prove yourself: Practical solutions to identification and signature problems. In -\it Proc. Advances in Cryptology ---CRYPTO}'86}, Santa Barbara, California, USA, 1987, pp.186--194.

[22]Santis A D, Micali S, Persiano G. Non-interactive zero-knowledge proof systems. In -\it Proc. RYPTO'87}, Pomerance C (ed.), Santa Barbara, California, United States, -\it Lecture Notes in Computer Science}, Springer-Verlag, 1988, Vol. 293, pp.52--72.

[23] Algesheimer J, Camenisch J, Shoup V. Efficient computation modulo a shared secret with application to the generation of shared safe-prime products. In -\it Proc. Advances in Cryptology ---CRYPTO}'02}, Santa Barbara, California, USA, 2002, pp.417--432.

[24] Sander T. Efficient accumulators without trapdoor extended abstracts. In -\it Proc. ICICS}, Sydney, Australia, Varadharajan V, Mu Y (eds.), -\it Lecture Notes in Computer Science}, Vol. 1726, Springer, 1999, pp.252--262.

[25] Chaum C, Evertse J H, van de Graaf J, Peralta R. Demonstrating possession of a discrete logarithm without revealing it. In -\it Proc. Advances in Cryptology ---CRYPTO}'86}, Santa Barbara, California, USA, 1987, pp.200--212.

[26] Schnorr C P. Efficient signature generation by smart cards, -\it Journal of Cryptology}, 1991, 4: 161--174.

[27] Feige U, Fiat A, Shamir A. Zero knowledge proofs of identity. -\it Journal of Cryptology}, 1988, 1(2): 77--94.

[28] Granville A. Harold Cram\'er and the distribution of prime numbers. -\it Scandanavian Actuarial Journal}, 1995, 1: 12--28.

[29] Shoup V. Practical threshold signatures. In -\it Proc. Advances in Cryptology ---EUROCRYPT}'00}, Bruges, Belgium, 2000, pp.207--220.
[1] Yong-Hao Long, Yan-Cheng Chen, Xiang-Ping Chen, Xiao-Hong Shi, and Fan Zhou. Test-Driven Feature Extraction of Web Components [J]. Journal of Computer Science and Technology, 2022, 37(2): 389-404.
[2] Chun-Hui Wang, Zhi Jin, Wei Zhang, Didar Zowghi, Hai-Yan Zhao, Wen-Pin Jiao. Activity Diagram Synthesis Using Labelled Graphs and the Genetic Algorithm [J]. Journal of Computer Science and Technology, 2021, 36(6): 1388-1406.
[3] Jie Xiao, Zhan-Hui Shi, Jian-Hui Jiang, Xu-Hua Yang, Yu-Jiao Huang, Hai-Gen Hu. A Locating Method for Reliability-Critical Gates with a Parallel-Structured Genetic Algorithm [J]. Journal of Computer Science and Technology, 2019, 34(5): 1136-1151.
[4] Rong-Zhi Qi, Zhi-Jian Wang, Shui-Yan Li. A Parallel Genetic Algorithm Based on Spark for Pairwise Test Suite Generation [J]. , 2016, 31(2): 417-427.
[5] Chun-Meng Kang, Lu Wang, Pei Wang, Yan-Ning Xu, Xiang-Xu Meng. Coherent Photon Mapping on the Intel MIC Architecture [J]. , 2015, 30(3): 519-527.
[6] Concha Bielza, Juan A. Fernández del Pozo, and Pedro Larrañaga. Parameter Control of Genetic Algorithms by Learning and Simulation of Bayesian Networks —— A Case Study for the Optimal Ordering of Tables [J]. , 2013, 28(4): 720-731.
[7] Antonio M. Mora, Antonio Fernández-Ares, Juan J. Merelo, Pablo García-Sánchez, and Carlos M. Fernandes. Effect of Noisy Fitness in Real-Time Strategy Games Player Behaviour Optimisation Using Evolutionary Algorithms [J]. , 2012, 27(5): 1007-1023.
[8] Yong Wu (吴勇) and Arun Kumar. A Parallel Interval Computation Model for Global Optimization with Automatic Load Balancing [J]. , 2012, 27(4): 744-753.
[9] Zhu-Fei Chu (储著飞), Student Member, IEEE, Yin-Shui Xia (夏银水), and Lun-Yao Wang (王伦耀). Cell Mapping for Nanohybrid Circuit Architecture Using Genetic Algorithm [J]. , 2012, 27(1): 113-120.
[10] Ozgur Sinanoglu, Mohammed Al-Mulla, Noora A. Shunaiber, and Alex Orailoglu, Member, IEEE. Scan Cell Positioning for Boosting the Compression of Fan-Out Networks [J]. , 2009, 24(5): 939-948.
[11] Feng Zeng, Student Member, CCF, and Zhi-Gang Chen, Member, CCF. Cost-Sensitive and Load-Balancing Gateway Placement in Wireless Mesh Networks with QoS Constraints [J]. , 2009, 24(4): 775-785.
[12] Sriparna Saha, Student Member, IEEE, and Sanghamitra Bandyopadhyay, Senior Member, IEEE. A New Line Symmetry Distance and Its Application to Data Clustering [J]. , 2009, 24(3): 544-556.
[13] Dong-Nian Cheng, Yu-Xiang Hu, and Cai-Xia Liu. Parallel Algorithm Core: A Novel IPSec Algorithm Engine for Both Exploiting Parallelism and Improving Scalability [J]. , 2008, 23(5 ): 792-805 .
[14] Ji-Bao Lai , Hui-Qiang Wang, Xiao-Wu Liu, Ying Liang, Rui-Juan Zheng, and Guo-Sheng Zhao. WNN-Based Network Security Situation Quantitative Prediction Method and Its Optimization [J]. , 2008, 23(2): 222-230 .
[15] Ehab Z. Elfeky, Ruhul A. Sarker, and Daryl L. Essam. Analyzing the Simple Ranking and Selection Process for Constrained Evolutionary Optimization [J]. , 2008, 23(1): 19-34 .
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved