A polynomial time algorithm for the braid Diffie-Hellman conjugacy problem. (English) Zbl 1122.94364
Boneh, Dan (ed.), Advances in cryptology – CRYPTO 2003. 23rd annual international cryptology conference, Santa Barbara, California, USA, August 17–21, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40674-3/pbk). Lect. Notes Comput. Sci. 2729, 212-225 (2003).
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].
For the entire collection see [Zbl 1027.00041].
MSC:
94A60 | Cryptography |
20F36 | Braid groups; Artin groups |
68P25 | Data encryption (aspects in computer science) |
68Q25 | Analysis of algorithms and problem complexity |