Cryptographic accumulator

A cryptographic accumulator compresses a finite set into a short value together with, for each , a short witness that was accumulated, such that no efficient adversary can produce a valid witness for an element outside the set — BP97.

Syntax

An accumulator over a domain is a tuple of efficient algorithms :

  • , a randomized algorithm outputting public parameters,
  • , a deterministic algorithm accumulating a finite set ,
  • , a deterministic algorithm outputting a witness for ,
  • , a deterministic algorithm that checks a witness.

The accumulator value and witnesses have length , independent of or growing at most polylogarithmically with it. The domain has superpolynomially many elements: . For a polynomial-size , the characteristic vector of as , with empty witnesses, meets this length bound and the properties below unconditionally — standard.

Properties

Correctness

An accumulator is perfectly correct if for all , all finite of polynomial size and all ,

over .

Collision-freeness

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{acc}}_{\mathsf{ACC},\calA}(\secpar)$}
\begin{algorithmic}
\State $\pp \gets \Gen(1^\secpar)$
\State $(X, x, w) \gets \calA(\pp)$
\Return $[X \subseteq \calD \wedge x \in \calD \setminus X \wedge \Vrfy(\pp, \Acc(\pp, X), x, w) = 1]$
\end{algorithmic}
\end{algorithm}

An accumulator is collision-free if for all efficient ,

is negligible — BP97.

Variations

Dynamic accumulators

A dynamic accumulator has , where is a trapdoor (the factorization of for the RSA accumulator), and adds algorithms that add an element to, or delete one from, the accumulated set, updating at a cost independent of , and that update a witness after each change without — CL02. Witness updates make dynamic accumulators a revocation mechanism for anonymous credentials: a user proves in zero knowledge that its credential’s identifier is accumulated in the current value — CL02.

TODO: the security game of CL02 for dynamic accumulators, stated from the paper: which add and delete operations of the manager, who holds , the adversary invokes and what update information each returns, the winning condition (a valid witness for an element outside the current set), and the consistency requirement that after any sequence of updates for the current set . Register the notion as a variant once the game is encoded.

Other results

  • RSA accumulator: for an RSA modulus and , elements are primes, , and the witness for is , checked by . It is collision-free under the strong RSA assumption (Strong RSA ⇒ accumulator) — BP97. BdM93 introduced the exponentiation accumulator as a quasi-commutative one-way function.
  • A Merkle tree over the sorted set, with the tree depth included in (or leaf and internal-node hashes under distinct prefixes) and padding leaves repeating an element of , is a collision-free accumulator with witnesses of hash values if the hash is collision-resistant (CRHF ⇒ accumulator) — folklore.
  • The RSA accumulator is dynamic: additions and witness updates need no trapdoor, deletions use the factorization, and collision-freeness still rests on strong RSA for safe-prime moduli (Strong RSA (safe-prime moduli) ⇒ dynamic accumulator) — CL02.
  • In bilinear groups, for a secret , with public parameters , accumulates sets of at most elements and is collision-free under the -SDH assumption — Ngu05.

Participates in

Produces Cryptographic accumulator