Accumulator (cryptography)

A cryptographic accumulator is a one way membership function. It answers a query as to whether a potential candidate is a member of a set without revealing the individual members of the set. The concept was introduced by J. Benaloh and M. de Mare in 1993.

Formal definition

Benaloh and de Mare define a one-way hash function as a family of functions $h_{\ell }:X_{\ell }\times Y_{\ell }\to Z_{\ell }$ which satisfy the following three properties:

1. For all $\ell \in \mathbb {Z} ,x\in X_{\ell },y\in Y_{\ell }$, one can compute $h_{\ell }(x,y)$ in time ${\text{poly}}(\ell ,|x|,|y|)$. (Here the "poly" symbol refers to an unspecified, but fixed, polynomial.)
2. No probabilistic polynomial-time algorithm will, for sufficiently large $\ell$, map the inputs $\ell \in \mathbb {Z} ,(x,y)\in X_{\ell }\times Y_{\ell },y'\in Y_{\ell }$, find a value $x'\in X_{\ell }$ such that $h_{\ell }(x,y)=h_{\ell }(x',y')$ with more than negligible probability.
3. For all $\ell \in \mathbb {Z} ,x\in X_{\ell },y_{1},y_{2}\in Y_{\ell }$, one has $h(h(x,y_{1}),y_{2})=h(h(x,y_{2}),y_{1})$.

(With the first two properties, one recovers the normal definition of a cryptographic hash function.)

Examples

One example is how large composite numbers accumulate their prime factors, as it's currently impractical to factor a composite number, but relatively easy to divide a specific prime into another number to see 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 simply 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 where the size (number of bits) of the accumulator does not grow with the number of members.

Applications

The concept has received renewed interest recently due to the proposed Zerocoin add on to bitcoin, which employs cryptographic accumulators to eliminate trackable linkage in the bitcoin blockchain, which would make bitcoin anonymous and untraceable, increasing privacy of transactions.

See also

• Cryptography
• Zero-knowledge proof

External links

• Cryptographic Accumulators: Definitions, Constructions and Applications
• Cryptographic Accumulators for Authenticated Hash Tables.