New Cryptosystems of Noncommutative Cryptography based on Eulerian Semigroups of Multivariate Transformations Vasyl Ustimenkoa,b and Oleksandr Pustovitb a University of Marie Curie-Sklodowska in Lublin, 5 Plac Marii Curie-Skłodowskiej str., Lublin, 20031, Poland b Institute of Telecommunications and the Global Information Space of the National Academy of Sciences of Ukraine, 13 Chokolivsky ave., Kyiv, 02000, Ukraine Abstract The intersection of Commutative and Multivariate cryptography contains studies of cryptographic applications of subsemigroups an90d subgroups of affine Cremona semigroups defined over finite commutative ring K with the unity. We consider special subsemigroups in a semigroup of all endomorphisms of K[x1, x2, …, xn] which preserve the variety (K*)n. Efficiently computed homomorphisms between such subsemigroups can be used in Post Quantum key exchange protocols and their inverse versions when correspondents elaborate mutually inverse transformations of (K*)n. The security of these schemes is based on the complexity of the decomposition problem for an element of a semigroup into a product of given generators. We suggest two public key cryptosystems for which security rests on the complexity of the problem to compute the inverse of a given semigroup element. The usage of the protocols allows converting these encryption schemes into new cryptosystems which are not public keys and have some similarity with El Gamal cryptosystem. New protocols can be used for the Post Quantum key exchange for one-time pad encryption. Keywords 1 Noncommutative cryptography, multivariate cryptography, key exchange protocol, inverse protocols, semigroup of transformations, decomposition problem, public-key cryptosystem. 1. Post Quantum, Multivariate, and Noncommutative Cryptography Post Quantum 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 standardization process [1]. In March 2019, NIST published a list of candidates qualified for the second round of the standardization process. Few public key candidates are implemented, like candidate called Round 5 [2] or the classic McEliece algorithm [3]. In July 2020 the third round was started, only rainbow-like oil and vinegar digital signatures are among selected algorithms of multivariate cryptography. They use nonbijective quadratic maps of affine space and can not be used as encryption algorithms. The outcome of the NIST competition stimulates innovative research on studies of cryptographical applications of multivariate maps of unbounded degree and studies of multivariate cryptosystems which are not public keys. In this publication, we continue to develop new cryptosystems within an alternative approach [4– 6] to public-key cryptography based on the idea of modified Diffie-Hellman type protocol which output is a pair of mutually inverse multivariate transformations of affine space Kn defined over finite commutative ring K. Security of these algorithms rests on the complexity of word problem to decompose given multivariate map into generators of affine Cremona [7] semigroup. The first usage of the complexity of word problems for groups was considered in [8]. Cybersecurity Providing in Information and Telecommunication Systems, January 28, 2021, Kyiv, Ukraine EMAIL: vasulustimenko@yahoo.pl (A.1); sanyk_set@ukr.net (B.2) ORCID: 0000-0002-2138-2357 (A.1); 0000-0002-3232-1787 (B.2) ©️ 2021 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) 18 In the inverse protocols considered in this paper, the encryption rule is not given publicly. We introduce new cryptosystems defined in terms of semigroups of transformations of affine space Kn which consist of transformations moving variable to a single monomial term. One of the directions of PQC is multivariate cryptography [9] which uses polynomial maps of affine space K n defined over a finite commutative ring into itself as encryption tools. It exploits the complexity of finding a solution to a system of nonlinear equations from many variables. Multivariate cryptography uses as encryption tools nonlinear polynomial transformations of kind x1→f1(x1, x2,…,xn), x2→f2(x1, x2,…,xn), …, xn→fn(x1, x2,…,xn) transforming affine space Kn, where fi ϵ K[x1, x2,…,xn], i=1,2,…,n are multivariate polynomials usually given in the standard form, i. e. via a list of monomials in a chosen order. We are going to present new crypto algorithms in the area of the intersection of multivariate cryptography and non-commutative cryptography which appeared with attempts to apply combinatorial group theory to information security. If G is a noncommutative group then correspondents can use conjugations of elements involved in the protocol, some algorithms of this kind were suggested in [10–13], where group G is given with the usage of generators and relations. Security of such algorithms is connected to Conjugacy Search Problem (CSP) and Power Conjugacy Search Problem (PCSP), which combine CSP and Discrete Logarithm Problem and their generalizations. The extension of group-based cryptography is essentially wider direction of Non-commutative cryptography which is an active area of cryptology, where the cryptographic primitives and systems are based on algebraic structures like groups, semigroups, and noncommutative rings [14–18, 20, 21]. This direction of security research has very rapid development [22, 23] and further references in these publications). One of the earliest applications of a non-commutative algebraic structure for cryptographic purposes was the usage of braid groups to develop cryptographic protocols. Later several other non-commutative structures like Thompson groups and Grigorchuk groups have been identified as potential candidates for cryptographic post-quantum applications. The standard way of presentations of groups and semigroups is the usage of generators and relations (combinatorial group theory). This direction must be well supported by cryptanalytic research [29–33] Semigroup-based cryptography consists of general cryptographical schemes defined in terms of wide classes of semigroups and their implementations for chosen semigroup families (so-called platform semigroups). Papers [4], [5], and [6] contain some modifications of the Diffie-Hellman protocol when G is given as a subgroup of affine Cremona semigroup S(Kn) over finite commutative ring K of all polynomial transformations. These papers use the assumption that each element is given in its standard form of multivariate cryptography. To use semigroup operation one has to compute the composition of transformations. This was an attempt to combine methods of non-commutative cryptography and multivariate cryptography. Paper [4] suggests some usage of homomorphisms of subsemigroups of affine Cremona groups for protocols and cryptosystems which are not generalizations of the Diffie-Hellman algorithm and its El Gamal type modifications. Some examples are given there. The implementations of these schemes with an evaluation of densities of involved polynomial transformations are described in [6]. Elements of graph-based stable subgroups used in [6] can serve as encryption tools of stream ciphers (see [25] and further references). The current paper aims to apply formal schemes of [4] to the case of transformations of variety (K*)n, where K* is a multiplicative group of commutative ring K with unity such that |K*| >1. Natural examples of such rings are K=Zm and K=Fq where m>2, q>2. We present the new post-quantum key exchange protocols and cryptosystems of El Gamal type of non-commutative cryptography which uses homomorphisms of two semigroups acting on (K*)n (3.1- 3.4), some straightforward algorithms without the usage of homomorphisms are given in [26]. We hope that some of the presented algorithms will be used in the post-quantum future. 19 2. On Eulerian Semigroup and Hard Computational Problem Let K be a finite commutative ring with the unit such that multiplicative group K* of regular elements of the ring contains at least 2 elemments. We take Cartesian power nE(K) =(K*)n and consider an Eulerian semigroup nES(K) of transformations of kind x1 → ϻ1x1 a(1,1) x2 a(1,2) … xm a(1,n), x2 → ϻ2x1 a(2,1) x2 a(2,2) … xm a(2,n), (1) … xm →ϻnx1 a(n,1) x2 a(n,2) … xm a(n,n), where a(i,j) are elements of arithmetic ring Zd, d=|K*|, ϻiϵK*. Let nEG(K) stand for the Eulerian group of invertible transformations from nES(K). Simple example of an element from nEG(K) is a written above transformation where a(i,j)=1 for i ≠ j or i=j=1, and a(j,j)=2 for j ≥2. It is easy to see that the group of monomial linear transformations Mn is a subgroup of nEG(K). So semigroup nES(K) is a highly non-commutative algebraic system. Each element from nES(K) can be considered as a transformation of a free module Kn. Let π and δ be two permutations on the set {1,2,..., n}. Let us consider a transformation of (K*)n, K=Zm or K= Fq and d =|K*|. We define transformation AJG(π, δ), where A is a triangular matrix with positive integer entries 0≤a(i,j)≤d, i≥d defined by the following closed formula. yπ(1)=ϻ1xδ(1)a(1,1) yπ(2)= ϻ2xδ(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,n) where (a(1,1),d)=1, (a(2,2),d)=1,…,( a(n,n),d)=1. We refer to AJG(π, δ) as Jordan - Gauss multiplicative transformation or simply JG element. It is an invertible element of nES(K) with the inverse of kind BJG(δ, π) such that a(i,i)b(i,i)=1 (mod d). Notice that in the case K=Zm straightforward process of computation the inverse of JG element is connected with the factorization problem of integer m. If n=1 and m are a product of two large primes p and q the complexity of the problem is used in RSA public key algorithm. The idea to use the composition of JG elements or their generalizations with injective maps of Kn into Kn was used in [27] (K=Zm) and [28] (K=Fq). We say that  is a tame Eulerian element over Zm or Fq. if it is a composition of several Jordan Gauss multiplicative maps over commutative ring or field respectively. It is clear that  sends variable xi to a certain monomial term. The decomposition of  into product of Jordan Gauss transformation allows us to find the solution of equations  ( x)  b for x from ( Z m* ) n or (F*q)m. So tame Eulerian transformations over Zm or Fq. are special elements of nEG(Zm) or nEG(Fq) respectively. We refer to elements of nES(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 nES(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(n4). We are not discussing here the complexity of computing the inverse for general element gϵ nEG(K) on Turing machine or Quantum computer and the problem of finding the inverse for computationally tame Eulerian elements. Remark 2.1. Let G be a subgroup of nEG(K) generated by Jordan-Gauss elements g1, g2, …, gt. The word problem of finding the decomposition of gϵG into the product of generator gi is difficult, i. e. polynomial algorithms to solve it with Turing machine or Quantum Computer is unknown. If the word problem is solved and the inverses of gi are computable then the inverse of g is determined. Notice that if n=1, K=Zm, m=pq where p and q are large primes and G is generated by g1=ϻg1a the problem is unsolvable with the Turing machine but it can be solved with Quantum Computer. Each element of the semigroup nES(K) is written in the chosen basis e1, e2,…, en. Let J={i(1), i(2),…, i(k)} be a subset of {1,2,..,n} and WJ= be a corresponding symplectic subspace . We refer to totality nPJ (K) of maps F ϵ nES(K) preserving WJ as parabolic semigroup of n ES(K) . The map F from nPJ (K) transforms tuple (xi(1), xi(2), …, xi(n)) accordingly to the rule xi(1) →ϻi(1) xi(1)a(1,1) xi(2)a(1,2)… xi(k)a(1,k), xi(2) →ϻi(2) xi(1)a(2,1) xi(2)a(2,2)… xi(k)a(2,k),…, xi(k) →ϻi(k) xi(1)a(k,1) xi(2)a(k,2)… xi(k)a(2,k). 20 Let πJ be the restriction of element F from nPJ(K) onto WJ. The map πJ defines the canonical homomorphism of nPJ(K) onto kES(K). If Q is an extension of K we can consider semigroup nPJ,K(Q) of maps from nES(Q) transforming (xi(1), xi(2), …, xi(n)) accordingly to written above rule. The restriction of map Fϵ nPJ,K(Q) on WJ defines homomorphism πJ,K from nPJ,K(Q) onto kES(K). 3. Protocols and Cryptosystems in Terms of Semigroup nES(K) Let us consider some protocols and cryptosystems based on the idea of a hidden canonical homomorphism. Notice that if commutative ring K’ is an extension of K then embedding of K into K’ defines canonical embedding of nES(K) into nES(K’). Let nJG(K) stand for the totality of all Jordan- Gauss transformations from nES(K). 3.1 Tahoma Protocol Alice takes finite extensions Q and R of Kϵ{Zm., Fq} and J of cardinality k and consider a zigzag diagram n PJ,K (Q) → nES(Q) ↓ k ES(R) ← kES (K) The horizontal arrows correspond to embeddings of semigroups, vertical arrow corresponds to πJ,K.. Alice takes elements h1, h2, …, hs from kES(K) and creates elements ext(hi) from their πJ,K.reimages via adding the rules xj → ϻjx1 a(j,1) x2 a(j,2) … xn a(j,n) where ϻjϵ Q* and j is not an element of J. She selects set S= {g1, g2, …, gt} of Jordan-Gauss elements gi, i=1,2, …,t in nES(Q) and word in alphabet S to form tame element w of subgroup G = of nES(Q) together with w-1. Similarly Alice takes Jordan-Gauss generators S’={u1, u2, …, ur} in kES(R), selects word in alphabet S’ and forms tame element u ϵ and its inverse u-1. She forms pairs (ai =w-1ext(hi)w, bi =u-1(hi)u), i=1, 2,…,s and sends them to Bob. He takes formal alphabet Z={z1, z2, …, zs} and writes word wB=v(z1, z2, …, zs) in Z of length d, d>s and computes specialization zi=ai and zi=bi and takes resulting elements a=v(a1, a2, …, as)ϵ nES(Q) and b=v(b1, b2, …, bs)ϵ kES(R) respectively. Bob keeps b for himself and sends a to Alice. Alice computes 1a=wa w-1. She takes 2a=πJ,K.(1a) and obtains collision element b as u- 1(2a)u. 3.2. Inverse Tahoma Protocol As in the previous protocol, Alice works with the presented above zigzag diagram. She selects sets of Jordan - Gauss generators S in nES(Q) and S’ in kES(R) to construct pairs of tame elements w, w-1 and u, u-1. Now she takes set 1S of Jordan Gauss elements over R from kES(K)∩kJG(R) and forms elements h1, h2, …, hs from <1S > and their inverses h1-1 h2-1, …, hs-1 in kEG(R). Notice that elements hi-1, i=1,2,…,s are elements of kES(K) and larger semigroups kES(R) and kES(Q). Alice forms ext(hi) in nES(Q). In the new algorithm she computes pairs (ai =w-1ext(hi)w, bi =u-1(hi- 1 )u), i=1, 2,…,s and sends them to Bob. He takes formal alphabet Z={z1, z2, …, zs} and writes word wB=v(z1, z2, …, zs)=(u1, u2, …, ud) in Z of length d, d>s together with the reverse word Rev(wB)=(ud, ud-1, …, u1 ). Bob computes the specialization zi=ai of word wB and zi=bi of word Rev(wB) and takes resulting elements a=v(a1, a2, …, as)ϵ nES(Q) and b=v(b1, b2, …, bs)ϵ kES(R) respectively. Notice that bϵ kEG(R). He sends a to Alice and keeps b for himself. Alice computes 1a=wa w-1. She takes 2a=πJ,K.( 1 a) and obtains element b-1 as u- 1( 2a)u. Remark. Alice and Bob can securely communicate in the following way. Alice writes a message as a string of characters (p1, p2, …, pk) in alphabet R* encrypts it by application of b-1. Bob decrypts it with his transformation b. Similarly, Bob uses b for the encryption of his message from the plain space (R*)k and Alice decrypts it with b-1. 3.3. Group Enveloped Diffie-Hellman Key Exchange Protocol As in the inverse protocol of the previous unit Alice works with the presented above zigzag diagram. She selects sets. For simplicity assume that Q=K=R. Alice selects sets of Jordan - Gauss 21 generators S in nES(K) and S’ in kES(K) to construct pairs of tame elements w, w-1 and u, u-1. Now she takes set 1S of Jordan Gauss elements over K from kES(K) and forms elements h1, h2, …, hs from <1S > and their inverses h1-1 h2 -1, …, hs-1 in kEG(K). Alice takes gϵ kES(K) and positive integer parameter kA. Alice creates elements ext(hi), ext( hi-1) and ext(g) from their πJ .reimages via adding the rules xj → ϻjx1 a(j,1) x2 a(j,2) … xn a(j,n) where ϻjϵ K* and j is not an element of J. She forms pairs (ai =w-1ext(hi)w, bi =u-1(hi) u), i=1, 2,…,s and sends them to Bob together with pairs (ai-1, bi-1), gA = u-1gl u, l= kA and g’=w-1ext(g)w. Bob takes formal alphabet Z={z1, z2, …, zs} and writes word wB=v(z1, z2, …, zs)= (u1, u2, …, ud) in Z of length d, d>s together with the reverse word Rev(wB)=(ud, ud-1, …, u1). Bob computes the specialization zi=ai of word wB and zi = ai-1 of Rev(wB) and writes resulting elements a and a-1 from n ES(K). Similarly, he creates b and b-1 via specialization zi=bi of wB and specialization and zi=bi -1 of word Rev(wB) in the group kEG(K) respectively. Bob takes his natural integer kB. He computes Bg=a-1 gda, d=kB and sends it to Alice, and keeps the collision map c=b-1gA db, d=kB. Alice computes the collision map as u-1(πJ (w Bg w-1)) l u, l= kA. Remark 3.1. The adversary has to decompose Bg into ai and g’. After that he/she has to substitute gA instead of g’ and bi instead of ai. 3.4. The Inverse Version of Group Enveloped Diffie-Hellman Key Exchange Protocol Assume that K=R=Q and Alice works with the simplified zigzag diagram kES(R)= kES(K). She forms the same data as in the case of 3.4 but gϵkES(K) has to be invertible. So Alice takes an additional set 2S of Jordan-Gauss elements from kEG(K) and forms pair of kind (g, g-1), gϵ<2S>. She sends Bob pairs (ai-1, bi-1), gA = u-1gl u, l= kA and g*=w-1ext(g-1)w instead of g’ of 3.4. Bob uses a word in the alphabet of formal variables and generates elements a and a-1 from nEG(K) and b, b-1 ϵ kEG(K) in the same way with the case of 3.4 and takes his natural integer kB. Now he computes Bg=a-1 g*da, d=kB and sends it to Alice and keeps the map f=b-1gA db, d=kB. Alice computes the inverse map for f as u-1(πJ (w Bg w-1)) l u, l= kA. Remark 3.2. Alice and Bob have bijective transformations f and f-1 of the variety (K*) k. So they can exchange messages written in the alphabet. 4. New Cryptosystems related to the Semigroup of Eulerian Transformations and Their Transition into Private Mode Algorithm 4.1. Let us assume that K is a finite commutative group with unity with nontrivial group K*. Several Jordan - Gauss transformations J1, J2, …, Js from EGn(K) of kind x1 → b1x1a(1,1) x2 → b2x1a(2,1)x2 a(2,2) ... xn →bnx1 a(n,1)x2 a(n,2) … xn a(n,n), where a(i, j)ϵ Zm, m=|K*|, (a(i,i), m)=1 are selected by Alice. She can select s+1 monomial bijective affine transformations 1T, 2T, ..., s+1 T from AGLn(K) and use G=1T J1 2T J2 3T J3 … sT Js s+1T. (2) Noteworthy that the knowledge of decomposition (2) allows her to find the inverse of G via straightforward algorithms of computing inverses of Ji and jT. Alice computes G in its standard form and sends it to Bob. Correspondents use (K*)n as plain space and cipher space. Bob writes plain space (p)=(p1, p2, …, pn) computes the ciphertext G((p)), and sends it to Alice. She decrypts because of her knowledge of decomposition (1). Algorithm 4.2. Correspondents use plain space Mn(Zm) of square matrices (a(i,j)), i=1,2,…,n, j=1,2,…,n of size n over arithmetic ring Zm of residues modulo m=|K*|. Cipherspace is formed by elements of nES(K). Alice chooses invertible transformations B and C of kind (1) formed via selected decompositions of kind 2. She sends standard forms of B and C to Bob. 22 Bob writes his message in the alphabet Zm in the form of matrix A=(a(i,j)) and pseudo-random parameters μi, i=1,2,…, n to write transformation G written as (1). Bob computes the composition D=BAC and sends it to Alice. She computes B-1DC-1 and gets plaintext A. Remark 4.1. We can generalize the algorithm via the selection of μi, i=1,2,…, n from K-{0}. 5. Symbiotic Combination of Protocols with One-Time Pads Noteworthy that cryptosystem 3.1 and 3.3 can be combined with a one-time pad similar to the classical combination of Diffie-Hellman key exchange protocol and absolutely secure encryption in the sense of C. Shannon. Let us consider the case K=Zm, m=2r . Group Z*m is formed by all odd residues r(j)=2j+1, j=0, 1, …, 2(2 r-2)+1. Let j be a residue of Zm’, m’=2 r-1. The map π(r(j))=j is a bijection of (Z*)m onto Z m’. So correspondents use protocol 3.1 or 3.3. So they are elaborate collision element G of nES(K) in the form (I). The change μi for π(μi)=a i allows us to identify G with the password tuple (a)= (a1, a(1,1), a(1,2),…, a(1,n), a2, a(2,1), …, a(2,n),….,an, a(n,1), a(n,2),…, a(n,n)) from (Z m’)n(n+1)=V. So correspondents can use V as plainspace, Bob writes plaintext ((p1, p(1,1), p(1,2),…, p(1,n), p2, p(2,1), …, p(2,n),….,pn, p(n,1), p(n,2),…, p(n,n)) and add password tuple (a) to form ciphertext ((p1 + a1, p(1,1)+ a(1,1), p(1,2)+a(2,2),…, p(1,n)+a(1,n), p2+a1, p(2,1)+a(2,1), …, p(2,n)+a(2,n),…,pn + an, p(n,1)+a(n,1), p(n,2)+a(n,2),…, p(n,n)+a(n,n)). Thus we can use m=28, m’=27 and encrypt files with extension .txt. or use m=29, m’=28 to encrypt various files in the binary alphabet. We use pairs (233, 232) and (265, 264) to work with numerical data in popular alphabets of residues modulo 232 or 264. We can use prime field F257 to work with binary files. F* 257 is a cyclic group of order 256. So correspondents use nES(F257). Let us consider bijection π between F* 257 and Z 256 given by rule π(x mod 257) =x-1 mod 256. Then we can identify G with the element of (Z256) t, t=n(n+1) and use described above combination of the protocols and one-time pad based on the group (Z 256, +). Similarly, they can use next Fermat’s prime number 216+1=65537. They conduct the protocol in n ES(F65537) and work with a one-time pad with alphabet Zq, q=216. Correspondents could not use the next two Fermat numbers 232+1 and 264+1 because they are composite integers (the smallest one has prime factors 641 and 6708417). Correspondents can work with nES(F3), use π(x mod 3)=x-1 mod 2, and encrypt tuples over F2. Alternatively, they can use protocols defined for nES(F4) to work with classical one-time pads over F2. Another option is the usage of finite fields of characteristic two and works with nES(Fq), q=2m. In this case order of Fq is Mersenne number 2m-1. We can identify element of F*q of kind am-1xm-1 + am-2xm-2 +..+ a1x + a0 with (am-12m-1 + am-22m-2 +..+ a12 +a0)-1 of Zd, d=2m -1 and work with one time pad over the additive group of this ring. These one time pads are especially attractive in the case of Mersenne primes 2m -1 ( for m=2,3,7,13, 17,19, 31, 61, 89,107, 127,…). Remark 5.1. We can easily switch from one time pad over (Zq,+) and (Fq,+), q=2r which isomorphic to additive subgroup of vector space (F2) r . The natural bijection π is the map sending ar- r-1 r-2 r-1 r-2 r 1x +ar-2x + +a1x+…+ a0 from Fq to ar-12 +ar-22 + +a12+…+ a0 (mod 2 ). Remark 5.2. Correspondents can use inverse protocols 3.2 and 3.4. to get keys for one-time pad encryption. If Alice gets H and Bob receives Hr-1. Then Alice can generate “pseudorandom G” and sends HG (or HGH) to Bob and he restores G. 6. Conversion of Algorithm 4.1 to Cryptosystem of El Gamal Type Option 1. Correspondents use one of the protocols 3.1 and 3.3 based on the semigroup nES(K), and described above homomorphism of m(n)ES(K), where m(n) some linear expression in variable n such that m(n)>n. Recall that the security of these protocols rests on the complexity of word problems in the semigroup. So they elaborate the collision element H ϵ nES(K) written in the form xi→hi(x1, x2,…,xn), i=1,2,…,n where hi are monomial terms from K[x1, x2,…, xn]. Alice creates map G of Algorithm 4.1 via decomposition of kind (2) written as 23 xi →gi(x1, x2, …, xn). She sends the tuple (h1g1, h2g2,…, hngn) with all components written in standard form to Bob. He restores g1, i=1,2,…,n and correspondents start algorithm 4.1. Option 2. Correspondents use homomorphism of m(n)ES(K) onto mEG(K). They use protocol 4.2. and elaborate mutually inverse transformations G-1 (in the possession of Alice) and G (on the Bob side). So Bob uses G for the encryption of the plaintext (p) and Alice uses her G-1 to decrypt. Option 3. Alice selects expression G’=1T J1 2T J2 3T J3 … sT Js s+1T. She sends F= G-1 G’ (or G-1 G’G-1). Bob computes G’ as GF (or GFG). He uses G’ as an encryption tool. Alice uses her knowledge on the decomposition of kind (2) and decrypts. Remark 6.1. Adversaries can use some cyber-terrorist tools to get more than n pairs of kind (plaintext (pi), corresponding ciphertext (ci)). It allows him to start the investigation of equations G(pi)=ci, i=1,2,…,t, t>n for the approximation of G (or G’). Noteworthy that the polynomial algorithm for solving this approximation problem is unknown. Remark 6.2. Noteworthy that correspondents can restrict the number of exchanged messages by [n/2]. This restriction does not allow an adversary to collect sufficient data for the approximation process. When the number of Bob’s messages rich [n/2] correspondents they start a new protocol of kind 4.1 to establish a new encryption rule for Bob. Noteworthy that in the presented schemes correspondents can use protocol 3.3 instead of 3.1 and protocol 3.4 instead of 3.2. 7. Conversion of Algorithm 4.2 to a Cryptosystem of El Gamal Type Option 1. Correspondents use twice data for protocols of kind 3.1 or 3.3 based on the semigroup n ES(K), and described above homomorphism of m(n)ES(K), where m(n) some linear expression in variable n such that m(n)>n. So correspondents elaborate two collision elements H and H’ from nES(K) written in the form xi→hi(x1, x2,…,xi) and xi→h’i(x1, x2,…,xi) i=1,2,…,n where hi, h’i, are monomial terms from K[x1, x2,…, xn]. Alice uses different sequences of Jordan-Gauss elements and different sequences of linear monomial transformations to construct two bijective transformations B and C from nEG(K) in their standard forms xi→bi(x1, x2,…,xi) and xi→ci(x1, x2,…,xi) together with their decompositions of kind (2). So she computes B-1 and C-1 presented in their standard forms together with corresponding decompositions. Alice sends tuples (h1b1, h2b2, …, hnbn) and (h’1c1, h’2c’2, …, h’nb’n) to Bob. He restores transformations B and C and uses Algorithm 4.2 with these data. All suggested algorithms were implemented in the case of finite fields K=Fq and arithmetic rings Zq, q=28, 216, 232. Remark 7.1. Adversary has to intercept many pairs of kind (plaintext pi, corresponding ciphertext ci), i=1,2,…,t. He/she can consider transformations Z: x1 → z1x1 z(1,1) x2 z(1,2) … xn z(1,n), x2 → z2x1 z(2,1) x2 z(2,2) … xn z(2,n), …, xn →znx1 z(n,1) x2 z(n,2) … xnz(n,n) and Y: x1 → y1x1 y(1,1) x2 y(1,2) … xn y(1,n) , x2 → y2x1 y(2,1) x2 y(2,2) … xn y(2,n),…, xn →ynx1 y(n,1) x2 y(n,2) … xny(n,n ). where z i, yi, z(i,j), y(i,j) are variables. Adversary writes intercepted ciphertects C(l) as transformation of kind (1) with μi = lci, i=1,2,…,n and a(i,j)=lc(i,j). He/she forms elements P(l) of nES(K) from intercepted plaintexts pl with unknown μi =lui, i=1,2,…,n and a(i,j)=lp(i,j). Adversary has to investigate nonlinear system of equations XP(l)Y=C(l), l=1,2,…,t. Each equation in the group nES(K) corresponds to n2equalities in Zd and n equalities for variables from K*. We have 2n2 variables in Zd and 2n +tn variables which are parameters from K*. Simple counting of numbers of variables from Zd demonstrates that interception of one message does not allow an adversary to compute transformations B and C. So Alice and Bob can exchange two messages safely and start a new session of the protocol. So we have a postquantum version of the combination Diffie Hellman key exchange protocol and an absolutely secure one-time pad. The advantage is that we can use the encryption scheme at least two times. 24 In the case of arbitrary t the number of unknown parameters from K* is larger than a number of equations in terms of ring elements. It means that the usage of pseudorandom parameters in the algorithm allows avoiding new session of the protocol. 8. Conclusion We present two public-key cryptosystems (Algorithms 4.1 and 4.2) for which security rests on the complexity of finding the inverse for an element from nEG(K). The polynomial algorithm for the solution to this problem is unknown. So we hope that the suggested PK system is an interesting one for cryptanalytics. The combinations of Algorithm 4.1, 4.2, and one-time pads with postquantum protocols of Section 3 produce cryptosystems that are not public keys. They have a certain similarity with the number-theoretic El Gamal cryptosystem. Security of these algorithms as well as security of corresponding protocols rest on the known hard problem of word decomposition. Noteworthy that used platforms nEG(K) are highly noncommutative semigroup for which word decomposition problem is NP-hard. So these two cryptosystems can be used as post-quantum instruments. 9. References [1] Post-Quantum Cryptography: Call for Proposals.URL: https://csrc.nist.gov/Project; Post- Quantum-Cryptography-Standardization/Call-for-Proposals. [2] M. Andrzejczak, The Low – Area FPGA Design for the Post – Quantum Cryptography Proposal Round 5, in: Proceedings of the Federated Conference on Computer Science and Information Systems (FedCSIS), Cryptography and Security Systems, Leipzig, September 2019. [3] R. J. McEliece, A Public-Key Cryptosystem Based On Algebraic Coding Theory, 1978. DSN Progress Report No. 44 114–116. [4] V. Ustimenko, On new symbolic key exchange protocols and cryptosystems based on hidden tame homomorphism, Dopovidi 10 (2018) 26–36. [5] V. Ustimenko, On the families of stable transformations of large order and their cryptographical applications, Tatra Mt. Math. Publ. 70 (2017) 107–117. [6] V. Ustimenko, M. Klisowski, On Non-commutative Cryptography with Cubical Multivariate Maps of Predictable Density, in: Intelligent Computing, Springer International Publishing, Cham, 2019, pp. 654–674. [7] M. Noether, L. Cremona, Mathematische Annalen 59 (1904) 1–19. [8] R. Wagner, M. R. Magyarik, A Public-Key Cryptosystem Based on the Word N Problem, Advances in Cryptology, in: Proceedings of CRYPTO '84, Santa Barbara, California, USA, 1984, pp. 19–36. [9] L. Goubin, J. Patarin, Bo-Yin Yang, Multivariate Cryptography, Encyclopedia of Cryptography and Security, 2nd ed., 2011, pp. 824–828. [10] D. N. Moldovyan, N. A. Moldovyan, A New Hard Problem over Non-commutative Finite Groups for Cryptographic Protocols, in: International Conference on Mathematical Methods, Models, and Architectures for Computer Network Security, MMM-ACNS 2010: Computer Network Security, 2010, pp. 183–194. [11] L. Sakalauskas., P. Tvarijonas, A. Raulynaitis, Key Agreement Protocol (KAP) Using Conjugacy and Discrete Logarithm Problema in Group Representation Level, INFORMATICA 8 (2007) 115–124. [12] V. Shpilrain, A. Ushakov, The conjugacy search problem in public key cryptography: unnecessary and insufficient, Applicable Algebra in Engineering, Communication and Computing 17 (2006) 285–289. [13] D. Kahrobaei, B. Khan, A non-commutative generalization of ElGamal key exchange using polycyclic groups, in: IEEE GLOBECOM 2006 - 2006 Global Telecommunications Conference, 2006 p. 4150920. doi:10.1109/GLOCOM.2006.290. 25 [14] Cao Zhenfu, New Directions of Modern Cryptography. Boca Raton, CRC Press, Taylor & Francis Group, 2012. [15] B. Fine, M. Habeeb, D. Kahrobaei, G. Rosenberger, Aspects of Nonabelian Group Based Cryptography: A Survey and Open Problems, arXiv:1103.4093 [cs, math], 2011. [16] A. Myasnikov, V. Shpilrain, А. Ushakov, Non-commutative Cryptography and Complexity of Group-theoretic Problems, American Mathematical Society, 2011. doi:10.1090/surv/177. [17] I. Anshel, M. Anshel, D. Goldfeld, An algebraic method for public-key cryptography, Math. Res.Lett. 6 (1999) 287–291. [18] S. R. Blackburn, S. D. Galbraith, Cryptanalysis of two cryptosystems based on group actions, in: Advances in Cryptology – ASIACRYPT ’99, Springer, Berlin, 1999, pp. 52–61. [19] K. H. Ko, S. J. Lee, J. H. Cheon, J. W. Han, J. Kang, C. Park, New Public-Key Cryptosystem Using Braid Groups, in: Advances in Cryptology — CRYPTO, Berlin, Heidelberg, 2000. pp. 166–183. [20] G. Maze, C. Monico, J. Rosenthal, Public key cryptography based on semigroup actions. Adv.Math. Commun 1 (2007), 489–507. [21] P. H. Kropholler, 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 81 (2010) 172– 186. [22] J. A. Lopez Ramos, J. Rosenthal, D. Schipani, R. Schnyder, Group key management based on semigroup actions, Journal of Algebra and its applications 16 (2019). [23] G. Kumar, H. Saini, Novel Noncommutative Cryptography Scheme Using Extra Special Group, Security and Communication Networks ID 9036382 (2017). doi:10.1155/2017/9036382 [24] V. Ustimenko, On desynchronised multivariate El Gamal algorithm, Cryptology ePrint Archive 712 (2017). [25] 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 ID 2137561 (2019). doi:10.1155/2019/2137561. [26] V. Ustimenko, On semigroups of multivariate Cremona transformations and new solutions of Post Quantum Cryptography, Cryptology ePrint Archive 133 (2019). [27] V. Ustimenko, On new multivariate cryptosystems based on hidden Eulerian equations, Dopov. Nath Acad of Sci 5 (2017) 17–24. [28] V. Ustimenko, On new multivariate cryptosystems based on hidden Eulerian equations over finite fields, Cryptology ePrint Archive 093 (2017). [29] A. G. Myasnikov, A. Roman'kov, A linear decomposition attack, Groups Complex. Cryptol. 7 (2015) 81–94. [30] V. A. Roman'kov, A nonlinear decomposition attack, Groups Complex. Cryptol. 8 (2016) 197– 207. [31] V. Roman'kov, An improved version of the AAG cryptographic protocol, Groups, Complex., Cryptol 11 (2019) 35–42. [32] A. Ben-Zvi, A. Kalka and B. Tsaban, Cryptanalysis via algebraic span, in: Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, 2018, pp. 255–274. [33] B. Tsaban, Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography, J. Cryptol 28 (2015) 601–622. 26