[Resource Topic] 2001/113: Efficient Revocation of Anonymous Group Membership

Welcome to the resource topic for 2001/113

Efficient Revocation of Anonymous Group Membership

Authors: Jan Camenisch, Anna Lysyanskaya


An accumulator scheme, introduced be Benaloh and de Mare
and further studied by Baric̈ 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.

ePrint: https://eprint.iacr.org/2001/113

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .