Paper 2023/1001

Oblivious Accumulators

Foteini Baldimtsi, George Mason University
Ioanna Karantaidou, George Mason University
Srinivasan Raghuraman, Visa (United States), Massachusetts Institute of Technology

A cryptographic accumulator is a succinct set commitment scheme with efficient (non-)membership proofs that typically supports updates (additions and deletions) on the accumulated set. When elements are added to or deleted from the set, an update message is issued. The collection of all the update messages essentially leaks the underlying accumulated set which in certain applications is not desirable. In this work, we define oblivious accumulators, a set commitment with concise membership proofs that hides the elements and the set size from every entity: an outsider, a verifier or other element holders. We formalize this notion of privacy via two properties: element hiding and add-delete indistinguishability. We also define almost-oblivious accumulators, that only achieve a weaker notion of privacy called add-delete unlinkability. Such accumulators hide the elements but not the set size. We consider the trapdoorless, decentralized setting where different users can add and delete elements from the accumulator and compute membership proofs. We then give a generic construction of an oblivious accumulator based on key-value commitments (KVC). We also show a generic way to construct KVCs from an accumulator and a vector commitment scheme. Finally, we give lower bounds on the communication (size of update messages) required for oblivious accumulators and almost-oblivious accumulators.

Available format(s)
Cryptographic protocols
Publication info
oblivious accumulatorsvector commitmentskey-value commitmentslower bounds
Contact author(s)
foteini @ gmu edu
ikaranta @ gmu edu
srraghur @ visa com
2023-06-29: approved
2023-06-27: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Foteini Baldimtsi and Ioanna Karantaidou and Srinivasan Raghuraman},
      title = {Oblivious Accumulators},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1001},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.