## Cryptology ePrint Archive: Report 2001/113

**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{\'c} 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)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]