**Efficient Revocation of Anonymous Group Membership**

*Jan Camenisch and Anna Lysyanskaya*

**Abstract: **An accumulator scheme, introduced be Benaloh and de Mare
and further studied by Barić and Pfitzmann, is an algorithm that
allows to hash a large set of inputs into one short value, called the
\textit{accumulator}, such that there is a short witness that a given
input was incorporated into the accumulator.

We put forward the notion of \textit{dynamic accumulators}, i.e., a method that allows to dynamically add and delete inputs from the accumulator, such that the cost of an add or delete is independent on 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.

In turn, our construction of dynamic accumulator enables efficient membership revocation in the anonymous setting. This method applies to membership revocation in group signature schemes, such as the one due to Ateniese et al., and efficient revocation of credentials in anonymous credential systems, such as the one due to Camenisch and Lysyanskaya. Using our method, allowing revocation does not alter the complexity of any operations of the underlying schemes. In particular, the cost of a group signature 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 and Ateniese and Tsudik incurred an increase in these costs that was linear in the number of members.

**Category / Keywords: **public-key cryptography / digital signature, revocation, anonymity

**Date: **received 24 Dec 2001

**Contact author: **jca at zurich ibm com

**Available format(s): **PDF | BibTeX Citation

**Version: **20011228:164925 (All versions of this report)

**Short URL: **ia.cr/2001/113

[ Cryptology ePrint archive ]