Breaking and Repairing Trapdoor-free Group Signature

Group signature schemes allow a member of a group to sign messages anonymously on behalf

of the group. In case of later dispute, a designated group manager can revoke the anonymity and identify

the originator of a signature. In Asiacrypt 2004, Nguyen and Safavi-Naini proposed a group signature

scheme that has a constant-size public key and signature length, and more importantly, their group

signature scheme does not require trapdoor. Their scheme is very eñcient and the sizes of signatures are

shorter compared to the existing schemes that were proposed earlier. In this paper, we point out that

Nguyen and Safavi-Naini's scheme is insecure. In particular, we provide a cryptanalysis of the scheme

that allows a non-member of the group to sign on behalf of the group. The resulting group signature can

convince any third party that a member of the group has indeed generated such a signature, although

none of the members has done it. Therefore, in case of dispute, the group manager cannot identify who

has signed the message. We also provide a new scheme that does not suîer from this problem.