Diophantine cryptography over infinite groups

V. A. Romankov

Prikladnaâ diskretnaâ matematika, no. 2 (2012), pp. 15-42.

Résumé

Here, a short survey is presented on the group-based cryptography that is a contemporary area of an activity which explores how abstract infinite groups can be used as platforms for constructing cryptographic primitives, systems and protocols. Studying in the area is developed by the methods of group theory, complexity theory and theory of computations. Undecidable and allegebly hard algorithmic problems from group theory are the base of the constructing. Different complexity aspects of the algorithmic problems and the corresponding search problems are discussed. The universality of the diophantine language in cryptography is explained, and its combining role is noted. The free metabelian groups as platforms for constructing cryptographic systems and protocols is suggested. Some reasons for the suggestion including a decidability of the word problem and existing normal forms of elements are stated. One more reason is a non-decidability of the equation solvability problem and non-decidability of the endomorphism problem in these groups that follow from a non-decidability of the 10-th Hilbert Problem. It is promised that the considerations of the paper will be used in the forthcoming paper by the author and S. Y. Erofeev for constructing a possibly one-way function and an autentification protocol with zero knowledge on a free metabelian group.

Détail

Keywords: group-based cryptography, algorithmic problem, search problem, generic complexity, diophantine language, free metabelian group, endomorphism problem.
Mots-clés : diophantine cryptography

Bibliographie

[1] Myasnikov A., Shpilrain V., Ushakov A., Group-based cryptography, Advances courses in Math., CRM, Barselona, Birkhäuser Verlag, Basel–Berlin–New York, 2008, 183 pp. | MR | Zbl

[2] Myasnikov A., Shpilrain V., Ushakov A., Non-commutative cryptography and complexity of group-theoretic problems, Amer. Math. Soc. Surveys and Monographs, Amer. Math. Soc., Providence, RI, 2011, 385 pp. | MR | Zbl

[3] http://www.grouptheory.info/PersonalPages/Shpilrain,Vladimir/CryptologyePrintArchive

[4] Anshel I., Anshel M., Goldfeld D., “An algebraic method for public-key cryptography”, Math. Res. Lett., 6 (1999), 287–291 | MR | Zbl

[5] Markov A. A., “Osnovy algebraicheskoi teorii kos”, Trudy Matem. in-ta AN SSSR, 16, 1945, 3–53 | MR | Zbl

[6] Dehornoy P., Braids and self-distributivity, Progress in Math., 192, Birkhäuser Verlag, Basel–Berlin–New York, 2000, 623 pp. | MR | Zbl

[7] Lin V. Ya., “Kosy Artina i svyazannye s nimi gruppy i prostranstva”, Itogi nauki i tekhn. Algebra. Geometriya. Topologiya, 17, VINITI, M., 1983, 159–227 | MR | Zbl

[8] Dehornoy P., “Braid-based cryptography”, Group theory, statistics and cryptography, Contemp. Math., 360, Amer. Math. Soc., Providence, RI, 2004, 5–33 | DOI | MR | Zbl

[9] Mahlburg K., An overview of braid group cryptography, , 2004 http://www.math.wisc.edu/~boston/mahlburg.pdf

[10] Neiman Kh., Mnogoobraziya grupp, Mir, M., 1974, 264 pp. | MR

[11] Romankov V. A., “O nerazreshimosti problemy endomorfnoi svodimosti v svobodnykh nilpotentnykh gruppakh i v svobodnykh koltsakh”, Algebra i logika, 16:4 (1977), 457–471 | MR

[12] Romankov V. A., “Ob uravneniyakh v svobodnykh metabelevykh gruppakh”, Sib. matem. zh., 40:3 (1979), 671–673 | MR

[13] Grigoriev D., Shpilrain V., “Zero-knowledge autentification schemes from actions on graphs, groups and rings”, Ann. Pure Appl. Logic, 162 (2010), 194–200 | DOI | MR | Zbl

[14] Matiyasevich Yu. V., “Diofantovost perechislimykh mnozhestv”, Dokl. AN SSSR, 191:2 (1970), 279–282 | MR | Zbl

[15] Matiyasevich Yu. V., “Diofantovo predstavlenie perechislimykh predikatov”, Izv. AN SSSR. Ser. matem., 35:1 (1971), 3–30 | MR | Zbl

[16] Matiyasevich Yu. V., Desyataya problema Gilberta, Nauka, M., 1993, 223 pp. | MR | Zbl

[17] Shpilrain V., Zapata G., “Using decision problems in public key cryptography”, Groups. Complexity. Cryptology, 1 (2009), 33–40 | DOI | MR

[18] Shpilrain V., Zapata G., “Using the subgroup membership problem in public key cryptography”, Contemp. Math., 418, Amer. Math. Soc., Providence, RI, 2006, 169–179 | DOI | MR

[19] Shpilrain V., Zapata G., “Combinatorial group theory and public key cryptography”, Applicable Algebra in Engineering Communication and Computing, 17 (2006), 291–302 | DOI | MR | Zbl

