Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions

Authors: M. Bellare, D. Micciancio and B. Warinschi

Abstract: This paper provides theoretical foundations for the group signature primitive. We introduce strong, formal definitions for the core requirements of anonymity and traceability. We then show that these imply the large set of sometimes ambiguous existing informal requirements in the literature, thereby unifying and simplifying the requirements for this primitive. Finally we prove the existence of a construct meeting our definitions based only on the assumption that trapdoor permutations exist.

Ref: An extended abstract of this paper appeared in Advances in Cryptology - Eurocrypt 2003 Proceedings, Lecture Notes in Computer Science Vol. 2656, E. Biham ed, Springer-Verlag, 2003. Full paper available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).

Related work and links: This paper considers the case where the group is static. A treatment for the case of dynamic groups is provided by Bellare, Shi and Zhang.