Cryptology ePrint Archive: Report 2016/154

Fully-Anonymous Short Dynamic Group Signatures Without Encryption

David Derler and Daniel Slamanig

Abstract: 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 and concurrently 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.

We answer this question to the affirmative by proposing 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 the fastest constructions providing anonymity in the BSZ model known to date. Regarding constructions providing a weaker anonymity notion than BSZ, we surprisingly outperform the popular short BBS group signature scheme (Crypto'04) and thereby even obtain shorter signatures.

Category / Keywords: public-key cryptography / group signatures, BSZ model, CCA2-full anonymity, efficiency

Date: received 17 Feb 2016, last revised 3 Feb 2017

Contact author: david derler at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Version: 20170203:084855 (All versions of this report)

Short URL: ia.cr/2016/154

Discussion forum: Show discussion | Start new discussion