[20] Kurt Y., A new key exchange primitive based on the triple decomposition problem, Preprint http://eprint.iacr.org/2006/378

[21] Birget J.-C., Magliveras S., Sramka M., “On public-key cryptosystems based on combinatorial group theory”, Tatra Mountains Math. Publ., 33 (2006), 137–148 | MR | Zbl

[22] Novikov P. S., “Ob algoritmicheskoi nerazreshimosti problemy tozhdestva slov v teorii grupp”, Trudy Matem. in-ta AN SSSR, 44, 1955, 3–143 | MR | Zbl

[23] Novikov P. S., “Nerazreshimost problemy sopryazhennosti v teorii grupp”, Izv. AN SSSR. Ser. matem., 18:6 (1954), 485–524 | MR | Zbl

[24] Adyan S. I., “Nerazreshimost nekotorykh algoritmicheskikh problem v teorii grupp”, Trudy Mosk. matem. obschestva, 6, 1957, 231–298 | MR | Zbl

[25] Remeslennikov V. N., Romankov V. A., “Teoretiko-modelnye i algoritmicheskie voprosy teorii grupp”, Itogi nauki i tekhn. Algebra. Geometriya. Topologiya, 21, VINITI, M., 1983, 3–79 | MR | Zbl

[26] Adyan S. I., Durnev V. G., “Algoritmicheskie problemy dlya grupp i polugrupp”, Uspekhi matem. nauk, 55:2 (2000), 3–94 | MR | Zbl

[27] Miller III C. F., “Decision problems for groups – survey and reflections”, Algorithms and Classification in Combinatorial Group Theory, Springer Verlag, Berlin–Heidelberg–New York, 1992, 1–60 | DOI | MR

[28] Sims C. C., Computation with finitely presented groups, Cambridge Univ. Press, Cambridge, 1994, 604 pp. | MR

[29] Holt D. F., Eick B., O'Brien E. A., Handbook of computational group theory, Chapman Hall/CRC, London, 2005, 414 pp. | MR | Zbl

[30] Detinko A., Eick B., Flannery D., “Computing with matrix groups”, London Math. Soc. Lect. Notes Ser., 387, 2011, 256–270 | MR | Zbl

[31] Mikhailova K. A., “Problema vkhozhdeniya dlya pryamykh proizvedenii grupp”, Dokl. AN SSSR, 119 (1958), 1103–1105 | Zbl

[32] Kargapolov M. I., Merzlyakov Yu. I., Osnovy teorii grupp, Lan, M., 2009, 288 pp. | MR

[33] Kurosh A. G., Teoriya grupp, Fizmatgiz, M., 2008, 808 pp.

[34] Garside F. A., “The braid group and other groups”, Quart. J. Math., 20:1 (1969), 235–254 | DOI | MR | Zbl

[35] Gebhardt V., “Conjugacy search in braid groups from a braid-based cryptography point of view”, Applicable Algebra in Engineering Communication and Computing, 17 (2006), 219–238 | DOI | MR | Zbl

[36] Gebhardt V., “A new approach to the conjugacy problem in Garside groups”, J. Algebra, 292 (2005), 282–302 | DOI | MR | Zbl

[37] Petrides G., “Cryptoanalisis of the public key cryptosystem based on the word problem on the Grigorchuk groups”, LNCS, 2898, 2003, 234–244 | MR | Zbl

[38] Magyarik M. R., Wagner N. P., “A public key cryptosystem based on the word problem”, LNCS, 196, 1985, 19–36 | MR | Zbl

[39] Fine B., Habeeb M., Kahrobaei D., Rosenberger G., “Survey and open problems in non-commutative cryptography”, JP J. Algebra, Number Theory and Applications, 21 (2011), 1–40 | MR | Zbl

[40] Papadimitriou C., Computation complexity, Addison-Wesley, Boston, 1994, 523 pp. | MR | Zbl

[41] S. Rudich, A. Wigderson (eds.), Computational complexity theory, Amer. Math. Soc. Institute for Advanced Study, IAS/Park City Math. Series, 10, Amer. Math. Soc., Providence, RI, 2004, 389 pp. | MR | Zbl

[42] Gurevich Y., “Average case completeness”, J. Comput. Syst. Sci., 42 (1991), 346–398 | DOI | MR | Zbl

[43] Levin L., “Average case complete problems”, SIAM J. Comput., 15 (1986), 285–286 | DOI | MR | Zbl

[44] Kapovich I., Myasnikov A., Shupp P., Shpilrain V., “Average-case complexity and decision problems in group theory”, Adv. Math., 190 (2005), 343–359 | DOI | MR | Zbl

[45] Kapovich I., Myasnikov A., Shupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264 (2003), 665–694 | DOI | MR | Zbl

[46] Celler F., Leedham-Green C. R., Murray S. H., et al., “Generating random elements of a finite group”, Comm. Algebra, 23:3 (1995), 4931–4948 | DOI | MR | Zbl

[47] Borovik A., Myasnikov A., Shpilrain V., “Measuring sets in infinite groups”, Contemp. Math., 298, Amer. Math. Soc., Providence, RI, 2002, 21–42 | DOI | MR | Zbl

