Summary: 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 K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J.-S. Kang and C. Park [ Lect. Notes Comput. Sci. 1880, 166–183 (2000; Zbl 0995.94531)]. 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 \(O(n^{14}\ell^{3.2})\) or \(O(n^{4\tau+2\epsilon}\ell^{2\epsilon})\) bit operations for \(\tau=\log_2\;7\approx2.8\) and \(\epsilon>\log_2 3\approx 1.57\).
For the entire collection see [Zbl 1027.00041].