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.
Category / Keywords: public-key cryptography / Group signatures, revocation, standard model, efficiency, short private keys Publication Info: Crypto 2012 -- This is the full version Date: received 2 Aug 2012, last revised 7 Aug 2012 Contact author: benoit libert at uclouvain be Available format(s): PDF | BibTeX Citation Version: 20120807:144612 (All versions of this report) Short URL: ia.cr/2012/442 Discussion forum: Show discussion | Start new discussion