Is there a cumulative commitment scheme?

Question

For a certain application I need a commitment scheme where each user could make a commitment, and a single verification operation could verify all the commitments simultaneously, faster than single verifications. It's like a batch verification of signatures but we are able to build each commitment based on the previous one (that's not the usual case for batch verification of signatures)

Formally:
Each user i, makes a commitment $C(i)$ to a value $x(i)$, as $C(i):=Commit(C(i-1),x(i),open(i))$, with $open(i)$ the randomness used for computing the commitment, or nothing if the scheme is deterministic. $C(0)$ is an initial value.

Then $CheckReveal(C(n),x(1) .. x(n),open(1) .. open(n))\ $ verifies the commitment equations very fast (e.g. $O(\log(n))$ modexps or $O(1)$ modexps).

Obviously the simple scheme $C(i)=C(i-1)^{x(i)} \mod p\ $ does not work, because two parties $i$ and $j$ (in collusion) can now change their commitments setting $x'(i) = x(i) · k$ and $x'(j) = x(j) · \frac{1}{k}$.

Answer 1

It sounds like you are thinking about this the wrong way. Verifying a commitment is very fast, if you choose the commitment scheme properly.

In particular, I recommend that you use a hash-function-based commitment scheme: C(i) = Hash(x(i) || open(i)). Then verifying an opened commitment requires just one hash evaluation, which is very fast. Based on my measurements with openssl speed sha1, you should be able to verify several million commitments per second, if you use a SHA1-based commitment.

The question talks about modexps. That suggests that you are considering the wrong kind of commitment scheme. Modexps are much slower than hash evaluations. If you are choosing a modexp-based commitment scheme, you are going to end up with something significantly slower than the best possible. Rather than trying to make up for the suboptimal choice of commitment scheme by looking for fancy batching tricks, I recommend you simply move straight to a fast commitment scheme (based on a cryptographic hash), and then you won't need anything fancy. My guess is that straightforward use of a hash-based commitment is going to be faster than any modexp-based commitment scheme, even with batching.

Answer 2

One approach that may work is the following. You can represent the accumulated values as a polynomial, where the roots are equal to the messages:

1. User $1$ creates a representation of $P_1(x)=(x-C(1))$
2. User $i$ creates a representation of $P_i(x)=(x-C(i))P_{i-1}$

A commitment scheme with properties very close to what you want is PolyCommit. It allows any size of a polynomial to be accumulated into a single representation and allows batch evaluations (i.e., batch opening of messages committed to).

The challenge is adapting the construction, which is designed for a single party to create a commitment, into allowing different parties to add in their contributions to the underlying polynomial (and performing a distributed opening of the commitment).

I haven't considered it beyond this preliminary sketch and so this isn't an answer, just "brainstorming."