Algorithmic problems in Engel groups and cryptographic applications

Document Type : Proceedings of the conference "Engel conditions in groups" - Bath - UK - 2019


1 Department of Computer Science Deramore Lane, University of York

2 Department of Mathematics (University of Salerno), Italy - Department of Mathematics and Statistic (University of the Basque Country), Spain


‎The theory of Engel groups plays an important role in group theory since these groups are closely related to the Burnside problems‎. ‎In this survey we consider several classical and novel algorithmic problems for Engel groups and propose several open problems‎. ‎We study these problems with a view towards applications to cryptography‎.


Main Subjects

[1] Y. Antol´ın, A. Martino and E. Ventura, Degree of commutativity of infinite groups, Proc. Amer. Math. Soc., 145
(2015) 479–485.
[2] J. Avenhaus and D. Wi:Gbmann, Using rewriting techniques to solve the generalized word problem in polycyclic
groups, Proc. Amer. Math. Soc., 145 (1989) 322–337.
[3] R. Baer, Engelsche elemente noetherscher gruppen, Math. Ann., 133 (1957) 256–270.
[4] L. Bartholdi, Algorithmic decidability of Engel’s property for automaton groups, Computer sciencetheory and applications, Lecture Notes in Comput. Sci., Springer, Cham, 2016 29–40.
[5] M. Noce and A. Tortora, A note on Engel elements in the first Grigorchuk group, Int. J. Group Theory, 8 no. 3
(2019) 9–14.
[6] L. Bartholdi and R. I. Grigorchuk, Lie methods in growth of groups and groups of finite width, Computational and
geometric aspects of modern algebra (Edinburgh, 1998), London Math. Soc. Lecture Note Ser., 275, Cambridge
Univ. Press, Cambridge, 2000 1–27.
[7] M. Batty, S. L. Braunstein, A. J. Duncan and S. Rees, Quantum algorithms in group theory, Proceedings of
Computational and experimental group theory, 349 (2004) 1–62.
[8] G. Baumslag, N. Fazio, A. R. Nicolosi, V. Shpilrain and W. E. Skeith, Generalized learning problems and applications to non-commutative cryptograph, Provable security, Lecture Notes in Comput. Sci., Springer, Heidelberg, 2011 324–339.
[9] G. Baumslag, B. Fine and X. Xu, Cryptosystems using linear groups, Appl. Algebra Engrg. Comm. Comput., 17
(2006) 205–217.
[10] N. Blackburn, Conjugacy in nilpotent groups, Proc. Amer. Math. Soc., 16 (1965) 143–148.
[11] W. Burnside, On an unsettled question in the theory of discontinous groups, Quart. J. Pure Appl. Math., 33 (1902)
[12] P. G. Crosby and G. Traustason, A remark on the structure of n-Engel groups, Comm. Algebra, 39 (2011) 3998–
[13] B. Eick and D. Kahrobaei, Polycyclic groups: A new platform for cryptology?, arXiv Mathematics e-prints (2004),
available at math/0411077.
[14] A. Erfanian, R. Rezaei and P. Lescot, On the relative commutativity degree of a subgroup of a finite group, Comm.
Algebra, 35 (2007) 4183–4197.
[15] G. A. Fern´andez-Alcober, A. Garreta and M. Noce, Engel elements in some fractal groups, Monatsh. Math., 189
(2019) 651–660.
[16] G. A. Fern´andez-Alcober and M. Noce and G. M. Tracey, Engel elements in weakly branch groups, J. Algebra,
554 (2020) 54–77.
[17] N. Fazio, K. Iga, A. R. Nicolosi, L. Perret and W. E. Skeith III, Hardness of learning problems over Burnside
groups of exponent 3, Des. Codes Cryptogr., 75 (2015) 59–70.
[18] R. Flores and D. Kahrobaei, Cryptography with right-angled artin groups, Theoretical and Applied Informatics,
28 (2016) 8–16.
[19] R. Flores, D. Kahrobaei and T. Koberda, Algorithmic problems in right-angled Artin groups: complexity and
applications, J. Algebra, 519 (2019) 111–129.
[20] E. Formanek, Conjugate separability in polycyclic groups, J. Algebra, 42 (1976) 1–10.
[21] M. Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes tudes Sci. Publ. Math., no. 53 (1981)
[22] K. W. Gruenberg, Two theorems on Engel groups, Proc. Cambridge Philos. Soc., 49 (1953) 377–380.
[23] F. Grunewald and D. Segal, Conjugacy in polycyclic groups, Comm. Algebra, 6 (1978) 775–798.
[24] F. J. Grunewald and D. Segal, The solubility of certain decision problems in arithmetic and algebra, Bull. Amer.
Math. Soc. (N.S.), 1 (1979) 915–918.
[25] J. Gryak and D. Kahrobaei, The status of polycyclic group-based cryptography: a survey and open problems,
Groups Complex. Cryptol., 8 (2016) 171–186.
[26] W. H. Gustafson, What is the probability that two group elements commute?, Amer. Math. Monthly, 80 (1973)
[27] M. Habeeb, D. Kahrobaei, C. Koupparis and V. Shpilrain, Public key exchange using semidirect product of
(semi)groups, Applied Cryptography and Network Securitym ACNS, (2013) 475–486.
[28] M. Habeeb, D. Kahrobaei and V. Shpilrain, A secret sharing scheme based on group presentations and the word
problem, Computational and combinatorial group theory and cryptography, Contemp. Math., Amer. Math. Soc.,
Providence, RI, 582 (2012) 143–150.
[29] P. Hall, The Edmonton notes on nilpotent groups, Queen Mary College Mathematics Notes, Mathematics Department, Queen Mary College, London, 1969.
[30] G. Havas and M. R. Vaughan-Lee, 4-Engel groups are locally nilpotent, Internat. J. Algebra Comput., 15 (2005)
[31] H. Heineken, Eine Bemerkung ¨uber engelsche Elemente, (German), Arch. Math. (Basel), 11 (1960) 321.
[32] H. Heineken, Engelsche Elemente der L¨ange drei, (German), Illinois J. Math., 5 (1961) 681–707.
[33] K. Horan and D. Kahrobaei, The hidden subgroup problem and post-quantum group-based cryptography, Mathematical softwareICMS, Lecture Notes in Comput. Sci., 10931, Springer, Cham, 2018 218–226.
[34] Y. Inui and F. Le Gall, Efficient quantum algorithms for the hidden subgroup problem over semi-direct product
groups, Quantum Inf. Comput., 7 (2007) 559–570.
[35] D. Kahrobaei and V. Shpilrain, Using semidirect product of (semi) groups in public key cryptography, Pursuit of
the universal, Lecture Notes in Comput. Sci., 9709, Springer, 2016 132–141.
[36] D. Kahrobaei, A. Tortora and M. Tota, Multilinear Cryptography using Nilpotent Groups, De Gruyter, (2020)
[37] K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang and C. Park, New public-key cryptosystem using braid groups,
Advances in cryptologyCRYPTO 2000 (Santa Barbara, CA), Lecture Notes in Comput. Sci., 1880, Springer, Berlin,
2000 166–183.
[38] P. Lescot, Isoclinism classes and commutativity degrees of finite groups, J. Algebra, 177 (1995) 847–869.
[39] F. W. Levi, Groups in which the commutator operation satisfies certain algebraic conditions, J. Indian Math. Soc.
(N.S.), 6 (1942) 87–97.
[40] H. FLiebeck, Concerning nilpotent wreath products, Proc. Cambridge Philos. Soc., 58 (1962) 443–451.
[41] R. J. Lipton and Y. Zalcstein, Word problems solvable in logspace, J. Assoc. Comput. Mach., 24 (1977) 522–526.
[42] P. Longobardi and M. Maj, Semigroup identities and Engel groups, Groups St. Andrews 1997 in Bath, II, London
Math. Soc. Lecture Note Ser., 261, Cambridge Univ. Press, Cambridge, 1999 527–531.
[43] A. Mahalanobis and P. Shinde, Bilinear cryptography using groups of nilpotency class 2, Cryptography and coding,
Lecture Notes in Comput. Sci., 10655, Springer, Cham, 2017 127–134.
[44] M. R. R. Moghaddam, A. R. Salemkar and K. Chiti, n-isoclinism classes and n-nilpotency degree of finite groups,
Algebra Colloq., 12 (2005) 255–261.
[45] A. Myasnikov, V. Shpilrain and A. Ushakov, Non-commutative cryptography and complexity of group-theoretic problems, With an appendix by Natalia Mosina, Mathematical Surveys and Monographs, 177, American Mathematical
Society, Providence, RI, 2012.
[46] W. Nickel, Computation of nilpotent Engel groups, Group theory. J. Austral. Math. Soc. Ser. A, 67 (1999) 214–222.
[47] M. Noce and A. Tortora, A note on Engel elements in the first Grigorchuk group, Int. J. Group Theory, 8 no.3
(2019) 9–14.
[48] P. S. Novikov and S. I. Adjan, Infinite periodic groups. I, II, III, Izv. Akad. Nauk SSSR Ser. Mat., 32 (1968) 212–244 251–524 709–731, English transl in Math. USSR Izv., 2 (1968).
[49] A. Odlyzko, Discrete logarithms: the past and the future. Towards a quarter-century of public key cryptography,
Des. Codes Cryptogr., 19 (2000) 129–145.
[50] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, STOC’05: Proceedings of the
37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005 84–93.
[51] V. N. Remeslennikov, Conjugacy in polycyclic groups, Algebra and Logic, 8 (1969) 404–411.
[52] V. N. Remeslennikov, An algorithmic problem for nilpotent groups and rings, Siberian Mathematical Journal, 20
(1979) 761–764.
[53] D. J. S. Robinson, A course in the theory of groups, Second edition. Graduate Texts in Mathematics, 80, SpringerVerlag, New York, 1996.
[54] V. Roman’kov, Unsolvability of the endomorphic reducibility problem in free nilpotent groups and in free rings,
Algebra and Logic, 16 (1977) 310–320.
[55] D. Segal, Decidable properties of polycyclic groups, Proc. London Math. Soc. (3), 61 (1990) 497–528.
[56] A. Shamir, How to share a secret, Comm. ACM, 22 (1979) 612–613.
[57] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,
SIAM J. Comput., 26 (1997) 1484–1509.
[58] V. Shpilrain, Search and witness problems in group theory, Groups Complex. Cryptol., 2 (2010) 231–246.
[59] D. A.Suprunenko and M. S. Garauk, Linear groups with Engel’s condition, (Russian), Dokl. Akad. Nauk BSSR, 6
(1962 277–280.
[60] A. V. Sutherland, Structure computation and discrete logarithms in finite abelian p-groups, Math. Comp., 80
(2011) 477–500.
[61] S. Sze, D. Kahrobaei, R. Dambreville and M. Dupas, Finding n-th roots in nilpotent groups and applications in
cryptology, Int. J. Pure Appl. Math., 70 (2011) 571–593.
[62] J. S. Wilson, Two-generator conditions for residually finite groups, Bull. London Math. Soc., 23 (1991) 239–248.
[63] M. Zorn, Nilpotency of finite groups, Bull. Amer. Math. Soc., 42 (1936) 485–486.
Volume 9, Issue 4 - Serial Number 4
Proceedings of the conference "Engel conditions in groups"- Bath-UK-2019
December 2020
Pages 231-250
  • Receive Date: 16 September 2019
  • Revise Date: 29 January 2020
  • Accept Date: 08 February 2020
  • Published Online: 01 December 2020