Disadvantages of one-way accumulators?

Question

One-way accumulators are built upon a (quasi)-commutative one-way function. With quasi-commutativity, I refer to the following property:

For $f : X \times Y \to X$, it is true that $f(f(x, y_1), y_2) = f(f(x, y_2), y_1)$.

Although accumulators seem like a very useful cryptographic building block, I don't see them often in practical applications (in fact I can only think of Zerocoin). I suspect that this is because the scheme has certain disadvantages.

I wonder what these disadvantages are (if this is indeed the reason): is the function $f$ weak in terms of eg. collision-resistance, is it not efficient enough...?

---

The accumulators that I know of (note: I don't really know a lot about them, so this doesn't say much), seem to be based on number-theory (unlike conventional hash functions). This makes them a lot slower.

For example, Wikipedia describes the following function:

One trivial example is how large composite numbers accumulate their prime factors, as it's currently impractical to factor the composite number, but relatively easy to find a product and therefore check if a specific prime is one of the factors. New members may be added or subtracted to the set of factors simply by multiplying or factoring out the number respectively. 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.

As they mention, this is clearly not practical because of the size of the output values.

Another example I have seen is $f(x, y) = x^y \pmod n$ where $n = pq$ (with $p$ and $q$ both safe primes). Even though this doesn't have the problem of the Wikipedia example, it is still not very efficient (even though you can do the exponentiations using the square-and-multiply method).

Answer 1

An advantage of a cryptographic accumulator and actually the reason to use them is that due to the quasi commutativity you can compute witnesses for membership of values in the accumulator where the accumulator and the witnesses are of constant size.

Say you have a set $Y=\{y_1,y_2,y_3\}$ and compute the accumulator as $acc=f(f(f(x,y_1),y_2),y_3)$ you want to compute a witness for a value say $y_2$, then by quasi commutativity, the value for your witness is $wit_{y_2} = f(f(x,y_1),y_3)$ and you can check given $y_2$ and $wit_{y_2}$ whether $y_2$ is in the accumulator $acc$, you can check whether $acc=f(wit_{y_2},y_3)$ holds.

Furthermore, existing accumulator schemes (CL02, C+09, N05) come with zero-knowledge proofs of accumulator membership (you do not have to reveal the value $y_2$ and the witness $wit_{y_2}$ directly, but you provide a zero-knowledge proof of knowledge of such a pair - which makes them attractive for privacy-preserving applications). Such accumulators are typically also dynamic, i.e., allow update of witnesses in the public if the accumulator is updated. Furthermore, there are also so called universal accumulators, which also allow to produce witnesses for non-membership of a value in the accumulated set (see A+09 or L+07).

All known efficient accumulators are based on number theoretic assumption, but I would not say that they are inefficient. Note that in your last RSA example, the membership check requires one exponentiation, which is not really very expensive.

is the function f weak in terms of eg. collision-resistance, is it not efficient enough...?

For a secure accumulator one requires collssion-freeness, i.e., it is computationally infeasible to find a witness for some value that is not accumulated in the accumulator. For RSA accumulators that requires that you only accumulate primes (so you have to map your values to accumulate to primes with some deterministic algorithm). Otherwise, you could factor your value into two factors and exponentiate one onto your witness and provide the second as value to be checked and the check would work. This is ruled out if you take primes. There are however, other secure pairing based accumulators that do not suffer from this problem.

Accumulators are used for various purposes, such as timestamping (the original application), membership testing, distributed signatures, redactable and sanitizable signatures as well as for revocation in group signatures and anonymous credential systems.

There are constructions for accumulators based on bloom filters (see Nyberg, Fast accumulated hasing, FSE 1996), but they are rather impractical (but do not rely on number theoretic assumptions).