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

Date: received 22 May 2018

Contact author: menshov a v at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180523:030630 (All versions of this report)

Short URL: ia.cr/2018/491