On constructing possibly one-way functions based on the non-decidability of the endomorphism problem in groups

S. Y. Erofeev ; V. A. Romankov

Prikladnaâ diskretnaâ matematika, no. 3 (2012), pp. 13-24.

Résumé

The paper considers a schema for constructing a possibly one-way function on a group with the decidable word problem and undecidable endomorphism problem. Possible prerequisites for reliability of the proposed schema are analyzed. A corresponding authentication protocol with zero knowledge is proposed as an application. It is noted that for its security a more strong assumption on the undecidability of the two-level endomorphism problem is needed.

Détail

Keywords: one-way function, endomorphism problem
Mots-clés : authentication protocol.

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 p. pp. | MR | Zbl

[3] Romankov V. A., “Diofantova kriptografiya na beskonechnykh gruppakh”, Prikladnaya diskretnaya matematika, 2012, no. 2, 15–42

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

[5] Goldwasser S., Bellare M., Lecture Notes on Cryptography, MIT, Cambridge, 2008

[6] Sipser M., Introduction to the theory of computation, PWS Publishing, 1997, 416 pp. | Zbl

[7] Levin L. A., “One-way Functions and Pseudorandom Generators”, Combinatorica, 7:4 (1987), 357–363 | DOI | MR | Zbl

[8] Levin L. A., “Odnostoronnie funktsii”, Problemy peredachi informatsii, 39:1 (2003), 103–117 | MR | Zbl

[9] Kozhevnikov A. A., Nikolenko S. I., “O polnykh odnostoronnikh funktsiyakh”, Problemy peredachi informatsii, 45:2 (2009), 101–118 | MR | Zbl

[10] Romankov V. A., “Ob uravneniyakh v svobodnykh metabelevykh gruppakh”, Sibirskii matematicheskii zhurnal, 20:3 (1979), 671–673 | 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] Matiyasevich Yu. V., “Diofantovost perechislimykh mnozhestv”, Dokl. AN SSSR, 191:2 (1970), 279–282 | MR | Zbl

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

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

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

[16] 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

[17] Shpilrain V., Zapata G., “Combinatorial group theory and public key cryptography”, Applicab. Alg. Eng. Comm. Comp., 17 (2006), 291–302 | DOI | MR | Zbl

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

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

[20] Lohrey M., “Word problems on compressed words”, Automata, Languages and Programming, LNCS, 3142, 2004, 906–918 | MR | Zbl

[21] Lohrey M., Schleimer S., “Efficient computation in groups via compression”, LNCS, 4649, 2007, 249–258 | Zbl

[22] Scheimer S., “Polynomial-time word problems”, Comment. Math. Helv., 83:4 (2008), 741–765 | DOI | MR

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

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

[25] Menezes A. J., van Oorschot P. C., Vanstone S. A., Handbook of Applied Cryptography, CRC Press, 1996, 816 pp.

[26] Romankov V. A., Vvedenie v kriptografiyu, Kurs lektsii, Forum, M., 2012, 240 pp.

[27] Matijasevich Y. V., Robinson J., “Reduction of an arbitrary diophantine equation to one in 13 unknowns”, Acta Arithmetica, 27 (1975), 521–553 | MR

[28] Matijasevich Y. V., “Some purely mathematical results inspired by mathematical logic”, Logic, foundations of mathematics and computability theory, Proc. Fifth Intern. Congr. Logic, Methodology and Philos. of Sci. (Univ. Western Ontario, London, Ont., 1975), Reidel, Dordrecht, Holland, 1977, 121–127 | MR

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

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

[31] Makanin G. S., “Uravneniya v svobodnoi gruppe”, Izv. AN SSSR. Ser. matem., 46:6 (1982), 1199–1273 | MR | Zbl

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

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

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

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

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

[37] 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

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

[39] 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

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