Accumulator
Overview
Basics
universal: supports non-membership witnesses
dynamic: accumulator manager can remove elements from the set
strong even a corrupt accumulator manager cannot forge a proof of (non-)membership
Examples for understanding
digital signatures
signature verification key is the accumulator representing the set of signed messages
signatures are membership witnesses
The owner of the signing key is the accumulator manager, and she can add elements to the set by signing them.
not dynamic: she cannot un-sign elements (without publishing a revocation list, which is not constant in size)
not universal: she cannot produce a proof that a given element has not been signed
not strong: she can also always prove the membership of arbitrary elements
Merkle hash tree
The tree root is the accumulator representing the set of leaf nodes
the authenticating paths through the tree are membership witnesses
dynamic: This accumulator supports both element addition and deletion
but when either of those events occur, all existing witnesses must be updated, requiring total work that is linear in the number of member elements. In many situations, this is prohibitively inefficient.
strong: all additions and deletions are publicly verifiable (by means of re-execution).
it can be modified to be universal
Classification
David Derler, Christian Hanser, and Daniel Slamanig
Institute for Applied Information Processing and Communications (IAIK), Graz University of Technology (TUG)
a unified formal model for (randomized) cryptographic accumulators
an exhaustive classification of all existing schemes
https://gyazo.com/fde7ff27ef8b8f8f324aa34280410c22
Impossibility results
Application
Resources
Proposed universal accumulator
strong RSA assumption
Philippe Camacho (University of Chile), Alejandro Hevia, Marcos Kiwi, and Roberto Opazo
strong universal accumulator schemes
the main advantages of our scheme in comparison to Li et al.’s:
1. the accumulator manager need not to be trusted
2. since we only assume the existence of cryptographic hash functions as opposed to the Strong RSA Assumption
The drawbacks of using a hash tree based scheme
1. the size of witnesses and the update time is logarithmic in the number of values accumulated.
In contrast, witnesses and updates can be computed in constant time in RSA modular exponentiation based schemes
2. the accumulator’s manager storage space requirements which is linear in the number of elements
Foteini Baldimtsi, Ran Canetti, Sophia Yakoubov (Boston University)
RSA Accumulator
Alex Ozdemir Riad S. Wahby Dan Boneh
Class groups of imaginary quadratic orders
Helger Lipmaa (University of Tartu)
Merkle tree
Urkel Tree
An optimized and cryptographically provable key-value store for decentralized naming.
MMR
Others