Accumulator (cryptography)

In cryptography, an accumulator is a one way membership hash function. It allows users to certify that potential candidates are a member of a certain set without revealing the individual members of the set. This concept was formally introduced by Josh Benaloh and Michael de Mare in 1993.
Formal definitions.
There are several formal definitions which have been proposed in the literature. This section lists them by proposer, in roughly chronological order.
Benaloh and de Mare (1993).
Benaloh and de Mare define a one-way hash function as a family of functions formula_1 which satisfy the following three properties:
From such a function, one defines the "accumulated hash" of a set formula_11 w.r.t. a value formula_12 to be formula_13. (This does not depend on the order of elements because formula_14 is quasi-commutative.)
Barić and Pfitzmann (1997).
The basic functionality of a quasi-commutative hash function is not immediate from the definition. 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:
It is relatively easy to see that one can define an accumulator scheme from any quasi-commutative hash function, using the technique shown above.
Camenisch and Lysyanskaya (2002).
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:
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.
Examples.
One example is multiplication over large prime numbers. 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. New members may be added or subtracted to the set of factors by multiplying or factoring out the number respectively. 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).
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 formula_77 for some composite number formula_78. They recommend to choose formula_78 to be a "rigid" integer (i.e. the product of two safe primes). Barić and Pfitzmann proposed a variant where formula_24 was restricted to be prime and at most formula_81 (this constant is very close to formula_82, but does not leak information about the prime factorization of formula_78).
David Naccache observed in 1993 that formula_84 is quasi-commutative for all constants formula_85, 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.
In 1996, Nyberg constructed an accumulator which is provably information-theoretically secure in the random oracle model. Choosing some upper limit formula_86 for the number of items that can be securely accumulated and formula_87 the security parameter, define the constant formula_88 to be an integer multiple of formula_89 (so that one can write formula_90) and let formula_91 be some cryptographically secure hash function. Choose a key formula_16 as a random formula_93-bit bitstring. Then, to accumulate using Nyberg's scheme, use the quasi-commutative hash function formula_94, where formula_95 is the bitwise and operation and formula_96 is the function that interprets its input as a sequence of formula_89-bit bitstrings of length formula_93, replaces every all-zero bitstring with a single 0 and every other bitstring with a 1, and outputs the result.
Applications.
Haber and Stornetta showed in 1990 that accumulators can be use to timestamp documents through cryptographic chaining. (This concept anticipates the modern notion of a cryptographic blockchain.) Benaloh and de Mare proposed an alternative scheme in 1991 based on discretizing time into rounds.
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). Each person selects a formula_24 representing their identity, and the group collectively selects a public accumulator formula_14 and a secret formula_12. Then, the group publishes or saves the hash function and the accumulated hash of all the group's identities w.r.t the secret formula_12 and public accumulator; simultaneously, each member of the group keeps both its identity value formula_24 and the accumulated hash of all the group's identities "except that of the member". (If the large group of people do not trust each other, or if the accumulator has a cryptographic trapdoor as in the case of the RSA-inspired accumulator, then they can compute the accumulated hashes by secure multiparty computation.) 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. With a dynamic accumulator scheme, it is additionally easy to add or remove members afterward.
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. 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). Since the initial proposal of Zerocoin, it has been succeeded by the Zerocash protocol and is currently being developed into Zcash, a fully-fledged digital currency. 