International Association
for Cryptologic Research

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.