Cryptology ePrint Archive: Report 2012/424

Scalable Group Signatures with Revocation

Benoit Libert and Thomas Peters and Moti Yung

Abstract: 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.

Category / Keywords: public-key cryptography / Group signatures, revocation, standard model, efficiency

Publication Info: Eurocrypt 2012 - This is the full version

Date: received 27 Jul 2012, last revised 7 Aug 2012

Contact author: benoit libert at uclouvain be

Available formats: PDF | BibTeX Citation

Version: 20120807:144213 (All versions of this report)

Discussion forum: Show discussion | Start new discussion