On Multivariate Maps of High Degree for the Post Quantum Protection of Virtual Organizations Vasyl Ustimenko1,2,3 and Tymoteusz Chojecki1 1 University of Marie Curie-Sklodowska in Lublin, 5 Plac Marii Curie-Skłodowskiej str., Lublin, 20-031, Poland 2 Institute of Telecommunications and the Global Information Space of the National Academy of Sciences of Ukraine, 13 Chokolivsky boul., Kyiv, 02000, Ukraine 3 Royal Holloway University of London, Egham Hill, Egham TW20 0EX, UK Abstract The intersection of Commutative and Multivariate cryptography contains studies of cryptographic applications of subsemigroups and subgroups of affine Cremona semigroups defined over finite commutative ring K with the unit. We consider two special families of subsemigroups in a semigroup of all endomorphisms of K[x1, x2, …, xn]. They can be used in Post Quantum Cryptography for the development of key exchange protocols of Noncommutative Cryptography with output presented as multivariale map of high degree and density. The security of these schemes is based on a complexity of Conjugacy Power Problem. Suggested schemes can be converted in protocol based cryptosystems of El Gamal type and used for post quantum protection of Virtual Organisations in Global Information Space. Algorithms are implemented in the cases of finite fields of characteristic 2 and arithmetic rings Zm, m=2n, n=8,16,32. Keywords 1 Multivariate transformations, virtual organization, knowledge base, noncommutative cryptography, multivariate cryptography, graph based cryptography. 1. Introduction 2. Post Quantum, Multivariate and Noncommutative Cryptography NIST 2017 tender starts the standardisation process of possible Post-Quantum Public keys and Virtual Organizations aimed for purposes to be:  Encryption tools. Noteworthy that all multivariate NIST  Tools for digital signatures [1]. candidates were presented by multivariate rule of In July 2020 the Third round of the degree bounded by constant (2 or 3) of kind competition was started. In the category of x1→f1(x1, x2, …, xn), x2→f2(x1, x2, …, xn), …, Multivariate Cryptography (MC) remaining xn→fn(x1, x2, …, xn). candidates are easy to observe [2]. In fact RUOV is given by quadratic system of For the first task multivariate algorithm were polynomial equations. During Third Round of not selected, single multivariate candidate is NIST project [5] some crypto analytical Rainbow Like Unbalanced Oil and Vinegar instruments for breaking ROUV were found. So, (RUOV) In fact RUOV algorithm is investigated all multivariate algorithms-candidates were as appropriate instrument for the second task rejected during the project and first four winners [3, 4]. were announced in July, 2022. All of them are within the area of Lattice based Cryptography. We think that these NIST outcomes motivate investigations of alternating options in CPITS-2022: Cybersecurity Providing in Information and Telecommunication Systems, October 13, 2022, Kyiv, Ukraine EMAIL: vasulustimenko@yahoo.pl (V. Ustimenko); tymoteusz.chojecki@umcs.pl (T. Chojecki) ORCID: 0000-0002-2138-2357 (V. Ustimenko); 0000-0002-3294-2794 (T. Chojecki) ©️ 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) 156 Multivariate Cryptography oriented on encryption rows Mi = (mi,1, mi,2, …, mi,n), i ϵ J for some tools and conducting digital signatures. “potentially infinite” set J. (a) To work with plainspace Fqn and its So, Alice and Bob can periodically compute transformation G of linear degree cn, c > 0 on the G(Mi) and use this tuple as entrance password. level of stream ciphers or public keys. Additionally they can use G for symmetric (b) To use protocols of Noncommutative communication via one time pad. Cryptography with platforms of multivariate Alice writes her plaintext P=(p1, p2, …, pn) transformations for the secure elaboration of from Fqn. She computes P + G(Mi) and sends it to multivariate map G from End(Fq[x1, x2, …, xn]) of Bob. He knows Mi as well. So, Bob restores the linear or superlinear degree and density bounded plaintext. below by function of kind cnr, where c>0 and r>1. Surely instead of one time pad correspondents Recall that density is the number of all can use other stream cipher with periodical monomial term in standard form xi → gi(x1, x2, …, change of password. xn), i = 1,2,…,n of G, where polynomials g1 are It is naturally to consider more general case of given via the lists of monomial terms in the arbitrarily commutative ring K instead of finite lexicographical order. field Fq. We will use Algebraic Graphs to generate Solution of task (b) can be used for the control highly nonlinear automorphisms of K[x1, x2, …, access to the portal B of virtual organisation xn] over commutative ring. (knowledge base, virtual decision making centre, For creation of Mi, i ϵ J ontological etc.) via secure communications of portal technologies can be used. We use files obtained administrator (Alice) and public user (Bob). by ontological instruments presenting for example Assume that the information in B is presented key words of texts with the relations between in binary alphabet. So we can identify characters them in the form of graph (trees or other of this alphabet with elements of finite field Fq, diagrams). One can combine ontological q=256. Portal has a search engine. So, we can extraction with hashing technologies to make assume that the size of the information through the digests of documents of appropriate size. portal is practically unlimited. We hope that this new application of Assume that some secure tools are used to technologies for special ontological extractions protect the entrance of B. To enter the system user will motivate further research in this important need a password which is a tuple E of length n direction. written in alphabet Fq. It has to be changed The task is new because of postquantum regularly with the usage of certain period ∆. protocols with outputs in the form of highly We suggest the following access control nonlinear map of affine map of K n to itself appear scheme. Alice and Bob use several session of very recently. Postquantum Secure Protocols of We present one of them below. Noncommutative Cryptography based on a subsemigroup S of End Fq [x1, x2, …, xn] to 3. Multivariate Platforms of elaborate multivariate map G from S of kind xi→fi(x1, x2, …, xn), i = 1,2,…,n of degree bounded Noncommutative Cryptography below by cn, c>0 and density bounded below by and Their Applications dnr where c, d are positive constants and r > 2. The standard form of G can be unknown. This Regular algebraic graph A(n, q) =A(n, Fq) is an map could be non bijective one. It has to be given important object of Extremal Graph Theory. In with a polynomial algorithm of computation the fact we can consider more general graphs A(n, K) value of G in given tuple P = (p1, p2, …, pn). defined over arbitrary commutative ring K. Alice use some pseudorandom generator of This graph is a bipartite graph with the point tuples for the creation of P = (p1, p2, …, pn) and set P=Kn and line set L=Kn (two copies of a sends it to Bob via open channel. She enters Cartesian power of K are used). It is convenient to password E = G(p1, p2, …, pn) to secure the use brackets and parenthesis to distinguish tuples portal. from P and L. Bob also computes the tuple E and enters the So, (p) = (p1, p2, …, pn) ϵ Pn and [l] = [l1, l2, …, system. We can assume that data storage B ln] ϵ Ln. The incidence relation I = A(n,K) (or contains a pseudorandom (or genuinely random, corresponding bipartite graph I) can be given by obtained via quantum computations) matrix of 157 condition p I l if and only if the equations of the P=K n defined bythe rule x1 → x1 + ak, x2→f1(x1, following kind hold: x2), x3 → f2(x1, x2, x3), …, xn→ fn-1(x1 x2, …, p2 – l2 = l1p1 xn).This transformation is bijective map of Kn to p3 – l3 = p1l2, itself. It is an element of affine Cremona group p4 – l4 = l1p3, CG(Kn) of elements from Aut(K[x1, x2, …, xn]) p5 – l5 = p1l4, … , acting naturally on Kn. The inverse for this map is pn – ln = p1ln-1 n ή(w)-1 which coincides with nή(w’) for w’ for odd n and pn – ln = l1pn–1 for even n. =Rev(w)=(-at ,b1-at, a2-at, b2-at, …, bt-at).We refer They were intensively used for the to Rev(w) as reverse string for w from BP(K). constructions of LDPC codes for satellite Proposition 2.1.1 [6]. The map nή from BP(K) communications and cryptographic algorithms. to CG(Kn) is a homomorphism of the semigroup In the case of K=Fq, q > 2 of odd characteristic into group. graphs A(n, Fq), n > 1 form a family of small We refer to nή as compression map and denote world graphs because their diameter is bounded n ή(BP(K)) as GA(n, K). Degree of element g of by linear function in variable n. We can consider Cremona group CG(Kn) of kind xi→gi(x1, x2, …, an infinite bipartite graph A(K) with points (p1, p2, xn) is the maximal degree of polynomials gi. …, pn, …) and lines [l1, l2, …,ln, …]. If K, |K| > 2 Theorem 2.1.1 [7]. The maximal degree of is an integrity then A(K) is a tree and A(n, K), multivariate element g from GA(n, K) equals 3. n=2,3,… is its algebraic approximation of large It means that subgroup G of kind TGA(n,K)T–1 girth. where T is an element of AGLn(K) can be used We refer to the first coordinates p1=ῤ((p)) and efficiently as a platform for the implementation of l1=ῤ([l]) as colors of vertices of A(K) (or A(n, K)). protocols of Noncommutative Cryptography. It is easy to check that each vertex v of the graph has a unique neighbor Na(v) of selected colour a. 3.2. Semigroup Family So the walk of length 2k from vertex (0,0,…) will be given by the sequence w of colours of its Let K be a finite commutative ring with the elements b1, a1, b2, a2, …, bk, ak. unit such that multiplicative group K* of regular It will be the walk without repetition of edges if 0 ≠ a1, ai ≠ ai+1 and bi ≠ bi+1 for i=1, 2,…, k-1. elements of the ring contains at least 2 elements. So we can identify walks from 0 point of even We take Cartesian power nE(K) = (K*)n and length point with sequence of kind w. Let w’=(b’1, consider an Eulerian semigroup nES(K) of a’1, b’2, a’2, …, b’s, a’s).We define the transformations of kind composition u of w and w’ as the sequence u=(b1, x1 → ϻ1x1 a(1,1)x2 a(1,2) … xm a(1,n), a1, b2, a2, …,bk, ak, b’1 + ak, ak + a’1, b’2 + ak, …, x2 → ϻ2x1a(2,1)x2 a(2,2) … xn a(2,n), (1) b’s + ak, a’s + ak). If w and w’ are paths and … b’1 + ak ≠ bk then u is also a path. xn → ϻnx1 a(n,1) x2 a(n,2) … xn a(n,n), Let BP(K) be a semigroup of all walks with this where a(i,j) are elements of arithmetic ring Zd, operation. One can identify empty string with the d=|K*|, ϻiϵK*. unity of BP(K).We use term branching semigroup for BP(K). 3.3. Two Platforms in a Tandem 3.1. Group Family Let nEG(K) stand for Eulerian group of invertible transformations from nES(K). It is easy Let us take graph A(n, K) together with A(n, to see that the group of monomial linear K[x1, x2, …, xn]). For each element w from BP(K) transformations Mn is a subgroup of nEG(K). So we consider a walk ∆(w) in A(n, K[x1, x2, …, xn]) semigroup nES(K) is a highly noncommutative with starting point (x1, x2, …, xn) where xi are algebraic system. Each element from nES(K) can generic elements of K[x1, x2, …, xn] and special be considered as transformation of a free module colors of vertices x1 + b1, x1 + a1, …, x1 + bk, Kn. x1 + ak. Let p’=dest(∆(w)) be a destination, i. e. a 1. Twisted Diffie-Hellman protocol. final point of this walk. The destination has Let S be an abstract semigroup which has coordinates (x1 + ak, f1(x1, x2), f2(x1, x2, x3), …, fn- some invertible elements. Alice and Bob share element g ϵ S and pair of 1(x1, x2, …, xn) where f1 are elements of K[x1, x2, …, xn]. We consider the transformation nή(w) of invertible elements h, h–1 from this semigroup. 158 Alice takes positive integer t = kA and d = rA Alice enters the access password P and sends and forms h-dghd = gA. Bob takes s = kB and p = rB. HX(P) it to Bob. He restores the P and enters B. and forms h-pgshp = gB. They exchange gA and gB Alternatively Bob enters the access password and compute collision element X as Ag = h-dgBthd P andsends H–1X–1(P) to Alice. She restores P and and Bg = h-pgAs hp respectively. puts as entrance rule to the system. 2. Inverse twisted Diffie-Hellman protocol. Let S be a group. Table 1 Correspondents follow the scheme 1 with the Density of the map HX of linear degree induced inverse element g ϵ nEG(K) and Alice sends by the graph 𝑨(𝒏, 𝑭𝟐𝟑𝟐 ), case I h–dg–thd = gA to Bob and she gets h–pgshp = gB from Length of the walk d(HX) him. They use the same formulae for Ag and Bg. n 16 32 64 128 256 But in the new version these elements are mutual 16 5623 5623 5623 5623 5623 inverses. Alice has X but Bob possesses X–1. 32 53581 62252 62252 62252 62252 64 454375 680750 781087 781087 781087 Both schemes can be implemented with the 128 3607741 6237144 9519921 10826616 10826616 multivariate platforms S=TGA(n,K)T–1 and n ES(K). Algorithm 2.3.1. Correspondents executes Table 2 pairs of directed twisted DH protocols with Density of the map of linear degree induced by platforms P1 = nES(K) and P2 = TGA(n,K)T–1. the graph 𝑨(𝒏, 𝑭𝟐𝟑𝟐 ), case II Assume that they have outputs H and X. Length of the walk d(HX) Each of correspondents have HX of linear n 16 32 64 128 256 16 6544 6544 6544 6544 6544 degree Θ(n) and density Θ(n4). 32 50720 50720 50720 50720 50720 They can compute standard form of G=HX, or 64 399424 399424 399424 399424 399424 use two step procedure to compute G(p) as 128 3170432 3170432 3170432 3170432 3170432 1 p = H(p) and 2p = X(1p). Remark 2.3.1 The density of HX is the Usage of transformations of kind HX as in number of monomial terms of this map in its algorithm 2 in the form of public key was standard form. It is function of the length of considered in [10] and [11]. Classical approach of reimage of X under the homomorphism ή’ sending Multivariate Cryptography are presented in [12]. u from BP(K) to Tnή(u)T–1. It depends on Ideas of fast developing Noncommutative d(HX)=d(X)=l(ή’–1 (X)). Cryptography reader can find in [13]–[28]. Parameter d(X) depends on kA, kB, rA, rB, ή’– 1 (g), ή’-1(h) and linear transformation T of the protocol with the platform TGA(n,k)T–1 [8, 9]. 4. Conclusions Thus, adversary does not able to estimate d(HX). Multivariate Cryptography started from Results of computer simulation demonstrate studies of bijective transformations G of a vector connection between d(HX) in the case of field Fq space (Fq)n. as possible encryption tools. One can of characteristic 2. increase number of variables n in the equation of Table 1 corresponds to the case of sparse kind G(x) = b and rewrite the condition of matrix T eith 2n – 1 no zero entries. Table 2 existence of solution for this equation in the form reflects the case of the matrix with n2 nonzero G’(y) = b’ where G’ is quadratic transformation entries. of V = (Fq)m where m is essentially larger than n, Algorithm 2.3.2. Correspondents executes y and b’ are vectors from V. pairs of inverse twisted DH protocols with The complexity of initial and rewritten platforms P1 = nES(K) and P2 = TGA(n,K)T–1. systems of equations are essentially differs. Assume that Alice has outputs H and X, Bob has Anyway this possibility motivates studies of H–1 and X–1 from P1 and P2 respectively. quadratic maps as tools for Public Key Correspondents use space of plaintexts (K*)n and Cryptography. space of ciphertexts Kn. All algorithms of Multivariate Cryptography Alice and Bob encrypt via HX and H–1X–1 and under NIST investigation were based on quadratic decrypt via XH and X–1 H–1. equations and were not selected as finalists. The Remark 2.3.2. In the case of inverse first four winners of the NIST competition are protocols. The access control does not use the described in term of Lattice based Cryptography. extraction of information from knowledge base B. 159 We have to mention that NIST project International Conference on the Theoryand compares implementations of some public keys as Applications of Cryptographic Techniques, products of Software Engineering. On the level of part I, 2021. Theoretical Computer Science all 5 classic [6] V. Ustimenko, On the Extremal Graph direction of Post Quantum Cryptography Theory and Symbolic Computations, inclusive Multivariate Cryptography have future Dopovidi National Academy of Sci, Ukraine, perspectives because they are based on known no. 2, 2013, pp. 42–49. NP-hard problems. One of such problems is about [7] V. Ustimenko, A. Wroblevska, On the key finding solution of nonlinear system of m = m(n) exchange with nonlinear polynomial maps of equations in n variables. stable degree, Annalles UMCS Informatica We already mention that restriction on the case AI X1, 2, 2011, pp. 81–93. of quadratic equations is not well motivated. [8] M. Klisowski, V. Ustimenko, On the Outcomes of NIST project motivates for search of Comparison of Cryptographical Properties of efficient and secure public keys based on Two Different Families of Graphs with Large multivariate transformation of unbounded degrees Cycle Indicator, Mathematics in Computer of affine space Kn defined over finite commutative Science, vol. 6, no. 2, 2012, pp. 181–198. ring K. [9] V. Ustimenko, M. Klisowski, On Noteworthy that some efficient public keys Noncommutative Cryptography with over finite fields and arithmetical rings Zm are Cubical Multivariate Maps of Predictable suggested in [10] and [11]. They use no bijective Density, in Computing Conference, transformations of Kn of unbounded linear degree Londone, vol. 2, Part of Advances in d(n). Crypto analytical instruments for breaking Intelligent Systems and Computing these algorithms are not founded yet. Other idea (AISC), volume 998, 2019, pp. 654–674. to use hard problems of Noncommutative [10] V. Ustimenko, On New Multivariate Cryptography in case of platform-semigroups of Cryptosystems based on Hidden Eulerian multivariate transformations is explored in this Equations, Dopov. Nath Acad of Sci, paper. Ukraine, no. 5, 2017, pp 17–24. [11] V. Ustimenko, On New Multivariate 5. References Cryptosystems based on Hidden Eulerian Equations over Finite Fields, Cryptology ePrint Archive, 093, 2017. [1] Post-Quantum Cryptography: Call for [12] L. Goubin, J. Patarin, B.-Y. Yang, Proposals, https://csrc.nist.gov/. Multivariate Cryptography, Encyclopedia of [2] V. Grechaninov, et al., Formation of Cryptography and Security, 2nd ed., 2011, Dependability and Cyber Protection Model pp. 824–828. in Information Systems of Situational [13] D. Moldovyan, N. Moldovyan, A New Hard Center, in Workshop on Emerging Problem over Non-commutative Finite Technology Trends on the Smart Industry Groups for Cryptographic Protocols, and the Internet of Things, vol. 3149, 2022, International Conference on Mathematical pp. 107–117. Methods, Models, and Architectures for [3] A. Bessalov, et al., Analysis of 2-isogeny Computer Network Security, MMM-ACNS properties of generalized form Edwards 2010, pp. 183–194. curves, in: Proceedings of the Workshop on [14] L. Sakalauskas, P. Tvarijonas, A. Raulynai- Cybersecurity Providing in Information and tis, Key Agreement Protocol (KAP) Using Telecommunication Systems, July 7, 2020, Conjugacy and Discrete Logarithm vol. 2746, pp. 1–13. Problema in Group Representation Level, [4] A. Bessalov, et al., Implementation of the Informatica, vol. 18, no. 1, 2007, pp. 115– CSIDH Algorithm Model on Supersingular 124. Twisted and Quadratic Edwards Curves, in [15] V. Shpilrain, A. Ushakov, The Conjugacy Workshop on Cybersecurity Providing in Search Problem in Public Key Cryptography: Information and Telecommunication Unnecessary and Insufficient, Applicable Systems, vol. 3187, no. 1, 2022, pp. 302– Algebra in Engineering, Communication and 309. Computing, vol. 17, iss. 3–4, 2006, pp 285– [5] A. C. François, Xavier Standaert, Eurocrypt 289. 2021, LNCS 12696, 40th Annual 160 [16] D. Kahrobaei, B. Khan, A non-commutative generalization of ElGamal key exchange using polycyclic groups, in IEEE GLOBECOM Global Telecommunications Conference [4150920], 2006. doi: 10.1109/glocom.2006. [17] Z. Cao, New Directions of Modern Cryptography. Boca Raton: CRC Press, Taylor & Francis Group, 2012. [18] B. Fine, et al., Aspects of Non abelian Group Based Cryptography: A Survey and Open Problems, arXiv:1103.4093. [19] A. Myasnikov, V. Shpilrain, A. Ushakov, Non-commutative Cryptography and Complexity of Group-theoretic Problems. American Mathematical Society, 2011. [20] I. Anshel, M. Anshel, D. Goldfeld, An Algebraic Method for Public-Key Cryptography, Math. Res. Lett. 6(3–4), 1999, pp. 287–291. [21] S. R. Blackburn, S. D. Galbraith, Cryptanalysis of Two Cryptosystems based on Group Actions, in Advances in Cryptology—ASIACRYPT’99. Lecture Notes in Computer Science, vol. 1716, 1999, pp. 52–61. [22] P. H. Kropholler, et al., Properties of Certain Semigroups and Their Potential as Platforms for Cryptosystems, Semigroup Forum 81, 2010, pp. 172–186. [23] J. A. Lopez Ramos, et al., Group Key Management based on Semigroup Actions, Journal of Algebra and Its Applications, vol. 16, 2019. [24] A. G. Myasnikov, A. Roman'kov, A Linear Decomposition Attack, Groups Complex. Cryptol., vol. 7, no. 1, 2015, pp. 81–94. [25] V. A. Roman'kov, A Nonlinear Decompo- sition Attack, Groups Complex. Cryptol., vol. 8, no. 2, 2016, pp. 197–207. [26] V. Roman'kov, An improved version of the AAG cryptographic protocol, Groups, Complex., Cryptol, 11, No. 1 (2019), 35-42. [27] A. Ben-Zvi, A. Kalka, B. Tsaban, Cryptanalysis via Algebraic Span, in Advances in Cryptology, CRYPTO, 38th Annual International Cryptology Conference, part I, vol. 10991, 2018, pp. 255–274. [28] B. Tsaban, Polynomial-time solutions of computational problems in noncommutative- algebraic cryptography, J. Cryptol. 28, No. 3 (2015), 601-622. 161