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. [1] [2]
There are several formal definitions which have been proposed in the literature. This section lists them by proposer, in roughly chronological order. [2]
Benaloh and de Mare define a one-way hash function as a family of functions which satisfy the following three properties: [1] [2]
(With the first two properties, one recovers the normal definition of a cryptographic hash function.)
From such a function, one defines the "accumulated hash" of a set and starting value w.r.t. a value to be . The result, does not depend on the order of elements because is quasi-commutative. [1] [2]
If belong to some users of a cryptosystem, then everyone can compute the accumulated value Also, the user of can compute the partial accumulated value of . Then, So the user can provide the pair to any other part, in order to authenticate .
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: [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. [2]
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).[ 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 for some composite number . They recommend to choose to be a rigid integer (i.e. the product of two safe primes). [1] Barić and Pfitzmann proposed a variant where was restricted to be prime and at most (this constant is very close to , but does not leak information about the prime factorization of ). [2] [3]
David Naccache observed in 1993 that is quasi-commutative for all constants , 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. Choosing some upper limit for the number of items that can be securely accumulated and the security parameter, define the constant to be an integer multiple of (so that one can write ) and let be some cryptographically secure hash function. Choose a key as a random -bit bitstring. Then, to accumulate using Nyberg's scheme, use the quasi-commutative hash function , where is the bitwise and operation and is the function that interprets its input as a sequence of -bit bitstrings of length , replaces every all-zero bitstring with a single 0 and every other bitstring with a 1, and outputs the result. [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). Each person selects a representing their identity, and the group collectively selects a public accumulator and a secret . Then, the group publishes or saves the hash function and the accumulated hash of all the group's identities w.r.t the secret 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. (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. [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. [13] [14]