密码累加器研究进展及应用

doi:10.19665/j.issn1001-2400.2022.01.008

Abstract

Abstract:

Cryptographic accumulators can accumulate all the elements in a set and efficiently give the (non)membership proof of any element,that is,to prove whether an element exists in the set.Cryptographic accumulators are mainly divided into three types:static accumulators,dynamic accumulators and universal accumulators.Specifically,static accumulators aim at accumulating the elements in the static set;dynamic accumulators further allow the dynamic addition and deletion of elements from the accumulation set;universal accumulators support both membership proof and non-membership proof (elements are not in the set).For the above different types of cryptographic accumulators,many scholars have given specific structures based on different cryptographic tools,which can be divided into RSA based cryptographic accumulator,bilinear mapping based cryptographic accumulator and Merkle hash tree based cryptographic accumulator.Cryptographic accumulators have a wide range of application scenarios,such as group signature,ring signature,anonymous certificate,timestamp,outsourced data verification and so on.In recent years,cryptographic accumulators have been applied to the blockchain to solve the problem of high storage overhead.This paper first classifies,analyzes and summarizes the existing scheme from the aspects of the construction scheme and function application of the cryptographic accumulators,then introduces the main application scenarios of the cryptographic accumulators,and finally points out some problems faced by the existing scheme,as well as the future development trend and research direction.

Key words: cryptographicaccumulator, RSA accumulator, accumulator based on bilinear mapping, accumulator based on Merkle hash tree

CLC Number:

TP309.2

MIAO Meixia,WU Panru,WANG Yunling. Research progress and applications of cryptographic accumulators[J].Journal of Xidian University, 2022, 49(1): 78-91.

Figures/Tables 1

References 47

