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

doi:10.19665/j.issn1001-2400.2022.01.008

摘要/Abstract

摘要：

密码累加器能够将集合中的所有元素进行累加,并高效地给出任意元素的(非) 成员证明,即该元素是否存在于集合中。密码累加器主要分为静态累加器、动态累加器以及通用累加器三种类型。静态累加器针对静态集合中元素的累加;动态累加器进一步允许从累加集合中动态地添加和删除元素;通用累加器能够同时支持成员证明和非成员证明(元素不在集合中)。针对上述不同类型的密码累加器,许多学者基于不同的密码工具给出了具体构造,可分为基于RSA的密码累加器、基于双线性映射的密码累加器和基于Merkle哈希树的密码累加器。密码累加器有广泛的应用场景,如群签名、环签名、匿名凭证、时间戳、外包数据验证等。近年来,密码累加器开始应用于区块链中用来解决存储开销大的问题。文中首先从密码累加器的构造方案和功能应用等方面对现有方案进行了分类、分析、总结,其次介绍了密码累加器的主要应用场景,最后指出了现有方案面临的一些问题,以及未来的发展趋势和研究方向。

关键词: 密码累加器, RSA累加器, 双线性映射累加器, 基于Merkle哈希树的累加器

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

中图分类号:

TP309.2

苗美霞,武盼汝,王贇玲. 密码累加器研究进展及应用[J]. 西安电子科技大学学报, 2022, 49(1): 78-91.

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

图/表 1

参考文献 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)