zbMATH — the first resource for mathematics

A new approach to the conjugacy problem in Garside groups. (English) Zbl 1105.20032
Summary: The cycling operation endows the super summit set \(S_x\) of any element \(x\) of a Garside group \(G\) with the structure of a directed graph \(\Gamma_x\). We establish that the subset \(U_x\) of \(S_x\) consisting of the circuits of \(\Gamma_x\) can be used instead of \(S_x\) for deciding conjugacy to \(x\) in \(G\), yielding a faster and more practical solution to the conjugacy problem for Garside groups. Moreover, we present a probabilistic approach to the conjugacy search problem in Garside groups. The results have implications for the security of recently proposed cryptosystems based on the hardness of problems related to the conjugacy (search) problem in braid groups.

20F36 Braid groups; Artin groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
94A60 Cryptography
Full Text: DOI arXiv
[1] Anshel, I.; Anshel, M.; Goldfeld, D., An algebraic method for public-key cryptography, Math. res. lett., 6, 3-4, 287-291, (1999) · Zbl 0944.94012
[2] Artin, E., Theory of braids, Ann. of math. (2), 48, 101-126, (1947) · Zbl 0030.17703
[3] Birman, J.; Ko, K.H.; Lee, S.J., A new approach to the word and conjugacy problems in the braid groups, Adv. math., 139, 2, 322-353, (1998) · Zbl 0937.20016
[4] Birman, J.S.; Ko, K.H.; Lee, S.J., The infimum, supremum, and geodesic length of a braid conjugacy class, Adv. math., 164, 1, 41-56, (2001) · Zbl 1063.20039
[5] Bosma, W.; Cannon, J.; Playoust, C., The MAGMA algebra system I: the user language, J. symbolic comput., 24, 235-265, (1997) · Zbl 0898.68039
[6] Dehornoy, P., Groupes de garside, Ann. sci. école norm. sup. (4), 35, 2, 267-306, (2002) · Zbl 1017.20031
[7] Dehornoy, P.; Paris, L., Gaussian groups and garside groups, two generalisations of Artin groups, Proc. London math. soc. (3), 79, 3, 569-604, (1999) · Zbl 1030.20021
[8] El-Rifai, E.A.; Morton, H.R., Algorithms for positive braids, Quart. J. math. Oxford ser. (2), 45, 479-497, (1994) · Zbl 0839.20051
[9] Epstein, D.B.A.; Cannon, J.W.; Holt, D.F.; Levy, S.V.F.; Paterson, M.S.; Thurston, W.P., Word processing in groups, (1992), Jones & Bartlett Boston, MA, Chapter 9
[10] Franco, N.; González-Meneses, J., Conjugacy problem for braid groups and garside groups, J. algebra, 266, 1, 112-132, (2003) · Zbl 1043.20019
[11] Garside, F.A., The braid group and other groups, Quart. J. math. Oxford ser. (2), 20, 235-254, (1969) · Zbl 0194.03303
[12] V. Gebhardt, Conjugacy search in braid groups, Appl. Algebra Engrg. Comm. Comput. (2005), in press · Zbl 1105.20032
[13] Ko, K.H.; Lee, S.J.; Cheon, J.H.; Han, J.W.; Kang, J.-S.; Park, C., New public-key cryptosystem using braid groups, (), 166-183 · Zbl 0995.94531
[14] Lee, E.; Lee, S.J.; Hahn, S.G., Pseudorandomness from braid groups, (), 486-502 · Zbl 1002.94026
[15] Picantin, M., The conjugacy problem in small Gaussian groups, Comm. algebra, 29, 3, 1021-1039, (2001) · Zbl 0988.20024
[16] Thurston, W.P., On the geometry and dynamics of diffeomorphisms of surfaces, Bull. amer. math. soc. (N.S.), 19, 2, 417-431, (1988) · Zbl 0674.57008
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.