Since the paper of Camenisch and Stadler [7], the same
method has always been used to set a group signature scheme up. It
is based on a difficult problem implying two or more values. Alice
is a member of the group if and only if she knows a solution of
this difficult problem.
If Alice wants to become a group member, she interacts with GM
(who holds a secret key) in order to obtain in a blind manner her
private key and her membership certificate. This latter value
allows GM to establish the link between a signature and a group
member.
During the signature protocol, Alice encrypts her membership
certificate, then ``proves'' that she knows a solution of the
difficult problem and that she has correctly encrypted her
certificate. As a consequence, this protocol involves numerous
modular exponentiations. Someone who wants to verify the signature
only has to verify the whole proof, also known as a signature of
knowledge. The group manager can open the signature by decrypting
Alice's certificate.
Coalition-resistance has often be defeated ([7]) and was
an unsolved problem until [1] and [6]. In these
two articles, the authors propose new group signature schemes
based on the strong RSA assumption ([3] and [9])
and prove that they are resistant to coalitions.