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}\}}$ and starting value ${\displaystyle x}$ w.r.t. a value ${\displaystyle z}$ to be ${\displaystyle h(h(\cdots h(h(x,y_{1}),y_{2}),\dots ,y_{m-1}),y_{m})}$. The result, does not depend on the order of elements ${\displaystyle y_{1},y_{2},...,y_{n}}$because ${\displaystyle h}$ is quasi-commutative.[1][2]

If ${\displaystyle y_{1},y_{2},...,y_{n}}$ belong to some users of a cryptosystem, then everyone can compute the accumulated value ${\displaystyle z.}$ Also, the user of ${\displaystyle y_{i}}$ can compute the partial accumulated value ${\displaystyle z_{i}}$ of ${\displaystyle (y_{1},...,y_{i-1},y_{i+1},...,y_{n})}$. Then, ${\displaystyle h(z_{i},y_{i})=z.}$ So the ${\displaystyle i-}$user can provide the pair ${\displaystyle (z_{i},y_{i})}$ to any other part, in order to authenticate ${\displaystyle y_{i}}$.

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]

1. Gen: a probabilistic algorithm that takes in two parameters ${\displaystyle \lambda ,N}$ (the security parameter and the number of values that can be securely accumulated, respectively), and returns an appropriate key ${\displaystyle k}$.
2. Eval: a probabilistic algorithm that takes in a key ${\displaystyle k}$ and accumulation set ${\displaystyle Y:=\{y_{1},\dots ,y_{N'}\}}$, where ${\displaystyle N'\leq N}$, and returning an accumulated value ${\displaystyle z}$ and auxiliary information ${\displaystyle aux}$. We insist that Eval must be deterministic for ${\displaystyle z}$.
3. Wit: a probabilistic algorithm that takes in a key ${\displaystyle k}$, a value ${\displaystyle y}$, an accumulated value ${\displaystyle z}$ of some set ${\displaystyle Y}$, and some auxiliary information ${\displaystyle aux}$, and returns either a witness ${\displaystyle w}$ or the special symbol ${\displaystyle \bot }$. We insist that, if ${\displaystyle y\in L}$, that Wit returns a witness, and that Wit otherwise returns ${\displaystyle \bot }$.
4. Ver: a deterministic algorithm that takes in a key ${\displaystyle k}$, a value ${\displaystyle y}$, a witness ${\displaystyle w}$, and an accumulated value ${\displaystyle z}$, and returns a Yes/No value. We insist that if ${\displaystyle w}$ was generated from running Wit on a tuple ${\displaystyle (k,y,z,aux)}$, where ${\displaystyle z,aux}$ were generated from running Eval on some ${\displaystyle k,L}$, and where ${\displaystyle L}$ was chosen arbitrarily and ${\displaystyle k}$ 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.[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]

1. Add: a (possibly probabilistic) algorithm that takes in a key ${\displaystyle k}$, an accumulated value ${\displaystyle z}$, and another value to accumulate ${\displaystyle y}$, and returns a new accumulated value ${\displaystyle z'}$ and auxiliary information ${\displaystyle aux}$. We insist that if ${\displaystyle z}$ was generated by accumulating some set ${\displaystyle L}$, then ${\displaystyle z'}$ must be as if it were generated by accumulating the set ${\displaystyle L\cup \{y\}}$.
2. Del: a (possibly probabilistic) algorithm that takes in a key ${\displaystyle k}$, an accumulated value ${\displaystyle z}$, and another value to accumulate ${\displaystyle y}$, and returns a new accumulated value ${\displaystyle z'}$ and auxiliary information ${\displaystyle aux}$. We insist that if ${\displaystyle z}$ was generated by accumulating some set ${\displaystyle L}$, then ${\displaystyle z'}$ must be as if it were generated by accumulating the set ${\displaystyle L\backslash \{y\}}$.
3. Upd: a deterministic algorithm that takes in the key ${\displaystyle k}$, a value ${\displaystyle y}$, a witness ${\displaystyle w}$, the accumulated value ${\displaystyle z}$, and auxiliary information ${\displaystyle aux}$, and returns a new witness ${\displaystyle w'}$. We insist that if ${\displaystyle k}$ was generated by Gen, ${\displaystyle y}$ is part of a set ${\displaystyle L}$, ${\displaystyle w}$ is a witness for ${\displaystyle y}$ being a member of ${\displaystyle L}$, and ${\displaystyle z}$ is an accumulated value for ${\displaystyle L}$, and ${\displaystyle aux}$ was generated by running Add or Del, then ${\displaystyle w'}$ will be a witness for ${\displaystyle y}$ 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.[2]