Group Signatures with
Almost-for-free Revocation
Benoit Libert (UCL,
Thomas
Peters (UCL,
Moti Yung (Google
Inc. and
Abstract:
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 (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 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 (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.