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
[ Cryptology ePrint archive ]