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

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

Paper 2018/491

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

Matvei Kotov, Anton Menshov, Alexey Myasnikov, 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Algebraic eraser braid group colored Burau presentation conjugacy problem conjugacy separation key agreement cryptography
Contact author(s): menshov a v @ gmail com
History: 2018-05-23: received
Short URL: https://ia.cr/2018/491
License: CC BY

BibTeX

@misc{cryptoeprint:2018/491,
      author = {Matvei Kotov and Anton Menshov and Alexey Myasnikov and Dmitry Panteleev and Alexander Ushakov},
      title = {Conjugacy Separation Problem in Braids: an Attack on the Original Colored Burau Key Agreement Protocol},
      howpublished = {Cryptology ePrint Archive, Paper 2018/491},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/491}},
      url = {https://eprint.iacr.org/2018/491}
}