Fully-Anonymous Short Dynamic Group Signatures Without Encryption.
David Derler, Daniel Slamanig · IACR Cryptology ePrint Archive · 2016
Group signatures are a central tool in privacy-enhancing crypto, which allow members of a group to anonymously sign 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 anonymity 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 providing strong anonymity in the sense of BSZ, 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 without requiring random oracles. Moreover, when opting for an instantiation in the ROM, the so obtained scheme is extremely efficient and outperforms existing fully anonymous constructions following the SEP paradigm regarding computational efficiency. Regarding constructions providing a weaker anonymity notion than BSZ, we surprisingly even outperform the popular short BBS group signature scheme (Crypto’04) and thereby obtain shorter signatures.