Accumulator (cryptography)

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

1. For all ${\displaystyle \ell \in \mathbb {Z} ,x\in X_{\ell },y\in Y_{\ell }}$, one can compute ${\displaystyle h_{\ell }(x,y)}$ in time ${\displaystyle {\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 ${\displaystyle \ell }$, map the inputs ${\displaystyle \ell \in \mathbb {Z} ,(x,y)\in X_{\ell }\times Y_{\ell },y'\in Y_{\ell }}$, find a value ${\displaystyle x'\in X_{\ell }}$ such that ${\displaystyle h_{\ell }(x,y)=h_{\ell }(x',y')}$ with more than negligible probability.
3. For all ${\displaystyle \ell \in \mathbb {Z} ,x\in X_{\ell },y_{1},y_{2}\in Y_{\ell }}$, one has ${\displaystyle h(h(x,y_{1}),y_{2})=h(h(x,y_{2}),y_{1})}$. (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 ${\displaystyle \{y_{1},\dots ,y_{m}\}}$ w.r.t. a value ${\displaystyle x}$ to be ${\displaystyle h(\dots h(h(x,y_{1}),y_{2}),\dots ,y_{m})}$. (This does not depend on the order of elements because ${\displaystyle h}$ is quasi-commutative.)

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 ${\displaystyle h(x,y):=x^{y}{\pmod {n}}}$ for some composite number ${\displaystyle n}$. They recommend to choose ${\displaystyle n}$ to be a rigid integer (i.e. the product of two safe primes).[1]

David Naccache observed that ${\displaystyle e_{n,c}(x,y):=x^{y}c^{y-1}{\pmod {n}}}$ is quasi-commutative for all constants ${\displaystyle c,n}$, generalizing the previous RSA-inspired cryptographic accumulator. Naccache has 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]

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.)[1][3] Benaloh and de Mare proposed an alternative scheme in 1991 based on discretizing time into rounds.[1][4]

Additionally, 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. Each person selects a ${\displaystyle y}$ representing their identity, and the group collectively selects a public accumulator ${\displaystyle h}$ and a secret ${\displaystyle x}$. Then, the group publishes or saves the hash function and the accumulated hash of all the group's identities w.r.t the secret ${\displaystyle x}$ and public accumulator; simultaneously, each member of the group keeps both its identity value ${\displaystyle y}$ 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; 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]

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.[5][6][7]

• Cryptography
• Zero-knowledge proof

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