Applications of automaton groups in cryptography

References

• I. Anshel, M. Anshel, and D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Let. 6(3) (1999), pp. 287–291.
   Web of Science ®Google Scholar
• L. Bartholdi, V.A. Kaimanovich, and V.V. Nekrashevych, On amenability of automata groups, Duke Math. J. 154(3) (2010), pp. 575–598.
   Web of Science ®Google Scholar
• C. Battarbee, D. Kahrobaei, L. Perret, and S.F. Shahandashti, A subexponential quantum algorithm for the semidirect discrete logarithm problem, 4th PQC NIST Conference 2022, pp. 1–27. https://ia.cr/2022/1165.
   Google Scholar
• A. Childs, D. Jao, and V. Soukharev, Constructing elliptic curve isogenies in quantum subexponential time, J. Math. Cryptol. 8(1) (2014), pp. 1–29.
   Google Scholar
• E. Di Domenico, G.A. Fernández-Alcober, M. Noce, and A. Thillaisundaram, p-Basilica groups, Mediterr. J. Math. 19(6) (2022), pp. 275.
   Web of Science ®Google Scholar
• B. Eick and D. Kahrobaei, Polycyclic groups: A new platform for cryptology?, arXiv Mathematics e-prints, available in math/0411077, 2004.
   Google Scholar
• D. Garber, D. Kahrobaei, and H.T. Lam, Length-based attacks in polycyclic groups, J. Math. Cryptol.9(1) (2015), pp. 33–43.
   Google Scholar
• D. Garber, S. Kaplan, M. Teicher, B. Tsaban, and U. Vishne, Length-based conjugacy search in the braid group, Contemp. Math. 418 (2006), pp. 75–87.
   Google Scholar
• M. Garzon and Y. Zalcstein, The complexity of Grigorchuk groups with application to cryptography, Theoret. Comput. Sci. 88(1) (1991), pp. 83–98.
   Web of Science ®Google Scholar
• R.I. Grigorchuk, Degrees of growth of finitely generated groups and the theory of invariant means, Izv. Akad. Nauk SSSR Ser. Mat. 48(5) (1984), pp. 939–985.
   Google Scholar
• R.I. Grigorchuk and D. Grigoriev, Key agreement based on automaton groups, Groups Complex. Cryptol. 11(2) (2019), pp. 77–81. doi:10.1515/gcc-2019-2012
   Google Scholar
• R.I. Grigorchuk and J.S. Wilson, The conjugacy problem for certain branch groups, Tr. Mat. Inst. Steklova. Din. Sist., Avtom. I Beskon. Gruppy 231 (2000), pp. 215–230.
   Google Scholar
• R.I. incollection Grigorchuk and A. Żuk, On a torsion-free weakly branch group defined by a three state automaton, in International Conference on Geometric and Combinatorial Methods in Group Theory and Semigroup Theory (Lincoln, NE, 2000), Vol. 12, 2002, pp. 223–246. doi:10.1142/S0218196702001000
   Google Scholar
• J. Gryak and D. Kahrobaei, The status of polycyclic group-based cryptography: A survey and open problems, Groups Complex. Cryptol. 8(2) (2016), pp. 171–186.
   Google Scholar
• D. Hofheinz and R. Steinwandt, Cryptanalysis of a public key Cryptosystem based on Grigorchuk Group, Unpublished.
   Google Scholar
• D. Kahrobaei, R. Flores, and M. Noce, Group-based cryptography in the quantum era, Not. Am. Math. Soc. 70(05) (2023), pp. 752–763.
   Google Scholar
• D. Kahrobaei, R. Flores, M. Noce, M. Habeeb, and C. Battarbee, Applications of group theory in cryptography: Post-quantum group-based cryptography, Vol. 278, The Mathematical Surveys and Monographs series of the American Mathematical Society, in press.
   Google Scholar
• D. Kahrobaei and B. Khan, Nis05-6: A non-commutative generalization of ElGamal key exchange using polycyclic groups, IEEE Globecom, 2006, pp. 1–5.
   Google Scholar
• D. Kahrobaei and C. Koupparis, Non-commutative digital signatures, Groups Complex. Cryptol. 4(2) (2012), pp. 377–384. doi:10.1515/gcc-2012-0019
   Google Scholar
• K.H. Ko, S.J. Lee, J.H. Cheon, J.W. Han, J. Kang, and C. Park, New public-key cryptosystem using braid groups, in Advances in Cryptology – CRYPTO, M. Bellare, ed., Springer, Berlin, 2000, pp. 166–183.
   Google Scholar
• G. Kuperberg, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, SIAM J. Comput. 35(1) (2005), pp. 170–188.
   Web of Science ®Google Scholar
• G. Kuperberg, The hidden subgroup problem for infinite groups, 2020, www.math.ucdavis.edu.
   Google Scholar
• Y.G. Leonov, The conjugacy problem in a class of 2-groups, Mat. Zametki 64(4) (1998), pp. 573–583.
   Google Scholar
• I. Lysenok, A. Myasnikov, and A. Ushakov, The conjugacy problem in the grigorchuk group is polynomial time decidable, Groups Geom. Dyn. 4(4) (2010), pp. 813–833.
   Web of Science ®Google Scholar
• A.G. Myasnikov and S. Vassileva, Log-space conjugacy problem in the grigorchuk group, Groups Complex. Cryptol. 9(1) (2017), pp. 77–85.
   Google Scholar
• G. Petrides, Cryptanalysis of the public key cryptosystem based on the word problem on the Grigorchuk groups, in Cryptography and coding, K. G. Paterson, ed., Springer, Berlin, 2003, pp. 234–244.
   Google Scholar
• R.I. Grigorchuk, V.I. Sushchansky, and V. Nekrashevych, Automata, dynamical systems, and groups, Trudy Matemat. Inst. Im. VA Steklova 231 (2000), pp. 134–214.
   Google Scholar
• O. Regev, A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space, arXiv preprint quant-ph 2004.
   Google Scholar
• A.V. Rozhkov, The conjugacy problem in an automorphism group of an infinite tree, Mat. Zametki64(4) (1998), pp. 592–597. doi:10.1007/BF02314633
   Google Scholar
• P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26(5) (1997), pp. 1484–1509. doi:10.1137/S0097539795293172
   Web of Science ®Google Scholar
• V. Shpilrain, Search and witness problems in group theory, Groups Complex. Cryptol. 2(2) (2010), pp. 231–246.
   Google Scholar
• J.P. Wächter and A. Weiss, An automaton group with PSPACE-Complete Word Problem, Theory of Computing Systems, abs/1906.03424 2022.
   Google Scholar
• N.R. Wagner and M.R. Magyarik, A public-key cryptosystem based on the word problem, in Advances in cryptology (Santa Barbara, Calif., 1984), G. R. Blakley and D. Chaum, eds., Springer, Berlin, 1985, pp. 19–36. doi:10.1007/3-540-39568-7_3
   Google Scholar
• J.S. Wilson and P.A. Zalesskii, Conjugacy separability of certain torsion groups, Arch. Math. (Basel)68(6) (1997), pp. 441–449. doi:10.1007/s000130050076.
   Web of Science ®Google Scholar
• A. Zuk, Automata groups – topics in noncommutative geometry, Clay Math. Proc., 16, Amer. Math. Soc., Providence, RI, 2012, pp. 165–196.
   Google Scholar
• Z. Šunić and E. Ventura, The conjugacy problem in automaton groups is not solvable, J. Algebra 364 (2012), pp. 148–154.
   Web of Science ®Google Scholar