Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-01-10T23:59:15.826Z Has data issue: false hasContentIssue false

Group theory in cryptography

Published online by Cambridge University Press:  05 July 2011

By
Simon R. Blackburn ,
Carlos Cid  and
Ciaran Mullan
Edited by
C. M. Campbell ,
M. R. Quick ,
E. F. Robertson ,
C. M. Roney-Dougal ,
G. C. Smith  and
G. Traustason
Simon R. Blackburn
Affiliation:
University of London, United Kingdom
Carlos Cid
Affiliation:
University of London, United Kingdom
Ciaran Mullan
Affiliation:
University of London, United Kingdom
C. M. Campbell
Affiliation:
University of St Andrews, Scotland
M. R. Quick
Affiliation:
University of St Andrews, Scotland
E. F. Robertson
Affiliation:
University of St Andrews, Scotland
C. M. Roney-Dougal
Affiliation:
University of St Andrews, Scotland
G. C. Smith
Affiliation:
University of Bath
G. Traustason
Affiliation:
University of Bath
Get access

Summary

Abstract

This paper is a guide for the pure mathematician who would like to know more about cryptography based on group theory. The paper gives a brief overview of the subject, and provides pointers to good textbooks, key research papers and recent survey papers in the area.

Introduction

In the last few years, many papers have proposed cryptosystems based on group theoretic concepts. Notes from a recent advanced course on the subject by Myasnikov, Shpilrain and Ushakov have recently been published as a monograph [63], and a textbook (with a rather different focus) by González Vasco, Magliveras and Steinwandt [31] is promised in 2010. Group-based cryptosystems have not yet led to practical schemes to rival RSA and Diffie–Hellman, but the ideas are interesting and the different perspective leads to some worthwhile group theory. The cryptographic literature is vast and diverse, and it is difficult for a newcomer to the area to find the right sources to learn from. (For example, there are many introductory textbooks aimed at the mathematical audience that introduce RSA. How many of these textbooks hint that the basic RSA scheme is insecure if refinements such as message padding are not used? For a discussion of these issues, see Smart [78, Chapters 17,18 and 20], for example.) Our paper will provide some pointers to some sources that, in our opinion, provide a good preparation for reading the literature on group-based cryptography; the paper will also provide a high level overview of the subject.

