Abstract: The rapid development of quantum computing makes public key cryptosystcms based on noncommutativc al gebraic systems hot topic. Because of the non-commutativity property, the braid groups with braid index more than two become a new candidate for constructing cryptographic protocols. I}he security vulnerabilities of a group signature scheme based on the braid groups were pointed out that it does not satisfy the unlinkability, which means the signatures generated by the same group member can be linked, and the publication of several signatures will induce information leakage of the private key of the group. An improved scheme was proposed using random factor, which not only ensures the unlinkability of the scheme but also protects the group' s private key. Security analysis shows that the improved scheme satisfies the security requirements of group signature.

Key words: Braid group, Group signature, Conjugacy search, Multiple conjugacy search