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).
Theoretical danger of quantum computers to Information Security has been known since 1994. In the case of asymmetrical cryptography it affects both protocol based cryptosystems for which encryption tools are not given to public and public key cryptosystems.
For instance, a symbiotic combination of Diffie -Hellman protocol (DH) with one time pad encryption or El Gamal cryptosystem in terms of DH algorithm will not be safe in Postquantum era because discrete logarithm problem is not quantum resistant. Popular RSA public key cryptosystem is not quantum secure because factorisation problem can be solved in polynomial time with the usage of quantum computer. Nowadays this vulnerability is not only theoretical because large corporations like IBM, Google, governmental scientific centers in Europe, China, UK, Jappan and USA began to build working quantum computers.
That is why NSA has advised researchers to work on new security products, NIST and ETSI are currently investigating relevant standards and evaluating proposed public key algorithms. Asymmetrical Cryptography is largely based on theoretical complexity assumptions. Fundamental question whether or not P = NP have been open for decades. This assumption is connected with fundamental conjecture of cryptography that there are no polynomial-time algorithms for solving any NP-hard problem.
Such theoretical danger to Cryptography increase interest to problems that are hard to solve in the quantum setting. Noteworthy that many of the fundamental problems about polynomial time problems have analogs at the level of computability. Many NP-hard problems have analogs over various algebraic and combinatorial structures. Techniques from computational or statistical algebra afford insights into the distribution of hard instances.
Post Quantum Cryptography is divided into the following major areas: Code-based cryptography, Lattice-based cryptography, Multivariate cryptography. Hash functions base cryptography, Supersingular elliptic curve isogeny cryptography, Noncommutative Cryptography. This paper is dedicated to a new branch of Multivariate Cryptography (MC) dealing with polynomial transformations of affine spaces over various commutative rings of unbounded degree and large semigroups or groups of such transformations.
Multivariate cryptography is usually defined as the set of cryptographic schemes using the computational hardness of the Polynomial System Solving problem over a finite field. Solving systems of multivariate polynomial equations is proven to be NP-hard or NP-complete. That is why those schemes are often considered to be good candidates for post-quantum cryptography. Classical Multivariate Cryptography uses systems of quadratic (rarely cubic) equations. The idea to use degree 2 is motivated by possibility to transform system of equations of any constant degree to equivalent quadratic system of large size. Some weakness of this argument is caused by the fact that such transformation can seriously affect the complexity of system.
The first quadratic multivariate scheme based
on multivariate equations was introduced by
Matsumoto and Imai in 1988. These authors not
only introduced a multivariate scheme but in fact
a general principle to design public-key
cryptosystems using multivariate equations.
There are now plenty of proposals based on this
principle that are attractive because they offer the
possibility to have very short asymmetric
signatures that require only a small amount of
resources on embedded devices [
We believe in the capacity of Multivariate
Cryptography (MC) in wide sense as a source of
encryption cryptosystems. Recent constructions
of families of semigroups and groups of
transformation of affine spaces Kn with possibility
of computation of n elements from the semigroup
in polynomial time gives opportunity to use
methods of Semigroup based cryptography in
multivariate settings. So instead of one nonlinear
transformation of Classical Multivariate
Cryptography we can work with several
polynomial maps. It allows to construct protocols
which security rests on difficult problem to
decompose multivariate map into composition of
several given generators. If the map and
generators are given in a standard form of
Multivariate Cryptography then the
decomposition task is intractable problem of Post
Quantum Cryptography. In fact we work in the
area of intersection of MC with the
Noncommutative Cryptography which uses
complexity of problems from Noncommutative
algebra on groups, semigroups, algebras and other
algebraic systems [
The output of the protocol can be used for safe
creation of multivariate encryption map or safe
delivery of such map from one correspondent to
another [
In Section 2 we define affine Cremona group
and affine Cremona semigroup over general
commutative ring K which are central objects of
Multivariate Cryptography and Theory of
Symbolic Computations. Additionally, we
introduce Eulerian semigroup ESn(K) and group
EGn(K) via endomorphism of K[x1, x2, …, xn]
moving generic variable xi into monomial term.
We define invertable Jordan-Gauss
transformations of EGn(K) as triangular
transformation of (K*)n with obvious procedure of
reimage computation. Semigroup EGn(K) satisfies
to multiple composition property (MCP), which
means ability to compute the composition of n
elements in polynomial time. Other subgroups of
affine Cremona group with MCP can be
constructed as stable subgroups formed by
elements with maximal degree d, where d is
constant [
and Semigroups of Special Eulerian
Let K[x1, x2,…, xn] be commutative ring of all polynomials in variables x1, x2,… xn defined over a commutative ring K. Each endomorphism F of K[x1, x2,…, xn] is uniquely determined by its values on formal generators xi, i = 1, 2,…, n.
Symbol End(K[x1, x2,…, xn]) = En(K) stands for
semigroup of all endomorphisms of K[x1, x2,…,
xn]. So we can identify F and the formal rule x1
→f1(x1, x2,…, xn), x2 →f2(x1, x2,…, xn),…, xn
→fn(x1, x2,…, xn) where fi ϵ K[x1, x2,…, xn].
Element F naturally induces the transformation
∆(F) of affine space Kn given by the following rule
∆(F):(α1, α2,…, αn) → (f1(α 1, α2,…, αn), f2(α 1,
α2,…, αn),…, f1(α 1, α2,…, αn)) for each (α1, α2,…,
αn) ϵ Kn. Luigi Cremona [
Let K be a finite commutative ring with the unity such that multiplicative group K* of regular elements of this ring contains at least 2 elements. We take Cartesian power (K*)n and consider an Eulerian semigroup ESn(K) of transformations of kind x1→μ1x1a(1,1)x2a(1,2)…xna(1,n), x2→μ2x1a(2,1)x2a(2,2)…xna(2,n), … xn→μnx1a(n,1)x2a(n,2)…xna(n,n), where a(i, j) are elements of arithmetic ring Zd, d = |K*|, μi ϵ K*.
Let EGn(K) stand for Eulerian group of invertible transformations from ESn(K).It is easy to see that the group Mn of monomial linear transformations of kind xi → μixπ(i), i = 1, 2,…, n, where μi ϵ K*and π is a permutation on {1,2,…,n}, is a subgroup of EGn(K). So, semigroup ESn(K) is a highly noncommutative algebraic system. Each element from ESn(K) can be considered as n transformation of a free module K .
Let π and σ be two permutations on the set {1,2,…,n}.
We define transformation JGA,m(π, σ) which sends (x1, x2,…, xn) into (y1, y2,…, yn) defined by triangular matrix A = (a(i; j)) with integer entries a(i,j)<d and m=(μ1, μ2,…, μn) ϵ (K*)n via the following closed formula.
yπ(1)=μ1xσ(1)a(1,1), yπ(2)=μ2 xσ(1)a(2,1)xσ(2)a(2,2), … yπ(n)=μnxσ(1)a(n,1)xσ(2)a(n,2)… xσ(n)a(n,1), where (a(1; 1); d) = 1, (a(2; 2); d) = 1,…, (a(n; n); d) = 1.
We refer to JGA,m(π, σ) as Jordan - Gauss
multiplicative transformation or simply JG
element. It is an invertible element of ESn(K) with
the inverse which is also JG element. The idea to
use composition of JG elements or their
generalisations with injective maps of Kn into Kn
in cryptography was used in [
So, tame Eulerian transformations over K are special elements of EGn(K). We refer to elements of ESn(K) as multiplicative Cremona elements. Assume that the order of K is a constant. As it follows from the definition the computation of the value of element from ESn(K) on the given element of Kn is estimated by O(n2). The product of two multiplicative Cremona elements can be computed in time O(n3).
Similarly to the case of commutative ring (see
[
We define colours ρ((p)) and ρ([l]) of the point (p) and the line [l] as the tuple of their first coordinates of kind a = (p1, p2,…, ps) or a = (l1, l2,…, lr) and introduce well defined operator N(v; a) of computing the neighbour of vertex v of colour a ϵ Gs or a ϵ Gr. Similarly to the case of linguistic graph over commutative ring we define colour jump operator J(p, a), a ϵ Gs on partition set P and J(l, a), a ϵ Gr on partition set L by conditions J(p, a) =(a1, a2,…, as, p1+s, p2+s,…, ps+n) and J(l, a)=[a1, a2,…, ar, l1+r, l2+r,…, lr+m].
If G’ > G then we can consider graph I(G’) of type (r, s, m) with partition sets P’=(G’)m+s and L’ = (G’)m+r given by the same equations with qi from G. Note that group G’ can be an infinite one. Let x1, x2,…, xn be the list of variables. We define G < x1, x2,…, xs > as a totality of monomial terms with coefficients from G of kind gx1a(1)x2a(2)… xna(n), where a(i), i = 1, 2,…, n are elements of Zd, d = |G|. We introduce sBs(G) as (G < x1, x2,…, xs >)s and rBs as G(< x1, x2,…, xs >)r. Element (f1, f2,…, fs) from sBs(G) can be identified with the endomorphism x1 → f1, x2 → f2,…, xs → fs of G < x1, x2,…, xs > as a group with the operation given via the following rule gx1a(1)x2a(2)…xsa(s)×hx1b(1)x2b(2)…xsb(s)=ghx1a(1)+b(1)x 2a(2)+b(2)…xsa(s)+b(s).
We assume that G = K* for the commutative ring K. Endomorphism H ϵ ESs(K) acts naturally on rBSs(K*). The result of action of H on G from rBSs(K*) will be written as G(H) or simply GH.
We consider the concept of time dependent linguistic graph over commutative group K*.
Let Ls,r,m(K*) = L(K*) be variety of all linguistic graphs of type (s, r, m) over K*. F(Ls,r,m(K*)) = F(L(K*)) stands for the free semigroup over the alphabet L(K*). We interpret word (I(1), I(2),…, I(l)) = F(L) as time dependent linguistic graph It(K*) on interval [1; l] and refer to j of I(j) as time parameter. We think that there is a function, given by some Oracle, which establishes coefficients qi = qi(t) from K*, a(i, j) = a(i, j)(t) from Zd, i = 1, 2,…, m, j =1, 2,…, m. Product of (I(1), I(2),…, I(l)) with (I’(1), I’(2),…, I’(p)) is time dependent graph (shortly t.d.g.) (I(1), I(2),…, I(l), I(l+1); I’(l+2),…, I’(l+p)).
Let us define special subsemigroup sSTr(K*). We consider totality sSTr(K*) of tuples of kind tu = u = (H1, G1, G2, H2, H3, G3, G4, H4,…, H2t-1, G2t1, G2t, H2t, H0) where Hi and Gi are elements of sBs(G) and rBs(G) respectively of various rank t, t ≥0. We refer to such tuple tu as symbolic strings of type (s; r) and rank t = r(u).
We define a product of u = (H1, G1, G2, H2, H3, G3, G4, H4,…, H2t-1, G2t-1, G2t, H2t, H0) and v (H~1, G~1, G~2 , H 2 , H~3 , G~3 , G~4 , ~ H 4 ,..., H~ 2k 1G2k 1, G~2k , H~ 2k , H~ 0 ) ~ ~ as w u (H1, G1 , G2 , H 2 , H 3 , G3 , G4 , H 4 ,..., H 2t1, G2t1, G2t , H 2t , H~1H 0 , G~1H 0 , G2 H 0 , ~ ~ ~ ~ H 2 H 0 , H~ 3 H 0 , G3 H 0 , G4 H 0 , H~ 4 H 0 ,..., ~ ~ ~ H 2k 1H 0 , G2k 1H 0 , G2k H 0 , H~ 2k H 0 , H~ 0 H 0 ) So, r(w) = r(u) + r(v).
It is easy to see that this products converts sSTr(K*) into a semigroup. The totality of symbolic strings of length 1 forms subsemigroup which is isomorphic to ESs(K). The unity of sSTr(K*) is (H0) where H0 is the unity of semigroup ESs(K)
Let us consider the pair (tu, It) such that ut is element of sSTr(K*) of rank t and It ϵ F(Lr,s,m(K)) of length t.
Selected time dependent linguistic graph I = It from Ls,r,m(K*) defined on the interval [1, t]. Let us expand K* for R = K* < x1,x2,…, xs+m >. This change instantly converts t.d.g. It = (I(1), I(2),…, I(t)) into I’t =(I’(1), I’(2),…, I’(t)) from F(Ls,r,m(R)). It is easy to see that this products converts sSTr(K*) into a semigroup. The totality of symbolic strings of length 1 forms subsemigroup which is isomorphic to ESs(K). The unity of sSTr(K*) is (H0) where H0 is the unity of semigroup ESs(K).
We will construct time dependent walk W(tu, It) with colour jumps in the I’t(R) which starts in the graph I(1) with selection of initial point v0 = (x1, x2,…, xs+m) from Rs+m. Further construction of the walk is prescribed by symbolic string u. During initial time interval (0; 1] we have to compute J(v0;H1) =v1, N(v1,G1) = v2, J(v2;G2) = v3 and N(v3;H2) = v4 in the graph I’(1). Doing these computations we use only multiplication of K* < x1, x2,…, xs+m >.
Next step corresponds to time interval (1; 2]. We treat the output v4 of computations within interval (0; 1] as point of the graph I’(2).
Now we compute J(v4,H3) = v5, N(v5,G3) = v6, J(v6,G4) = v7 and N(v7;H4) = v8 in the graph I’(2).
Continuation of this process subdivided into t steps to the last four vertexes of graph I’(t) given by the list J(v4t-4,H2t-1) = v4t-3, N(v4t-3,G2t-1) = v4t-2, J(v4t-2,G2t) = v4t-1 and N(v4t-1,H2t) = v4t.
Finally, we compute v4t+1 = J(v4t,H0) from sBs(R) in the graph I’(t). Noteworthy that output v4t+1 is a tuple (1H0,2H0,…,sH0, Fs+1, Fs+2,…, Fs+m) 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, x2 →2H0,…, xs →sH0, xs+1 → Fs+1, xs+2 → Fs+2,…, xs+m → Fs+m from Es+m(K). Let us consider these maps in formal way. We consider a direct product s,rDm(K*) of sSTr(K*) and F(Lr,s,m(K*)) and its subdirect product s,rSWm(K*) formed by elements of kind (tu, It).
Lemma 2.1. The η =s,r ηm = ηm is the homomorphism of semigroup of s,rSWm(K*) into ESn(K), n = s + m.
We refer to s,rSWm(K*) as space of symbolic walks of type (s, r) and say that η is a compression map of this space. We refer to η (s,rSWm(K*) =s,r Sm(K*) as chain transition subsemigroup of ESs+m(K) of type (s, r) and to η (u, It) as chain transition of time dependent linguistic graph It with symbolic trace u.
Let s,rGWm(K*) be subsemigroup of s,rSWm(K*) formed by pairs (tu, It) for which tu = u is a symbolic strings of kind (H1, G1, G2, H2, H3, G3, G4, H4,…, H2t-1, G2t-1, G2t, H2t, H0) where H0 is an element of EGn(K).
Lemma 2.2. The map η induces homomorphism ~ of s,rGWm(K*) into EGs+m(K).
We refer to ~(s,rGWm (K*))s,rGm (K*) as chain transition group of type (s, r,m).
Assume that ~(tu, It ) F is written in its standard form, s = O(1) and r = O(1). The knowledge of some reimage ~ of kind (tu, It) and ~ H0 (H0 )1 allow us to compute F-1(y) in given y in time O(tn2).
In fact we can form the reverse string v (H 2t H~ 0 , G2t H~ 0 , G2t1H~ 0 , H 2t1H~~0 , H 2t2 H~ 0 , G2t2 H 0 , G2t3 H 0 , H 2t3 H 0 ,..., ~ ~ H 2 H~ 0 , G2 H 0 , G1H 0 , H1H~ 0 , H~ 0 )
~ ~ and check that (tu, It ) (tv, I~t ),(I~t ) (I (t), I (t 1),...,I (1) is an identity map.
Let us consider the data D consisting of
symbolic walk (tu, It), where It is time dependent
graph of type (s, r,m), element tu of sGTr(K*), and
two lists of Jordan - Gauss generators of EGs+m(K)
formed by G1, G2,…, Gt(1) and F1, F2,…, Ft(2) with
t(1) ≥ 1, t(2) ≥ 1. We say that element F
=G1G2…Gt(1)η(tu, It)F1F2,…,Ft(2) written in its
standard form has inverting accelerator D.
Noteworthy that knowledge of D allows us to find
F-1 in its standard form in polynomial time in
variable n = m + s. Pairs of kind (F,D) can be used
instead of products of Jordan - Gauss elements for
the constructions of public key cryptosystems
introduced in [
of Time Dependent Graphs and Protocols of Noncommutative
Let us consider time dependent linguistic graph It = (I(1), I(2),…, I(t)) over group K* of type (r, s, m) and parameter n, n < m. We can define another time dependent linguistic graph where I~( j) , j n (It ) (I~(1), I~(2),...,I~(t)) =1, 2,…, t is obtained from I(j) by deleting the last coordinates xn+s+1, xn+s+2,…, xm+s of points and yn+s+1, yn+s+2,…, ym+s of lines and cancellation of the last n - m equations in the definition of It. The map μn is the homomorphism of semigroups F(Ls,r,m(K*)) onto F(Ls,r,n(K*)).
It induces the homomorphism πn of sSTr(K*) × F(Ls,r,m(K*)) onto sSTr(K*) × F(Ls,r,n(K*)) acting by the rule πn(u, It) = (u, μn(It)). It is clear that π(s,rSWm(K*) =s,rSWn(K*).
Composition of πn and s,rηn defines homomorphism of s,rSWm(K*) onto s,rSn(K*) In fact, the diagram formed by maps π : s,rSWm(K*) → s, rSWn(K*), s,rηm :s,rSWm(K*) →s,r Sm(K*),
s,rηn :s,rSWn(K*) →s,r Sn(K*), τn :s,r Sm(K*) →s,r Sn(K*)
where τn is the restriction of endomorphism of K* < x1, x2,…, xm+s > on K* < x1, x2,…, xn+s > given by its values on x1, x2,…, xn+s, is the commutative one.
TAHOMA PROTOCOL (tahoma stands for the abbreviation of "tame homomorphism”)
Alice selects positive integers s, r, m and n, n < m together with commutative ring K with the unity. Assume that m = O(n) and m > αn where α > 1, s ≥1, r ≥ 1, s = 0(1), r = O(1). Alice considers semigroup s,rSWm(K*) and takes its elements c1= (t(1)u1,1It(1)), c2 = (t(2)u2,2It(2)),…, ck(1) =(t(k(1)ut(k(1)),k(1) It(k(1))) where k(1) ≥ 2, k(1)=O(1) , t(i) ≥ 2, i = 1, 2,…, k(1).
Additionally, she takes d1 = (tu, It), It = (I(1), I(2),…, I(t)), t ≥ 2 from s,rGWm(K*) with tu = (H1, G1, G2, H2,…,H4t-1, G4t-1, H4t, H0) where H0 is Jordan - Gauss element of EGs(K). She computes H01,t u' rev(tu), It' (I (t), I (t),..., I (1)) and d1' (tu', It' ) .
Alice computes d1c1d1' , d1c2d1' ,...,d1ck(1)d1' in the semigroup s,rSWm(K*). She applies mη to these elements and gets z1 m (d1c1d1' ), z2 m (d1c2 d1' ),..., zk(1) m (d1ck(2) d1'
Alice takes some Jordan Gauss generators J1, J2,…, Jk(2), k(2) ≥1, from EGm+s(K) and computes their inverses J1' , J 2',..., J k'(2) and J1 J2… Jk(2) together with J-1. She forms a1 = Jz1J-1, a2 = Jz2J1,…, ak(1) = Jzk(1)J-1.
Alice computes с~1 n (c1),c~2 n (c2),...,k(1) n (ck(1) ) .
She takes d2 (t' v, I~ ' ) from s,rGWn(K*), t where has type (s, r, n), ~
It v (H1' , G1' , G 2' , H 2' ,..., H 4't' 1, G 4't' 1, G 4't' , H 4't' , H 0' ) and forms
rev(d2 ) d 2' . Alice constructs y1 n (d2c1' d 2'), y2 n (d2c2'd 2'),..., yk(1) n (d2ck'(1)d 2')
She takes some Jordan Gauss generators G1, G2,…, Gk(3), k(3) ≥ 1 from EGn+s(K) and computes their inverses G1' ,G2',...,Gk' (3) and G = G1G2k(3) with G-1. Alice forms b1 = Gy1G-1, a2 = Gy2G-1,…, bk(1) = Gyk(1)G-1.
She sends pairs (ai, bi), i = 1, 2,…, k(1) to Bob.
Bob takes tuple (j(1), j(2),…, j(q)), q = O(1), q ≥2 where j(i) ϵ {1, 2,…, k(1)} such that |{j((1), j(2),…, j(q)}| ≥ 2. He forms a =aj(1)aj(2)… aj(q) and sends it to Alice. Bob computes b = bj(1)bj(2)… bj(q) and keeps it safely in his private storage.
Alice computes 1a = J-1aJ, 2a = m(rev(d1))1aηm(d1), τn(2a) =1 b, 2b=ηn(d2)(2b)ηn(rev(d2) and collision element b as G(2b)G-1. Note that b is an element ESn+s(K).
Remark 3.1. The security of protocol rests on the complexity of problem of decomposition of element from ESn(K) in the composition of generators. This problem is an intractable one even in the case of the usage Turing machine jointly with Quantum computer.
Well known linguistic graph A(k;K) over
commutative ring K [
We define class of time dependent graphs DAT
(k, K*), T ≥ 1, k ≥ 2 given by equations x2a(1,t)y2b(1,t)
= 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(k1,t)ykb(k-1,t) = y1c(k-1,t)xk-1d(k-1,t) with a(i, t), b(i, t), c(i,
t), d(i, t) from Zd - 0, d = |K*|, i = 1, 2,…, k - 1, t
= 1, 2,…, T such that a(i) and b(i) are mutually
prime with d. The graph depends on data D given
by parameters (a(i, t), b(i, t), c(i, t), d(i, t)), t ϵ [1;
T], i = 1, 2,…, k -1. These graphs were used for
the implementation of the protocol together with
Jordan - Gauss transformations of kind J: x1 →
qx1 m(1)x2 m(2) … xk m(k), xi → xi, i = 2, 3,…, k. In [
We suggest the method of generation transformations of semigroup nES(K) and group nEG(K), where K is finite commutative ring, in terms of time dependent linguistic graphs over commutative group K*. The method can be used for generation of subsemigroups nS<nES(K) or subgroups nEG(K).
Homomorphisms of time dependent linguistic graphs induce the homomorphisms of corresponding generated semigroups or groups. These effectively computable homomorphisms between two semigroups (or groups) can be used for the data preparation for Postquantum Tahoma Protocol. Its security rests on the complexity of word decomposition problem for subsemigroup of nES(K).
The concept of linguistic graphs over
commutative group is traditionally used in graph
based cryptography for generation of encryption
maps from affine Cremona group CGn(K). We
suggest combination of Tahoma Protocol with
output from nES(K) and symmetric protocol
based on transformation of Kn defined in terms of
linguistic graph over commutative ring K.
Illustrating example uses known graph A(n, K) for
creation of transformation of Kn and time
depending analog of graph A(n, K*) for generation
of data for Tahoma protocol. Other examples
reader can find in [
[1] J. Ding, J. E. Gower, D. S. Schmidt, Multivariate Public Key Cryptosystems. Springer, Advances in Information Security, vol. 25, 2006. [2] L. Goubin, J. Patarin, B.-Y. Yang, Multivariate Cryptography, Encyclopedia of Cryptography and Security, 2nd Ed., 2011, 824-828.