Conjugacy Separation Problem in Braids: an Attack on the Original Colored Burau Key Agreement Protocol
In this paper, we consider the conjugacy separation search problem in braid groups. We deeply redesign the algorithm presented in [18] and provide an experimental evidence that the problem can be solved for 100% of very long randomly generated instances. The lengths of tested randomly generated instances is increased by the factor of two compared to the lengths suggested in the original proposal for 120 bits of security. An implementation of our attack is freely available in CRAG, [6]. In particular, the implementation contains all challenging instances we had to deal with on a way to 100% success. We hope it will be useful to braid-group cryptography community.