**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.

**Category / Keywords: **public-key cryptography / cryptanalysis

**Date: **received 28 Jan 2003, last revised 8 Apr 2003

**Contact author: **jhcheon at icu ac kr

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

**Version: **20030408:080857 (All versions of this report)

**Short URL: **ia.cr/2003/019

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]