## Cryptology ePrint Archive: Report 2018/491

Conjugacy Separation Problem in Braids: an Attack on the Original Colored Burau Key Agreement Protocol

Matvei Kotov and Anton Menshov and Alexey Myasnikov and Dmitry Panteleev and Alexander Ushakov

Abstract: In this paper, we consider the conjugacy separation search problem in braid groups. We deeply redesign the algorithm presented in (Myasnikov & Ushakov, 2009) 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. 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.

Category / Keywords: public-key cryptography / Algebraic eraser, braid group, colored Burau presentation, conjugacy problem, conjugacy separation, key agreement, cryptography