Paper 2004/104

Efficient and Provably Secure Trapdoor-free Group Signature Schemes from Bilinear Pairings

Lan Nguyen and Rei Safavi-Naini


Group signature schemes are cryptographic systems that provide revocable anonymity for signers. We propose a group signature scheme with constant-size public key and signature length that does not require trapdoor. So system parameters can be shared by multiple groups belonging to different organizations. The scheme is provably secure in the formal model recently proposed by Bellare, Shi and Zhang (BSZ04), using random oracle model, Decisional Bilinear Diffie-Hellman and Strong Diffie-Hellman assumptions. We give a more efficient variant scheme and prove its security in a formal model which is a modification of BSZ04 model and has a weaker anonymity requirement. Both schemes are very efficient and the sizes of signatures are approximately one half and one third, respectively, of the sizes of the well-known ACJT00 scheme. We will show that the schemes can be used to construct a traceable signature scheme and identity escrow schemes. They can also be extended to provide membership revocation.

Note: This full version provides new signing and verifying algorithms that are secure against the attack in Eprint 2005/122 "Breaking and Repairing Trapdoor-free Group Signature Schemes from Asiacrypt 2004". The new algorithms are more efficient than the improvement proposed in Eprint 2005/122.

Available format(s)
Publication info
Published elsewhere. An extended abstract appears in ASIACRYPT 2004
Group signaturestraceable signaturesidentity escrowidentity escrowprivacy and anonymity.
Contact author(s)
ldn01 @ uow edu au
2005-05-01: last of 3 revisions
2004-05-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lan Nguyen and Rei Safavi-Naini},
      title = {Efficient and Provably Secure Trapdoor-free Group Signature Schemes from Bilinear Pairings},
      howpublished = {Cryptology ePrint Archive, Paper 2004/104},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.