[1]	CAMPANELLI M, FIORE D, GRECO N, et al. Incrementally Aggregatable Vector Commitments and Applications to Verifiable Decentralized Storage[C]// International Conference on the Theory and Application of Cryptology and Information Security.Berlin:Springer, 2020:3-35.
[2]	WANG Q, ZHOU F, XU J, et al. A (Zero-Knowledge) Vector Commitment with Sum Binding and its Applications[J]. The Computer Journal, 2020, 63(4):633-647. doi: 10.1093/comjnl/bxz115
[3]	MICALI S, RABIN M,KILIANJ. Zero-Knowledge Sets[C]// Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science.Piscataway:IEEE, 2003:80-91.
[4]	WU C, CHEN X, SUSILO W. Concise ID-Based Mercurial Functional Commitments and Applications to Zero-Knowledge Sets[J]. International Journal of Information Security, 2020, 19(2):453-464. doi: 10.1007/s10207-019-00466-7
[5]	BENALOH J, MD M. One-Way Accumulators:A Decentralized Alternative to Digital Signatures[C]// Advances in Cryptology.Berlin:Springer, 1993:274-285.
[6]	CAMENISCH J, LYSYANSKAYA A. Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[C]// Proceedings of the Advances in Cryptology.Berlin:Springer, 2002:61-76.
[7]	LI J, LI N, RUI X. Universal Accumulators with Efficient Nonmembership Proofs[C]// Proceedings of the Applied Cryptography and Network Security.Berlin:Springer, 2007:253-269.
[8]	BARIC N, PFITZMANN B. Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees[C]// Proceedings of the International Conference on the Theory & Applications of Cryptographic Techniques.Berlin:Springer, 1997:480-494.
[9]	NGUYEN L. Accumulators from Bilinear Pairings and Applications to ID-Based Ring Signatures and Group Membership Revocation[C]// Proceedings of the Topics in Cryptology.Berlin:Springer, 2005:275-292.
[10]	DAMGARD I, TRIANDOPOULOS N. Supporting Nonmembership Proofs with Bilinear-Map Accumulators(2008)[EB/OL]. [2008-1-1]. http://eprint.iacr.org/2008/538.pdf.
[11]	AU M H, TSANG P P, SUSILO W, et al. Dynamic Universal Accumulators for DDH Groups and Their Application to Attribute-Based Anonymous Credential Systems[C]// Proceedings of the The Cryptographers' Track at the RSA Conference 2009 on Topics in Cryptology.Berlin:Springer, 2009:295-308.
[12]	CAMENISCH J, KOHLWEISS M, SORIENTE C. An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[C]// Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography.Berlin:Springer, 2009:481-500.
[13]	CAMACHO P, HEVIA A, KIWI M, et al. Strong Accumulators from Collision-Resistant Hashing[C]// Proceedings of the Information Security Conference.Berlin:Springer, 2008:471-486.
[14]	GOLDREICH O, OREN Y. Definitions and Properties of Zero-Knowledge Proof Systems[J]. Journal of Cryptology, 1994, 7(1):1-32. doi: 10.1007/BF00195207
[15]	PENNINO D, PIZZONIA M, GRISCIOLI F. Pipeline-Integrity:Scaling the Use of Authenticated Data Structures up to the Cloud[J]. Future Generation Computer Systems, 2019, 100(1):618-647. doi: 10.1016/j.future.2019.05.018
[16]	SUN Y, LIU Q, CHEN X, et al. An Adaptive Authenticated Data Structure with Privacy-Preserving for Big Data Stream in Cloud[J]. IEEE Transactions on Information Forensics and Security, 2020, 15:3295-3310. doi: 10.1109/TIFS.2020.2986879
[17]	MARTEL C, NUCKOLLS G, DEVANBU P, et al. A General Model for Authenticated Data Structures[J]. Algorithmica, 2004, 39(1):21-41. doi: 10.1007/s00453-003-1076-8
[18]	XU J, WEI L, WU W, et al. Privacy-Preserving Data Integrity Verification by Using Lightweight Streaming Authenticated Data Structures for Healthcare Cyber-Physical System[J]. Future Generation Computer Systems, 2018, 108(1):1287-1296. doi: 10.1016/j.future.2018.04.018
[19]	BONEH D, BENEDIKT B, FISCH B. Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains[C]// Proceedings of the 39th Annual International Cryptology Conference.Berlin:Springer, 2019:561-586.
[20]	SLAMANIGO D. Dynamic Accumulator Based Discretionary Access Control for Outsourced Storage with Unlinkable Access[C]// Proceedings of the 16th International Conferenceon Financial Cryptography and Data Security.Berlin:Springer, 2012:215-222.
[21]	GOODRICH M T, TAMASSIA R, HASI J. An Efficient Dynamic and Distributed Cryptographic Accumulator[C]// Proceedings of the 5th International Conferenceon Information Security.Berlin:Springer, 2002:372-388.
[22]	PHLS H C, PETERS S, KAI S, et al. Malleable Signatures for Resource Constrained Platforms[C]// Proceedings of the 7th IFIP WGInternational Workshop.Berlin:Springer, 2013:18-33.
[23]	BULDAS A, LAUD P, LIPMAA H. Accountable Certificate Management Using Undeniable Attestations[C]// Proceedings of the 7th ACM conference on Computer and Communications Security. New York: ACM, 2002:9-17.
[24]	SK A, LZ A, XY B, et al. Accountable Credential Management System for Vehicular Communication[J]. Vehicular Communications, 2020, 25(4):100279. doi: 10.1016/j.vehcom.2020.100279
[25]	MEER H D, LIEDEL M, POHLS H C, et al. Indistinguishability of One-Way Accumulators(2012)[EB/OL]. [2012-12-20]https://www.fim.uni-passau.de/fileadmin/dokumente/fakultaeten/fim/forschung/mip-berichte/MIP_1210.pdf.
[26]	DERLER D, HANSER C, SLAMANIG D. Revisiting Cryptographic Accumulators,Additional Properties and Relations to Other Primitives[C]// Proceedings of the Topics in Cryptology.Berlin:Springer, 2015:127-144.
[27]	SANDER T. Efficient Accumulators without Trapdoor[C]// Proceedings of the Second International Conference on Information and Communications Security.Berlin:Springer, 1999:252-262.
[28]	LIPMAA H. Secure Accumulators from Euclidean Rings without Trusted Setup[C]// Proceedings of the 10th International Conference.Berlin:Springer, 2012:224-240.
[29]	TSUDIK G, XU S. Accumulating Composites and Improved Group Signing[C]// Proceedings of the Advances in Cryptology,Berlin:Springer, 2003:269-286.
[30]	CAMACHO P, HEVIA A. On the Impossibility of Batch Update for Cryptographic Accumulators[C]// Proceedings of the Progress in Cryptology.Berlin:Springer. 2009:178-188.
[31]	WESOLOWSKI B. Efficient Verifiable Delay Functions[J]. Journal of Cryptology, 2019, 33(4):379-407.
[32]	FIAT A, SHAMIR A. How to Prove Yourself:Practical Solutions to Identification and Signature Problems[C]// Proceedings of the Advances in Cryptology.Berlin:Springer, 2000:186-194.
[33]	BEN-SASSON E, CHIESA A, SPOONER N. Interactive Oracle Proofs[C]// Proceedings of the Theory of Cryptography.Berlin:Springer, 2016:31-60.
[34]	FORTNOW L, GOLDWASSER S, MICALI S, et al. The Knowledge Complexity of Interactive Proof Systems[J]. SIAM Journal on Computing, 1989, 18(1):186-208. doi: 10.1137/0218012
[35]	TOLGA A,LANN. Revocation for Delegatable Anonymous Credentials[C]// International Workshop on Public Key Cryptography.Berlin:Springer, 2011:423-440.
[36]	BADIMTSI F, CANETTI R, YAKOUBOV S. Universally Composable Accumulators[C]// Proceedings of the Topics in Cryptology.Berlin:Springer, 2020:638-666.
[37]	程小刚, 王箭, 杜吉祥. 群签名综述[J]. 计算机应用研究, 2013, 30(10):2881-2886.
	CHENG Xiaogang, WANG Jian, DU Jixiang. Overview of Group Signatures[J]. Application Research of Computers, 2013, 30(10):2881-2886.
