RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

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

This article is cited 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.

UDC: 512.62



© Steklov Math. Inst. of RAS, 2024