International Association
for Cryptologic Research

Group signatures are a central cryptographic primitive where users

can anonymously and accountably sign messages in the name of a group

they belong to. Several efficient constructions with security proofs

in the standard model ({\\it i.e.}, without the random oracle idealization) appeared in the recent years. However, like standard PKIs, group signatures need an efficient revocation system to be practical.

Despite years of research, membership revocation remains a non-trivial problem: many existing solutions do not scale well due to

either high overhead or constraining operational requirements (like

the need for all users to update their keys after each revocation). Only recently, Libert, Peters and Yung (Eurocrypt\'12) suggested a new

scalable revocation method, based on the Naor-Naor-Lotspiech (NNL)

broadcast encryption framework, that interacts nicely with techniques

for building group signatures in the standard model. While promising, their mechanism introduces important storage requirements at group members. Namely, membership certificates, which used to have constant size in existing standard model constructions, now have polylog size in the maximal cardinality of the group (NNL, after all, is a tree-based technique and such dependency is naturally expected).

In this paper we show how to obtain private keys of {\\it constant}

size. To this end, we introduce a new technique to leverage the NNL

subset cover framework in the context of group signatures but,

perhaps surprisingly, without logarithmic relationship between the

size of private keys and the group cardinality. Namely, we provide a

way for users to efficiently prove their membership of one of the

generic subsets in the NNL subset cover framework. This technique

makes our revocable group signatures competitive with ordinary group

signatures ({\\it i.e.}, without revocation) in the standard model. Moreover, unrevoked members (as in PKIs) still do not need to update their keys at each revocation.