Prikladnaya Diskretnaya Matematika
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Prikl. Diskr. Mat.:

Personal entry:
Save password
Forgotten password?

Prikl. Diskr. Mat., 2012, Number 2(16), Pages 15–42 (Mi pdm362)  

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

Abstract: 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.

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

Full text: PDF file (675 kB)
References: PDF file   HTML file
UDC: 512.62

Citation: V. A. Romankov, “Diophantine cryptography over infinite groups”, Prikl. Diskr. Mat., 2012, no. 2(16), 15–42

Citation in format AMSBIB
\by V.~A.~Romankov
\paper Diophantine cryptography over infinite groups
\jour Prikl. Diskr. Mat.
\yr 2012
\issue 2(16)
\pages 15--42

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. 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  mathnet
    2. V. A. Roman'kov, “Linear decomposition method in analyzing hidden information protocols on algebraic platforms”, Algebra and Logic, 54:1 (2015), 81–87  mathnet  crossref  crossref  mathscinet  isi
    3. 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  mathnet  crossref
    4. A. N. Rybalov, “O genericheskoi slozhnosti problemy razreshimosti sistem diofantovykh uravnenii v forme Skolema”, PDM, 2017, no. 37, 100–106  mathnet  crossref
    5. A. N. Rybalov, “O genericheskoi nerazreshimosti desyatoi problemy Gilberta dlya polinomialnykh derevev”, PDM, 2019, no. 44, 107–112  mathnet  crossref  elib
    6. E. I. Timoshenko, “A basis for a partially commutative metabelian group”, Izv. Math., 85:4 (2021), 813–822  mathnet  crossref  crossref  isi
  • Прикладная дискретная математика
    Number of views:
    This page:685
    Full text:311
    First page:1

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021