Welcome to the resource topic for 2003/019
Title:
A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem
Authors: Jung Hee Cheon, 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.
ePrint: https://eprint.iacr.org/2003/019
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .