Paper 2003/019

A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem

Jung Hee Cheon and Byungheup Jun

Abstract

We propose the first polynomial time algorithm for the braid Diffie-Hellman conjugacy problem (DHCP) on which the braid key exchange scheme and the braid encryption scheme are based~\cite{KLCHKP01}. We show the proposed method solves the DHCP for the image of braids under the Lawrence-Krammer representation and the solutions play the equivalent role of the original key for the DHCP of braids. Given a braid index $n$ and a canonical length $\ell$, the complexity is about $2^{-2}\ell^3 n^{4\tau+2}\log n$ bit operations, where $\tau=\log_27\approx 2.8$ (Theoretically, it can be reduced to $O(\ell^3 n^{8.3}\log n)$ using $\tau=2.376$). Further, we show that the generalization into the decomposition problem causes only 8 times of the complexity.

Note: We improved the complexity of the algorithm and generalized to the decomposition problem.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
cryptanalysis
Contact author(s)
jhcheon @ icu ac kr
History
2003-04-08: last of 2 revisions
2003-01-30: received
See all versions
Short URL
https://ia.cr/2003/019
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/019,
      author = {Jung Hee Cheon and Byungheup Jun},
      title = {A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2003/019},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/019}},
      url = {https://eprint.iacr.org/2003/019}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.