Type
Chapter
Information
Groups St Andrews 2009 in Bath , pp. 133 - 149
Publisher: Cambridge University Press
Print publication year: 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Iris, Anshel, Michael, Anshel and Dorian, Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett. 6 (1999), 287–291.Google Scholar
[2] Iris, Anshel, Michael, Anshel, Dorian, Goldfeld and Stephane, Lemieux, Key agreement, the Algebraic Eraser™, and lightweight cryptography, Contemp. Math. 418 (2006), 1–34.Google Scholar
[3] Emil, Artin, The theory of braids, Annals of Math. 48 (1947), 101–126.Google Scholar
[4] arXiv e-print archive, http://arxiv.org/.
[5] Daniel J., Bernstein, Johannes, Buchmann and Erik, Dahmen (eds.), Post-Quantum Cryptography (Springer-Verlag, Berlin Heidelberg 2009).Google Scholar
[6] Norman, Biggs, The critical group from a cryptographic perspective, Bull. London Math. Soc. 39 (2007), 829–836.Google Scholar
[7] Joan S., Birman, Volker, Gebhardt and Juan, González-Meneses, Conjugacy in Garside groups I: cycling, powers and rigidity, Groups Geom. Dynamics 1 (2007), 221–279.Google Scholar
[8] Joan S., Birman, Volker, Gebhardt and Juan, González-Meneses, Conjugacy in Garside groups II: structure of the ultra-summit set, Groups Geom. Dynamics 2 (2008), 13–61.Google Scholar
[9] Joan S., Birman, Volker, Gebhardt and Juan, González-Meneses, Conjugacy in Garside groups III: periodic braids, J. Algebra 316 (2007), 746–776.Google Scholar
[10] Simon R., Blackburn, Cryptanalysing the critical group: efficiently solving Biggs's discrete logarithm problem, J. Math. Cryptol. to appear.
[11] Simon R., Blackburn, Carlos Cid and Ciaran Mullan, Cryptanalysis of the MST3 cryptosystem, J. Math. Cryptol. to appear.
[12] Simon, Blackburn, Sean, Murphy and Jacques, Stern, The cryptanalysis of a public key implementation of Finite Group Mappings, J. Cryptology 8 (1995), 157–166.Google Scholar
[13] Jens-Matthias, Bohli, Rainer, Steinwandt, María Isabel González, Vasco and Consuelo, Martinez, Weak keys in MST1, Des. Codes Cryptogr. 37 (2005), 509–524.Google Scholar
[14] Ryan D., Budney, On the image of the Lawrence–Krammer representation, J. Knot Theory Ramifications 14 (2005), 1–17.Google Scholar
[15] Keith W., Campbell and Michael J., Wiener, DES is not a group, in Advances in Cryptology – CRYPTO '92 (E.F., Brickell, ed.), Lecture Notes in Computer Science 740 (Springer–Verlag, Berlin 1993), 512–520.Google Scholar
[16] V., Canda, T., van Trung, S. S., Magliveras and T., Horvath, Symmetric block ciphers based on group bases, in Selected Areas in Cryptography, SAC 2000 (D.R., Stinson and S.E., Tavares, eds.), Lecture Notes in Computer Science 2012 (Springer–Verlag, Berlin 2001), 89–105.Google Scholar
[17] A., Caranti, Francesca Dalla, Volta and M., Sala, An application of the O'Nan–Scott theorem to the group generated by the round functions of an AES-like cipher, Des. Codes Cryptogr. 52 (2009), 293–301.Google Scholar
[18] A., Caranti, Francesca Dalla, Volta and M., Sala, On some block ciphers and imprimitive groups, http://arxiv.org/abs/0806.4135.
[19] CGC Bulletin – Combinatorial Group Theory and Cryptography, http://u.cs.biu.ac.il/~tsaban/CGC/cgc.html.
[20] Jung Hee, Cheon and Byungheup, Jun, A polynomial-time algorithm for the braid Diffie–Hellman conjugacy problem, in Advances in Cryptology – CRYPTO 2003 (D., Boneh, ed.), Lecture Notes in Computer Science 2729 (Springer, Berlin 2003), 212–225.Google Scholar
[21] D., Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, IBM Research Report RC 18613 (IBM 1992).Google Scholar
[22] Patrick, Dehornoy, Braid-based cryptography, Contemp. Math. 360 (2004), 5–33.Google Scholar
[23] Whitfield, Diffie and Martin E., Hellman, New directions in cryptography, IEEE Trans. Information Theory 22 (1976), 644–654.Google Scholar
[24] Steven, Galbraith and Alfred, Menezes, Algebraic curves and cryptography, Finite Fields Appl. 11 (2005), 544–577.Google Scholar
[25] David, Garber, Braid group cryptography, in Braids: Introductory Lectures on Braids, Configurations and Their Applications (J., Berrick, F.R., Cohen and E., Hanbury, eds.), (World Scientific, Singapore 2009) http://arxiv.org/abs/0711.3941.Google Scholar
[26] David, Garber, Shmuel, Kaplan, Mina, Teicher, Boaz, Tsaban and Uzi, Vishne, Probabilistic solutions of equations in the braid group, Adv. Appl. Math. 35 (2005), 323–334.Google Scholar
[27] F.A., Garside, The braid group and other groups, Quart. J. Math. Oxford 20 (1969), 235–254.Google Scholar
[28] Robert, Gilman, Alex D., Miasnikov, Alexei G., Myasnikov and Alexander, Ushakov, New developments in commutator key exchange, in Proc. First Int. Conf. on Symbolic Computation and Cryptography (SCC-2008), Bejing, 2008. http://www.math.stevens.edu/~rgilman/.Google Scholar
[29] Oded, Goldreich, Shafi, Goldwasser, and Shai, Halevi, Public-key cryptosystems from lattice reduction problems, in Advances in Cryptology – CRYPTO 97 (B.S., Kaliski Jr, ed.), Lecture Notes in Computer Science 1294 (Springer, Berlin 1997), 112–131.Google Scholar
[30] Oded, Goldreich et al., Letters to the editor, Notices Amer. Math. Soc. 54 (2007), 1454–1456.Google Scholar
[31] María Isabel González, Vasco, Spyros, Magliveras and Rainer, Steinwandt, Grouptheoretic cryptography (Chapman & Hall / CRC Press, to appear).
[32] María Isabel González, Vasco, Martin, Rötteler and Rainer, Steinwandt, On minimal length factorizations of finite groups, Exp. Math. 12 (2003), 1–12.Google Scholar
[33] María Isabel González, Vasco and Rainer, Steinwandt, A reaction attack on a public key cryptosystem based on the word problem, Appl. Algebra Engrg. Comm. Comput. 14 (2004), 335–340.Google Scholar
[34] María Isabel González, Vasco and Rainer, Steinwandt, Obstacles in two public-key cryptosystems based on group factorizations, Tatra Mt. Math. Pub. 25 (2002), 23–37.Google Scholar
[35] Markus, Grassl, Ivana, Ilić, Spyros Magliveras and Rainer Steinwandt, Cryptanalysis of the Tillich–Zémor hash function, http://eprint.iacr.org/2009/229.
[36] D., Hofheinz and R., Steinwandt, A practical attack on some braid group based cryptographic primitives, in Public Key Cryptography – PKC 2003 (Y.G., Desmedt, ed.), Lecture Notes in Computer Science 2384 (Springer, Berlin 2002), 176–189.Google Scholar
[37] P. E., Holmes, On minimal factorisations of sporadic groups, Exp. Math. 13 (2004), 435–440.Google Scholar
[38] G., Hornauer, W., Stephan and R., Wernsdorf, Markov ciphers and alternating groups, in Advances in Cryptology – EUROCRYPT '93 (T., Helleseth, ed.), Lecture Notes in Computer Science 765 (Springer–Verlag, Berlin 1994), 453–460.Google Scholar
[39] James, Hughes, A linear algebraic attack on the AAFG1 braid group cryptosystem, in Information Security and Privacy (G., Goos, J., Hartmanis and J., van Leeuwen, eds.), Lecture Notes in Computer Science 2384 (Springer–Verlag, Berlin 2002), 176–189.Google Scholar
[40] J., Hughes and A., Tannenbaum, Length-based attacks for certain group based encryption rewriting systems, http://arxiv.org/PS_cache/cs/pdf/0306/0306032v1.pdf.
[41] IACR Calendar of Events in Cryptology, http://www.iacr.org/events/.
[42] IACR Cryptology ePrint Archive, http://eprint.iacr.org/.
[43] David, Kahn, The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet, Second Edition (Simon & Schuster, London 1997).Google Scholar
[44] Burton S., Kaliski Jr, Ronald L., Rivest and Alan T., Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES), J. Cryptology 1 (1988), 3–36.Google Scholar
[45] Arkadius, Kalka, Mina, Teicher and Boaz, Tsaban, Cryptanalysis of the Algebraic Eraser and short expressions of permutations as products, http://arxiv.org/abs/0804.0629.
[46] Jonathan, Katz and Yehuda, Lindell, Introduction to Modern Cryptography (Chapman & Hall / CRC Press, Boca Raton 2007).Google Scholar
[47] Aviad, Kipnis and Adi, Shamir, Cryptanalysis of the HFE public key cryptosystem, in Advances in Cryptology – CRYPTO '99 (M., Weiner, ed.), Lecture Notes in Computer Science 1666 (Springer, Berlin 1999), 19–30.Google Scholar
[48] Ki Hyoung, Ko, Sang Jin, Lee, Jung Hee, Cheon, Jae Woo, Han, Ju-sung, Kang, and Choonsik Park, New public-key cryptosystem using braid group, in Advances in Cryptology – CRYPTO 2000 (M., Bellare, ed.), Lecture Notes in Computer Science 1880 (Springer, Berlin 2000), 166–183.Google Scholar
[49] Neal, Koblitz, The uneasy relationship between mathematics and cryptography, Notices Amer. Math. Soc. 54 (2007), 972–979.Google Scholar
[50] Sang Jin, Lee and Eonkyung, Lee, Potential weaknesses of the commutator key agreement protocol based on braid groups, in Advances in Cryptology – EUROCRYPT 2002 (L., Knudsen, ed.), Lecture Notes in Computer Science 2332 (Springer, Berlin 2002), 14–28.Google Scholar
[51] Wolfgang, Lempken and Tran van, Trung, On minimal logarithmic signatures of finite groups, Exp. Math. 14 (2005), 257–269.Google Scholar
[52] Wolfgang, Lempken, Tran van, Trung, Spyros S., Magliveras and Wandi, Wei, A public key cryptosystem based on non-abelian finite groups, J. Cryptology 22 (2009), 62–74.Google Scholar
[53] Françoise, Levy-dit-Vehel and Ludovic, Perret, On the Wagner–Magyarik cryptosystem, in Coding and Cryptography (Ø., Ytrehus, ed.), (Springer, Berlin 2006), 316–329.Google Scholar
[54] Françoise, Levy-dit-Vehel and Ludovic, Perret, Security analysis of word problem-based cryptosystems, Des. Codes Cryptogr. 54 (2010), 29–41.Google Scholar
[55] Helger, Lipmaa, Multiparty computations, http://research.cyber.ee/~lipmaa/crypto/link/mpc/.
[56] S. S., Magliveras, A cryptosystem from logarithmic signatures of finite groups, in Proceedings of the 29th Midwest Symposium on Circuits and Systems (Elsevier Publishing Company 1986), 972–975.Google Scholar
[57] S. S., Magliveras, Secret and public-key cryptosystems from group factorizations, Tatra Mt. Math. Publ. 25 (2002), 1–12.Google Scholar
[58] Spyros S., Magliveras and Nasir D., Memon, The algebraic properties of cryptosystem PGM, J. Cryptology 5 (1992), 167–183.Google Scholar
[59] S. S., Magliveras, D. R., Stinson and Tran van, Trung, New approaches to designing public key cryptosystems using one-way functions and trap-doors in finite groups, J. Cryptology 15 (2002), 167–183.Google Scholar
[60] R.J., McEliece, A public key cryptosystem based on algebraic coding theory, DSN Progress Report 42–44 (Jet Propulsion Lab, Pasadena 1978), 114–116.Google Scholar
[61] Alfred J., Menezes and Scott A., Vanstone, A note on cyclic groups, finite fields and the discrete logarithm problem, Appl. Algebra Engrg. Comm. Comput. 3 (1992), 67–74.Google Scholar
[62] Sean, Murphy, Kenneth, Paterson and Peter, Wild, A weak cipher that generates the symmetric group, J. Cryptology 7 (1994), 61–65.Google Scholar
[63] Alexei, Myasnikov, Vladimir, Shpilrain and Alexander, Ushakov, Group-based Cryptography, Advanced Courses in Mathematics CRM Barcelona (Birkhäuser, Basel 2008).Google Scholar
[64] Alex D., Myasnikov and Alexander, Ushakov, Length based attack and braid groups: cryptanalysis of Anshel–Anshel–Goldfeld key exchange protocol, in Public Key Cryptography – PKC 2007 (T., Okamoto and X., Wang, eds.), Lecture Notes in Computer Science 4450 (Springer, Berlin 2007), 76–88.Google Scholar
[65] A.G., Myasnikov and A., Ushakov, Random subgroups and analysis of the length-based and quotient attacks, J. Math. Cryptology 2 (2008), 29–61.Google Scholar
[66] Phong Q., Nguyen, Cryptanalysis of the Goldreich–Goldwasser–Halevi cryptosystem from CRYPTO 97, in Advances in Cryptology – CRYPTO '99 (M., Weiner, ed.), Lecture Notes in Computer Science 1666 (Springer, Berlin 1999), 288–304.Google Scholar
[67] ,National Bureau of Standards, The Data Encryption Standard, Federal Information Processing Standards Publication (FIPS) 46, 1977.
[68] ,National Institute of Standards and Technology, Secure Hash Standard, Federal Information Processing Standards Publication (FIPS) 180-1, 1995.
[69] ,National Institute of Standards and Technology, Secure Hash Standard, Federal Information Processing Standards Publication (FIPS) 180-2 with Change Notice, 2002.
[70] ,National Institute of Standards and Technology, The Advanced Encryption Standard, Federal Information Processing Standards Publication (FIPS) 197, 2001.
[71] Jacques, Patarin, Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of Asymmetric Algorithms, in Advances in Cryptology – Eurocrypt '96 (U., Maurer, ed.), Lecture Notes in Computer Science 1440 (Springer, Berlin 1999), 33–48.Google Scholar
[72] Kenneth G., Paterson, Imprimitive permutation groups and trapdoors in iterated block ciphers, in Fast Software Encryption (L.R., Knudsen, ed.), Lecture Notes in Computer Science 1636 (Springer–Verlag, Berlin 1999), 201–214.Google Scholar
[73] Mingua, Qu and Scott, Vanstone, New public-key cryptosystems based on factorizations of finite groups, AUSCRYPT '92 Preproceedings.
[74] Dima, Ruinskiy, Adi, Shamir and Boaz, Tsaban, Length-based cryptanalysis: The case of Thompson's Group, J. Math. Cryptology 1 (2007), 359–372.Google Scholar
[75] C.E., Shannon, Communication theory of secrecy systems, Bell System Technical Journal 28 (1949), 656–715.Google Scholar
[76] Peter W., Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Computing 26 (1997), 1484–1509.Google Scholar
[77] V., Shpilrain, Cryptanalysis of Stickel's key exchange scheme, in Computer Science – Theory and Applications (E.A., Hirsch, A.A., Razborov, A., Semenov and A., Slissenko, eds.), Lecture Notes in Computer Science 5010 (Springer, Berlin 2008), 283–288.Google Scholar
[78] Nigel, Smart, Cryptography: An Introduction, Third Edition, http://www.cs.bris.ac.uk/~nigel/Crypto_Book/.
[79] Rüdiger, Sparr and Ralph, Wernsdorf, Group theoretic properties of RIJNDAEL-like ciphers, Discrete Appl. Math. 156 (2008), 3139–3149.Google Scholar
[80] Rainer, Steinwandt, Markus, Grassl, Willi, Geiselmann and Thomas, Beth, Weaknesses in the SL2 (F2n) hashing scheme, in Advances in Cryptology – CRYPTO 2000 (M., Bellare, ed.), Lecture Notes in Computer Science 1880 (Springer, Berlin 2000), 287–299.Google Scholar
[81] Eberhard, Stickel, A new method for exchanging secret keys, in Proc. Third International Conference on Information Technology and Applications (ICITA '05) (IEEE Computer Society, Piscataway 2005), 426–430.Google Scholar
[82] Douglas R., Stinson, Cryptography: Theory and Practice, Third Edition (Chapman & Hall, Boca Raton 2005).Google Scholar
[83] The Hash Function Zoo, http://ehash.iaik.tugraz.at/wiki/The_Hash_Function_Zoo.
[84] Jean-Pierre, Tillich and Gilles Zémor, Hashingwith SL2, in Advances in Cryptology – CRYPTO '94 (Y., Desmedt, ed.), Lecture Notes in Computer Science, 839 (Springer, Berlin 1994), 40–49.Google Scholar
[85] Jean-Pierre, Tillich and Zémor, Gilles, Collisions for the LPS expander graph hash function, in Advances in Cryptology – EUROCRYPT 2008 (N., Smart, ed.), Lecture Notes in Computer Science 4965 (Springer, Berlin 2008), 254–269.Google Scholar
[86] Neal R., Wagner and Marianne R., Magyarik, A public key cryptosystem based on the word problem, in Advances in Cryptology – CRYPTO '84 (G.R., Blakley and David, Chaum, eds.), Lecture Notes in Computer Science 196 (Springer, Berlin 1985), 19–36.Google Scholar
[87] Laurence C., Washington, Elliptic Curves: Number Theory and Cryptography, Second Edition (CRC Press, Boca Raton 2008).Google Scholar
[88] Ralph, Wernsdorf, The one-round functions of the DES generate the alternating group, in Advances in Cryptology – EUROCRYPT 1992 (R.A., Rueppel, ed.), Lecture Notes in Computer Science 658 (Springer–Verlag, Berlin 1993), 99–112.Google Scholar
[89] Ralph, Wernsdorf, The round functions of RIJNDAEL generate the alternating group, in Fast Software Encryption (J., Daemen and V., Rijmen, eds.), Lecture Notes in Computer Science 2365 (Springer–Verlag, Berlin 2002), 143–148.Google Scholar
[90] Gilles, Zémor, Hash functions and Cayley graphs, Des. Codes Cryptogr. 4 (1994), 381–394.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×