Paper 2004/076

Group Signatures: Provable Security, Efficient Constructions and Anonymity from Trapdoor-Holders

Aggelos Kiayias and Moti Yung


To date, a group signature construction which is efficient, scalable, allows dynamic adversarial joins, and proven secure in a formal model has not been suggested. In this work we give the first such construction in the random oracle model. The demonstration of an efficient construction proven secure in a formal model that captures all intuitive security properties of a certain primitive is a basic goal in cryptographic design. To this end we adapt a formal model for group signatures capturing all the basic requirements that have been identified as desirable in the area and we construct an efficient scheme and prove its security. Our construction is based on the Strong-RSA assumption (as in the work of Ateniese et al.). In our system, due to the requirements of provable security in a formal model, we give novel constructions as well as innovative extensions of the underlying mathematical requirements and properties. Our task, in fact, requires the investigation of some basic number-theoretic techniques for arguing security over the group of quadratic residues modulo a composite when its factorization is known. Along the way we discover that in the basic construction, anonymity does not depend on factoring-based assumptions, which, in turn, allows the natural separation of user join management and anonymity revocation authorities. Anonymity can, in turn, be shown even against an adversary controlling the join manager.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. see also : Secure scalable group signature with dynamic joins and separable authorities, International Journal of Security and Networks 2006 - Vol. 1, No.1/2 pp. 24—45.
group signatures
Contact author(s)
aggelos @ cse uconn edu
2007-06-30: last of 3 revisions
2004-03-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aggelos Kiayias and Moti Yung},
      title = {Group Signatures: Provable Security, Efficient Constructions and Anonymity from Trapdoor-Holders},
      howpublished = {Cryptology ePrint Archive, Paper 2004/076},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.