Breaking and Repairing Trapdoor-Free Group Signature Schemes from Asiacrypt 2004

Group signature schemes allow a member of a group to sign messagesanonymously on behalf of the group. In case of later dispute, adesignated group manager can revoke the anonymity and identify theoriginator of a signature. In Asiacrypt2004, Nguyen andSafavi-Naini proposed a group signature scheme that has aconstant-sized public key and signature length, and more importantly,their group signature scheme does \em not require trapdoor.Their scheme is very efficient and the sizes of signatures aresmaller than those of the other existing schemes.In this paper, we point out that Nguyen and Safavi-Naini's scheme isinsecure. In particular, it is shown in our cryptanalysis of the schemethat it allows a non-member of the group to sign on behalf of thegroup. And the resulting signature convinces any third partythat a member of the group has indeed generated such a signature,although none of the members has done so. Therefore is in case ofdispute, even the group manager cannot identify who has signed themessage. In the paper a new scheme that does not suffer from thisproblem is provided.