In cryptography, an accumulator is a one way membership hash function.
This concept was formally introduced by Josh Benaloh and Michael de Mare in 1993.
This section lists them by proposer, in roughly chronological order.
From such a function, one defines the "accumulated hash" of a set
belong to some users of a cryptosystem, then everyone can compute the accumulated value
To fix this, Barić and Pfitzmann defined a slightly more general definition, which is the notion of an accumulator scheme as consisting of the following components:[2][3] It is relatively easy to see that one can define an accumulator scheme from any quasi-commutative hash function, using the technique shown above.
[2] One observes that, for many applications, the set of accumulated values will change many times.
Naïvely, one could completely redo the accumulator calculation every time; however, this may be inefficient, especially if our set is very large and the change is very small.
To formalize this intuition, Camenish and Lysyanskaya defined a dynamic accumulator scheme to consist of the 4 components of an ordinary accumulator scheme, plus three more:[2][4] Fazio and Nicolosi note that since Add, Del, and Upd can be simulated by rerunning Eval and Wit, this definition does not add any fundamentally new functionality.
This is a cryptographic accumulator, since it takes superpolynomial time to factor a composite number (at least according to conjecture), but it takes only a small amount of time (polynomial in size) to divide a prime into an integer to check if it is one of the factors and/or to factor it out.
In this system, two accumulators that have accumulated a single shared prime can have it trivially discovered by calculating their GCD, even without prior knowledge of the prime (which would otherwise require prime factorization of the accumulator to discover).
[citation needed] More practical accumulators use a quasi-commutative hash function, so that the size of the accumulator does not grow with the number of members.
For example, Benaloh and de Mare propose a cryptographic accumulator inspired by RSA: the quasi-commutative function
to be a rigid integer (i.e. the product of two safe primes).
, generalizing the previous RSA-inspired cryptographic accumulator.
Naccache also noted that the Dickson polynomials are quasi-commutative in the degree, but it is unknown whether this family of functions is one-way.
[1] In 1996, Nyberg constructed an accumulator which is provably information-theoretically secure in the random oracle model.
Then, to accumulate using Nyberg's scheme, use the quasi-commutative hash function
[2][5] Haber and Stornetta showed in 1990 that accumulators can be used to timestamp documents through cryptographic chaining.
(This concept anticipates the modern notion of a cryptographic blockchain.
)[1][2][6] Benaloh and de Mare proposed an alternative scheme in 1991 based on discretizing time into rounds.
[1][7] Benaloh and de Mare showed that accumulators can be used so that a large group of people can recognize each other at a later time (which Fazio and Nicolosi call an "ID Escrow" situation).
representing their identity, and the group collectively selects a public accumulator
and public accumulator; simultaneously, each member of the group keeps both its identity value
and the accumulated hash of all the group's identities except that of the member.
To verify that a claimed member did indeed belong to the group later, they present their identity and personal accumulated hash (or a zero-knowledge proof thereof); by accumulating the identity of the claimed member and checking it against the accumulated hash of the entire group, anyone can verify a member of the group.
[1][2] With a dynamic accumulator scheme, it is additionally easy to add or remove members afterward.
[2][4] Cryptographic accumulators can also be used to construct other cryptographically secure data structures: The concept has received renewed interest due to the Zerocoin add on to bitcoin, which employs cryptographic accumulators to eliminate trackable linkage in the bitcoin blockchain, which would make transactions anonymous and more private.
[10][11][12] More concretely, to mint (create) a Zerocoin, one publishes a coin and a cryptographic commitment to a serial number with a secret random value (which all users will accept as long as it is correctly formatted); to spend (reclaim) a Zerocoin, one publishes the Zerocoin's serial number along with a non-interactive zero-knowledge proof that they know of some published commitment that relates to the claimed serial number, then claims the coin (which all users will accept as long as the NIZKP is valid and the serial number has not appeared before).
[10][11] Since the initial proposal of Zerocoin, it has been succeeded by the Zerocash protocol and is currently being developed into Zcash, a digital currency based on Bitcoin's codebase.