International Association
for Cryptologic Research

Group signatures are an important privacy-enhancing tool which allow members of a group to anonymously produce signatures on behalf of the group. Ideally, group signatures are dynamic and thus allow to dynamically enroll new members to a group. For such schemes Bellare et al. (CT-RSA'05) proposed a strong security model (BSZ model) that preserves anonymity of a group signature even if an adversary can see arbitrary key exposures or arbitrary openings of other group signatures. All previous constructions achieving this strong security notion follow the so called sign-encrypt-prove (SEP) paradigm. In contrast, all known constructions which avoid this paradigm and follow the alternative "without encryption" paradigm introduced by Bichsel et al. (SCN'10), only provide a weaker notion of anonymity (which can be problematic in practice). Until now, it was not clear if constructions following this paradigm, while also being secure in the strong BSZ model, even exist. In this paper we positively answer this question by providing a novel approach to dynamic group signature schemes following this paradigm, which is a composition of structure preserving signatures on equivalence classes (Asiacrypt'14) and other standard primitives. Our results are interesting for various reasons: We can prove our construction following this "without encryption" paradigm secure in the strong BSZ model without requiring random oracles. Moreover, when opting for an instantiation in the ROM, the so obtained scheme is extremely efficient. It outperforms existing constructions following the SEP paradigm and being secure in the BSZ model regarding computational efficiency by some orders of magnitude and even yields shorter signatures. Regarding constructions providing a weaker anonymity notion than BSZ, we surprisingly outperform the popular short BBS group signature scheme (Crypto'04) and even obtain shorter signatures.