International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jung Hee Cheon
Byungheup Jun
Download:
URL: http://eprint.iacr.org/2003/019
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2003-11737,
  title={A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / cryptanalysis},
  url={http://eprint.iacr.org/2003/019},
  note={ jhcheon@icu.ac.kr 12150 received 28 Jan 2003, last revised 8 Apr 2003},
  author={Jung Hee Cheon and Byungheup Jun},
  year=2003
}