On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems
Results of implementation of several multivariate public keys of linear degree of size O(n) and polynomial density defined over commutative ring K with the nontrivial multiplicative group K*. are presented. The space of plaintexts of these cryptosystems is (K*)n and space of ciphertexts is Kn. The e...
Gespeichert in:
| Datum: | 2026 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Kyiv National University of Construction and Architecture
2026
|
| Schlagworte: | |
| Online Zugang: | https://es-journal.in.ua/article/view/364963 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Environmental safety and natural resources |
| Завантажити файл: |  |
Institution
Environmental safety and natural resources| _version_ | 1871012335483617280 |
|---|---|
| author | Ustimenko, Vasyl Pustovit, Oleksandr |
| author_facet | Ustimenko, Vasyl Pustovit, Oleksandr |
| author_institution_txt_mv | [
{
"author": "Vasyl Ustimenko",
"institution": "Доктор фізико-математичних наук, професор, завідуючий відділу інформаційної безпеки Інституту телекомунікацій і глобального інформаційного простору НАН України, Київ, Visiting Professor of Royal Holloway University of London"
},
{
"author": "Oleksandr Pustovit",
"institution": "Кандидат технічних наук, старший науковий співробітник Інституту телекомунікацій і глобального інформаційного простору НАН України, Київ"
}
] |
| author_sort | Ustimenko, Vasyl |
| baseUrl_str | http://es-journal.in.ua/oai |
| collection | OJS |
| datestamp_date | 2026-07-17T09:24:50Z |
| description | Results of implementation of several multivariate public keys of linear degree of size O(n) and polynomial density defined over commutative ring K with the nontrivial multiplicative group K*. are presented. The space of plaintexts of these cryptosystems is (K*)n and space of ciphertexts is Kn. The encryption map is the restriction on (K*)n of polynomial transformation of the space Kn which is the composition of special Eulerian trams-formation with cubical map of Multivariate Cryptography of kind T1QT2, where T1 and T2 are bijective affine trans-formations and Q is a nonlinear map defined via walk on algebraic bipartite graph points and lines of which form the space Kn.This scheme is implemented for the cases K=Fq and K=Zq, q=232. The knowledge of private key allows to decipher of the message from public user in time O(n2). The cryptosystems are generalisations of algorithms suggested 9 years ago cryptanalysis of which are unknown. The problem of breaking the cryptosystem is equivalent to solving of system of nonlinear equations in n variables of degree cn, de c>0. The computer packages for the investigation of such systems are undeveloped. |
| doi_str_mv | 10.32347/2411-4049.2026.2.135-153 |
| first_indexed | 2026-06-18T01:02:15Z |
| format | Article |
| fulltext |
~ 135 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
UDC 519.1,514.128
Vasyl Ustimenko1,2, Doctor of Physical and Mathematical Sciences, Professor, Head of the
information security department
ORCID ID: https://orcid.org/0000-0002-2138-2357 e-mail: vasulustimenko@yahoo.pl
Oleksandr Pustovit2, Candidate of Technical Sciences, Senior Researcher
ORCID ID: https://orcid.org/0000-0002-3232-1787 e-mail: sanyk_set@ukr.net
1University of Royal Holloway, London, Great Britain
2Institute of Telecommunications and Global Information Space of the NASU, Kyiv, Ukraine
ON EXTREMAL ALGEBRAIC GRAPHS, EULERIAN
TRANSFORMATIONS AND IMPLEMENTATIONS OF MULTIVARIATE
CRYPTOSYSTEMS
Abstract. Results of implementation of several multivariate public keys of linear
degree of size O(n) and polynomial density defined over commutative ring K with
the nontrivial multiplicative group K*. are presented. The space of plaintexts of
these cryptosystems is (K*)n and space of ciphertexts is Kn. The encryption map is
the restriction on (K*)n of polynomial transformation of the space Kn which is the
composition of special Eulerian trams-formation with cubical map of Multivariate
Cryptography of kind T1QT2, where T1 and T2 are bijective affine trans-formations
and Q is a nonlinear map defined via walk on algebraic bipartite graph points and
lines of which form the space Kn.
This scheme is implemented for the cases K=Fq and K=Zq, q=232. The knowledge of
private key allows to decipher of the message from public user in time O(n2). The
cryptosystems are generalisations of algorithms suggested 9 years ago cryptanalysis
of which are unknown. The problem of breaking the cryptosystem is equivalent to
solving of system of nonlinear equations in n variables of degree cn, de c>0. The
computer packages for the investigation of such systems are undeveloped.
Keywords: Multivariate Cryptography, Symbolic Computations, Algebraic Graphs,
Extremal Graph Theory.
https://doi.org/10.32347/2411-4049.2026.2.135-153
1. Introduction
Postquantum Cryptography (PQC) is an answer to a threat coming from a full-scale
quantum computer able to execute Shor’s algorithm. With this algorithm
implemented on a quantum computer, currently used public key schemes, such as
RSA and elliptic curve cryptosystems, are no longer secure. The U.S. NIST made a
step toward mitigating the risk of quantum attacks by announcing the PQC
standardisation process [1]. In June 2020 NIST published a list of candidates
qualified to the third round of the PQC process. Some public key candidates are
implemented like PQC Round 2 candidate called Round 5 or code based classic Mc
Eliece algorithm (see [2], [3]). Remaining third round candidate defined via
Multivariate Cryptography belong to category of digital signatures schemes.
It is “The Rainbow Like Unbalanced Oil and Vinegar” (RUOV) algorithm.
During its evaluation some cryptanalytic instruments against ROUV were found (see
[4]). In July 2022 first four winners of NIST standardisation competition were
chosen. They are all lattice based algorithms.
© V. Ustimenko, O. Pustovit, 2026
https://orcid.org/0000-0002-2138-2357
mailto:vasulustimenko@yahoo.pl
https://orcid.org/0000-0002-3232-1787
mailto:sanyk_set@ukr.net
~ 136 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
Note that the search for new solutions in Posquantum Cryptography is vintinued
(see the proceedings of PQCrypt 2023-2025 and Eurocrypt 2023-2025, look at
abstracts of Eurocrypt 2026).
Current absence of standardised Multivariate Cryptosystems stimulates further
research (see classical publications [54]-[78]). In the case of instruments for Data
encryption studies of multivariate maps of unbounded degree were proposed in 2017
in the paper [7]. The encryption map were defined over the arithmetical rings Zm but
as it was noticed in [8] they can be changed for the finite fields Fq. Later [2-22] the
encryption was defined over an arbitrary commutative ting K with nontrivial
multiplicative group Kn.
Recall that Multivariate and Noncommutative Cryptographies are among main
directions of Postquantum Cryptography together with Coding based Cryptography,
Lattice based Cryptography Hash based Cryptography, Superelliptic curves based
Cryptography. Each of these areas is based on the complexity of certain NP hard
problem. It is important that fundamental assumption of cryptography that there are
non polynomial-time algorithms for solving any NP-hard problem remains valid. So
all mentioned above directions are well justified theoretically and new Public Keys
will appear within each direction.
Extremal algebraic graphs were traditionally used for the construction of stream
ciphers of multivariate nature (see [5] and further references or [6]). Some
multivariate public keys were constructed via combinations of graph based maps
with highly nonlinear maps of minimal density [7], [8]. First examples of classical
multivariate rules, i. e. transformations of degree 2 and 3, defined in terms of walks
on graphs were obtained recently [9].
Algebraic instruments were used for the constructions of Platforms for the
protocols and El Gamal type tive Cryptography (see [18] and [33]-[46] and
cryptanalytical studies [48]-[53]). Noteworthy that all multivariate NIST candidates
were presented by multivariate rule of degree bounded by constant (2 or 3) of kind
x1 → f1(x1, x2, … , xn), x2 → f2(x1, x2, … , xn), …, xn → fn(x1, x2, … , xn).
We think that NIST outcomes motivate investigations of alternative options in
Multivariate Cryptography oriented on encryption tools for
(a) the work with the space of plaintexts (Fq)
n and its transformation G of linear
degree cn, c>0 on the level of stream ciphers or public keys;
(b) the usage of protocols of Noncommutative Cryptography with platforms of
multivariate transformations for the secure elaboration of multivariate map G from
End(Fq[x1, x2, … , xn]) of linear or superlinear degree and density bounded below by
function of kind cnr, where c>0 and r>1.
Some ideas in directions of (a) and (b) are presented in [9]. We hope that classical
multivariate public key approach, i. e. the usage of multivariate rules of degree 2 or
3 is still able to bring reliable encryption algorithms. We think that the possible
change of finite field for other commutative ring like arithmetic rings modulo m can
bring additional secure and efficient algorithms.
In this paper we discuss the implementation of multivariate public rules of cubic
density. Recall that the density is the number of all monomial terms in a standard
form xi → gi(x1, x2, … , xn), i=1, 2, …, n of multivariate map G, where polynomials
gi are given via the lists of monomial terms in the lexicographical order.
We use the known family of graphs D(n, q) and A(n. q) of increasing girth (see
[19], [20], [21]) and further references) and their analogs D(n, K) and A(n, K) defined
over finite commutative ring K with unity for the construction of our public keys.
~ 137 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
Noteworthy to mention that for each prime power q, q>2 graphs D(n, q), n=2, 3, …
form a family of graphs of large girth (see [20]). There is well defined projective
limit of these graphs which is a q-regular forest. In fact if K is an integral domain
both families A(n, K) and D(n, K) are approximations of infinite dimensional
algebraic forests. The definitions of such approximations are given in Section 3
together with a short survey of their usage.
In Section 2 we present the known mathematical definitions of some objects of
algebraic geometry for the further usage of them as instruments of Multivariate
Cryptography. In particular definitions of affine Cremona semigroup of
endomorphisms of multivariate ring K[x1, x2, … , xn]) defined over commutative
ring K and affine Cremona group nCG(K) are presented there.
The concept of trapdoor accelerator of the transformation from affine Cremona
semigroup nCS(K) is presented there as a piece of information which allows
computation of reimage of the map in time O(n 2).
This is a weaker version of the definition of trapdoor one way function. The
definition of the trapdoor accelerator is independent from the conjecture P≠ NP of
the Complexity theory.
In section 3 we consider special class of algebraic graphs known as linguistic
graphs.
Together with arbitrary linguistic graph Г(K) defined over finite commutative
ring with unity one can consider associated graph Г=Г’( K[x1, x2, … , xn]). We use
this possibility to use walks in Г’ and well defined special colouring on this graph
for the construction of polynomial transformations on selected partition set. Section
4 is dedicated to special families of linguistic graphs with remarkable extremal
properties.
In the case of these linguistic graphs degrees of multivariate transformations
defined in terms of walks and the colouring are at most 3. We use this fact to define
cubic trapdoor accelerators and construct trapdoor accelerators on unbounded degree
and polynomial density. They can be used for the constructions of multivariate public
keys.
Some properties of these cryptosystems are considered in Section 5. Detailed
implementations of procedures for generating of multivariate public key and private
key decryption are given in Section 6. Last section contains conclusive remarks.
2. On elements of Algebraic Algebraic Geometry and trapdoor accelerators
Let K be a commutative ring with a unity. We consider the ring K’=K[x1, x2, … , xn] of
multivariate polynomials over K. Endomorphisms σ of K’ can be given via the
values of σ(xi)=fi(x1, x2, … , xn), fi є K’.
They form the semigroup End(K[x1, x2, … , xn])= nCS(K) of K’ known also as
affine Cremona semigroup (see [22], [23]) after the famous Luigi Cremona (see
[24]). The map σ’:(x1, x2,…, xn) →(f1(x1, x2,…, xn), f2(x1, x2, …, xn),…, fn(x1, x2, …,
xn)) is polynomial transformation of affine space Kn.
These transformations generate transformation semigroup nCS(Kn). Note that the
kernel of homomorphism of nCS(K) to CS(Kn) sending σ to σ’ depends on the choice
of commutative ring K. Affine Cremona Group nCG(K)=Aut(K[x1, x2, …, xn]) acts
bijectively on Kn. Noteworthy that some elements of nCS(K) can act bijectively on
Kn but do not belong to nCG(K).
~ 138 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
For instance endomorphism x → x3 of R[x] acts bijectively on the set R of real
numbers but the inverse x →x1/3 of this map is a birational element outside of 1CG®.
Recall that degree of σ is the maximal degree of polynomials σ(xi), i=1, 2, … , n. The
density of σ is a total number of monomial terms in all σ(xi).
Assume that automorphism F from nCG(K) has constant degree d, d≥ 2. It is given
in its standard form written as x1 → f1(x1, x2, …, xn), x2→ f2(x1, x2, …, xn) ,..., xn →
fn(x1, x2, … , xn) where fi, i=1, 2, …, n are elements of K[x1, x2, … , xn] and used as
public rule to encrypt plaintexts from Kn .
The following definition was motivated by the idea to have a weaker version of
trapdoor one way function.
We say that family Fn є nCG(K) of nonlinear polynomial transformations of affine
space Kn has trapdoor accelerator nT if the knowledge of piece information nT
(“trapdoor accelerator”) allows to compute the reimage x for Fn in time O(n 2).
If F is bijective of degree bounded by constant c and the degree of Fn
-1 is at least
d, d≥ 3 we say that nT is of level d.
Notice that if Fn are given by their standard forms and degrees of Fn
-1 are equal
to d then the inverse can be approximated in polynomial time f(n, d)=O(nd/2) via
linearisation technique.
One can see that the approximation task becomes unfeasible if d is “sufficiently
large” like d=100. Examples of cubic families Fn with trapdoor accelerator of high
level t are given in the case of special finite fields Fq in the in [9].
Let nES(K) stands for the semigroup of Eulerian endomorphisms, i. e.
endomorfisms σ from nCS(K) such that σ(xi)=aix1
(i, 1) x2
a(i, 2)… xn
a(i, n), where ai are
elements of multiplicative group K* of the ring. We consider the group nEG(K) of
all invertible elements of nES(K) as transformations of (K*)n.
We consider the totality TA(n, K) of toric endomorphisms, i. e. endomorphisms
σ from nCS(K) such that their restrictions on (K*)n are injective maps into Kn. For σ
from TA(n, K) we define its toric inverter as polynomial map σ’ from nCS(K) such
that σ’σ acts on (K*)n as identity.
It is easy to see that if G є TA(n, K) and H є nEG(K) then composition HG of H
and G is a toric endomorphism as well. Assume that automorphism F from nCG(K)
has constant degree d, d ≥2. It is given in its standard form written as x1 →f1(x1, x2,
…, xn), x2 →f2(x1, x2, …, xn), …, xn →f1(x1, x2, …, xn), where fi, i=1, 2, …, n are
elements of K[x1, x2, …, xn] and used as public rule to encrypt plaintexts from Kn.
Then we can use Eulerisation of this public rule given by standard form of
Gn =HF where H is an element of nEG(K). New public rule uses space of plaintexts
(K*)n and space of ciphertexts Kn.
Noteworthy that the decryption is equivalent to consecutive application of
(Fn)
-1 and inverse H’n in nEG(K) of the map Hn. Noteworthy that standard form of
this composition is of nonpolynomial density.
More general class of multivariate rules is the totality of toric multivariate rules
G of kind xi → Gi where G is a toric endomorphism of K[x1, x2 , …, xn] of constant
degree d. We can take element H of nES(K) in “general position” and consider HGn
of linear degree and polynomial density instead of Gn. We say that HGn is
an Eulerisation of Gn.
~ 139 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
3. Linguistic graphs and symbolic computations
Let K be a commutative ring. We refer to an incidence structure with a point set
P=Ps,m =Ks+m and a line set L=Lr,m =Kr+m as linguistic incidence structure Im(K) of
type (s, r, m) if point x=(x1, x2,…, xs , x s+1, x s+2, …, x s+m ) is incident to line
y=[y1 , y2 , …, yr , y r+1, yr+2,…, …, y r+m ] if and only if the following relations hold
a 1 xs+1 +b1y r+1 =f 1(x 1, x2,…,xs , y1, y2,…,yr ), a2xs+2 +b2y r+2 =f 2(x 1 , x2,…,x s, x s+1,
y1, y2,…, yr , y r+1), …am xs+m+bmy r+m =f m(x1 , x2,…, x s, x s+1,…,x s+m, y1, y2,…, yr,
y r+1,…,y r+m),
where aj and bj , j=1,2, …, m are not zero divisors, and fj are multivariate
polynomials with coefficients from K. Brackets and parenthesis allow us to
distinguish points from lines (see [25] or [6] and further references). The colour
ῤ(x)=ῤ((x)) (ῤ(y)=ῤ([y])) of point (x) (line [y]) is defined as projection of an element
(x) (respectively [y]) from a free module on its initial s (relatively r) coordinates. As
it follows from the definition of linguistic incidence structure Im(K) for each vertex
of its incidence graph Г(m, K) there exists the unique neighbour of a chosen colour.
For each b є K r and p=(p1, p2, …, ps+m) there is the unique neighbour of the point
[l]=Nb(p) with the colour b. Similarly,for each c є Ks and line l=[l1, l2,…, lr+m] there
is the unique neighbour of the line (p)= Nc([l]) with the colour c. We refer to
operator of taking the neighbour of vertex accordingly chosen colour as
neighbourhood operator.
On the sets P and L of points and lines of linguistic graph we define jump
operators J= Jb(p) = (b1, b2, … , bs , ps+1, ps+2, …, ps+m), where (b1, b2, … , bs) є Ks
and J=Jb([l])=[b1, b2, … , br, lr+1, lr+2, … , lr+m], where (b1, b2, …, br) є Kr for the
point (p1, p2, …, ps+m) and the line [l1, l2, …, lr+m].
Noteworthy, that the path in v0, v1, … , vk the linguistic graph Im is determined by
starting vertex v0 and colours of vertexes v1, v2, ... , vk. We can take commutative ring
R=K[y1,y2,…,yl] and consider graph Im(K) together with infinite graph Im®=Im(K[y1,
y2, … , yl]) defined by the same polynomials fi, i=1, 2, … , m with coefficients from
K but with partition sets Rs+m and Rr+m .
Assume that l=m+s. We can consider the path in Im® of length 2k in with starting
point (y1, y2, …, ys, ys+1,ys+2, …, ys+m) and consecutive colours G1, H1, G2, H2, …, Gk,
Hk such that Gi є K[x1,x2, …, xs]
s and H1 є K[x1, x2,…, xs]
r .
The last vertex of this path will be a point(p) with consecutive coordinates h1, h2, …,
hs, fs+1, fs+2 ,… , fs+m where f1, f2,…, fs+m are elements of K[x1, x2,…, xs, xs+1, xs+2, …, xs+m]s.
Finally we consider u=JH(p) where H=(g1, g2,…,gs) is the element of K[x1, x2, …,
xs]
s. We define passage transformation Г(m,K)Pas(G1, G2, …, Gk, H1, H2, …, Hk, H) of
Kr+s (space of points) with symbolic colours G1, H2 , …, Gk, Hk and H via multivariate
rule y1 →
g1(y1, y2, …, ys), y2 → g2(y1, y2, …, ys),…, ys → gs(y1, y2, …, ys), ys+1 → fs+1(y1,
y2, … ,ys+m), ys+2→ fs+2(y1, y2, …, ym+s), …, ys+m→ fs+m(y1, y2, … , ym+s). It is easy to
see that this transformation is bijective if the map yi→hi(y1, y2, …, ys), i=1, 2, … , s
is bijective on Ks.
We are searching for families of linguistic graphs Г(m, K) of type (r, s, m) with
constant parameters r and s and m=1, 2,… such that standard forms of nonlinear
transformations Fm =
Г(m,K)Pas(G1, G2, …, Gk, H1, H2, …, Hk, H), k=O(m) where
symbolic colours are taken from a special class of tuples have trapdoor accelerator
G1, G2, …, Gk, H1, H2, …, Hk, H.
Several examples of such families with s=r=1 will be introduced in the following
sections.
~ 140 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
4. On algebraic forest approximations and their applications
We define thick forest as simple graph without cycles such that each of its vertex has
degree at least 3. In probability theory branching process is a special stochastic
process corresponding to a random walk on a thick forest. A genealogy of single
vertex is a tree.
One of the basic properties of finite tree is the existence of a leaf, i. e. vertex of
degree 1. Thus each thick tree is an infinite simple graph.
Let K be a commutative ring and Kn be an affine space of dimension n over K
(free module in other terminology). A subset M in Kn is an algebraic set over K if it
is a solution set for the system of algebraic equations of kind f=0 or inequalities of
kind g≠0 where f and g are elements of K[x1, x2, …, xn]. There are several alternative
approaches to define dimension of M. In the case when K is a field these approaches
are equivalent and dimension of M can be computed with the usage of Grőbner basis
technique (see [26], [27], [28]).
We say that graph Г is algebraic over K if its vertex and edge sets are algebraic
sets over K. We investigate a possibility to define thick forest F by system of
equations over some commutative ring K, i.e. construct F as a projective limit of
algebraic over K bipartite graphs Гi, i=1, 2, …. Noteworthy that the girth g i =g(Гi ),
which is the length of minimal cycle in Гi tends to infinity when i is growing. In this
situation we refer to F as algebraic forest over K. We say that the family Гi is an
algebraic forest approximation over the ring K.
In the case gi ≥ cni, where n i are dimensions of the algebraic sets V(Гi ) of
vertices of the graph Гi and c is some positive constant we use term algebraic forest
approximation of large girth. Note that algebraic forest approximations of large girth
over finite field Fq, q>2 are families of graphs of large girth in sense of P. Erdős’
(see [29] and further references).
The first algebraic forest approximation of a large girth was introduced by
F. Lazebnik and V. Ustimenko (see [19]) in the case of K=Fq. The properties of trees
of this algebraic forest and their approximations over Fq were investigated in the
paper by [20].
In 1998 more general algebraic graphs D(n,K) defined over arbitrary
commutative ring K were introduced (see [30] and further references). It was stated
that a girth of D(n, K) is ≥ n+5 in the case of arbitrary integrity domain K. This
inequality insures that is algebraic forest approximation of large girth. The prove of
the inequality reader can find in [30], simpler prove of this fact the reader can find
in [31].
Noteworthy that in the case of integrity domain K together with D(n, K), n=2,3,…
one can consider another thick forest approximation D(n, K[x1, x 2 , …, xm]), n=2,3,…
for each parameter m. Thus paper [30] opened a possibility to use extremal
properties of these graphs in the Theory of Symbolic Computations and its various
applications to Cryptography.
The paths of even length t on trees and their approximations can be used to induce
multivariate transformations on varieties Pi and Li of points and lines of the large
cycle indicator. We can assume that c is the largest possible constant for the property
in the definition.
These transformations can serve as encryption maps acting on the potentially
infinite space Pi of plaintexts (see [6] and further references). They form a group
Gi=G(Гi), which can be a platform for the protocols of Noncommutative
~ 141 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
Cryptography (see [18], [32]-[46]). Noteworthy that if t is at most half of the girth
of Гi then different paths produce distinct transformations. So, forest approximations
of large girth are preferable for cryptographic applications.
Other tree approximation over the integrity domain K is formed by graphs
A(n, K) considered in [47]. In fact these graphs were defined earlier [30] as
homomorphic images E(n, K) of graphs D(n, K) or their connected components
CD(n, K). As it was stated recently in short paper [21] for each integrity domain.
K, K ≠ F2 graphs A(n, K) form a tree approximation of large girth.
For each vertex v of graph Г we define its cycle indicator Cind(v) as length of
the shortest cycle through v. We define cycle indicator Cind(Г) of the graph as
maximal value of Cind (v) via all vertexes of the graph.
Let family Гi be an algebraic forest approximation over the ring K. In the case
Cind(Гi) ≥ cni where ni are dimensions of the algebraic manifold V(Гi ) of vertices
of the graph Гi and c is some positive constant we use term algebraic forest
approximation with large cycle indicator. A(n, K) form algebraic forest
approximation with large cycle indicator for which c=2. Noteworthy that speed of
girth growth for A(n, Fq) is not evaluated properly yet. Some encryption algorithms
(stream ciphers) based on A(n, K) and D(n, K) were already introduced (see [6] and
further references). Note that research on design of new stream ciphers based on
these graph is in progress (see [79]-[81]).
For the constructions of multivariate public keys the following observation is
important type. Graphs A(n, K) and D(n, K) are linguistic graphs of type (1, 1, n-1),
the incidence between point (p1, p2, …, pn) and line [l1, l2, …, ln] is defined by the
system of equations pi-li=pt(i)lj(i) where l(i)<i, j(i)<i, i=2, 3, …, n.
The following statement follows directly from the written above equations.
Proposition 1. Let Г(n. K) be one of the graphs A(n, K) or D(n, K) defined over
commutative ring K.
Assume that degrees of polynomials gi(y), hi(y) and h(y) from K[y] are bounded
by constant c, h(y) is from 1CG(K) and j=O(n). Then polynomial map G=Pas(g1, g2,
…, gj, h1, h2,…, hj, h) has trapdoor accelerator gi, hi , h , i=1, 2, …, j.
Remark. This statements can be generalized for the class of linguistic graphs of
Г(n, K) type (1, 1, n-1) such that densities of fi are bounded by some constant. The
easiest choice for h(y) is a linear expression ay+b with regular a.
To use this fact in Cryptography we have to evaluate degree or density of
G=Pas(g1, g2, …, gj, h1, h2,…, hj, h) and G-1.
The following statement can be found in [6].
Theorem 1. Let K be a commutative ring with unity. Г(n, K) be one of the graphs
A(n, K) or D(n, K). Then degree of Pas(y+a1, y+a2,…, y+aj, y+b1, y+b2,…, y+bj,
y+bj), j ≥1 is three.
The statement below is an instant corollary of Proposition 1 and Theorem 1.
Lemma 1. Let Г(n, K) , h(y) and j satisfy to conditions of Proposition 1 and
deg(h(y))≤3. Then degree of the automorphism
Pas(y+a1, y+a2,…, y+aj, y+b1, y+b2,…, h(y)), h(y), j ≥1 is 3.
The following statement is proven in [9].
Lemma 2. Let K coincides with Fq, q=2m, m ≥3, Г(n, K) , h(y) and j satisfy to
conditions of Proposition 1 and h(y)=ay 2+b, a≠0. Then standard form of cubic
automorphism Pas(y+a1, y+a2,…, y+aj, y+b1, y+b2,…, y+bj , h(y)) has trapdoor
accelerator nT which is a sequence y+a1, y+a2,…, y+aj, y+b1, y+b2,…, y+bj ,
ay 2+b) of level d≥2m-1.
~ 142 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
We can modify the cubic map of presented above lemma via affine
transformations T1 and T2 from AGLn(Fq) and get G= T1 Pas(y+a1, y+a2,…, y+aj,
y+b1, y+b2,…, y+bj , h(y))T2.
Then new map has the trapdoor accelerator T1, T2,
nT (see [9] of the same level
with nT. We implemented the Eulerisation of this map, i. e toric endomorphism EG,
where E is obtained as composition of “ upper triangular element” 1E
x1→q1x1
a(1,1)x2
a(1,2)… xn
a(1,n),
x2→q2x2
a(2,2)x2
a(2,3)… xn
a(2,n),
…,
xn→qnxn
and lower triangular element
x1→r1x1
b(1,1) ,
x2→r2x1
b(2,1) x2
b(2,2),
…,
xn→rnx1
b(n,1) x2
b(n,2) …xn
b(1,n) where qi and r1 are nonzero elements of Fq, elements
a(i,j), b(i,j) are from the group Zq-1 and elements a(i,i), b(i,i) are mutually prime with
the modulo q-1.
Noteworthy that computation of the inverse elements of 1E and 2E is straightforward.
It means that reimage of the restriction of standard form F of toric map 1E2ET1
Pas(y+a1, y+a2,…, y+aj, y+b1, y+b2,…, y+bj , y2+b)T2 onto (Fq)
* has trapdoor
accelerator nT which consist of 1E, 2E, T1, T2 and tuple (a1, a2,…, aj, b1, b2, …, bj, b)
of length 2j+1.
We can estimate the density den(F) of F easily. One can see that den(F) coincide
with the density den (G) of quadratic map. Each of G(yi) consists of O(n2) monomial
terms. So all F(yi), i=1, 2, .., n together contains O(n3) monomial terms. Notice that
computation of each term of linear degree takes time O(n).
The implementations of public key cryptosystems based on the map F and its
trapdoor accelerator in the case of finite field of order 232 are and arithmetic ring Zq
are presented in the next section.
Computed parameters den(F) are given there.
5. On the feasibility of implementations of cryptosystems
Computed parameters den(F) are given there. This cryptosystem is an obfuscation
of public key [7] based on toric endomorphism 1E2ET1Pas(y+a1, y+a2,…, y+aj, y+b1,
y+b2,…, y+bj , y+b)T2.
Main difference between these maps is the following fact. The trapdoor
accelerator of bijective map G is cubic in the case of old scheme and it has level
2m-1 in the case of new scheme based on the finite field of order 2m.
We can change the finite field of characteristic 2 for the field Fq
where q-1 is
mutually prime with 3 and change the term y 2 +b in our trapdoor accelerator for
expression y 3+b. The level of corresponding cubic trapdoor accelerator is discussed
in [9].
Proposition 2. Let Г(n. K) be one of a linguistic graph of type (1, 1, n-1) defined
over commutative ring K via equations with righthand sides fi(x) of density O(1)
bounded by constant c.
Assume that degrees of polynomials gi(y), hi(y) and h(y) from K[y] are bounded
by constant c, h(y) is from 1EG(K) and j=O(n).
~ 143 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
Then toric endomorphism G=Pas(g1, g2, …, gj, h1, h2,…, hj, h) has trapdoor
accelerator gi, hi , h , i=1, 2, …, j.
Proof. Let G’ be the restriction of G onto (K*)n. Then equations G’(x)=c where
c=(c1, c2, …, cn) has to be found via the following procedure. Firstly we have to solve
the equation h(x)=c1. Let t be the solution. Secondly we have to look at the path in
the graph Г(n, K) with the starting point (hj(t), c2, c3,…, cn) and consecutive colours
gj(t), hj-1(t), gj-1(t), hj-2(t),…, g1(t), t. The final point of this walk is the reimage p=(t,
p2, p3…, pn). So point p is uniquely determined. The complexity of presented
procedure is O(n 2).
We are investigating properties of the toric endomorphism described in
Proposition 2 for the cases Г(n, K)=A(n, K), Г(n, K)=D(n, K), K=Zm where
(3, φ(m))=1 with the trapdoor accelerator of kind y+a1, y+a2,…, y+aj, y+b1, y+b2,…,
y+bj , y
3+b. For the implementation we select the case m=2 t, t≥2. In this case Euler
function φ has value 2 2 t-1. So we have (3, 2 t-1 )=1 for each value of t. The toric
inverse for G has polynomial degree ≥ 2 m([t-1/2]) (see [archive]).
The map of kind T1
Г(m,K)Pas(G1, G2, …, Gk, H1, H2, …, Hk, y
3+b)T2 , where T1
and T2 are elements of AGLn(Zm) will be a toric automorphism if in the expression
T1(y1)=a1y1+a2y2+…+anyn+an+1 the number of odd ai, i=1, 2,…,n is odd.
We generate the Eulerisation of this map with Gi=y+ai and Hi=y+bi of kind
F=1E2ET1Pas(y+a1, y+a2,…, y+aj, y+b1, y+b2,…, y+bj , y
3+b)T2.
The conditions ai≠ai+1, bi≠bi+1 insure the used walk in Г(n, K) is a path.
Noteworthy that density of F is O(n3). The multivariate public key based on F as
above is the obfuscation of cryptosystems described in [7], [8].
To implement considered above cryptosystem one need just knowledge on the
explicit constructions of graphs A(n,K) and D(n,K). We present this missing
information below.
Let K be a commutative ring.
We define A(n, K) as bipartite graph with the point set P=Kn and line set L=Kn
(two copies of a Cartesian power of K are used). We will use brackets and parenthesis
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 corresponding bipartite graph I) is given by
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 - l5 = p1 l4,
… ,
pn - ln = p1 ln-1 for odd n and pn - ln = l1 pn-1 for even n.
The following interpretation of a family of graphs D(n. K) in case of general
commutative ring K can be found in [5].
Let us use the same notations for points and lines as in previous case of graphs
A(n, K).
Points and lines are elements of two copies of the affine space over
K. Point (p)=(p1, p2, … , pn) is incident with the line [l]=[l1, l2 , … , ln] if the
following relations between their coordinates hold:
p2 - l2=l1p1,
p3 - l3= p1 l2,
~ 144 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
p4 - l4 = l1p3,
…,
li-pi=p1li-2 if i congruent to 2 or 3 modulo 4,
li-pi=l1pi-2 if i congruent to 1 or 0 modulo 4.
6. The outline of public key algorithm and remarks on its implementation
6.1. The computation of multivariate rule
Alice has to use some software package for symbolic computation like SAGE or
other tools to works.
Firstly she has to select the ring K. It can be Fq or Zq where q=2m, m ≥8. Secondly
Alice chooses parameter n for the work with the space of plaintexts (K*)n.
She selects two affine transformation T1 and T2 from AGLn(K). In the case of Zq
the linear expression T1(y1)=c1y1+c2y2+…+cnyn+cn+1=1 has to be with odd number
of odd coefficients ci, i=1,2,…, n, n+1 from Zq.
Additionally Alice selects parameter j of size O(n) together with parameters a1,
a2, …, aj, b1, b2,…,bj and b. The conditions ai≠ai+1, bi ≠bi+1 insure that used walk in
the graph is a path.
After that Alice selects elements a(i,j) and b(i,j) from definitions of toric
transformations 1E and 2E such that (a(i.i), d)=1, (b(i, i), d)=1 where d is the order
of group K*.
Finally she selects the graph Г(n, K) making a choice between D(n, K) or
A(n, K). Alice sets initial tuple (y1, y2, …, yn) and conducts the following steps.
Step1. Alice forms the tuple u=(1E(y1),
2E(y2),…., 1E(yn)) and form intermediate
tuple 2E(u)=z=(z1, z2,…,zn). Noteworthy that zi are monomial terms in variables y1,
y2,…, yn.
Step 2. Alice uses affine transformation T1 and compues T1(z)=v=(v1, v2,…, vn).
Noteworthy that vi are polynomials in variables yi, i=1,2, …n.
Step 3. She works with graph Г(n, K[y1, y2, …, yn]). Alice forms the path with the
starting point (v1, v2,…, vn) and sequence of consecutive colours v1+b1, v1+a1,
v1+b2,…, v1+bj, v1+aj. She computes the final point of this path (v1+aj, f2, f3, …, fn)=p.
For this procedure Alice use operations of addition and multiplication of the
commutative ring K[y1, y2,…, yn].
Step 4. Alice changes the first coordinate of tuple (p) and gets r=((v1)
e+b, f2, f3,…,
fn)=(r1, r2,…, rn), where e=2 in the case of K=Fq and e=3 for the case K=Zq.
Step 5. She computes T2®=(g1, g2, …, gn) where gi are presented in their standard
form. So Alice is ready to send the multivariate rule G: y1 →g1(y1, y2, …, yn), y2→g2(y1,
y2,…, yn), …, yn→fn(y1, y2,…, yn) to public user Bob.
Public users work with the space of plaintexts (K*)n and space of ciphertexts (K)n.
The complexity of usage of G is O(n 4).
6.2. On the private key description procedure
Alice gets from Bob the ciphertext c=G(p) where p is the plaintext of the public user.
She use her knowledge of the trapdoor accelerator 1E, 2E, T1, T2, ai, bi, b, e and graph
Г(n, K). Noteworthy that Alice can use ready for the usage transformations 1E-1,2E-1,
T1
-1, T2
-1.
Alice decrypt the ciphertext via the following procedure.
Step 1. She computes the tuple 1c= T2
-1( c).
~ 145 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
Step 2. Alice solve equation (v1)
e+b=1c1 with the unknown v1 and gets v1=v*.
Noteworthy that in the case of commutative ring K=Zq the parameter v* is odd.
Step 3. Alice forms the point 2c=(v*+aj,
1c2,
1c3,…., 1cn) of the graph Г(n, K). She
considers the path with the starting point 2c given by consecutive colours
v*+bj, v*+aj-1, v*+bj-1, v*+aj-2, v*+bj-2,…, v*+a1, v*+b1, v*. Alice computes the
final point of this path 3c. In the case of K=Zq the first coordinate of 3c is an odd
residue modulo q.
Step 4. Alice computes 4c as (T1)
-1(3c).
Step 5. She applies consecutively 2E and 1E and computes the plaintext as
1E-1 (2E-1(4c)).
We implement firstly these procedures in cases of graphs A(n, K) for n=16, 32,
64, 128 and K=Fq, K=Zq. We use the case when j=n and T1, T2 are linear
transformations given by the matrices with nozero entries. It turns out that the results
of computer simulations do not depend on the choice of the matrices and toric
transformations 1E and 2E in the general position.
Let S(n, K) stands for the length of plaintext in bites and N(n, K) is the density of
the multivariate map in the case of graph, i. e total number of its monomial terms.
The pairs of these parameters are given below
(S(16, Fq), N(16, Fq))= (512, 6440),
(S(16, Zq)), N(16, Zq))= (496, 15504),
(S(32, Fq), N(32, Fq))= (1024, 50720),
(S(32, Fq), N(16, Fq))= (992, 209440),
(S(64, Fq), N(64, Fq))= (2048, 399424),
(S(64, Zq), N(64, Fq))= (1984, 3065920),
(S(128, Fq), N(128, Fq))= (4096, 3170432),
(S(128, Zq), N(128, Zq))= (3968, 468665600).
Change of A(n, K) for D(n, K) produces similar results.
The encryption procedure requires computation of the sum of N(n, K) monomial
terms of kind x1
a(1)x2
a(2)… xn
a(n) where a(i) are integers within the interval [0, d-1]
where d is 2 32-1 for K=Fq and d=2 31 for K=Zq. To speead up this procedure we
used loaded tables for function e(x, y)=x y where x is element of K* and y is in Zd. So
the size of table is d 2.
To computation of the ciphertext requires nN(n, K) usages of e(x, y) together with
nN(n, K) multiplications and N(n, K) additions. This part of computation depends
heavily on the choice of computer. It is easy to see that Alice conducts decryption in
essentially shorter time than encryption by public user.
We implement the cryptosystems in the cases of graphs A(n, K) and D(n, K) in
cases of finite fields and arithmetical rings in various cases of length j of the symbolic
word.
Below we present the measurement of densities of the encryption map. These
parameters are important for the evaluation of the execution speed. They
illustratejigjly nonlinear nature of encryption function.
We consider 3 following cases.
Case 1. Both linear transformations in the combination are identity maps.
Case2. Both linear transformations are maps of kind x1→ x1+a2x2+a3x3,…, anxn,
ai ≠ 0, xj →x1+j for j=1, 3, …, n.
Case 3. Both linear maps have nonsingular matrices with nozero entries.
~ 146 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
Fig. 1. Number of monomial terms of the
cubic map induced by the graph (𝑛 = 128)
(graph 𝐷(𝑛, 𝐾), 𝐾 = 𝑍232 , 𝐹232), case I
Fig. 2. Number of monomial terms of the
cubic map induced by the graph (𝑛 = 128)
(graph 𝐷(𝑛, 𝐾), 𝐾 = 𝑍232 , 𝐹232), case II
Fig. 3. Number of monomial terms of the
cubic map induced by the graph (𝑛 = 128)
(graph 𝐷(𝑛, 𝐾), 𝐾 = 𝑍232 , 𝐹232), case III
Fig. 4. Number of monomial terms of the
cubic map induced by the graph (𝑛 = 128)
(graph 𝐴(𝑛, 𝐾), 𝐾 = 𝑍232 , 𝐹232), case I
Fig. 5. Number of monomial terms of the
cubic map induced by the graph (𝑛 = 128)
(graph 𝐴(𝑛, 𝐾), 𝐾 = 𝑍232 , 𝐾 = 𝐹232, case II
Fig. 6. Number of monomial terms of the
cubic map induced by the graph (𝑛 = 128)
(graph 𝐴(𝑛, 𝐾), 𝐾 = 𝑍232 , 𝐾 = 𝐹232, case III
~ 147 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
Table 1. Number of monomial terms of the cubic map induced by the graph 𝐷(𝑛, 𝐹232),
case I
length of the word
𝑛 16 32 64 128 256
16 145 145 145 145 145
32 544 545 545 545 545
64 1584 2112 2113 2113 2113
128 3664 6240 8320 8321 8321
Table 2. Number of monomial terms of the cubic map induced by the graph 𝐷(𝑛, 𝐹232),
case II
length of the word
𝑛 16 32 64 128 256
16 3649 3649 3649 3649 3649
32 41355 41356 41356 41356 41356
64 440147 529052 529053 529053 529053
128 3823600 6149213 7405944 7405945 7405945
Table 3. Number of monomial terms of the cubic map induced by the graph 𝐷(𝑛, 𝐹232),
case III
length of the word
𝑛 16 32 64 128 256
16 6544 6544 6544 6544 6544
32 50720 50720 50720 50720 50720
64 399424 399424 399424 399424 399424
128 3170432 3170432 3170432 3170432 3170432
Table 4. Number of monomial terms of the cubic map induced by the graph 𝐴(𝑛, 𝐹232),
case I
length of the word
𝑛 16 32 64 128 256
16 250 250 250 250 250
32 770 1010 1010 1010 1010
64 1810 3074 4066 4066 4066
128 3890 7202 12290 16322 16322
~ 148 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
Table 5. Number of monomial terms of the cubic map induced by the graph 𝐴(𝑛, 𝐹232),
case II
length of the word
𝑛 16 32 64 128 256
16 5623 5623 5623 5623 5623
32 53581 62252 62252 62252 62252
64 454375 680750 781087 781087 781087
128 3607741 6237144 9519921 10826616 10826616
Table 6. Number of monomial terms of the cubic map induced by the graph 𝐴(𝑛, 𝐹232),
case III
length of the word
𝑛 16 32 64 128 256
16 6544 6544 6544 6544 6544
32 50720 50720 50720 50720 50720
64 399424 399424 399424 399424 399424
128 3170432 3170432 3170432 3170432 3170432
7. Conclusion
The paper is dedicated to feasibility studies for two families of multivariate public
keys which use the transformations of linear degree O(n) of
n-dimensional affine spaces over Fq and Zq where q=232. These cryptosystems use
Eulerian transformations which have degree O(n) and convert each variable xi to a
monomial term. The cryptosystem based on the composition of Eulerian and cubic
transformations were introduced in [7] and [8]. They attracted attention of some
cryptanalytics in Ukraine. Each of these cryptosystems is implemented in cases of
extremal graphs D(n, K) and A(n, K) where K is finite field or arithmetical ring.
During 9 years period after the publications cryptanalytical instruments to break
these cryptosystem were not found. Recently [9] the serious obfuscations of these
public key were suggested. The cubic maps with cubic inverses were substituted
by cubic maps with inverses of high degree. Computer simulations demonstrate
that the density of obfuscated schemes are the same with densities of original
schemes.
The idea to use loaded tables for powers of regular elements make the
implementation feasible task. It requires essential memory in the cases of a large
field or large arithmetic ring but for modern computers it is not a problem.
Noteworthy that users can work with nonbijective transformation via the change
of bijective linear transformation for injective linear map from Kn to Kt where t>n.
This modification can be useful for the realisation of digital signatures
procedures.
We are going to present described algorithms for the state certification in Ukraine.
~ 149 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
REFERENCES
1. Post-Quantum Cryptography: Call for Proposals: https://csrc.nist.gov/Project; Post-
Quantum-Cryptography-Standardization/Call-for-Proposals, Post-Quantum Cryptography:
Round 2 Submissions.
2. M. Andrzejczak, The Low –Area FPGA Design for the Post – Quantum Cryptography
Proposal Round 5, Proceedings of the Federated Conference on Computer Science and
Information Systems (FedCSIS), Cryptography and Security Systems, Leipzig, September,
2019 (to appear).
3. R. J. McEliece, A Public-Key Cryptosystem Based On Algebraic Coding
Theory (1978), DSN Progress Report, 44: 114–116.
4. Anne Canteaut, François-Xavier Standaert (Eds.), Eurocrypt 2021, LNCS 12696, 40th
Annual International Conference on the Theory and Applications of Cryptographic
Techniques Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I, Springer, 2021,
839 p.
5. V. Ustimenko, U. Romanczuk-Polubiec, A. Wroblewska, M. Polak, E. Zhupa, On the
constructions of new symmetric ciphers based on non-bijective multivariate maps of
prescribed degree, Security and Communication Networks, Volume 2019, Article ID
2137561, 15 pages https://doi.org/10.1155/2019/2137561
6. V. Ustimenko, Graphs in terms of Algebraic Geometry, symbolic computations and
secure communications in Post-Quantum world, UMCS Editorial House, Lublin,
2022, 198 p.
7. V. Ustimenko, On new multivariate cryptosystems based on hidden Eulerian equations,
Dopov. Nath Acad of Sci, Ukraine, 2017. № 5, pp 17-24.
8. V. Ustimenko, On new multivariate cryptosystems based on hidden Eulerian equations
over finite fields, Cryptology ePrint Archive, 093, 2017.
9. Vasyl Ustimenko, On Extremal Algebraic Graphs and Multivariate Cryptosystems
IACR e-print archive, 2022/1537.
10. V. Ustimenko, On new symbolic key exchange protocols and cryptosystems based on
hidden tame homomorphism. Dopovidi. NAS of Ukraine, 2018, n 10, pp. 26-36.
11. V. Ustimenko, On the families of stable transformations of large order and their
cryptographical applications, Tatra Mt. Math. Publ., 70 (2017), 107-117.
12. V. Ustimenko, On desynchronised multivariate El Gamal algorithm, Cryptology ePrint
Archive, 712, 2017.
13. V. Ustimenko, M. Klisowski, On Noncommutative Cryptography with cubical
multivariate maps of predictable density, In “Intelligent Computing’’, Proceedings of the
2019 Computing Conference, Volume 2, Part ofAdvances in Intelligent Systems and
Computing (AISC, volume 998), pp. 654-674.
14. V. Ustimenko, On desynchronised multivariate algorithms of El Gamal type for stable
semigroups of affine Cremona group, Theoretical and Applied Cybersecurity, National
Technical University of Ukraine “Igor Sikorsky Kiev Polytechnic Institute”, vol 1, 2019,
pp 22-30.
15. V. Ustimenko, On the usage of postquantum protocols defined in terms of transformation
semigroups and their homomophisms, Theoretical and Applied Cybersecurity, National
Technical University of Ukraine “Igor Sikorsky Kiev Polytechnic Institute”, Volume 1,
No. 2, pp. 32-44 (2020).
16. V. Ustimenko, On the families of stable transformations of large order and their
cryptographical applications, Tatra Mt. Math. Publ., 70 (2017), рр. 107-117.
17. V. Ustimenko, M. Klisowski On D(n; q) quotients of large girth and hidden homomorphism
based cryptographic protocols. FedCSIS (Communication Papers) 2022: рр. 199-206.
18. Alexei G. Myasnikov; Vladimir Shpilrain and Alexander Ushakov (2011), Non-
commutative Cryptography and Complexity of Group-theoretic Problems, American
Mathematical Society.
http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF
http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF
https://doi.org/10.1155/2019/2137561
https://link.springer.com/bookseries/11156
https://link.springer.com/bookseries/11156
https://dblp.org/db/conf/fedcsis/fedcsis2022c.html#UstimenkoK22
~ 150 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
19. F. Lazebnik, V. Ustimenko, Some Algebraic Constructions of Dense Graphs of Large
Girth and of Large Size, DIMACS series in Discrete Mathematics and Theoretical
Computer Science, v. 10, (1993) рр. 75-93.
20. F. Lazebnik, V. Ustimenko and A.J. Woldar, A new series of dense graphs of high
girth, Bulletin of the AMS 32 (1) (1995), рр. 73-79.
21. V. Ustimenko, On new results on Extremal Graph Theory, Theory of Algebraic Graphs
and their applications in Cryptography and Coding The ory, Reports of Nath. Acad. of Sci.
of Ukraine, 2022, No. 4, рр. 42-49.
22. Yu. Bodnarchuk, Every regular automorphism of the affine Cremona group is inner,
Journal of Pure and Applied Algebra 157 (2001), рр. 115-119.
23. I.R. Shafarevich, On some infinite dimension groups II, Izv. Akad. Sci. Ser. Math.
2 (1) (1981), рр. 214-226.
24. M. Noether, Luigi Cremona, Mathematische Annalen, 59 (1904), pp. 1-19.
25. V. Ustimenko, Maximality of affine group, hidden graph cryptosystem and graph’s
stream ciphers, Journal of Algebra and Discrecadete Mathematics, 2005, v.1, pp 51-65.
26. O. Zariski, P. Samuel, Commutative algebra, 2, Springer (1975).
27. I.R. Shafarevich, Basic algebraic geometry, Springer (1977).
28. R. Hartshorne, Algebraic geometry, Springer (1977).
29. B. Bolloba’s, Extremal Graph Theory. London: Academic Press, 1978, 440 P.
30. V. A. Ustimenko, Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography,
Journal of Mathematical Sciences, Springer, vol. 140, N 3 (2007), pp. 412-434.
31. V. Ustimenko, On the families of algebraic graphs with the fastest growth of cycle
indicator and their applications, IACR e-print archive 2022/1668.
32. R. Wagner, M. R. Magyarik, “A Public-Key Cryptosystem Based on the Word Problem”,
Advances in Cryptology, Proceedings of CRYPTO‘84, Santa Barbara, California, USA,
August 19-22, 1984.
33. D. N. Moldovyan and N.A. Moldovyan, A New Hard Problem over Non-commutative
Finite Groups for Cryptographic Protocols, International Conference on Mathematical
Methods, Models, and Architectures for Computer Network Security, MMM-ACNS 2010:
Computer Network Security pp 183-194.
34. L. Sakalauskas, P. Tvarijonas and A. Raulynaitis, Key Agreement Protocol (KAP) Using
Conjugacy and Discrete Logarithm Problem in Group Representation Level,
INFORMATICA, 2007, vol. 18, No 1, рр. 115-124.
35. V. Shpilrain, A. Ushakov, The conjugacy search problem in public key cryptography:
unnecessary and insufficient, Applicable Algebra in Engineering, Communication and
Computing, August 2006, Volume 17, Issue 3–4, pp. 285–289.
36. Delaram Kahrobaei and Bilal Khan, A non-commutative generalization of ElGamal key
exchange using polycyclic groups, In IEEE GLOBECOM 2006-2006 Global
Telecommunications Conference [4150920] DOI: 10.1109/GLOCOM.2006
37. Alexei Myasnikov; Vladimir Shpilrain and Alexander Ushakov (2008), Group-based
Cryptography, Berlin: BirkhäuserVerlag.
38. Zhenfu Cao (2012), New Directions of Modern Cryptography. Boca Raton: CRC Press,
Taylor & Francis Group. ISBN 978-1-4665-0140-9.
39. Benjamin Fine, et. al. “Aspects of Non abelian Group Based Cryptography: A Survey
and Open Problems”, arXiv:1103.4093.
40. I. Anshel, M. Anshel and D. Goldfeld, An algebraic method for public-key cryptography.
Math. Res. Lett. 6(3–4), рр. 287–291 (1999).
41. S.R. Blackburn and S.D. Galbraith, Cryptanalysis of two cryptosystems based on group
actions. In: Advances in Cryptology—ASIACRYPT ’99. Lecture Notes in Computer
Science, vol. 1716, pp. 52–61. Springer, Berlin (1999).
42. K.H. Ko, S.J. Lee, J.H. Cheon, J.W. Han, J.S. Kang and C. Park, New public-key
cryptosystem using braid groups. In: Advances in Cryptology—CRYPTO 2000, Santa
Barbara, CA. Lecture Notes in Computer Science, vol. 1880, pp. 166–183. Springer, Berlin
(2000).
https://en.wikipedia.org/wiki/International_Standard_Book_Number
https://en.wikipedia.org/wiki/Special:BookSources/978-1-4665-0140-9
https://en.wikipedia.org/wiki/ArXiv
https://arxiv.org/abs/1103.4093
~ 151 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
43. G. Maze, C. Monico and J. Rosenthal, Public key cryptography based on semigroup
actions, Adv. Math. Commun. 1(4), рр. 489–507 (2007).
44. P.H. Kropholler and S.J. Pride, W.A.M. Othman K.B. Wong, P.C. Wong, Properties of
certain semigroups and their potential as platforms for cryptosystems, Semigroup Forum
(2010) 81: рр. 172–186.
45. J.A. Lopez Ramos, J. Rosenthal, D. Schipani and R. Schnyder, Group key management
based on semigroup actions, Journal of Algebra and its applications, vol. 16 (to appear in
2019).
46. Gautam Kumar and Hemraj Saini, Novel Noncommutative Cryptography Scheme Using
Extra Special Group, Security and Communication Networks, Volume 2017, Article ID
9036382, 21 pages, https://doi.org/10.1155/2017/9036382
47. V. Ustimenko, U. Roma´nczuk, On Extremal Graph Theory, Explicit Algebraic
Constructions of Extremal Graphs and Corresponding Turing Encryption Machines, in
”Artificial Intelligence, Evolutionary Computing and Metaheuristics”, In the footsteps of
Alan Turing Series: Studies in Computational Intelligence, Vol. 427, Springer, 2013, Volume
427, pр. 257-285.
48. V. A. Roman’kov, A nonlinear decomposition attack, Groups Complex. Cryptol. 8,
No. 2 (2016), 197-207.27.
49. V. Roman’kov, An improved version of the AAG cryptographic protocol, Groups
Complex. Cryptol, 11, No. 1 (2019), 35-42.
50. A. Ben-Zvi, A. Kalka and B. Tsaban, Cryptanalysis via algebraic span, In: Shacham H.
and Boldyreva A. (eds.) Advances in Cryptology - CRYPTO 2018 - 38th Annual
International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018,
Proceedings, Part I, Vol. 10991, 255{274, Springer, Cham (2018).
51. B. Tsaban, Polynomial-time solutions of computational problems in
noncommutative-algebraic cryptography, J. Cryptol. 28, No. 3 (2015), 601-622.
52. V. Roman’kov, Cryptanalysis of a new version of the MOR scheme, arXiv:1911.00895.
53. V. Roman’kov, Cryptanalysis of two schemes of Baba et al. by linear algebra
methods. CoRR abs/1910.09480 (2019).
54. N. Koblitz, Algebraic aspects of cryptography, Springer (1998), 206 p.
55. L. Goubin, J. Patarin and Bo-Yin Yang, Multivariate. Cryptography, Encyclopedia of
Cryptography and Security, (2nd Ed.) 2011, 824-828.
56. Billet O, Patarin J, Seurin Y (2008) Analysis of intermediate field systems. In:
Proceedings of SCC 2008, Beijing.
57. Chen AI-T, Chen M-S, Chen T-R, Cheng C-M, Ding J, Kuo EL-H, Lee FY-S, Yang B-Y.
(2009) SSE Implementation of multivariate PKCs on modern x86 CPUs. In: Proceedings of
CHES 2009. Lecture notes in computer science, vol 5747, pp 33–48.
58. Courtois NT (2001) Efficient zero-knowledge authentication based on a linear algebra
problem MinRank. In: Proceedings of ASIACRYPT 2001. Lecture notes in computer
science, vol 2248. Springer, pp 402–421.
59. Courtois NT, Goubin L, Patarin J (2001) QUARTZ, 128-bit long digital signatures. In:
Proceedings of CT-RSA 2011. Lecture notes in computer science, vol 2020. Springer,
pp 282–297.
60. Ding J, Dubois V, Yang B-Y, Chen C-H, Cheng C-M (2008) Can SFLASH be repaired.
In: Proceedings of ICALP 2008. Lecture notes in computer science, vol 5126. Springer,
pp 691–701.
61. Ding J, Schmidt D (2005) Rainbow, a new multivariable polynomial signature scheme.
In: Proceedings of ACNS 2005. Lecture notes in computer science, vol 3531. Springer,
pp 164–175.
62. Ding J, Werner F, Yang B-Y, Chen C-H, Chen M-S (2008) Odd-char multivariate hidden
field equations, Cryptology e-print archive report 2008/543 version 20081229:161921.
63. Ding J, Wolf C, Yang B-Y (2007) 𝓁𝓁-Invertible Cycles for Multivariate Quadratic (MQ)
Public Key Cryptography. In: Proceedings of PKC 2007. Lecture notes in computer science,
vol 4450, pp 266–281.
https://doi.org/10.1155/2017/9036382
~ 152 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
64. Ding J, Yang B-Y, Chen C-H, Chen M-S, Cheng C-M (2008) New differential-algebraic
attacks and reparametrization of rainbow. In: Proceedings of ACNS 2008. Lecture notes in
computer science, vol 5037, pp 242–257.
65. Ding J, Yang B-Y (2009) Multivariate public-key cryptography. In: Bernstein DJ,
Buchmann J, Dahmen E (eds) Post-quantum cryptography. Springer, ISBN: 978-3-540-
88701-0, e-ISBN: 978-3-540-88702-7.
66. Dubois V, Fouque P-A, Shamir A, Stern J (2007) Practical cryptanalysis of SFLASH. In:
Proceedings of Crypto 2007. Lecture notes in computer science, vol 4622, pp 1–12.
67. Faugère J-C, Joux A (2003) Algebraic cryptanalysis of hidden field equation (HFE)
Cryptosystems using Gröbner bases. In: Proceedings of Crypto 2003. Lecture notes in
computer science, vol 2729, pp 44–60.
68. Faugère J-C, Perret L (2006) Polynomial equivalence problems – algorithmic and
theoretical aspects. In: Proceedings of Eurocrypt 2006. Lecture notes in computer science,
vol 4004. Springer, pp 30–47.
69. Kipnis A, Patarin J, Goubin L (1999) Unbalanced oil and vinegar signature schemes. In:
Proceedings of Eurocrypt’99. Lecture notes in computer science, vol 1592. Springer,
pp 206–222.
70. Kipnis A, Shamir A (1998) Cryptanalysis of the oil and vinegar signature scheme. In:
Proceedings of CRYPTO’98. Lecture notes in computer science, vol 1462, pp 257–266.
71. Matsumoto T, Imai H, Harashima H, Miyakawa H (1983) A class of asymmetric
cryptosystems using obscure representations of enciphering functions. In: Proceedings of the
1983 national convention record on information systems, IECE Japan.
72. Matsumoto M, Imai H (1986) Algebraic methods for constructing asymmetric
cryptosystems. In: Proceedings of the 3rd international conference on Algebraic Algorithms
and Error-Correcting Codes (AAECC-3), Grenoble, France, 15-19 July 1985. Lecture notes
in computer science, vol 229. Springer, pp 108–119.
73. Matsumoto M, Imai H (1988) Public quadratic polynomial-tuples for efficient signature
verification and message-encryption. In: Proceedings of Eurocrypt’88. Lecture notes in
computer science, vol 330. Springer, pp 419–545.
74. Patarin J (1995) Cryptanalysis of the Matsumoto and Imai public key scheme of
Eurocrypt’88. In: Proceedings of CRYPTO’95. Lecture notes in computer science, vol 963.
Springer, pp 248–261.
75. Patarin J (1996) Hidden fields equations (HFE) and isomorphisms of polynomials (IP):
two new families of asymmetric algorithms. In: Proceedings of Eurocrypt’96. Lecture notes
in computer science, vol 1070. Springer, pp 33–48.
76. Patarin J, Courtois N, Goubin L (2001) FLASH, a Fast Multivariate Signature Algorithm.
In: Proceedings of the conference on topics in cryptology: the cryptographer’s track at RSA.
Lecture notes in computer science, vol 2020, Springer, pp 298–307.
77. Tsujii S, Itoh T, Fujioka A, Kurosawa K, Matsumoto T (1988) A public-key cryptosystem
based on the difficulty of solving a system of nonlinear equations. Syst Comput Jpn 19:10–18.
78. Yang B-Y, Chen J-M, Chen Y-H (2004) TTS: high-speed signatures on a low-cost smart
card. In: Proceedings of CHES 2004. Lecture notes in computer science, vol 3156. Springer,
pp 371–385.
79. V. Ustimenko, O. Pustovit, T. Svyrydenjo. On the stream ciphers based on the hidden
algebraic graphs, CPITS II 2025, рр. 358-365, https://ceur-ws.org/Vol-4145/short3.pdf80
80.V. Ustimenko, O. Pustovit, (2023). On security of GIS systems with N-tier architecture
and family of graph based ciphers. Екологічна безпека та природокористування, 47 (3),
113-132. https://doi.org/10.32347/2411-4049.2023.3.113-132
81. T. Chojecki, G. Erskine, J. Tuite, V. Ustimenko, On Affine Forestry over Integral
Domains and Families of Deep Jordan–Gauss Graphs, Eur. J. Math., 11(10) (2025).
doi:10.1007/s40879-024-00798-2
The article was received 12.01.2026, received after revision 23.02.2026, accepted
26.03.2026
~ 153 ~
ISSN: 2411-4049. Екологічна безпека та природокористування, вип. 2 (58), 2026
В.О. Устименко, О.С. Пустовіт
ПРО ЕКСТРЕМАЛЬНІ АЛГЕБРАЇЧНІ ГРАФИ, ЕЙЛЕРОВІ ПЕРЕТВОРЕННЯ
ТА РЕАЛІЗАЦІЇ БАГАТОВИМІРНИХ КРИПТОСИСТЕМ
Анотація. Представлено результати імплементації кількох відкритих ключів
криптографії від багатьох змінних лінійного ступеня розміру O(n) та поліноміальної
густини, визначених над комутативним кільцем K з нетривіальною
мультиплікативною групою K*. Простір відкритих текстів цих криптосистем дорівнює
(K*)n, а простір шифрограм – Kn. Відображення шифрування є обмеженням на (K*)n
поліноміального перетворення простору Kn, що є композицією спеціального
Ейлерівського перетворення з кубічним перетворенням криптографії від багатьох
змінних вигляду T1QT2, де T1 і T2 – афінні бієктивні перетворення, a Q – нелінійне
перетворення, визначене шляхом на алгебраїчному дводольному графі, точки і прямі
якого утворюють афінний простір Kn.
Схема реалізована для випадків K=Fq і K=Zq, q=232. Знання приватного ключа
дозволяє розшифрувати повідомлення від публічного користувача за час O(n2).
Криптосистеми є узагальненнями алгоритмів, запропонованих 9 років тому,
криптоаналіз для яких невідомий. Задача зламання криптосистеми еквівалентна
системі нелінійних рівнянь від n змінних ступеня cn, дe c>0. Комп’ютерних пакетів
для дослідження таких систем не розроблено.
Ключові слова: криптографія від багатьох змінних, символьні обчислення,
алгебраїчні графи, теорія екстремальних графів.
Стаття надійшла до редакції 12.01.2026, надійшла після рецензування 23.02.2026,
прийнята 26.03.2026
Устименко Василь Олександрович
доктор фізико-математичних наук, професор, завідуючий відділу інформаційної
безпеки Інституту телекомунікацій і глобального інформаційного простору НАН
України
Visiting Professor of Royal Holloway University of London, vasyl.ustymenko@rhul.ac.uk
Адреса робоча: 03186 Україна, м. Київ, Чоколівський бульвар 13
ORCID ID: https://orcid.org/0000-0002-2138-2357 e-mail: vasulustimenko@yahoo.pl
Пустовіт Олександр Сергійович
кандидат технічних наук, старший науковий співробітник Інституту телекомунікацій і
глобального інформаційного простору НАН України
Адреса робоча: 03186 Україна, м. Київ, Чоколівський бульвар 13
ORCID ID: https://orcid.org/0000-0002-3232-1787 e-mail: sanyk_set@ukr.net
https://orcid.org/0000-0002-2138-2357
mailto:vasulustimenko@yahoo.pl
https://orcid.org/0000-0002-3232-1787
mailto:sanyk_set@ukr.net
n
A ( n , F 2 32 )
n
A ( n , F 2 32 )
n
A ( n , F 2 32 )
n
D ( n , F 2 32 )
n
D ( n , F 2 32 )
n
D ( n , F 2 32 )
K = Z 2 32 , K = F 2 32
A ( n , K )
n = 128
K = Z 2 32 , K = F 2 32
A ( n , K )
n = 128
K = Z 2 32 , F 2 32
A ( n , K )
n = 128
K = Z 2 32 , F 2 32
D ( n , K )
n = 128
K = Z 2 32 , F 2 32
D ( n , K )
n = 128
K = Z 2 32 , F 2 32
D ( n , K )
n = 128
≠
|
| id | es-journalinua-article-364963 |
| institution | Environmental safety and natural resources |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-07-18T01:00:09Z |
| publishDate | 2026 |
| publisher | Kyiv National University of Construction and Architecture |
| record_format | ojs |
| resource_txt_mv | es-journalinua/e7/74ce40f058e1afcaa1013351d8615fe7.pdf |
| spelling | es-journalinua-article-3649632026-07-17T09:24:50Z On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems Ustimenko, Vasyl Pustovit, Oleksandr криптографія від багатьох змінних символьні обчислення алгебраїчні графи теорія екстремальних графів Multivariate Cryptography Symbolic Computations Algebraic Graphs Extremal Graph Theory Results of implementation of several multivariate public keys of linear degree of size O(n) and polynomial density defined over commutative ring K with the nontrivial multiplicative group K*. are presented. The space of plaintexts of these cryptosystems is (K*)n and space of ciphertexts is Kn. The encryption map is the restriction on (K*)n of polynomial transformation of the space Kn which is the composition of special Eulerian trams-formation with cubical map of Multivariate Cryptography of kind T1QT2, where T1 and T2 are bijective affine trans-formations and Q is a nonlinear map defined via walk on algebraic bipartite graph points and lines of which form the space Kn.This scheme is implemented for the cases K=Fq and K=Zq, q=232. The knowledge of private key allows to decipher of the message from public user in time O(n2). The cryptosystems are generalisations of algorithms suggested 9 years ago cryptanalysis of which are unknown. The problem of breaking the cryptosystem is equivalent to solving of system of nonlinear equations in n variables of degree cn, de c&gt;0. The computer packages for the investigation of such systems are undeveloped. Представлено результати імплементації кількох відкритих ключів криптографії від багатьох змінних лінійного ступеня розміру O(n) та поліноміальної густини, визначених над комутативним кільцем K з нетривіальною мультиплікативною групою K*. Простір відкритих текстів цих криптосистем дорівнює (K*)n, а простір шифрограм – Kn. Відображення шифрування є обмеженням на (K*)n поліноміального перетворення простору Kn, що є композицією спеціального Ейлерівського перетворення з кубічним перетворенням криптографії від багатьох змінних вигляду T1QT2, де T1 і T2 – афінні бієктивні перетворення, a Q – нелінійне перетворення, визначене шляхом на алгебраїчному дводольному графі, точки і прямі якого утворюють афінний простір Kn.Схема реалізована для випадків K=Fq і K=Zq, q=232. Знання приватного ключа дозволяє розшифрувати повідомлення від публічного користувача за час O(n2). Криптосистеми є узагальненнями алгоритмів, запропонованих 9 років тому, криптоаналіз для яких невідомий. Задача зламання криптосистеми еквівалентна системі нелінійних рівнянь від n змінних ступеня cn, дe c&gt;0. Комп’ютерних пакетів для дослідження таких систем не розроблено. Kyiv National University of Construction and Architecture 2026-05-01 Article Article application/pdf https://es-journal.in.ua/article/view/364963 10.32347/2411-4049.2026.2.135-153 Environmental safety and natural resources; Vol. 58 No. 2 (2026): Environmental safety and natural resources; 135-153 Екологічна безпека та природокористування; Том 58 № 2 (2026): Екологічна безпека та природокористування; 135-153 2616-2121 2411-4049 10.32347/2411-4049.2026.2 en https://es-journal.in.ua/article/view/364963/350488 Copyright (c) 2026 Vasyl Ustimenko, Oleksandr Pustovit http://creativecommons.org/licenses/by/4.0 |
| spellingShingle | Multivariate Cryptography Symbolic Computations Algebraic Graphs Extremal Graph Theory Ustimenko, Vasyl Pustovit, Oleksandr On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems |
| title | On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems |
| title_alt | On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems |
| title_full | On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems |
| title_fullStr | On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems |
| title_full_unstemmed | On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems |
| title_short | On extremal algebraic graphs, Eulerian transformations and implementations of multivariate cryptosystems |
| title_sort | on extremal algebraic graphs, eulerian transformations and implementations of multivariate cryptosystems |
| topic | Multivariate Cryptography Symbolic Computations Algebraic Graphs Extremal Graph Theory |
| topic_facet | криптографія від багатьох змінних символьні обчислення алгебраїчні графи теорія екстремальних графів Multivariate Cryptography Symbolic Computations Algebraic Graphs Extremal Graph Theory |
| url | https://es-journal.in.ua/article/view/364963 |
| work_keys_str_mv | AT ustimenkovasyl onextremalalgebraicgraphseuleriantransformationsandimplementationsofmultivariatecryptosystems AT pustovitoleksandr onextremalalgebraicgraphseuleriantransformationsandimplementationsofmultivariatecryptosystems |