26 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2018. № 10
1. On Post Quantum and Multivariate Cryptography, public key schemes approach. Post 
Quantum Cryptography (PQC) serves for the research of asymmetric cryptographic algorithms, 
which can be potentially resistant against attacks based on the use of a quantum computer. 
Multivariate cryptography is one of the oldest directions of PQC. It uses, as security tools, a non-
linear polynomial transformations f of kind:
x1 → f1(x1, x2, …, xn), x2 → f2(x1, x2, …, xn), ..., xn → fn(x1, x2, …, xn)
acting on the affine space Kn, where fi, i = 1, 2, ..., n, from K[x1, x2, …, xk] are multivariate polyno-
mials given in a standard form, i. e. via a list of monomials in a chosen order (see [1]).
The most popular form is the usage of a very special map f in a public key mode. It means the 
key holder Alice has some initial data D, which allow her to solve the equation f(x) = b, where b 
© V.A. Ustimenko, 2018
doi: https://doi.org/10.15407/dopovidi2018.10.026
UDC 519.1, 514.128
V.A. Ustimenko
Institute of Telecommunication and Global Information Space of the NAS of Ukraine, Kiev
Maria Curie-Sklodowska University, Lublin, Poland
E-mail: vasylustimenko@yahoo.pl
On new symbolic key exchange protocols 
and cryptosystems based on a hidden tame homomorphism
Presented by Corresponding Member of the NAS of Ukraine O.M. Trofimchuk
Multivariate cryptosystems are divided into public rules, for which tools of encryption are open for users and systems 
of the El Gamal type, for which the encryption function is not given in public, and, for its generation, the opponent 
has to solve a discrete logarithm problem in the affine Cremona group. Infinite families of transformations of a free 
module Kn over a finite commutative ring K such that the degrees of their members are not growing with iteration 
are called stable families of transformations. Such families are needed for practical implementations of multiva-
riate cryptosystems of the El Gamal type. New explicit constructions of such families and families of stable groups 
and semigroups of transformations of free modules are given. New methods of creation of cryptosystems, which use 
stable transformation groups and semigroups and homomorphisms between them, are suggested. The security of these 
schemes is based on a complexity of the decomposition problem for an element of the affine Cremona semigroup into 
a product of given generators. Proposed schemes can be used for the exchange of messages in a form of elements of 
a free module and for a secure delivery of multivariate maps, which could be encryption tools and instruments for 
digital signatures.
Keywords: Multivariate Cryptography, stable transformation groups and semigroups, problem of decomposition 
of a nonlinear multivariate map into given generators, wild and tame families of transformations, tame homomor-
phisms, key exchange protocols, cryptosystems, algebraic graphs.
27ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2018. № 10
On new symbolic key exchange protocols and cryptosystems based on a hidden tame homomorphism
and x are known and unknown elements of the free module Kn, but a public user Bob has only f 
given publicly in its standard form. Asymmetry means that Alice has tools for the encryption and 
decryption, but Bob has only an encryption procedure.
Public knowledge on f = fn (allows the adversary to create as many pairs of kind plaintext 
p-ciphertext c = f(p) as he/she wants. It makes the problem of practical design of such a crypto-
system to be a difficult task. First examples were based on families of quadratical bijective trans-
formations fn (see [1—3]), such choice implies a rather fast encryption process.
In [4], the idea of a multivariate Diffie—Hellman (DH) protocol was modified in various 
ways. It uses recent constructions of large families of stable subsemigroups of small degree in 
affine Cremona semigroups containing large cyclic semigroups.
In Section 2, we introduce new cryptographical protocols with the usage of the concept of a 
tame homomorphism of stable semigroups of affine transformations (homomorphic map, which 
is computable in polynomial time). The idea to exploit the complexity of word problem for the 
Cremona semigroup about the decomposition of a given polynomial transformation g from the 
semigroup into given generators is presented in Section 3.
The multivariate nature of collision maps allows us to use these algorithms for the safe ex-
change of multivariate transformations. Various deformation rules can be used for this purpose 
(see Section 4). Correspondents may use a family of invertible generators gn. Assume that one of 
them can generate the inverse of gn. Then the symbolic El Gamal type tahoma algorithms can be 
used by correspondents. They can use the inverse protocol to elaborate pairs of mutually invertible 
transformations. So, they can conduct the information exchange protected via the complexity of 
some difficult problem. Section 5 introduces the inverse of the group enveloped symbolic Diffie—
Hellman algorithm described in [4, 5].
The last section is devoted to the implementation of the algorithm of Section 3 via symbolic 
walks on graphs A(n, K) (see [6, 7]).
In all realizations of algorithms, we use stable subsemigroups S of the affine Cremona se-
migroup S(Kn) generated by special symbolic automata defined in terms of special algebraic 
graphs. The method of generation allows us to construct, for each bijective transformation of S, its 
inverse element. In fact, we use linguistic graphs defined in [8]. They are bipartite graphs with 
a special coloring of vertices such that, for each vertex, there is a unique neighbor of the selected 
color. We did not use the terminology and general technique of symbolic walks on linguistic 
graphs. In fact, for each family of graphs considered in the paper, an algorithm of generation of the 
corresponding stable semigroup was given in independent way.
2. Tame families and concept of stability. Let us consider basic algebraic objects of 
multiva riate cryptography, which are important for the choice of appropriate pairs of maps f, 
f –1 in both cases of public key approach or idea of asymmetric algorithms with protected en-
cryption rules.
Let us consider the totality SFn(K) of all rules f of kind:
x1 → f1(x1, x2, …, xn), x2 → f2(x1, x2, …, xn), ..., xn → fn(x1, x2, …, xn)
acting on the affine space Kn, where fi, i = 1, 2, …, n, for the given parameter n and a chosen com-
mutative ring K with the natural operation of composition. We refer to this semigroup as a semi-
group of formal transformations SFn(K) of free module K
n. In fact, it is a totality of all endo-
28 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2018. № 10
V.A. Ustimenko
morphisms of the ring K[x1, x2, …, xk] with the operation of their superposition. Each rule f from 
SFn(K) induces a transformation t(f), which sends the tuple (p1, p2, …, pn) into (f1(p1, p2, …, pn), 
f2(p, p2, …, pn), …, fn(p1, p2, …, pn)). The affine Cremona semigroup C(K
n) is a totality of all trans-
formations of kind t(f). The canonical homomorphism t: → t(f) maps the infinite semigroup 
SFn(K) onto a finite semigroup S(K
n) in the case of finite commutative ring K.
We refer to the pair (f, f ′) of elements SFn(K) such that ff ′and f ′f are two copies of the iden-
tical rule xi → xi, i = 1, 2, ..., n, as a pair of invertible elements. If (f, f ′) is such a pair, then the 
product t(f)}t(f ′) is an identity map. Let us consider the subgroup CFn(K) of all CFn(K)-inver-
ti ble elements of SFn(K) (group of formal maps). It means f is an element of CFn(K) if and only if 
there is f ′ such that ff ′ and f ′f are identity maps. It is clear that the image of a restriction of t on 
CFn(K) is the affine Cremona group Cn(K) of all transformations of K
n onto Kn, for which there 
exists a polynomial inverse.
We say that a family, of subsemigroups Sn of SFn(K) (or S(K
n) is stable of degree d, if the 
maximal degree of elements from Sn is an independent constant d, d > 2. If K is a finite commuta-
tive ring, then stable semigroup has to be a finite set. The brief observation of the known families 
of stable groups can be found in [4, 5] (see also [9—12]).
Let fn from SFn(K) be a family of nonlinear maps of degree bounded by constant d. We say
that fn form a tame family, if there is a family gn from SFn(K) of degree bounded by constant d′ such 
that fn gn = gn fn are identity maps. Let T1 and T2 be two elements from the group AGLn (K) of all 
affine bijective transformations, i. e., elements of the affine Cremona group of degree 1. Then we 
refer to f ′n = T1 fnT2 as linear deformation of fn. Obviously, f ′n is also a tame family of transforma-
tions, and the degrees of maps from this family are also bounded by d. The degrees of inverses of 
f ′n are bounded by d ′. Let Gn < SFn(K) be a stable family of subgroups of degree d, d . 2. Then the 
nonlinear representatives fn of Gn form a tame family of maps.
3. On the concept of tame homomorphism and related algorithms. Let G = Gn be a family of 
stable subsemigroups of SFn(K) (or S(K
n)), and let L = Lm, where m depends on n, be a family of 
stable subsemigroups of SFm(R) (or S(R
m)), where K and R are commutative rings. There are tame 
homomorphisms φ = φn from G into L, i. e. the value of φ at each point g from Gn is computable in 
polynomial time from n. Let us assume that there are semigroups B = Bn < Gn given by their ge-
nerators b1, b2, …, br. Let us assume that Alice has families of tame transformations π1 of Kn and of π2 of Rm. We assume that these data are known to Alice. She forms (ai = π1biπ1–1, a ′i = π2φ(bi)π2–1), 
i = 1, 2, ..., r and sends them to Bob. The elements of these pairs are given in their standard forms 
for representatives of SFn(K) or SFm(R).
3.1. Key exchange protocol. The list of pairs known for Bob defines a homomorphism Δ be-
tween the subsemigroups A = 〈a1, a2, ..., ar〉 and A′  = 〈a′1, a′2, , ..., a′r〉 given by its values on genera-
tors Δ (ai) = Δ (a′i) for i = 1, 2, ..., r. Bob forms a via his choice of word 1 21 2( ) ( )  ( ) tt kk ki i ia a a…  in 
the alphabet of generators of A such that ais ≠ ais+1 for s = 1, 2, ..., t–1. He sends a to Alice and keeps 
1 2
1 2
( ) ( ) ( ) ( ) t
t
kk k
i i ia a aa a ′ ′ ′′Δ = = …  as a collision element.
Alice knows the tame homomorphism φ and easily computes a′ as π2 φ(π1–1aπ1)π2–1.
Complexity remark. The adversary has to solve the word problem for the subsemigroup A, i. e., 
find the decomposition of a from A into generators a1, i = 1, 2, ..., t. The general algorithm to sol-
ve this problem in polynomial time in the variable n is unknown, as well as a procedure to get its 
solution in terms of quantum computations.
29ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2018. № 10
On new symbolic key exchange protocols and cryptosystems based on a hidden tame homomorphism
Remark 1. The condition of stability for the semigroups G and L and the usage of the tame 
transformations π1 and π2 allow us to estimate degrees of a and a collision map. If the maximal 
degrees of π1(n) and π1–1(n) are l1 and l ′1, the degrees of π1(n) and π1–1(n) are bounded by l2 and l2, 
and the stable groups G and L are of degrees d and d′, then the degrees of a and Δ(a) are boun-
ded by l1l ′1d and l2l ′2d ′.
Remark 2. One can use other natural conditions on π1 and π2. Let us assume that G < G1 and 
L < G2, where Gi are stable families of subsemigroups of degree t1, t1 - d and, t2 t2 - d′, respec-
tively. Let us consider normalizers N1 and N2 of G1 and G2 in the affine Cremona semigroups S(K
n) 
and S(Rm). It means that N1 and N2 are the totalities of transformations π from C(Kn) and C(Rm) 
such that πiGiπi–1, i = 1, 2, coincide with G1 and G2. We can take π1 of kind T1n1 and π2 of kind T2n2, 
where π1 of kind ni are elements of Ni, i = 1, 2, transformations T1 and T2 are elements of groups 
AGLn(K) and AGLm(R) Then the degrees of a and Δ(a) are restricted by t1 and t2.
Note that, in the case G = G1, L = G2, the degrees of a and Δ(a) are bounded by d and d′. We 
refer to the presented above algorithm as the tahoma word protocol. The term tahoma (name of 
shrift for word processing) stands for a tame homomorphism.
The protocol exploits the complexity of the word problem for a semigroup of polynomial trans-
formation of a free module. In the case considered in Remark 2, we use the term stable tahoma 
word protocol.
3.2. Inverse tahoma word protocol. Let us modify protocol 3.1 in the case of invertible ele-
ments φ(ai) with an assumption that their inverses are known to Alice. Instead of pairs (ai, a ′i), 
Alice forms (ai′, a*i), where a*i = (a ′i)–1, i = 1, 2, ..., r. Assume Bob gets the list of such pairs 
from Alice. Note that A′ is a group 〈a*i | i = 1, 2, ..., r〉. So, Bob is able to compute the antiisomor-
phism δ sending z from A into φ(z)–1, because he knows the values of δ on generators. Like in 
the previous protocol, Bob forms a via his choice of word 1 2
1 2
( ) ( )  ( ) t
t
kk k
i i ia a a…  in the alphabet 
of generators of A such that 
1
( ) ( )
s si i
a a
+
≠  for s = 1, 2, ..., t—1 and sends a to Alice. Now he keeps 
1 2 1
1 2 1
* * * *( ) ( ) ( ) ( ) ( )t t
t t
k k k k
i i i iaa a a a−
−
δ =  as an element of the collision pair. Alice computes her part of 
collision pair e = δ(a)–1 as π2φ(π1–1aπ1)π2–1.
3.3. Inverse tahoma cryptosystem. Both above-written protocols exploit the complexity of 
finding the decomposition of a into a product of given generating transformations. In the case 
of 3.2, Alice and Bob can securely communicate, because they are able to use mutually inverse 
transformations e and e–1 as encryption tools. Alice writes her message p and sends e(p) to Bob, 
who decrypts via the usage of δ(a). Bob can encrypt with δ(a) and Alice decrypts with e.
Remark 3. In the case where the transformation e = em of a free module Rm forms a stable 
family of degree d′, the adversary has to intercept O(md′) messages and conduct costly the li-
nearization attack to restore e and δ(a). So, the correspondents can safely exchange O(md′–1) 
messages. Note that, at any moment, Alice and Bob can start a new session of the inverse tahoma 
word protocol.
A different usage of homomorphisms of a subsemigroup of the Cremona semigroup in the 
cryptosystem was considered in [13, 14].
4. On the safe exchange of symbolic transformations. The symbolic nature of the collision 
map can be used for a task that differs from the exchange of keys. We refer to it as the usage of DH 
deformation symbolic rules.
30 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2018. № 10
V.A. Ustimenko
Let Alice have a free module Kn over a commutative ring K. She has a subset Ω of Kn and a 
polynomial map f: Kn → Kn such restriction of f|Ω is an injective map from Ω onto f(Ω) = Γ. 
Additionally, Alice has an algorithm to solve, in polynomial time, the equation x = b with respect 
to the unknown x from Ω and b from Ω.
Alice and Bob use the tahoma word protocol or symbolic Diffie—Hellman protocol to ela-
borate the collision map g acting on Kn. After this step, Alice sends Ω and the transformation 
h = f + g to Bob.
Now Bob can get f as h—g. He writes a plaintext p from Ω and sends the ciphertext c = f(x). 
Alice uses her data for the decryption.
Remark 4. Note that a new algorithm is still asymmetric because Bob can encrypt, but not 
decrypt. The encryption rule is known a to trusted customer (Bob) but the adversary has no ac-
cess to it. In fact, such access is protected by the word problem in a semigroup of transformations 
of Kn or the discrete logarithm problem in the corresponding affine Cremona semigroup.
Other deformations. Alice and Bob agree (via the open channel) on a deformation rule D(f) 
for a multivatiate rule f from the affine Cremona semigroup. For example, it can be the multipli-
cation, i. e. f is the rule xi → fi(x1, x2, …, xn) , i = 1, 2, ..., n, and g is the rule xi → gi (x1, x2, …, xn), 
i = 1, 2, ..., n, and Alice sends a tuple of polynomials fi gi, i = 1, 2, ..., n. Bob uses the division to re-
store f. Instead of the addition deformation rule (sending xi → fn(x1, x2, …, xn) + gn(x1, x2, …, xn), 
i = 1, 2, ..., n), Alice can use a deformation with adding an element K[x1, x2, …, xk]n obtained from 
g via the usage of an s-time conducted derivation δs, where δ = d/dx1 + d/dx2 + ... + d/dxn 
(rule xi → fn(x1, x2, …, xn) + δsgn(x1, x2, …, xn), i = 1, 2, ..., n). The last deformation is interesting, 
because, in many cases, we can achieve the equality of degrees for f and D(f). It is easy to con-
tinue this list of possible deformation rules.
Remark 5. Let us assume that Ω = Kn. So, f = fn is a bijection. Assume that the degrees of non-
linear maps fn are bounded by constant d. Let us assume that the adversary has option to inter-
cept some pairs plaintext-ciphertext (leakage from Bob’s data). In the case of interception of 
O(nd), the adversary has chance for a successful linearization attack and get the map f. For exam-
ple, if d = 3, then the linearization attack cost is O(n10). After that, the adversary has to find the 
inverse function for f like in the case of multivariate public key.
To prevent “transition to knowledge” of an encryption multivariate map, Alice (or Bob) can 
arrange a new session with the protocol and a transmission of a new deformed encryption rule, for 
which secret data for the decryption are known.
Remark 6. The technique of linearization attacks on nonbijective maps or maps fn of unbound-
ed degree and a low density is not developed yet.
5. On the inverse version of the group enveloped symbolic Diffie—Hellman key exchange 
protocol. Let G = Gn be a family of stable subsemigroups of SFn(K) (or S(Kn)) and L = Lm, where 
m depends on n, be a family of stable subsemigroups of SFm(R) (or S(R
m)), where K and R are 
commutative rings. There is a tame homomorphism φ = φn from G into L, i. e., the value of φ at each 
point g from Gn is computable in polynomial time from n. Let us assume that there are subgroups 
A = Am < Lm and B = Bn < Gn such that φ(b)a = aφ(b) for all elements a from A, b from B. Assume 
that two families of tame transformations π = π(n) and μ = μ(m) are chosen.
We assume that these data are known to Alice. She forms pairs (ci = π bi π–1, ci–1 = π bi–1π–1) 
and (di = μφ(bi)μ–1, di–1 = μφ(bi–1)μ–1), i = 1, 2, ..., r, where elements bi are from Bn, and they, in-
31ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2018. № 10
On new symbolic key exchange protocols and cryptosystems based on a hidden tame homomorphism
verses, and images are given in their standard form SFn(K) or SFm(R). She sends them to Bob. 
Let Δ be a homomorphism from 〈c1, c2, …, cr〉 to  〈d1, d2, …, dr〉 sending ci to di.
We present briefly the protocol of symbolic computations introduced in [4] and define its 
inverse version. We refer to this protocol as the group enveloped Diffie—Hellman scheme and 
inverse group enveloped Diffie—Hellman scheme.
5.1. Protocol. Alice takes a positive integer kA and a, a
–1 from Am and g′ from the semigroup 
G. She computes gA = μaφ(g′)a–1μ–1 and sends to Bob g = πg′π–1 together with gA.
Bob chooses a positive integer kB and an element c from R
m in 〈c1, c2, …, cr〉 (via the choice of a 
word in the alphabet c1, c2, …, cr. He computes gB = cg tc–1 with t = kB in standard form for elements 
of SFn(K) and sends it to Alice.
Bob computes a map Δ(c) gAt Δ (c–1), because he knows the decomposition of c and c–1 into 
their generators and keeps it as the collision map. 
Alice computes the collision map as μaφ(π–1gBsπ)a–1μ–1 with s = kA.
Remark 7. The adversary has to consider the group C′ = 〈 ci | i = 1, 2, ..., r〉 and solve the group 
enveloped discrete logarithm problem, i. e., to solve yg xy–1 = gB, where x is the unknown integer 
parameter and y from C ′ (possibly, via solving the decomposition problem of gB into semigroup 
generators c1, c2, …, cr, g (decomposition of elements into Cremona semigroup generators, the 
word problem in affine Cremona semigroup).
5.2. Inverse protocol. Let us assume that Alice can generate g′ such that φ(g′) is invertible 
and the inverse φ(g′)–1 is computable for her.
As in the previous algorithm, Alice takes a positive integer kA, elements a, a
–1 from Am, and g′ 
from the semigroup G. Now, she computes z = φ(g′)–1 and gA = μaza–1μ–1 and sends to Bob g = πg′π–1 
together with gA.
As in the previous algorithm, Bob chooses a positive integer kB and an element c from in 〈c1, c2, …, cr〉 via the choice of a word in the alphabet of generators. He computes gB = cg tc–1 with 
t = kB in standard form of SFn(K) and sends it to Alice.
Bob computes a map e = Δ(c)(gA )tΔ(c)–1, t = kB, because he knows the decomposition of c 
and c–1 into their generators and keeps e as his outcome of a collision.
Alice computes the map e–1 as μa φ(π–1(gB)sπ)a–1μ–1, s = kA.
5.3. Inverse group enveloped cryptosystem. Alice and Bob can communicate, because they 
have mutually inverse transformations e–1 and e.
1) Alice writes her message p and sends e–1(p) to Bob, who decrypts via the usage of e.
2) Bob can encrypt with e, and Alice decrypts with e–1.
Algorithm (5.3) was introduced in [4] as a desynchronized symbolic El Gamal algorithm.
6. Stable groups of cubical maps and a protocol based on the Cremona word problem. The 
following family of stable groups was considered in [4]. Let K be a commutative ring. We define 
A(n, K) as a bipartite graph with the point set P = Kn and a line set L = Kn (two copies of a Cartesian 
power of K are used). We will use brackets and parentheses to distinguish tuples from P and L. So, 
(p) = (p1, p2, …, pn) ∈ Pn and [l] = [l1, l2, …, ln] ∈ Ln. The incidence relation I = A(n, K) (or cor-
responding bipartite graph I) is given by the condition p I l if and only if the equations of the 
following kind hold:
p2—l2 = l1p1, p3—l3 = p1 l2, p4—l4 = l1p3, p5—l3 = p1l4, …,
32 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2018. № 10
V.A. Ustimenko
pn—ln = p1 ln–1 for odd n,
pn—ln = l1pn–1 for even n.
Let us consider the case of finite commutative ring K, |K| = m. As it instantly follows from the 
definition, the order of our bipartite graph A(n, K) is 2mn. The graph is m-regular. In fact, the 
neighbour of a given point p is given by the above equations, where the parameters p1, p2, …, pn are 
fixed elements of the ring, and the symbols l1, l2, …, ln are variables. It is easy to see that the value 
for l1 could be freely chosen. This choice uniformly establishes the values for l2, l3, …, ln. So, each 
point has precisely m neighbors. In a similar way, we observe the neighborhood of the line, which 
also contains m neighbors. We introduce the color ρ(p) of a point p and the color ρ(l) of a line l as 
parameters p1 and l1 respectively.
Graphs A(n, K) with coloring ρ belong to the class of Γ linguistic graphs considered in [8] 
(see also [15], which observes cryptographical applications of linguistic graphs). The linguistic 
graph Γ defined over a commutative ring K is a bipartite graph with partition sets Kn and Km that 
have color set L = K s and L = Kr, respectively. The projection ρ of a point x = (x1, x2, …, xn), or line 
y = [y1, y2, …, ym], on the tuple of their first s and r coordinates respectively, defines the colors 
of vertices. Each vertex has a unique neighbor with selected color. So, n + r = m + s. The incidence 
of linguistic graphs is given by a system of polynomial equations over the ring K.
In the case of a linguistic graph Γ with s = r = 1, the path consisting of its vertices v0, v1, 
v2, …, vk is uniquely defined by the initial vertex v0, and colours ρ(vi,), i = 1, 2, ..., k of other vertices 
from the path. So, the following symbolic computation can be defined. Take the symbolic point 
x = (x1, x2, …, xn), where xi are variables and the symbolic key, which is a string of polynomials 
f1, f2, ..., fk, from K[x1]. Form the path of vertices v0 = x, v1 such that v1Iv0 and ρ(v1) = f1(x1), v2 
such that v2Iv1 and ρ(v2) = f2(x1), ..., vk such that vkIvk–1 and ρ(vk) = fk(x1).
We use term symbolic point-to-point computation in the case of even k and talk about sym-
bolic point-to-line computation in the case of odd k. We note that the computation C of each 
coordinate of vi via the variables x1, x2, …, xn and polynomials f1, f2, ..., fk needs only arithme-
tical operations of addition and multiplication. As it follows from the definition of linguistic 
graph the final vertex vk (point or line) has coordinates (h1(x1), h2(x1, x2), h3(x1, x2, x3), ..., hn(x1, 
x2 ,…, xn)), where h1(x1) = fk(x1). Let us consider the map H = η(C): xi → hi(x1, x2, …, xn), i = 1, 
2, ..., n, which corresponds to the computation C. Assume that the equation b = fk(x1) has exa-
ctly one solution. Then the map H : xi → hi(x1, x2, …, xn), i = 1, 2, ..., n, is a bijective transforma-
tion. In the case of finite parameter k and finite densities of fi(x1), i = 1, 2, ..., n, the map H also 
has finite density. If all parameters deg(fi(x1)) are finite, then the map H has a linear degree in 
the variable n. Let us consider the totality ∑ = ∑(n, K) of point-to-point computations C with 
the symbolic key of kind fi(x1) = x1 + ai, i = 1, 2, ..., t, where the parameter t is even. In case of a 
linguistic graph with r = s = 1, we identify a computation C with the corresponding string (a1, 
a2, …, at). We assume that the empty string is also an element of ∑. The natural product of two 
strings given by tuples C1 = (a1, a2, …, at) and C2 = (b1, b2, …, bm) is a string C = C1 ◦ C2 = (a1, 
a2, …, at, b1 + at, b2 + at, …, bm + at). This product transforms ∑ to a semigroup. The map η' send-
ing C to η(C) is a homomorphism of ∑ into the affine Cremona group C(Kn). In the case of lin-
guistic graphs A(n, K), we can prove that the totality G(n, K) = η′(∑(n, K)) is a stable subgroup 
of degree 3 (see [5]).
33ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2018. № 10
On new symbolic key exchange protocols and cryptosystems based on a hidden tame homomorphism
We assume that a0 = 0 and say that a transformation η(C) is irreducible, if ai ≠ ai+2, i = 1, 
2, ..., t—2. If a1 ≠ at–1, and a2 ≠ at, we say that the irreducible computation C and the corresponding 
transformation η(C) are standard elements.
We have a natural homomorphism G(n + 1, K) onto G(n, K) induced by the homomorphism 
Δ from A(n + 1, K) onto A(n, K) sending a point (x1, x2, …, xn , xn + 1) to (x1, x2, …, xn) and a line 
[x1, x2, …, xn, xn + 1] to [x1, x2, …, xn]. It means that there is the well-defined projective limit A(K) 
of graphs A(n, K) and groups G(K) of groups G(n, K), when n is growing to infinity. As stated in 
[6] in the case of K = Fq, q > 2, the infinite graph A(Fq) is a tree.
It means that the group G(Fq) is a group of walks of even length on a q regular tree starting 
at the zero point with natural addition of them. A standard computation C defines a transfor-
mation η(C) in each group G(n, K), n . 2 and G(K). An irreducible transformation η(C) from 
G(K) has an infinite order.
Some examples of a tame homomorphism were considered in [4]. We are going to use the 
family of maps introduced below.
Let Δn, m,, n > m be a canonical homomorphism of A(n, K) onto A(m, K) corresponding to 
the procedure of deleting of the coordinates with indices m + 1, m + 2, …, n. This map defines 
the canonical homomorphism μ(n, m) of the group G(n, K) onto G(m, K).
Let R and K be finite extensions of a finite ring Q. Let us consider the diagram S(Rm) > 
> G(m, R) > G(m, Q) ← G(n, Q) < G(n, K) < S(Kn) with extreme nodes S(Rm) and S(Kn), where 
n > m, and the arrow corresponds to a canonical homomorphism μ = μ(n, m), n > m. Alice is going 
to use the stable tahoma word protocol with G = G(n, Q), G1 = G(n, K), L = G(m, K), L1 = G(m, R) 
(see Remark 2).
She can use the subgroups H1 = G1 and H2 = L1 of invertible elements instead of the whole 
normalizers N1 = N(G1) of a subgroup G1 in the affine Cremona group S(Kn), and N2 = N(L1) of 
subgroup in the Cremona group S(Rm). She also works with the affine subgroups AGLn(K) and 
AGLm(R).
Alice forms π1 = T1n1, where T1 ∈ AGL1n(K), n1 ∈ H1, and π2 = T2n2, where T2 ∈ AGL1m(R), 
n2 ∈ H2. She takes a subgroup, where G1 pt = π1Gπ1–1, L′ = π2L π2–1, and a homomorphism μ′ : x →→ π2(μ (π1xπ1–1))π2–1 between these semigroups. Alice will work with G ′, L′ and μ′ instead of G, 
L, μ. The map μ′ is tame for her, because she knows the decomposition of μ′ into the conjugation 
with π2, μ and the conjugation with π1.
6.1. Example of the stable tahoma word protocol. Alice takes a subgroup B of G′ given 
by the generators b1, b2, …, br and sends these generators to Bob together with a string μ′(bi), i = 1, 
2, ..., r. So, Bob knows just the restriction of μ′ on B given by its values on generators. He does 
not know the triple G′, L′ and μ′ with its decomposition into 3 maps. So, Bob selects a1, a2, …, as, 
where ai are elements of the alphabet {b1, b2, …, br}. He computes the composition b of selected 
powers of a transformation ai from S(K
n) and sends the standard form of b to Alice. He keeps a 
composition b′ of elements μ′(ai) according to the selected order. Alice gets b′ as μ′(b).
6.2. General complexity estimates for the cryptosystem in the case K = R = Q. Let us 
assume that Alice is going to use the homomorphism between A(n, K) and A(m, K) for m < n 
and m = O(n). We will count the number of arithmetical operations of the commutative ring K, 
which she needs to generate an element of g = G(n, K), which corresponds to the symbolic com-
putation with the key of length O(1).
34 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2018. № 10
V.A. Ustimenko
Counting steps of the recurrent process of creation g via the symbolic automaton gives us 
O(n) operations. Alice chooses affine transformations T and T –1. The computation T –1 costs O(n2) 
elementary operations. This means that Alice can create T–gT –1 for O(n5) operations. Alice forms 
elements b1, b2, …, br from G(n, K) together with their inverses and homomorphic images μ′(bi), 
i = 1, 2, ..., r, from G(m, K) in time O(n). She takes T– and T–1 from AGLn(K) and forms ai = T–biT –1 
and a′i = T(bi–1)T –1 in time O(n5).
Bob receives the list of pairs ai, a′i, i = 1, 2, ..., r. He computes a chosen word of the kind 
a = ai1k1ai2k2..., aitkt for the chosen finite parameter t and integers ki, i = 1, 2, ..., t, in time O(n13) ope-
rations and sends it to Alice. Bob writes his message p = (p1, p2, ..., pm). To form the ciphertext, 
he applies the transformation 
ti
a′  with multiplicity kt, tia′  with multiplicity kt-1, ..., 1tia −′  with mul-
tiplicity k1 to p and forms the ciphertext c. It takes him O(n
3) elementary operations. Alice com-
putes a cubical b = aT with O(n4) operations. After she gets d = T –1 b in time O(n4). Alice easily 
gets μ(d) and computes e = T1 d and f = eT1–1. She computes p as f(c). The last step costs her O(n3) 
elementary ring operations.
6.3. Special implementations. Let us consider an implementation of the above cryptosystem 
in the case of a choice of maps T and T1 as linear maps of finite density. Natural examples of such 
maps are monomial transformations or elements of direct sum of groups of kind GLd(K), where d 
is a finite constant.
Alice chooses the affine transformations T and T –1. The computation g T –1 costs O(n) elemen-
tary operations. This means that Alice can create T g T –1 for O(n) operations. Alice forms ele-
ments b1, b2, …, br from G(n, K) together with their inverses and homomorphic images μ(bi), i = 1, 
2, ..., r, from G(m, K) in time O(n). She takes T, T –1, T1, and T1
–1 from GL1n(K) and forms ai = T 
bi,T
–1 and a′i = T1 μ( bi–1)T1–1in time O(n).
Bob receives the list of pairs ai, a′i, i = 1, 2, ..., r, of cubical elements of density O(n). He com-
putes a chosen word of kind 1 2
1 2
, t
t
kk k
i i ia a a a= …  for the chosen finite parameter t and the integers ki, 
i = 1, 2, ..., t, in time O(n5) operations and sends it to Alice. Bob writes his message (p) = (p1, p2, …, 
pm). To form the ciphertext, he applies the transformation tia′  with multiplicity kt, 1tia −′  with mul-
tiplicity kt–1, ..., 1ia′  with multiplicity k1 to p and forms the ciphertext c. It takes him O(n) elemen-
tary operations. Alice computes a cubical b = aT with O(n2) operations. After that, she gets 
d = T –1b in time O(n2). Alice easily gets μ(d) and computes e = T1d and f = eT1–1. She computes p 
as f(c). The last step cost her O(n2) elementary ring operations.
This research is partially supported by the grant PIRSES-GA-2013-612669 of the 7th Framework 
Program of the European Commission.
REFERENCES
  1. Ding, J., Gower, J. E. & Schmidt, D. S. (2006). Multivariate public key cryptosystems. Advances in In for-
mation Security, Vol. 25, Springer.
  2. Koblitz, N. (1998). Algebraic aspects of cryptography. Springer.
  3. Goubin, L., Patarin, J. & Yang, Bo-Yin. (2011). Multivariate cryptography. In Encyclopedia of cryptography 
and security. 2nd ed. (pp. 824-828). Springer.
  4. Ustimenko, V. (2017). On desynchronised multivariate El Gamal algorithm. Retrieved from https://eprint.
iacr. org./2017/712.pdf.
  5. Ustimenko, V. (2017). On the families of stable multivariate transformations of large order and their crypto-
graphical applications. Tatra Mt. Math. Publ., 70, pp. 107-117.
35ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2018. № 10
On new symbolic key exchange protocols and cryptosystems based on a hidden tame homomorphism
  6. Ustimenko, V. & Romańczuk, U. (2013). On dynamical systems of large girth or cycle indicator and their 
applications to multivariate cryptography. In artificial intelligence, evolutionary computing and me ta-
heuristics (pp. 257-285). Berlin: Springer.
  7. Ustimenko, V. A. (2013). On the extremal graph theory and symbolic computations. Dopov. Nac. akad. nauk 
Ukr. No. 2, pp. 42-49 (in Russian).
  8. Ustimenko, V. A. (2005). Maximality of affine group, and hidden graph cryptosystem. Algebra Discrete Math., 
No. 1, pp. 133-150.
  9. Ustimenko, V. & Wróblewska, A. (2013). On the key exchange and multivariate encryption with nonlinear 
polynomial maps of stable degree. Annalles UMCS, Informatica, 13, No.1, pp. 63-80.
10. Wróblewska, A. (2008). On some properties of graph based public keys. Albanian J. Math., 2, No. 3, pp. 229-234.
11.  Klisowski, M. & Ustimenko, V.  (2015). Graph based cubical multivariate maps and their cryptographical 
applications. In Advances on superelliptic curves and their applications (pp. 305-327). Amsterdam etc.: 
IOS Press.
12. Wróblewska, A. & Ustimenko, V. (2014). On new examples of families of multivariate stable maps and their 
cryptographical applications. Annales UMCS, Informatica. 14, No. 1, pp. 19-36.
13. Romańczuk-Polubiec, U. & Ustimenko, V. (2015). On two windows multivariate cryptosystem depending on 
random parameters. Algebra Discrete Math., 19, No. 1, pp. 101-129.
14. Romańczuk-Polubiec, U. & Ustimenko, V. A. (2015). On new key exchange multivariate protocols based on 
pseudorandom walks on incidence structures. Dopov. Nac. akad. nauk Ukr., No. 1, pp. 41-49. doi: htpps://doi.
org/10.15407/dopovidi2015.01.041
15. Ustimenko, V. A. (2015). Explicit constructions of extremal graphs and new multivariate cryptosystems. 
Stud. Sci. Math. Hung. Spec. iss. Proceedings of The Central European Conference, 2014, Budapest. 52, No. 
2, pp. 185-204.
Received 14.03.2018
В.О. Устименко
Інститут телекомунікацій і глобального інформаційного 
простору НАН України, Київ
Університет Марії Кюрі-Склодовської, Люблін, Польща
E-mail: vasylustimenko@yahoo.pl
ПРО НОВІ СИМВОЛІЧНІ ПРОТОКОЛИ ОБМІНУ 
КЛЮЧІВ ТА КРИПТОСИСТЕМИ, ЩО ОПИРАЮТЬСЯ 
НА ПРИХОВАНІ РУЧНІ ГОМОМОРФІЗМИ
Криптосистеми від багатьох змінних поділяються на публічні ключі, для яких засіб шифрування відкри-
тий для всіх користувачів, та криптосистеми типу Ель Гамаля з функцією шифрування, що не надається 
публічно, для її генерування опонент повинен розв’язати проблему дискретного логарифма в афінній гру-
пі Кремони. Нескінченні родини перетворень вільних модулів Kn над скінченним комутативним кільцем 
K такі, що степені їх представників не зростають при ітерації, називають стабільними родинами перетво-
рень. Такі родини необхідні для практичних реалізацій криптосистем типу Ель Гамаля. Наведено нові кон-
струкції таких родин та родин стабільних напівгруп перетворень вільних модулів. Запропоновано нові 
методи створення криптосистем, які використовують стабільні групи та напівгрупи разом з гомомор-
фізмами між ними. Безпека таких схем ґрунтується на складності проблеми розкладу елемента афінної 
напівгрупи Кремони в добуток заданих твірних. Схеми можуть використовуватися як для обміну пові-
домленнями у вигляді елементів вільного модуля, так і для безпечного узгодження поліноміальних пе-
ретворень від багатьох змінних, які можуть бути знаряддям шифрування або інструментом для циф-
рового підпису.
Ключові слова: криптографія від багатьох змінних, стабільні групи та напівгрупи, проблема декомпозиції 
нелінійного перетворення від багатьох змінних за заданими твірними, дикі та ручні перетворення, ручні 
гомоморфізми, протоколи обміну ключів, криптосистеми, алгебраїчні графи.
36 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2018. № 10
V.A. Ustimenko
В.А. Устименко
Институт телекоммуникаций и глобального информационного 
пространства НАН Украины, Киев
Университет Марии Кюри-Склодовской, Люблин, Польша
E-mail: vasylustimenko@yahoo.pl
О НОВЫХ СИМВОЛИЧЕСКИХ ПРОТОКОЛАХ 
ОБМЕНА КЛЮЧЕЙ И КРИПТОСИСТЕМЫ, ОСНОВЫВАЮЩИХСЯ 
НА СКРЫТЫХ РУЧНЫХ ГОМОМОРФИЗМАХ
Криптосистемы от многих переменных подразделяются на публичные ключи, для которых способ шиф-
рования открыт для всех пользователей, и криптосистемы типа Эль Гамаля с функцией шифрования, не 
заданной публично, для ее генерации оппонент должен решить проблему дискретного логарифма в афин-
ной группе Кремоны. Бесконечные семейства преобразований свободного модуля Kn над конечным ком-
мутативным кольцом K такие, что степени их представителей не возрастают при итерации, называют ста-
бильными семействами преобразований. Такие семейства необходимы для практических реализаций 
криптосистем типа Эль Гамаля. Приведены новые конструктивные построения таких семейств и семейств 
стабильных полугрупп преобразований свободных модулей. Предложены новые способы построения 
криптосистем, использующие стабильные группы и полугруппы вместе с гомоморфизмами между ними. 
Безопасность таких схем опирается на сложность проблемы разложения элемента афинной полугруппы 
Кремоны в произведение заданных образующих. Схемы могут использоваться как для обмена сообще-
ниями в виде элементов свободного модуля, так и для безопасного согласования полиномиальных пре-
образований от многих переменных, которые могут быть средствами шифрования или инструментами 
цифровой подписи.
Ключевые слова: криптография от многих переменных, стабильные группы и подгруппы, проблема деком-
позиции нелинейного преобразования от многих переменных по заданным образующим, дикие и ручные пре-
образования, ручные гомоморфизмы, протоколы обмена ключей, криптосистемы, алгебраические графы.