New Signature Scheme over the Braid Groups

The braid group is a new candidate platform for constructing quantum attack-resistant cryptographic protocols. A new signature scheme is proposed based on the difficulty of the root extraction problem over braid groups, which can resist existential forgery against the adaptively chosen-message attack under the random oracle model. Compared with the Conjugacy Signature Scheme (CSS) and the Enhanced Conjugacy Signature Scheme (ECSS), the verification phase of the proposed scheme desires less computation because it does not have to determine whether two braids are conjugate. The signature is composed of an integer and a braid, which is much shorter than that of CSS and almost same as that of ECSS.