Paper 2012/424

Scalable Group Signatures with Revocation

Benoit Libert, Thomas Peters, and Moti Yung


Group signatures are a central cryptographic primitive, simultaneously supporting accountability and anonymity. They allow users to anonymously sign messages on behalf of a group they are members of. The recent years saw the appearance of several constructions with security proofs in the standard model ({\it i.e.}, without appealing to the random oracle heuristic). For a digital signature scheme to be adopted, an efficient revocation scheme (as in regular PKI) is absolutely necessary. Despite over a decade of extensive research, membership revocation remains a non-trivial problem in group signatures: all existing solutions are not truly scalable due to either high overhead (e.g., large group public key size), or limiting operational requirement (the need for all users to follow the system's entire history). In the standard model, the situation is even worse as many existing solutions are not readily adaptable. To fill this gap and tackle this challenge, we describe a new revocation approach based, perhaps somewhat unexpectedly, on the Naor-Naor-Lotspiech framework which was introduced for a different problem (namely, that of broadcast encryption). Our mechanism yields efficient and scalable revocable group signatures in the standard model. In particular, the size of signatures and the verification cost are independent of the number of revocations and the maximal cardinality $N$ of the group while other complexities are at most polylogarithmic in $N$. Moreover, the schemes are history-independent: unrevoked group members do not have to update their keys when a revocation occurs.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Eurocrypt 2012 - This is the full version
Group signaturesrevocationstandard modelefficiency
Contact author(s)
benoit libert @ uclouvain be
2012-08-07: revised
2012-08-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benoit Libert and Thomas Peters and Moti Yung},
      title = {Scalable Group Signatures with Revocation},
      howpublished = {Cryptology ePrint Archive, Paper 2012/424},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.