=Paper=
{{Paper
|id=Vol-3288/short6
|storemode=property
|title=On-Time Dependent Linguistic Graphs and Solutions of Postquantum Multivariate Cryptography (short paper)
|pdfUrl=https://ceur-ws.org/Vol-3288/short6.pdf
|volume=Vol-3288
|authors=Vasyl Ustimenko,Oleksandr Pustovit
|dblpUrl=https://dblp.org/rec/conf/cpits/UstimenkoP22
}}
==On-Time Dependent Linguistic Graphs and Solutions of Postquantum Multivariate Cryptography (short paper)==
https://ceur-ws.org/Vol-3288/short6.pdf
On-Time Dependent Linguistic Graphs and Solutions
of Postquantum Multivariate Cryptography
Vasyl Ustimenko1,2 and Oleksandr Pustovit2
1
University of Royal Holloway in London, Egham Hill, Egham TW20 0EX, United Kingdom
2
Institute of Telecommunications and the Global Information Space of the National Academy of Sciences of
Ukraine, 13 Chokolivsky boul., Kyiv, 02000, Ukraine
Abstract
Time dependent linguistic graphs over abelian group H are introduced. Subsemigroups of such
endomorphisms together with their special homomorphic images are used as platforms of
cryptographic protocols of noncommutative cryptography. The security of these protocol is
evaluated via complexity of hard problem of decomposition of Eulerian transformation into the
product of known generators of the semigroup. Nowadays the problem is intractable one in the
Postquantum setting. The symbiotic combination of such protocols with special graph based
stream ciphers working with plaintext space of kind Km where m = nt for arbitrarily chosen
positive parameter t is proposed. This way we obtained a cryptosystem with
encryption/decryption procedure of complexity O(m1+2/t).
Keywords 1
Post quantum cryptography, computer algebra, affine Cremona semigroup, Eulerian
transformations, linguistic graphs, commutative rings.
1. Introduction evaluating proposed public key algorithms.
Asymmetrical Cryptography is largely based on
theoretical complexity assumptions. Fundamental
Theoretical danger of quantum computers to
question whether or not P = NP have been open
Information Security has been known since 1994.
for decades. This assumption is connected with
In the case of asymmetrical cryptography it
fundamental conjecture of cryptography that there
affects both protocol based cryptosystems for
are no polynomial-time algorithms for solving
which encryption tools are not given to public and
any NP-hard problem.
public key cryptosystems.
Such theoretical danger to Cryptography
For instance, a symbiotic combination of
increase interest to problems that are hard to solve
Diffie -Hellman protocol (DH) with one time pad
in the quantum setting. Noteworthy that many of
encryption or El Gamal cryptosystem in terms of
the fundamental problems about polynomial time
DH algorithm will not be safe in Postquantum era
problems have analogs at the level of
because discrete logarithm problem is not
computability. Many NP-hard problems have
quantum resistant. Popular RSA public key
analogs over various algebraic and combinatorial
cryptosystem is not quantum secure because
structures. Techniques from computational or
factorisation problem can be solved in polynomial
statistical algebra afford insights into the
time with the usage of quantum computer.
distribution of hard instances.
Nowadays this vulnerability is not only
Post Quantum Cryptography is divided into
theoretical because large corporations like IBM,
the following major areas: Code-based
Google, governmental scientific centers in
cryptography, Lattice-based cryptography,
Europe, China, UK, Jappan and USA began to
Multivariate cryptography. Hash functions base
build working quantum computers.
cryptography, Supersingular elliptic curve
That is why NSA has advised researchers to
isogeny cryptography, Noncommutative
work on new security products, NIST and ETSI
Cryptography. This paper is dedicated to a new
are currently investigating relevant standards and
CPITS-2022: Cybersecurity Providing in Information and Telecommunication Systems, October 13, 2022, Kyiv, Ukraine
EMAIL: vasulustimenko@yahoo.pl (V. Ustimenko); sanyk_set@ukr.net (O. Pustovit)
ORCID: 0000-0002-2138-2357 (V. Ustimenko); 0000-0002-3232-1787 (O. Pustovit)
©️ 2022 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
96
branch of Multivariate Cryptography (MC) transformation of Classical Multivariate
dealing with polynomial transformations of affine Cryptography we can work with several
spaces over various commutative rings of polynomial maps. It allows to construct protocols
unbounded degree and large semigroups or which security rests on difficult problem to
groups of such transformations. decompose multivariate map into composition of
Multivariate cryptography is usually defined several given generators. If the map and
as the set of cryptographic schemes using the generators are given in a standard form of
computational hardness of the Polynomial System Multivariate Cryptography then the
Solving problem over a finite field. Solving decomposition task is intractable problem of Post
systems of multivariate polynomial equations is Quantum Cryptography. In fact we work in the
proven to be NP-hard or NP-complete. That is area of intersection of MC with the
why those schemes are often considered to be Noncommutative Cryptography which uses
good candidates for post-quantum cryptography. complexity of problems from Noncommutative
Classical Multivariate Cryptography uses systems algebra on groups, semigroups, algebras and other
of quadratic (rarely cubic) equations. The idea to algebraic systems [4–21], recently interesting
use degree 2 is motivated by possibility to cryptanalytic results have been obtained in this
transform system of equations of any constant area [22, 23].
degree to equivalent quadratic system of large The output of the protocol can be used for safe
size. Some weakness of this argument is caused creation of multivariate encryption map or safe
by the fact that such transformation can seriously delivery of such map from one correspondent to
affect the complexity of system. another [6, 24]. This approach can be also used for
The first quadratic multivariate scheme based the construction of digital signatures [6]. Note that
on multivariate equations was introduced by protocol based multivariate algorithms essentially
Matsumoto and Imai in 1988. These authors not differs from traditional for MC public keys. The
only introduced a multivariate scheme but in fact speed of execution of protocols eseentially differs
a general principle to design public-key in the cases of different platforms. In this paper,
cryptosystems using multivariate equations. we continue to use algebraic graphs for the
There are now plenty of proposals based on this construction of multivariate transformations. We
principle that are attractive because they offer the select the case of most efficient (O(n3)) case of
possibility to have very short asymmetric Eulerian transformations [25, 26], and suggest
signatures that require only a small amount of faster algorithm of generation initial data
resources on embedded devices [1–3]. After an constructed in terms of algebraic graphs theory.
intense period of cryptanalysis, few schemes We convert the protocol based on Eulerian
emerged as the most robust solutions: HFE transformations of affine space Kn to the
(Hidden Field Equations) and UOV (Unbalanced cryptosystem of El Gamal type which work with
Oil and Vinegar), both developed by J. Patarin in potentially infinite tuples of characters of
the late 1990’s. Variants of these schemes have elements from commutative ring K. In fact, the
been submitted to the post-quantum dimension of plaintext space is m = O(nt) where
standardization process for public key algorithms parameter t is more 1. The symmetric encryption
as encryption tools or digital signature algorithm has complexity O(m1+2/t). So, it is
instruments organized by NIST. For the third possible to work with the large files. We hope that
round of this competition in July 2020 NIST does this postquantum cryptosystem can be used
not select multivariate algorithm in the category instead of symbiotic combination of classical
of encryption instruments. Remaining Diffie-Hellman algorithm and one time pad.
Unbalanced Oil and Vinegar Rainbow system is In Section 2 we define affine Cremona group
investigated as possible digital signature tool. and affine Cremona semigroup over general
We believe in the capacity of Multivariate commutative ring K which are central objects of
Cryptography (MC) in wide sense as a source of Multivariate Cryptography and Theory of
encryption cryptosystems. Recent constructions Symbolic Computations. Additionally, we
of families of semigroups and groups of introduce Eulerian semigroup ESn(K) and group
transformation of affine spaces Kn with possibility EGn(K) via endomorphism of K[x1, x2, …, xn]
of computation of n elements from the semigroup moving generic variable xi into monomial term.
in polynomial time gives opportunity to use We define invertable Jordan-Gauss
methods of Semigroup based cryptography in transformations of EGn(K) as triangular
multivariate settings. So instead of one nonlinear transformation of (K*)n with obvious procedure of
97
reimage computation. Semigroup EGn(K) satisfies Symbol End(K[x1, x2,…, xn]) = En(K) stands for
to multiple composition property (MCP), which semigroup of all endomorphisms of K[x1, x2,…,
means ability to compute the composition of n xn]. So we can identify F and the formal rule x1
elements in polynomial time. Other subgroups of →f1(x1, x2,…, xn), x2 →f2(x1, x2,…, xn),…, xn
affine Cremona group with MCP can be →fn(x1, x2,…, xn) where fi ϵ K[x1, x2,…, xn].
constructed as stable subgroups formed by Element F naturally induces the transformation
elements with maximal degree d, where d is ∆(F) of affine space Kn given by the following rule
constant [27, 28]. Other classes of subsemigroups ∆(F):(α1, α2,…, αn) → (f1(α 1, α2,…, αn), f2(α 1,
of ESn(K) can be defined via the concept of α2,…, αn),…, f1(α 1, α2,…, αn)) for each (α1, α2,…,
linguistic graph over abelian group G in the case αn) ϵ Kn. Luigi Cremona [29] introduced ∆(En(K))
G = K* and more general concept of a time =CS(Kn) which is currently called affine Cremona
dependent linguistic graph of type (s, r,m) which semigroup. A group of all invertible
is simply a tuple of linguistic graphs of this type. transformations from CS(Kn) with an inverse from
We introduce semigroups sSTr(K*) of tuples of CS(Kn) is known as affine Cremona group CG(Kn)
multivariate maps (elements of Cartesian powers (shortly Cremona group, see, for instance [30]).
ES1(K) in the case of G = K* and l = r = s) named We refer to infinite En(K) as formal affine
as semigroups of symbolic strings. These Cremona semigroup. Density of the map Fi is the
semigroups are used for the constriction of maximal number of monomial terms in fi, i = 1,
semigroup s,rSWm(K*) of symbolic walks on time 2,…, n.
dependent linguistic graphs. Effectively Let K be a finite commutative ring with the
computable homomorphism s,rSWm(K*) → unity such that multiplicative group K* of regular
ESn(K), n = m + s is presented there. Its image is elements of this ring contains at least 2 elements.
a special subsemigroup of ESn(K). This We take Cartesian power (K*)n and consider an
homomorphism and the concept of Jordan- Gauss Eulerian semigroup ESn(K) of transformations of
transformation allows to define Eulerian kind
transformations with inverting accelerator. It can x1→μ1x1a(1,1)x2a(1,2)…xna(1,n),
be used as instrument for the development of x2→μ2x1a(2,1)x2a(2,2)…xna(2,n),
public keys algorithms. Section 3 presents the …
concept of homomorphisms of time dependent xn→μnx1a(n,1)x2a(n,2)…xna(n,n),
linguistic graphs over K*. Such graph where a(i, j) are elements of arithmetic ring Zd, d
homomorphism induces homomorphism of = |K*|, μi ϵ K*.
corresponding subsemigroups of Eulerian Let EGn(K) stand for Eulerian group of
transformations. The description of Tahoma invertible transformations from ESn(K).It is easy
protocol in terms of time dependent graph over K* to see that the group Mn of monomial linear
and its quotients is also presented there. This transformations of kind xi → μixπ(i), i = 1, 2,…, n,
section also contains examples of sparse families where μi ϵ K*and π is a permutation on {1,2,…,n},
of time dependent graphs. They can be used for is a subgroup of EGn(K). So, semigroup ESn(K) is
the faster generation of data for the protocol by a highly noncommutative algebraic system. Each
Alice (creator of protocols data). Finally we element from ESn(K) can be considered as
present a brief description of symbiotic transformation of a free module Kn.
combination of the protocol and graph based Let π and σ be two permutations on the set
stream cipher working with potentially infinite {1,2,…,n}.
plaintext space [31]. We define transformation JGA,m(π, σ) which
sends (x1, x2,…, xn) into (y1, y2,…, yn) defined by
2. On Affine Cremona Semigroups triangular matrix A = (a(i; j)) with integer entries
a(i,j) as a totality of monomial terms
generalisations with injective maps of Kn into Kn with coefficients from G of kind gx1a(1)x2a(2)…
in cryptography was used in [27] (K = Zm) and xna(n), where a(i), i = 1, 2,…, n are elements of Zd,
[32] (K = Fq). We say that g is a tame Eulerian d = |G|. We introduce sBs(G) as (G < x1, x2,…, xs
element over K if it is a composition of several >)s and rBs as G(< x1, x2,…, xs >)r. Element (f1,
Jordan - Gauss multiplicative maps over f2,…, fs) from sBs(G) can be identified with the
commutative ring K. It is clear that it sends endomorphism x1 → f1, x2 → f2,…, xs → fs of G <
variable xi to a certain monomial term. The x1, x2,…, xs > as a group with the operation given
decomposition of g into product of Jordan - - via the following rule
Gauss transformation allows us to find the gx1a(1)x2a(2)…xsa(s)×hx1b(1)x2b(2)…xsb(s)=ghx1a(1)+b(1)x
reimage of this transformation of (K*)n 2
a(2)+b(2)
…xsa(s)+b(s).
So, tame Eulerian transformations over K are We assume that G = K* for the commutative
special elements of EGn(K). We refer to elements ring K. Endomorphism H ϵ ESs(K) acts naturally
of ESn(K) as multiplicative Cremona elements. on rBSs(K*). The result of action of H on G from
r
Assume that the order of K is a constant. As it BSs(K*) will be written as G(H) or simply GH.
follows from the definition the computation of the We consider the concept of time dependent
value of element from ESn(K) on the given linguistic graph over commutative group K*.
element of Kn is estimated by O(n2). The product Let Ls,r,m(K*) = L(K*) be variety of all
of two multiplicative Cremona elements can be linguistic graphs of type (s, r, m) over K*.
computed in time O(n3). F(Ls,r,m(K*)) = F(L(K*)) stands for the free
Similarly to the case of commutative ring (see semigroup over the alphabet L(K*). We interpret
[28]) we introduce a linguistic graph I = Г(G) over word (I(1), I(2),…, I(l)) = F(L) as time dependent
finite abelian group G defined as bipartite graph linguistic graph It(K*) on interval [1; l] and refer
with a point set P = Ps,m = Gs+m and a line set L = to j of I(j) as time parameter. We think that there
Lr,m = Gr+m as linguistic incidence structure I=Is,r,m is a function, given by some Oracle, which
if point x = (x1, x2,…, xs, xs+1, xs+2,…, xs+m) is establishes coefficients qi = qi(t) from K*, a(i, j)
incident to line y = [y1, y2,…, yr, yr+1, yr+2,…,yr+m] = a(i, j)(t) from Zd, i = 1, 2,…, m, j =1, 2,…, m.
if and only if the following relations hold Product of (I(1), I(2),…, I(l)) with (I’(1), I’(2),…,
xs+1a(1)yr+1b(1)=q1w1(x1, x2,…, xs, y1, y2,…, yr) I’(p)) is time dependent graph (shortly t.d.g.)
xs+2a(2)yr+2b(2)=q2w2(x1, x2,…, xs+1, y1, y2,…, yr+1) (I(1), I(2),…, I(l), I(l+1); I’(l+2),…, I’(l+p)).
… Let us define special subsemigroup sSTr(K*).
xs+ma(m)yr+1b(m)=qmwm(x1, x2,…, xs+m-1, y1, y2,…, We consider totality sSTr(K*) of tuples of kind tu
yr+m-1) = u = (H1, G1, G2, H2, H3, G3, G4, H4,…, H2t-1, G2t-
where qj, j = 1, 2,…, m are elements of G, wi are 1, G2t, H2t, H0) where Hi and Gi are elements of
s
words in characters xi and yj from G and Bs(G) and rBs(G) respectively of various rank t, t
parameters a(i), b(i) are mutually prime with d = ≥0. We refer to such tuple tu as symbolic strings
|G|. Brackets and parenthesis allow us to of type (s; r) and rank t = r(u).
distinguish points from lines similarly to the case We define a product of u = (H1, G1, G2, H2, H3,
of linguistic graphs over commutative rings. G3, G4, H4,…, H2t-1, G2t-1, G2t, H2t, H0) and
~ ~ ~ ~ ~ ~ ~
We define colours ρ((p)) and ρ([l]) of the point v ( H1 , G1 , G 2 , H 2 , H 3 , G3 , G 4 ,
~ ~ ~ ~ ~ ~
(p) and the line [l] as the tuple of their first H 4 ,..., H 2 k 1G 2 k 1 , G 2 k , H 2 k , H 0 )
coordinates of kind a = (p1, p2,…, ps) or a = (l1, as
l2,…, lr) and introduce well defined operator N(v; w u ( H 1 , G1 , G 2 , H 2 , H 3 , G3 , G 4 , H 4 ,...,
a) of computing the neighbour of vertex v of ~ ~ ~
H 2t 1 , G 2t 1 , G 2t , H 2t , H 1 H 0 , G1 H 0 , G 2 H 0 ,
colour a ϵ Gs or a ϵ Gr. Similarly to the case of ~ ~ ~ ~ ~
H 2 H 0 , H 3 H 0 , G3 H 0 , G 4 H 0 , H 4 H 0 ,...,
linguistic graph over commutative ring we define ~ ~ ~ ~ ~
H 2 k 1 H 0 , G 2 k 1 H 0 , G 2 k H 0 , H 2 k H 0 , H 0 H 0 )
colour jump operator J(p, a), a ϵ Gs on partition So, r(w) = r(u) + r(v).
set P and J(l, a), a ϵ Gr on partition set L by It is easy to see that this products converts
conditions J(p, a) =(a1, a2,…, as, p1+s, p2+s,…, ps+n) s
STr(K*) into a semigroup. The totality of
and J(l, a)=[a1, a2,…, ar, l1+r, l2+r,…, lr+m]. symbolic strings of length 1 forms subsemigroup
If G’ > G then we can consider graph I(G’) of which is isomorphic to ESs(K). The unity of
type (r, s, m) with partition sets P’=(G’)m+s and L’
= (G’)m+r given by the same equations with qi
99
s
STr(K*) is (H0) where H0 is the unity of transition of time dependent linguistic graph It
semigroup ESs(K) with symbolic trace u.
Let us consider the pair (tu, It) such that ut is Let s,rGWm(K*) be subsemigroup of s,rSWm(K*)
element of sSTr(K*) of rank t and It ϵ F(Lr,s,m(K)) formed by pairs (tu, It) for which tu = u is a
of length t. symbolic strings of kind (H1, G1, G2, H2, H3, G3,
Selected time dependent linguistic graph I = It G4, H4,…, H2t-1, G2t-1, G2t, H2t, H0) where H0 is an
from Ls,r,m(K*) defined on the interval [1, t]. Let element of EGn(K).
us expand K* for R = K* < x1,x2,…, xs+m >. This Lemma 2.2. The map η induces
change instantly converts t.d.g. It = (I(1), I(2),…, homomorphism ~ of s,rGWm(K*) into EGs+m(K).
I(t)) into I’t =(I’(1), I’(2),…, I’(t)) from We refer to ~( s , r GWm ( K *)) s , r Gm ( K *) as
F(Ls,r,m(R)). It is easy to see that this products
chain transition group of type (s, r,m).
converts sSTr(K*) into a semigroup. The totality of
Assume that ~(t u, It ) F is written in its
symbolic strings of length 1 forms subsemigroup
which is isomorphic to ESs(K). The unity of standard form, s = O(1) and r = O(1). The
s
STr(K*) is (H0) where H0 is the unity of knowledge of some reimage ~ of kind (tu, It) and
~ -1
semigroup ESs(K). H 0 ( H 0 ) 1 allow us to compute F (y) in
We will construct time dependent walk W(tu, given y in time O(tn2).
It) with colour jumps in the I’t(R) which starts in In fact we can form the reverse string
the graph I(1) with selection of initial point v0 = ~ ~ ~ ~
v ( H 2t H 0 , G 2t H 0 , G 2t 1 H 0 , H 2t 1 H 0 ,
(x1, x2,…, xs+m) from Rs+m. Further construction of ~ ~ ~ ~
H 2t 2 H 0 , G 2t 2 H 0 , G 2t 3 H 0 , H 2t 3 H 0 ,...,
the walk is prescribed by symbolic string u. ~ ~ ~ ~ ~
H 2 H 0 , G 2 H 0 , G1 H 0 , H 1 H 0 , H 0 )
During initial time interval (0; 1] we have to and check that
compute J(v0;H1) =v1, N(v1,G1) = v2, J(v2;G2) = v3 ~ ~
( u , I t ) ( v, I t ), ( I t ) ( I (t ), I (t 1),..., I (1)
t t is
and N(v3;H2) = v4 in the graph I’(1). Doing these
an identity map.
computations we use only multiplication of K* <
Let us consider the data D consisting of
x1, x2,…, xs+m >.
symbolic walk (tu, It), where It is time dependent
Next step corresponds to time interval (1; 2].
graph of type (s, r,m), element tu of sGTr(K*), and
We treat the output v4 of computations within
two lists of Jordan - Gauss generators of EGs+m(K)
interval (0; 1] as point of the graph I’(2).
formed by G1, G2,…, Gt(1) and F1, F2,…, Ft(2) with
Now we compute J(v4,H3) = v5, N(v5,G3) = v6,
t(1) ≥ 1, t(2) ≥ 1. We say that element F
J(v6,G4) = v7 and N(v7;H4) = v8 in the graph I’(2).
=G1G2…Gt(1)η(tu, It)F1F2,…,Ft(2) written in its
Continuation of this process subdivided into t
standard form has inverting accelerator D.
steps to the last four vertexes of graph I’(t) given
Noteworthy that knowledge of D allows us to find
by the list J(v4t-4,H2t-1) = v4t-3, N(v4t-3,G2t-1) = v4t-2,
F-1 in its standard form in polynomial time in
J(v4t-2,G2t) = v4t-1 and N(v4t-1,H2t) = v4t.
variable n = m + s. Pairs of kind (F,D) can be used
Finally, we compute v4t+1 = J(v4t,H0) from
instead of products of Jordan - Gauss elements for
s
Bs(R) in the graph I’(t). Noteworthy that output
the constructions of public key cryptosystems
v4t+1 is a tuple (1H0,2H0,…,sH0, Fs+1, Fs+2,…, Fs+m)
introduced in [27, 31].
where H0 = (1H0, 2H0,…, sH0), Fj are elements of
K* < x1, x2,…, xs+m >. The walk W(tu, It) defines
the map η(tu; It) =s,rηm given by the rule x1 → 1H0, 3. Special Homomomrphisms
x2 →2H0,…, xs →sH0, xs+1 → Fs+1, xs+2 → Fs+2,…, of Time Dependent Graphs
xs+m → Fs+m from Es+m(K). Let us consider these
maps in formal way. We consider a direct product
and Protocols of Noncommutative
s,r
Dm(K*) of sSTr(K*) and F(Lr,s,m(K*)) and its Cryptography
subdirect product s,rSWm(K*) formed by elements
of kind (tu, It). Let us consider time dependent linguistic
Lemma 2.1. The η =s,r ηm = ηm is the graph It = (I(1), I(2),…, I(t)) over group K* of type
homomorphism of semigroup of s,rSWm(K*) into (r, s, m) and parameter n, n < m. We can define
ESn(K), n = s + m. another time dependent linguistic graph
We refer to s,rSWm(K*) as space of symbolic ~ ~ ~ ~
n ( I t ) ( I (1), I (2),..., I (t )) where I ( j ) , j
walks of type (s, r) and say that η is a compression =1, 2,…, t is obtained from I(j) by deleting the last
map of this space. We refer to η (s,rSWm(K*) =s,r coordinates xn+s+1, xn+s+2,…, xm+s of points and
Sm(K*) as chain transition subsemigroup of yn+s+1, yn+s+2,…, ym+s of lines and cancellation of
ESs+m(K) of type (s, r) and to η (u, It) as chain
100
the last n - m equations in the definition of It. The and forms rev(d 2 ) d 2' . Alice constructs
map μn is the homomorphism of semigroups
F(Ls,r,m(K*)) onto F(Ls,r,n(K*)). y1 n ( d 2c1' d 2' ), y2 n ( d 2c2' d 2' ),...,
It induces the homomorphism πn of sSTr(K*) × yk (1) n ( d 2ck' (1) d 2' )
F(Ls,r,m(K*)) onto sSTr(K*) × F(Ls,r,n(K*)) acting She takes some Jordan Gauss generators G1,
by the rule πn(u, It) = (u, μn(It)). It is clear that G2,…, Gk(3), k(3) ≥ 1 from EGn+s(K) and computes
π(s,rSWm(K*) =s,rSWn(K*). ' ' '
Composition of πn and s,rηn defines their inverses G1, G2 ,...,Gk (3) and G = G1G2k(3)
homomorphism of s,rSWm(K*) onto s,rSn(K*) with G-1. Alice forms b1 = Gy1G-1, a2 = Gy2G-1,…,
In fact, the diagram formed by maps bk(1) = Gyk(1)G-1.
π : s,rSWm(K*) → s, rSWn(K*), s,rηm :s,rSWm(K*) She sends pairs (ai, bi), i = 1, 2,…, k(1) to Bob.
→ Sm(K*),
s,r
Bob takes tuple (j(1), j(2),…, j(q)), q = O(1), q
s,r
ηn :s,rSWn(K*) →s,r Sn(K*), τn :s,r Sm(K*) →s,r ≥2 where j(i) ϵ {1, 2,…, k(1)} such that |{j((1),
Sn(K*) j(2),…, j(q)}| ≥ 2. He forms a =aj(1)aj(2)… aj(q) and
where τn is the restriction of endomorphism of sends it to Alice. Bob computes b = bj(1)bj(2)… bj(q)
K* < x1, x2,…, xm+s > on K* < x1, x2,…, xn+s > and keeps it safely in his private storage.
given by its values on x1, x2,…, xn+s, is the Alice computes 1a = J-1aJ, 2a =
m(rev(d1)) aηm(d1), τn(2a)
1
commutative one. =1 b,
TAHOMA PROTOCOL (tahoma stands for 2
b=ηn(d2)( b)ηn(rev(d2) and collision element b as
2
the abbreviation of "tame homomorphism”) G(2b)G-1. Note that b is an element ESn+s(K).
Alice selects positive integers s, r, m and n, n Remark 3.1. The security of protocol rests on
< m together with commutative ring K with the the complexity of problem of decomposition of
unity. Assume that m = O(n) and m > αn where α element from ESn(K) in the composition of
> 1, s ≥1, r ≥ 1, s = 0(1), r = O(1). Alice considers generators. This problem is an intractable one
semigroup s,rSWm(K*) and takes its elements c1= even in the case of the usage Turing machine
(t(1)u1,1It(1)), c2 = (t(2)u2,2It(2)),…, ck(1) =(t(k(1)ut(k(1)),k(1) jointly with Quantum computer.
It(k(1))) where k(1) ≥ 2, k(1)=O(1) , t(i) ≥ 2, i = 1,
2,…, k(1). 4. Examples of Sparse Graphs
Additionally, she takes d1 = (tu, It), It = (I(1),
I(2),…, I(t)), t ≥ 2 from s,rGWm(K*) with tu = (H1, and Protocol based
G1, G2, H2,…,H4t-1, G4t-1, H4t, H0) where H0 is Cryptosystems
Jordan - Gauss element of EGs(K). She computes
H 01,t u ' rev(t u ), I t' ( I (t ), I (t ),..., I (1)) and Well known linguistic graph A(k;K) over
d1' (t u ' , I t' ) . commutative ring K [27, 28] of type (1, 1, n - 1) is
Alice computes d1c1d1' , d1c2d1' ,..., d1ck (1) d1' in given by equations x2 - y2 = y1x1, x3 - y3 = x1y2, x4
- y4 = y1x3, x5 - y5 = x1y4,…, xk - yk = y1xk-1 in the
the semigroup s,rSWm(K*). She applies mη to these case of even k. We consider linguistic graph A(k,
elements and gets K*) over commutative group K* of type (1, 1, k -
z1 m ( d1c1 d1' ), z 2 m ( d1c 2 d1' ),..., 1) given by equations x2/y2 = y1x1, x3/y3 = x1y2,
z k (1) m ( d1c k ( 2) d1' x4/y4 = y1x3, x5/y5 = x1y4,…, xk/yk = y1xk-1.
Alice takes some Jordan Gauss generators J1, We define class of time dependent graphs DAT
J2,…, Jk(2), k(2) ≥1, from EGm+s(K) and computes (k, K*), T ≥ 1, k ≥ 2 given by equations x2a(1,t)y2b(1,t)
their inverses J1' , J 2' ,..., J k' ( 2) and J1 J2… Jk(2) = y1c(1,t)x1d(1,t), x3a(2,t)y3b(2,t) = x1c(2,t)y2d(2,t),x4a(3,t)y4b(3,t)
= y1c(3,t)x2d(3,t), x5a(4,t)y5b(4,t) = x1c(4,t)y4d(4,t),…, xka(k-
together with J-1. She forms a1 = Jz1J-1, a2 = Jz2J- 1,t) b(k-1,t)
yk = y1c(k-1,t)xk-1d(k-1,t) with a(i, t), b(i, t), c(i,
1
,…, ak(1) = Jzk(1)J-1. t), d(i, t) from Zd - 0, d = |K*|, i = 1, 2,…, k - 1, t
Alice computes = 1, 2,…, T such that a(i) and b(i) are mutually
с1 n (c1), c2 n (c2 ),...,k (1) n (ck (1) ) .
~ ~
prime with d. The graph depends on data D given
She takes d 2 (t v, I~ ' ) from
' s,r
GWn(K*), by parameters (a(i, t), b(i, t), c(i, t), d(i, t)), t ϵ [1;
~
t
T], i = 1, 2,…, k -1. These graphs were used for
where It has type (s, r, n), the implementation of the protocol together with
v ( H 1' , G1' , G 2' , H 2' ,..., H 4' t ' 1 , G 4' t ' 1 , G 4' t ' , Jordan - Gauss transformations of kind J: x1 →
H 4' t ' , H 0' ) qx1 m(1)x2 m(2) … xk m(k), xi → xi, i = 2, 3,…, k. In [8]
the output of implemented protocol from ESn+1(K)
101
is used for the construction of polynomial [3] F. Kipchuk, et al., Investigation of
encryption map of plaintext space K n , 1 , Availability of Wireless Access Points based
which has exponential degree and density. The on Embedded Systems, in VI International
execution speed is O(n 2 ) . The map is Scientific and Practical Conference
constructed in terms of linguistic graph A(nα;K). Problems of Infocommunications. Science
It is implemented in the case of finite fields of and Technology, 2019, pp. 246–250. doi:
10.1109/PICST47496.2019.9061551.
characteristic 2 and K Z l , l 2 . The security
2 [4] A Myasnikov, V. Shpilrain, A. Ushakov,
of this cryptosystem rests on the security of the Noncommutative Cryptography and
protocol. Complexity of Group-theoretic Problems,
Amer. Math Soc. 2011.
5. Conclusions [5] J. A. Lopez Ramos, et al., Group Key
Management based on Semigroup Actions,
Journal of Algebra and its Applications,
We suggest the method of generation
vol.16 , 2019.
transformations of semigroup nES(K) and group
n [6] V. Ustimenko, On semigroups of
EG(K), where K is finite commutative ring, in
multivariate transformations constructed in
terms of time dependent linguistic graphs over
terms of time dependent linguistic graphs and
commutative group K*. The method can be used
solutions of Post Quantum Multivariate
for generation of subsemigroups nS