Affine braid groups: a better platform than braid groups for cryptology? (English) Zbl 1276.94021
Summary: In recent years, various cryptographic protocols using infinite non-commutative groups, notably braid groups, have been proposed. Both experimental and theoretical evidence collected so far, however, makes it appear likely that braid groups are not a good choice for the platform. In this paper, we thus consider to use affine braid groups, a natural generalization of braid groups, as a platform. Like braid groups, affine braid groups have a very nice geometrical interpretation and have several properties that make them acceptable for cryptographic purposes. On the other hand, there are also essential differences between their structures; for example, unlike braid groups, affine braid groups have no Garside structure, which makes the conjugacy problem in these groups more difficult. We examine the feature that makes affine braid groups useful to cryptography and then conclude that this class of groups could provide a promising alternative platform for group-based cryptography.
Keywords:
affine braid group; braid group; conjugacy problem; normal form; public key cryptosystem; word problemReferences:
| [1] | Allcock D.: Braid pictures for Artin groups. Trans. Am. Math. Soc. 354(9), 3455–3474 (2002) · Zbl 1059.20032 · doi:10.1090/S0002-9947-02-02944-6 |
| [2] | Anshel, I., Anshel, M., Fisher, B., Goldfeld, D.: New key agreement protocols in braid group cryptography. In: Proceedings of 2001 Conference Topics in Cryptology: Crypt. Track RSA. Lect. Notes Comput. Sci. 2020, 13–27 (2001) · Zbl 0991.94034 |
| [3] | Anshel I., Anshel M., Goldfeld D.: An algebraic method for public-key cryptography. Math. Res. Lett. 6, 287–292 (1999) · Zbl 0944.94012 · doi:10.4310/MRL.1999.v6.n3.a3 |
| [4] | Baumslag G., Fine B., Xu X.: Cryptosystems using linear groups. Appl. Algebra Eng. Commun. Comput. 17, 205–217 (2006) · Zbl 1104.94017 · doi:10.1007/s00200-006-0003-z |
| [5] | Bessis D.: The dual braid monoid. Ann. Sci. Ecole Norm. Sup. 36(5), 647–683 (2003) · Zbl 1064.20039 |
| [6] | Bigelow S.: Braid groups are linear. J. Am. Math. Soc. 14, 471–486 (2001) · Zbl 0988.20021 · doi:10.1090/S0894-0347-00-00361-1 |
| [7] | Birman J., Gebhardt V., González-Meneses J.: Conjugacy in Garside groups I: cyclings, powers, and rigidity. Groups Geom. Dyn. 1, 221–279 (2007) · Zbl 1160.20026 · doi:10.4171/GGD/12 |
| [8] | Birman J., Gebhardt V., González-Meneses J.: Conjugacy in Garside groups III: periodic braids. J. Algebra 316(2), 746–776 (2007) · Zbl 1165.20031 · doi:10.1016/j.jalgebra.2007.02.002 |
| [9] | Birman J., Gebhardt V., González-Meneses J.: Conjugacy in Garside groups II: structure of the ultra summit set. Groups Geom. Dynam. 2(1), 16–31 (2008) · Zbl 1163.20023 |
| [10] | Birman J., Ko K., Lee S.: A new approach to the word and conjugacy problems in the braid groups. Adv. Math. 139(2), 322–353 (1998) · Zbl 0937.20016 · doi:10.1006/aima.1998.1761 |
| [11] | Brieskorn E.: Die Fundamentalgruppe des Raumes der regulären Orbits einer endlichen komplexen Spiegelungsgruppe. Invent. Math. 12, 57–61 (1971) · Zbl 0204.56502 · doi:10.1007/BF01389827 |
| [12] | Brieskorn E., Saito K.: Artin-gruppen und Coxeter-gruppen. Invent. Math. 17, 245–271 (1972) · Zbl 0243.20037 · doi:10.1007/BF01406235 |
| [13] | Budney R.: On the image of the Lawrence-Krammer representation. J. Knot Theory Ramif. 14(6), 1–17 (2005) · Zbl 1066.57013 · doi:10.1142/S0218216505003713 |
| [14] | Cao, Z.F., Dong, X.L., Wang, L.C.: New public key cryptosystems using polynomials over non-commutative rings. Preprint, p. 35. http://eprint.iacr.org/2007/009 (2007) |
| [15] | Charney R.: Artin groups of finite type are biautomatic. Math. Ann. 292(4), 671–683 (1992) · doi:10.1007/BF01444642 |
| [16] | Charney R., Peifer D.: The K({\(\pi\)}, 1)-conjecture for the affine braid groups. Comment. Math. Helv. 78(3), 584–600 (2003) · Zbl 1066.20043 · doi:10.1007/s00014-003-0764-y |
| [17] | Cheon, J., Jun, B.: A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem. In: CRYPTO 2003. Lect Notes Comput. Sci. 2729, 212–225 (2003) · Zbl 1122.94364 |
| [18] | Cohen A.M., Wales D.B.: Linearity of Artin groups of finite type. Israel J. Math. 131, 101–123 (2002) · Zbl 1078.20038 · doi:10.1007/BF02785852 |
| [19] | Collins D.: Relations among the squares of the generators of the braid group. Invent. Math. 117(1), 525–529 (1994) · Zbl 0822.20040 · doi:10.1007/BF01232254 |
| [20] | Crisp, J.: Injective maps between Artin groups. In: Geometrical Group Theory Down Under, Proceedings of Special Year Geometric Group Theory, pp. 119–137. Canberra, Australia (1996) |
| [21] | Dehornoy P.: A fast method for comparing braids. Adv. Math. 125(2), 200–235 (1997) · Zbl 0882.20021 · doi:10.1006/aima.1997.1605 |
| [22] | Dehornoy P.: Braid-based cryptography. Contemp. Math. 360, 5–33 (2004) · Zbl 1083.94008 · doi:10.1090/conm/360/06566 |
| [23] | Dehornoy, P., Dynnikov, I., Rolfsen, D., Wiest, B.: Ordering Braids. Math. Surv. Monogr. 148, Am. Math. Soc. (2008) · Zbl 1163.20024 |
| [24] | Dehornoy P., Paris L.: Gaussian groups and garside groups, two generalizations of artin groups. Proc. London Math. Soc. 79(3), 569–604 (1999) · Zbl 1030.20021 · doi:10.1112/S0024611599012071 |
| [25] | Deligne P.: Les immeubles des groupes de tresses généralisés. Invent. Math. 17, 273–302 (1972) · Zbl 0238.20034 · doi:10.1007/BF01406236 |
| [26] | Digne F.: On the linearity of Artin braid groups. J. Algebra 268(1), 39–57 (2003) · Zbl 1066.20044 · doi:10.1016/S0021-8693(03)00327-2 |
| [27] | Digne F.: Présentations duales des groupes de tresses de type affine Ã. Commun. Math. Helv. 81(1), 23–47 (2006) · Zbl 1143.20020 · doi:10.4171/CMH/41 |
| [28] | Dynnikov, I.A.: On a Yang-Baxter mapping and the Dehornoy ordering. Uspekhi Mat. Nauk 57(3), 151–152 (2002) (Russian); English Translation in Russ. Math. Surv. 57(3), 592–594 (2002) |
| [29] | Eick, B., Kahrobaei, D.: Polycyclic Groups: A New Platform for Cryptology? Preprint, p. 7. http://arxiv.org/abs/math/0411077 (2004) |
| [30] | El-Rifai E., Morton H.: Algorithms for positive braids. Quart. J. Math. 45(4), 479–497 (1994) · Zbl 0839.20051 · doi:10.1093/qmath/45.4.479 |
| [31] | Epstein D.B.A., Paterson M.S., Camon G.W., Holt D.F., Levy S.V., Thurston W.P.: Word Processing in Groups. Jones and Bartlett Publishers, Boston, MA, USA (1992) · Zbl 0764.20017 |
| [32] | Franco N.: Conjugacy problem for subgroups with applications to Artin groups and braid type group. Commun. Algebra 34(11), 4207–4215 (2006) · Zbl 1109.20028 · doi:10.1080/00927870600876375 |
| [33] | Franco N., González-Meneses J.: Conjugacy problem for braid groups and Garside groups. J. Algebra 266(1), 112–132 (2003) · Zbl 1043.20019 · doi:10.1016/S0021-8693(03)00292-8 |
| [34] | Garber D.: Braid group cryptography. In: Berrick, J., Cohen, F.R., Hanbury, E. (eds.) Braids: Introductory Lectures on Braids, Configurations and Their Applications, pp. 329–403. World Scientific, Singapore (2009) · Zbl 1203.94100 |
| [35] | Garber D., Kaplan S., Teicher M., Tsaban B., Vishne U.: Probabilistic solutions of equations in the braid group. Adv. Appl. Math. 35, 323–334 (2005) · Zbl 1109.20029 · doi:10.1016/j.aam.2005.03.002 |
| [36] | Garber D., Kaplan S., Teicher M., Tsaban B., Vishne U.: Length-based conjugacy search in the braid group. Contemp. Math. 418, 75–87 (2006) · Zbl 1149.94315 · doi:10.1090/conm/418/07947 |
| [37] | Garside F.: The braid group and other groups. Quart. J. Math. 20(1), 235–254 (1969) · Zbl 0194.03303 · doi:10.1093/qmath/20.1.235 |
| [38] | Gebhardt V.: A new approach to the conjugacy problem in Garside groups. J. Algebra 292(1), 282–302 (2005) · Zbl 1105.20032 · doi:10.1016/j.jalgebra.2005.02.002 |
| [39] | Gebhardt V., González-Meneses J.: The cyclic sliding operation in Garside groups. Math. Z. 265(1), 85–114 (2010) · Zbl 1253.20034 · doi:10.1007/s00209-009-0502-2 |
| [40] | Gersten S., Short H.: Rational subgroups of biautomatic groups. Ann. Math. 134(1), 125–158 (1991) · Zbl 0744.20035 · doi:10.2307/2944334 |
| [41] | Gersten S., Short H.: Small cancellation theory and automatic groups: part II. Invent. Math. 105(1), 641–662 (1991) · Zbl 0734.20014 · doi:10.1007/BF01232283 |
| [42] | Hofheinz D., Steinwandt R.: A practical attack on some braid group based cryptographic primitives. Lect. Notes Comput. Sci. 2567, 187–198 (2002) · Zbl 1033.94528 · doi:10.1007/3-540-36288-6_14 |
| [43] | Hughes J.: A linear algebraic attack on the AAFG1 braid group cryptosystem. Lect. Notes Comput. Sci. 2384, 176–189 (2002) · Zbl 1022.94508 · doi:10.1007/3-540-45450-0_15 |
| [44] | Hughes, J., Tannenbaum, A.: Length-based attacks for certain group based encryption rewriting systems. In: SÉcurité des Communications sur Internet (SECI02), Hôtel El Mechtel. Tunis, Tunisie, pp. 5–12 (2002) |
| [45] | Humphreys J.: Reflection Groups and Coxeter Groups. Cambridge University Press, Cambridge (1990) · Zbl 0725.20028 |
| [46] | Johnson D., Albar M.: The centre of the circular braid group. Math. Japon. 30, 641–645 (1985) · Zbl 0583.20029 |
| [47] | Kalka A.: Representation attacks on the braid Diffie-Hellman public key encryption. Appl. Algebra Eng. Commun. Comput. 17(3), 257–266 (2006) · Zbl 1104.94026 · doi:10.1007/s00200-006-0007-8 |
| [48] | Kapovich I., Myasnikov A., Schupp P., Shpilrain V.: Generic-case complexity, decision problems in group theory, and random walks. J. Algebra 264(2), 665–694 (2003) · Zbl 1041.20021 · doi:10.1016/S0021-8693(03)00167-4 |
| [49] | Kent IV R., Peifer D.: A geometric and algebraic description of annular braid groups. Int. J. Algebra Comput. 12, 85–97 (2002) · Zbl 1010.20024 · doi:10.1142/S0218196702000997 |
| [50] | Ko K., Lee S., Cheon J., Han J., Kang J., Park C.: New public-key cryptosystem using braid groups. CRYPTO 2000, Lect. Notes Comput. Sci. 1880, 166–183 (2000) · Zbl 0995.94531 · doi:10.1007/3-540-44598-6_10 |
| [51] | Krammer D.: Braid groups are linear. Ann. Math. 155(1), 131–156 (2002) · Zbl 1020.20025 · doi:10.2307/3062152 |
| [52] | Labruere C.: Generalized braid groups and mapping class groups. J. Knot Theory Ramif. 6(5), 715–726 (1997) · Zbl 0893.57011 · doi:10.1142/S021821659700039X |
| [53] | Lee E., Lee S.: Abelian subgroups of Garside groups. Commun. Algebra 36(3), 1121–1139 (2008) · Zbl 1155.20037 · doi:10.1080/00927870701715605 |
| [54] | McCammond, J.: Dual euclidean Artin groups and the failure of the lattice property. Preprint, p. 40. http://www.math.ucsb.edu/\(\sim\)mccammon/papers/lattice-failure.pdf (2011) · Zbl 1343.20039 |
| [55] | Myasnikov A., Shpilrain V., Ushakov A.: Random subgroups of braid groups: an approach to cryptanalysis of a braid group based cryptographic protocol. Lect. Notes Comput. Sci. 3958, 302–314 (2006) · Zbl 1151.94554 · doi:10.1007/11745853_20 |
| [56] | Myasnikov A., Shpilrain V., Ushakov A.: Group-based Cryptography. Birkhäuser Verlag, Springer, Berlin (2008) · Zbl 1248.94004 |
| [57] | Myasnikov, A., Ushakov, A.: Length based attack and braid groups: Cryptanalysis of Anshel-Anshel-Goldfeld key exchange protocol. In: Public Key Cryptography PKC 2007. Lect. Notes Comput. Sci. 4450, 76–88 (2007) · Zbl 1127.94017 |
| [58] | Paris L.: Braid groups and Artin groups. In: Papadopoulus, A. (ed.) Handbook of Teichmüller Theory, vol 2, EMS Publishing House, Zurich (2008) · Zbl 1230.20040 |
| [59] | Picantin M.: Explicit presentations for the dual braid monoids. C. R. Acad. Sci. Paris, Ser. I 334, 843–848 (2002) · Zbl 1020.20027 · doi:10.1016/S1631-073X(02)02370-1 |
| [60] | Ram, A., Ramagge, J.: Affine Hecke algebras, cyclotomic Hecke algebras and Clifford theory. A Tribute to CS Seshadri: A Collection of Articles on Geometry and Representation Theory (2003) · Zbl 1063.20004 |
| [61] | Shpilrain V., Ushakov A.: Thompson’s group and public key cryptography. Lect. Notes Comput. Sci. 3531, 151–163 (2005) · Zbl 1126.68416 · doi:10.1007/11496137_11 |
| [62] | Sibert H., Dehornoy P., Girault M.: Entity authentication schemes using braid word reduction. Discrete Appl. Math. 154(2), 420–436 (2006) · Zbl 1091.94036 · doi:10.1016/j.dam.2005.03.015 |
| [63] | Sidelnikov V., Cherepnev M., Yaschenko V.: Systems of open distribution of keys on the basis of noncommutative semigroups. Russ. Acad. Sci. Dokl. Math. 48(2), 384–386 (1994) |
| [64] | Tits J.: Normalisateurs de tores I Groupes de Coxeteretendus. J. Algebra 4(1), 96–116 (1966) · Zbl 0145.24703 · doi:10.1016/0021-8693(66)90053-6 |
| [65] | Vershik A., Nechaev S., Bikbov R.: Statistical properties of braid groups with application to braid groups and growth of heaps. Commun. Math. Phys. 212, 469–501 (2000) · Zbl 1010.20056 · doi:10.1007/s002200000221 |
| [66] | Wagner, N., Magyarik, M.: A public key cryptosystem based on the word problem. In: CRYPTO 1984. Lect. Notes Comput. Sci. 196, 19–36 (1985) · Zbl 0569.94010 |
| [67] | Wang L.C., Wang L.H., Cao Z.F., Yang Y.X., Niu X.X.: Conjugate adjoining problem in braid groups and new design of braid-based signatures. Sci. China Inform. Sci. 53, 524–536 (2010) · doi:10.1007/s11432-010-0046-4 |
| [68] | Zheng, H.: General cycling operations in Garside groups. Preprint, p. 22. http://arxiv.org/abs/math/0605741 (2006) |
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.
