Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials

AbstractAn accumulator scheme, as introduced by Benaloh and de Mare [BdM94] and further studied by Baric and Pfitzmann [BP97], is an algorithm that allows one to hash a large set of inputs into one short value, called the accumulator, such that there is a (short) witness that a given input was incorporated into the accumulator. At the same time, it is infeasible to find a witness for a value that was not accumulated. We put forward the notion of a dynamic accumulator, which is an accumulator that allows one to dynamically add and delete inputs, such that the cost of an add or delete is independent of the number of accumulated values. We achieve this under the strong RSA assumption. For this construction, we also show an efficient zero-knowledge protocol for proving that a committed value is in the accumulator. Dynamic accumulators enable efficient membership revocation in the anonymous setting. Our construction is especially suitable for membership revocation in group signature and identity escrow schemes, such as the one due to Ateniese et al. [ACJT00], and efficient revocation of credentials in anonymous credential systems, such as the one due to Camenisch and Lysyanskaya [CL01a]. Applying our method to these schemes enables membership revocation and yet does not significantly increase the complexity of any of the operations. In particular, the cost of a membership verification or credential showing increases by only a small constant factor, less than 2. All previously known methods (such as the ones due to Bresson and Stern [BS01] and Ateniese and Tsudik [AT01]) incur an increase in these costs that is linear in the number of members.
Year2002
Link to the paperhttps://cs.brown.edu/people/alysyans/papers/camlys02.pdf
Relevance scoreMaybe relevant
Quality score4
LabelsAnonymous CredentialsClassic reference

One of the papers by Camenisch and Lysyanskaya. A general overview of their work is provided in the following entry:

Work of Camenisch and Lysyanskaya on Anonymous Credentials

The present paper builds upon the Anonymous Credential functionality presented in the aforementioned note by designing an efficient credential revocation mechanism. This mechanism is implemented by means of the two primitives below. (Recall that, in its simplest version, an accumulator is a cryptographic primitive that allows demonstrating that some value belongs to an existing set SS of values, which we call set of accumulated elements).