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 which satisfy the following three properties:
For all , one can compute in time . (Here the "poly" symbol refers to an unspecified, but fixed, polynomial.) No probabilistic polynomial-time algorithm will, for sufficiently large , map the inputs , find a value such that with more than negligible probability. For all , one has . (A function that satisfies this property is called quasi-commutative.)
(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.
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 .
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:
Gen: a probabilistic algorithm that takes in two parameters (the security parameter and the number of values that can be securely accumulated, respectively), and returns an appropriate key . Eval: a probabilistic algorithm that takes in a key and accumulation set , where , and returning an accumulated value and auxiliary information . We insist that Eval must be deterministic for . Wit: a probabilistic algorithm that takes in a key , a value , an accumulated value of some set , and some auxiliary information , and returns either a witness or the special symbol . We insist that, if , that Wit returns a witness, and that Wit otherwise returns . Ver: a deterministic algorithm that takes in a key , a value , a witness , and an accumulated value , and returns a Yes/No value. We insist that if was generated from running Wit on a tuple , where were generated from running Eval on some , and where was chosen arbitrarily and was chosen from running Gen, that Ver always return Yes.
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:
Add: a (possibly probabilistic) algorithm that takes in a key , an accumulated value , and another value to accumulate , and returns a new accumulated value and auxiliary information . We insist that if was generated by accumulating some set , then must be as if it were generated by accumulating the set . Del: a (possibly probabilistic) algorithm that takes in a key , an accumulated value , and another value to accumulate , and returns a new accumulated value and auxiliary information . We insist that if was generated by accumulating some set , then must be as if it were generated by accumulating the set . Upd: a deterministic algorithm that takes in the key , a value , a witness , the accumulated value , and auxiliary information , and returns a new witness . We insist that if was generated by Gen, is part of a set , is a witness for being a member of , and is an accumulated value for , and was generated by running Add or Del, then will be a witness for being a member of the new set.
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.