[38]	GU K, DONG X, WANG L. Efficient Traceable Ring Signature Scheme without Pairings[J]. Advances in Mathematics of Communications, 2020, 14(2):207-232. doi: 10.3934/amc.2020016
[39]	BERA B, SAHA S, DAS A K, et al. Designing Blockchain-Based Access Control Protocol in IoT-Enabled Smart-Grid System[J]. IEEE Internet of Things Journal, 2020, 8(7):5744-5761. doi: 10.1109/JIOT.2020.3030308
[40]	王慧, 王励成, 柏雪, 等. 区块链隐私保护和扩容关键技术研究[J]. 西安电子科技大学学报, 2020, 47(5):28-39.
	WANG Hui, WANG Licheng, BAI Xue, et al. Research on Key Technology of Blockchain Privacy Protection and Scalability[J]. Journal of Xidian University, 2020, 47(5):28-39.
[41]	陈思吉, 翟社平, 汪一景. 一种基于环签名的区块链隐私保护算法[J]. 西安电子科技大学学报, 2020, 47(5):86-93.
	CHEN Siji, ZHAI Sheping, WANG Yijing. A Blockchain Privacy Protection Algorithm Based on Ring Signature[J]. Journal of Xidian University, 2020, 47(5):86-93.
[42]	OZCELIK I, MEDURY S, BROADDUS J, et al. An Overview of Cryptographic Accumulators[C]// International Conference on Information Systems Security and Privacy.Berlin:Springer, 2021:661-669.
[43]	ATENIESE G, CAMENISCH J, JOYE M, et al. A Practical and Provably Secure Coalition-Resistant Group Signature Scheme[C]// Proceedings of the Advances in Cryptology.Berlin:Springer, 2000:255-270.
[44]	BINDEL N, HERATH U, MCKAGUE M, et al. Transitioning to A Quantum-Resistant Public Key Infrastructure[C]// Proceedings of the Post-Quantum Cryptography.Berlin:Springer, 2017:384-405.
[45]	CAMENISCH J, LYSYANSKAYA A. An Identity Escrow Scheme with Appointed Verifiers[C]// Proceedings of the Advances in Cryptology.Berlin:Springer, 2001:388-407.
[46]	REDDYB S. SecurePrune:SecureBlock Pruning in UTXO Based Blockchains Using Accumulators[C]// 2021 International Conference on COMmunication Systems &NETworks.Piscataway:IEEE, 2021:174-178.
[47]	TOMESCU A, ABRAHAM I, BUTERIN V, et al. Aggregatable Subvector Commitments for Stateless Cryptocurrencies[C]// Proceedings of the Security and Cryptography for Networks,SCN 2020,in Lecture Notes in Computer Science.Berlin:Springer, 2020:45-64.

