×

Computation of centralizers in braid groups and Garside groups. (English) Zbl 1064.20040

The authors give a new method to compute the centralizer of an element in Artin braid groups and, more generally, in Garside groups. This method, together with the solution of the conjugacy problem given previously by the authors, are two main steps for solving conjugacy systems, thus breaking recently discovered cryptosystems based in braid groups. They also present the result of their computations, where they notice that their algorithm yields surprisingly small generating sets for the centralizers.

MSC:

20F36 Braid groups; Artin groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
94A60 Cryptography
20F05 Generators, relations, and presentations of groups
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI arXiv EuDML

References:

[1] Artin, E.: Theory of braids. Annals of Math. 48 (1946), 101-126. · Zbl 0030.17703 · doi:10.2307/1969218
[2] Anshel, I., Anshel, M. and Goldfeld, D.: An algebraic method for public-key cryptography. Math. Res. Lett. 6 (1999), no. 3-4, 287-291. · Zbl 0944.94012 · doi:10.4310/MRL.1999.v6.n3.a3
[3] Birman, J., Ko, K. H. and Lee, S. J.: A new approach to the word and conjugacy problems in the braid groups. Adv. Math. 139 (1998), no. 2, 322-353. · Zbl 0937.20016 · doi:10.1006/aima.1998.1761
[4] Birman, J., Ko, K. H. and Lee, S. J.: The infimum, supremum and geodesic length of a braid conjugacy class. Adv. Math. 164 (2001), 41-56. · Zbl 1063.20039 · doi:10.1006/aima.2001.2010
[5] Brieskorn, E. and Saito, K.: Artin-Gruppen und Coxeter-Gruppen. Invent. Math. 17 (1972), 245-271. · Zbl 0243.20037 · doi:10.1007/BF01406235
[6] Dehornoy, P.: Groupes de Garside. Ann. Sci. École Norm. Sup. (4) 35 (2002), 267-306. · Zbl 1017.20031 · doi:10.1016/S0012-9593(02)01090-X
[7] Dehornoy, P. and Paris, L.: Gaussian groups and Garside groups, two generalizations of Artin groups. Proc. London Math. Soc. 79 (1999), no. 3, 569-604. · Zbl 1030.20021 · doi:10.1112/S0024611599012071
[8] Elrifai, E. A. and Morton, H. R.: Algorithms for positive braids. Quart. J. Math. Oxford 45 (1994), 479-497. · Zbl 0839.20051 · doi:10.1093/qmath/45.4.479
[9] Franco, N. and González-Meneses, J.: Conjugacy problem for braid groups and Garside groups, to appear in Journal of Algebra. Available at http://arxiv.org/math.GT/0112310
[10] Garside, F. A.: The braid group and other groups. Quart. J. Math. Ox- ford 20 (1969), 235-154. · Zbl 0194.03303 · doi:10.1093/qmath/20.1.235
[11] González-Meneses, J. and Wiest, B.: On the structure of the central- izer of a braid. In preparation. · Zbl 1082.20024 · doi:10.1016/j.ansens.2004.04.002
[12] Ko, K. H., Lee, S. J., Cheon, J. H., Han, J. W., Kang, J. and Park, C.: New public-key cryptosystem using braid groups. In Advances in cryptology-CRYPTO 2000 (Santa Barbara, CA), 166-183. Lecture Notes in Comput. Sci. 1880, Springer, Berlin, 2000. · Zbl 0995.94531
[13] Lyndon, R. C. and Schupp, P. E.: Combinatorial group theory. Reprint of the 1977 edition. Classics in Mathematics, Springer-Verlag, Berlin, 2001.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.