A new dynamic accumulator for batch updates

Peishun Wang*, Huaxiong Wang, Josef Pieprzyk

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

18 Citations (Scopus)


A dynamic accumulator is an algorithm, which gathers together a large set of elements into a constant-size value such that for a given element accumulated, there is a witness confirming that the element was indeed included into the value, with a property that accumulated elements can be dynamically added and deleted into/from the original set such that the cost of an addition or deletion operation is independent of the number of accumulated elements. Although the first accumulator was presented ten years ago, there is still no standard formal definition of accumulators. In this paper, we generalize formal definitions for accumulators, formulate a security game for dynamic accumulators so-called Chosen Element Attack (CEA), and propose a new dynamic accumulator for batch updates based on the Paillier cryptosystem. Our construction makes a batch of update operations at unit cost. We prove its security under the extended strong RSA (es-RSA) assumption.

Original languageEnglish
Title of host publicationInformation and Communications Security - 9th International Conference, ICICS 2007, Proceedings
EditorsSihan Qing, Hideki Imai, Guilin Wang
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Number of pages15
Volume4861 LNCS
ISBN (Print)9783540770473
Publication statusPublished - 2007
Event9th International Conference on Information and Communications Security, ICICS 2007 - Zhengzhou, China
Duration: 12 Dec 200715 Dec 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4861 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Other9th International Conference on Information and Communications Security, ICICS 2007


Dive into the research topics of 'A new dynamic accumulator for batch updates'. Together they form a unique fingerprint.

Cite this