An accumulator scheme, as introduced by Benaloh and de Mare [BdM94] and further studied by Barić 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.
Camenisch and Lysyanskaya presented an efficient zero-knowledge protocol which proves that a value contained in a Pedersen commitment is also contained in a particular strong-RSA accumulator REF .
Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials
CRYPTO
Computer Science