Paper 2018/491 Original: eprint.iacr.org/2018/491 ↗
Conjugacy Separation Problem in Braids: an Attack on the Original Colored Burau Key Agreement Protocol
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.
- History
- 2018-05-23: last updated
- 2018-05-23: published
- Short URL
- https://ia.cr/2018/491
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2018/491}
}