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 eraserbraid groupcolored Burau presentationconjugacy problemconjugacy separationkey agreementcryptography
Contact author(s)
menshov a v @ gmail com
History
2018-05-23: received
Short URL
https://ia.cr/2018/491
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.