This article is cited in 6 scientific papers (total in 6 papers)
Mathematical Methods of Cryptography
Diophantine cryptography over infinite groups
V. A. Romankov
Omsk State University, Omsk, Russia
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.
group-based cryptography, algorithmic problem, search problem, generic complexity, diophantine language, diophantine cryptography, free metabelian group, endomorphism problem.
PDF file (675 kB)
V. A. Romankov, “Diophantine cryptography over infinite groups”, Prikl. Diskr. Mat., 2012, no. 2(16), 15–42
Citation in format AMSBIB
\paper Diophantine cryptography over infinite groups
\jour Prikl. Diskr. Mat.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
S. Yu. Erofeev, V. A. Romankov, “O postroenii vozmozhno odnostoronnikh funktsii na osnove algoritmicheskoi nerazreshimosti problemy endomorfnoi svodimosti v gruppakh”, PDM, 2012, no. 3(17), 13–24
V. A. Roman'kov, “Linear decomposition method in analyzing hidden information protocols on algebraic platforms”, Algebra and Logic, 54:1 (2015), 81–87
M. N. Gornova, E. G. Kukina, V. A. Romankov, “Kriptograficheskii analiz protokola autentifikatsii Ushakova–Shpilraina, osnovannogo na probleme binarno skruchennoi sopryazhennosti”, PDM, 2015, no. 2(28), 46–53
A. N. Rybalov, “O genericheskoi slozhnosti problemy razreshimosti sistem diofantovykh uravnenii v forme Skolema”, PDM, 2017, no. 37, 100–106
A. N. Rybalov, “O genericheskoi nerazreshimosti desyatoi problemy Gilberta dlya polinomialnykh derevev”, PDM, 2019, no. 44, 107–112
E. I. Timoshenko, “A basis for a partially commutative metabelian group”, Izv. Math., 85:4 (2021), 813–822
|Number of views:|