[48] Klee V., Minty G., “How good is the simplex algorithm?”, Inequalities. Proc. Third. Symp. (Univ. California), Academic Press, California, 1972, 159–175 | MR

[49] Khachiyan L. A., “Polinomialnyi algoritm v lineinom programmirovanii”, Dokl. AN SSSR, 244:5 (1979), 1093–1096 | MR | Zbl

[50] Vershik A. M., Sporyshev P. V., “Ogranichenie srednego chisla shagov v simpleks-metode i problemy asimptoticheskoi integralnoi geometrii”, Dokl. AN SSSR, 271:5 (1983), 1044–1048 | MR | Zbl

[51] Smale S., “On the average number of steps of the simplex method of linear programming”, Math. Programming, 27 (1983), 241–262 | DOI | MR | Zbl

[52] Gilman R., Myasnikov A. G., Miasnikov A. D., Ushakov A., “Report on generic case complexity”, Vestnik Omskogo universiteta, 2007, Spets. vyp. Kombinatornye metody algebry i slozhnost vychislenii, 103–110

[53] Cook S. A., Mitchell D. G., “Finding hard instances of the satisfiability problem: A survey”, Satisfiability problem: Theory and Applications, 35, Amer. Math. Soc., Providence, RI, 1997, 1–17 | MR | Zbl

[54] Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, Springer Verlag, Berlin–New York, 2004, 546 pp. | MR | Zbl

[55] Erofeev S. Yu., “Diofantovost diskretnogo logarifma”, Prikladnaya diskretnaya matematika, 2011, Prilozhenie No 4, 31–32

[56] Erofeev S. Yu., “Diofantovost diskretnogo logarifma”, Vestnik Omskogo universiteta, 2010, no. 4, 13–15

[57] Goldreich O., Foundations of cryptography, v. 1, Cambridge Univ. Press, Cambridge, 2001, 451 pp. ; v. 2, 2004, 798 pp. | MR | Zbl

[58] Erofeev S. Yu., “Skhemy postroeniya dvushagovo odnostoronnikh funktsii”, Vestnik Omskogo universiteta, 2011, no. 4, 15–18

[59] Rybalov A. N., “O genericheskoi nerazreshimosti desyatoi problemy Gilberta”, Vestnik Omskogo universiteta, 2011, no. 4, 19–22

[60] Timoshenko E. I., Endomorfizmy i universalnye teorii razreshimykh grupp, Izd-vo NGTU, Novosibirsk, 2011, 327 pp.

[61] Myasnikov A., Roman'kov V., Ushakov A., Vershik A., “The word and geodesic problems in free solvable groups”, Trans. Amer. Math. Soc., 362 (2010), 4655–4682 | DOI | MR | Zbl

[62] Vassileva S., “Polynomial time conjugacy in wreath products and free solvable groups”, Groups. Complexity. Cryptology, 3 (2011), 105–120 | DOI | MR | Zbl

[63] Romanovskii N. S., “O nekotorykh algoritmicheskikh problemakh dlya razreshimykh grupp”, Algebra i logika, 13:1 (1974), 26–34 | MR

[64] Timoshenko E. I., “Algoritmicheskie problemy dlya metabelevykh grupp”, Algebra i logika, 12:2 (1973), 232–240

[65] Noskov G. A., “O sopryazhennosti v metabelevykh gruppakh”, Matematicheskie zametki, 31:4 (1982), 495–507 | MR | Zbl

[66] Ventura E., Romankov V. A., “Problema skruchennoi sopryazhennosti dlya endomorfizmov metabelevykh grupp”, Algebra i logika, 48:2 (2009), 157–173 | MR

[67] Baumslag G., Cannonito F., Robinson D. J. S., “The algorithmic theory of finitely generated metabelian groups”, Trans. Amer. Math. Soc., 344 (1994), 629–648 | DOI | MR | Zbl

[68] Groves J. R. J., Miller III C. F., “Recognizing free metabelian groups”, Illinois J. Math., 30:2 (1986), 246–254 | MR | Zbl

[69] Baumslag G., Mikhailov R., Orr K. E., A new look at finitely generated metabelian groups, 2012, 17 pp., arXiv: 1203.5431[math.GR]

[70] Hall P., “Nilpotent groups”, Canad. Math. Cong. Summer Sem., University of Alberta, Vankuver, 1957, 12–30

[71] Kholl M., Teoriya grupp, IL, M., 1962, 467 pp.

[72] Stroud P., Ph. D. Thesis, Cambridge, 1966, 121 pp.

[73] Segal D., “Words: notes on verbal width in groups”, London Math. Soc. Lect. Notes, 361, Cambridge Univ. Press, Cambridge, 2009, 215 pp. | MR | Zbl

[74] Allambergenov Kh. S., Romankov V. A., “Proizvedeniya kommutatorov v gruppakh”, Dokl. AN Uz. SSR, 4 (1984), 14–15 | MR | Zbl

[75] Jones J., “Universal diophantine equation”, J. Symbolic Logic, 47:3 (1982), 549–571 | DOI | MR | Zbl