实现工具	假设	方案	类型	公共更新				B	\|pk_acc\|	\|w\|	\|u\|
实现工具	假设	方案	类型	w	u	a	d	B	\|pk_acc\|	\|w\|	\|u\|
		BM^[5]	S	-	-	-	-	×	O(1)	O(1)	-
		BP^[8]	S	-	-	-	-	×	O(1)	O(1)	-
RSA体制	S-RSA	CL^[6]	D	√	-	√	×	×	O(1)	O(1)	-
		LLX^[7]	DU	√	√	√	×	×	O(1)	O(1)	O(1)
		BBF^[19]	DU	√	√	√	√	×	O(1)	O(1)	O(1)
		NY^[9]	D	√	-	×	×	√	O(q)	O(1)	-
双线性映射	q-SDH	DT^[10]	DU	√	√	×	×	√	O(q)	O(1)	O(1)
		ATSM^[11]	DU	√	√	×	×	√	O(q)	O(1)	O(1)
	q-DEH	CKS^[12]	D	√	-	×	√	√	O(q)	O(1)	-
Merkle哈希树	CRH	CHKO^[13]	U	-	-	-	-	×	O(1)	O(logN)	O(logN)

Research progress and applications of cryptographic accumulators

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 1

References 47

Related Articles 12

Metrics

Comments

Recommended 0

[1]	SI Chengxiang,GAO Feng,ZHU Liehuang,GONG Guopeng,ZHANG Can,CHEN Zhuo,LI Ruiguang. Covert data transmission mechanism based on dynamic label in blockchain [J]. Journal of Xidian University, 2020, 47(5): 94-102.
[2]	MA Zhuoran, MA Jianfeng, MIAO Yinbin, SUN Cong. State transition-based access control model in the UAV network [J]. Journal of Xidian University, 2018, 45(6): 44-50.
[3]	ZHANG Hongbin;PEI Qingqi;WANG Chao;WANG Meihua. Sensing insider threat based on access vectors [J]. J4, 2014, 41(1): 110-115.
[4]	LI Huixian. Design and analysis of the light-weight mutual authentication protocol for RFID [J]. J4, 2012, 39(1): 172-178.
[5]	ZHOU Hua;MENG Xiang-ru;ZHANG Li;QIAO Xiang-dong. Proactive recovery algorithm in the distributed intrusion-tolerance system [J]. J4, 2009, 36(2): 378-384.
[6]	LI Hui-xian1;CAI Wan-dong1;PEI Qing-qi2. Design and analysis of a verifiable secret sharing scheme [J]. J4, 2008, 35(1): 148-151.
[7]	ZHANG Fan;MA Jian-feng. Security analysis of the Chinese wireless LAN standard implementation plan [J]. J4, 2005, 32(4): 545-548.
[8]	WEI Bao-dian;LIU Jing-wei;WANG Xin-mei. Two novel calculations of coordinates of finite field elements [J]. J4, 2004, 31(4): 518-522.
[9]	WEI Bao-dian1;2;LIU Jing-wei1;WANG Xin-mei1. The NESSIE block ciphers and their security [J]. J4, 2004, 31(3): 377-382.
[10]	WEI Bao-dian;LIU Dong-su;WANG Xin-mei. The correctional Square-6 attack [J]. J4, 2004, 31(1): 67-71.
[11]	WEI Bao-dian;MA Wen-ping;WANG Xin-mei. The algebraic expression for the AES Sbox [J]. J4, 2003, 30(1): 29-32.
[12]	ZHU Jian-ming1;2;MA Jian-feng1. Intrusion-tolerant based architecture for database system security [J]. J4, 2003, 30(1): 85-89.