# On the Constructions of New Symmetric Ciphers Based on Nonbijective Multivariate Maps of Prescribed Degree

Authors: Vasyl Ustimenko; Urszula Romańczuk-Polubiec; Aneta Wróblewska; Monika Katarzyna Polak; Eustrat Zhupa
Journal: Security and Communication Networks
 (2019)

---

## Abstract

The main purpose of this paper is to introduce stream ciphers with the nonbijective encryption function of multivariate nature constructed in terms of algebraic graph theory. More precisely, we describe the two main symmetric algorithms for creation of multivariate encryption transformations based on three families of bipartite graphs with partition sets isomorphic toKn, where K is selected as the finite commutative ring. The plainspace of the algorithm is Ω={x∣∑xi∈K⁎,x∈Kn}⊂Kn,Ω≅K⁎×Kn-1. The second algorithm is a generalization of the first one with using the jump operator, where generalized encryption map has an essentially higher degree in comparison with the previous version. Moreover, the degree of this generalized map is not bounded by some constant. This property guarantees resistance of the cipher to linearization attacks.


---

## Body

## 1. Introduction

This paper is an extension of article [1] reflecting our talk at the 5th International Conference on Cryptography and Security Systems (one of the events of Federated Conference on Computer Science and Information Systems, 2018). We expand our work by adding the generalization of our symmetric cipher of multivariate nature. Generalized encryption map has essentially higher degree in comparison with previous version. The degree is not bounded by some constant. This property insures resistance of the cipher to linearization attacks.Graph theory is applicating in diverse fields such as linguistics, biochemistry, coding theory, cryptography, communication networks, etc. The history of the use of sparse algebraic graphs in symmetric cryptographical algorithms was described in [1] with the full list of references which begins with the ideas of V. Ustimenko presented in the article from 1998 (see [2]). In this paper, we present only a short version of this history related to work of V. Ustimenko and his team. The reader can find also more general survey on some applications of Graph Theory in Cryptography in [3].The following known graphs defined over finite commutative ringK were used: D(n,K) (see [2]; for K=Fq graphs were defined in [4]), W(n,K) (Wenger graphs defined in [5]), graphs A(n,K) introduced in [6], and graphs D(n,K)~ of [7]. Popular choices of K are finite fields F127, F27, F28, F216, and F232 and rings modular arithmetic Z27, Z28, and Z216. This research history is presented in the next section. Section 2 observes graph based stream ciphers which use bijective encryption function of multivariate nature. In fact, multivariate cryptography uses nonbijective maps and a private key decryption is also given in each case of this type. However, the vast majority of stream ciphers is defined via bijective encryption. In each case of nonbijective symmetric encryption there is a deterministic decryption process that has to be described in clear way. In Section 3 we discuss the class of nonbijective multivariate maps defined in terms of Euler theorem for arithmetical rings Zm, where m is a composite number. Such a map F has a special subset D (domain) of affine space Zmn isomorphic to Zm∗×Zmn-1, such that the restriction FD of F onto D is injective (D=FD). It is important that FD is unknown to the adversary, who knows only cipherspace Zmn. Correspondents use their knowledge on the password to obtain a description of F(D). They are able to compute bijective map Fdec from F(D) onto D which is a decryption procedure; i.e., the composition of FD with Fdec is identity map on D. The definition of multivariate nonlinear map F:Zmn→Zmn uses Eulerian map x→axe+b of Zm with a∈Zm∗ and gcd(e,ϕ(m))=1, where ϕ is Euler function.An adversary does not have access toa, e, or b. A hidden Eulerian equation of kind xe=c gives a heuristic support to resistance of symmetric algorithm to attacks with interception of pairs plaintext/ciphertext. Notice that, in the case of classical RSA algorithm large m decomposable into two primes is known, parameter e is given. Security of RSA rests on the complexity of finding decomposition m=pq or finding multiplicative inverse d of e. In practical cases of multivariate encryption with hidden Eulerian equation (like m=2k) Eulerian function ϕ(m) is easy to compute, but multiplicative inverse of e is hard to find because the adversary simply does not know e. In fact, in our examples the degree deg⁡(F)=α(e,n) of multivariate map F on Zmn sending D to codomain D′=FD heavily depends on parameter e. Decryption map of D′ into D is induced by nonbijective multivariate map G:Zmn→Zmn and degree d′n,d of degree deg⁡(G)=β(d,n). So “Eulerian parameters” e and d are very essential for cryptanalysis. This approach is illustrated by 3 “toy examples” of graph based symbolic computations (see (G) at the end of Section 3 with items (G.1), (G.2), and (G.3)).A linearization attack has to disclose codomainD′=FD, determine the standard form of polynomial encryption map F with its degree, and construct a polynomial map G, such that FGD is identity function. If one of the parameters α(e,n) or β(d,n) is unbounded (or it is a large constant) then linearization tasks are infeasible. Of course, a cryptanalyst has to try alternative approaches like distinguish, Time Memory Data trade-off attacks, and guess-and-determine attack. These methods are constructed for investigation of stream ciphers with bijective encryption. Authors believe that in the case of multivariate nonbijective encryption such attacks have to be seriously modified for the practical implementation.This approach is illustrated by three “toy examples” of graph based encryption. In Section4 we introduce a class of bivariate graphs containing all the above-mentioned graphs. Such concept is convenient for uniform description of the encryption scheme and observation of common properties of graphs from this class (Sections 5 and 8). General Algorithm No. 1 is described in Section 5 presents symmetric cipher based on nonbijective maps. Implementation results are presented in Table 1. The Algorithm No. 2, presented in Section 8, is a generalization of the first one with using the jump operator, where generalized encryption map has an essentially higher degree in comparison with the previous version. Moreover, the degree of this generalized map is not bounded by some constant. This property guarantees resistance of the cipher to linearization attacks. We compare graphs and related algorithms corresponding to different families (W(n,K), D(n,K), A(n,K), and D(n,K)~) in Sections 6 and 9.Table 1
Encoding and decoding time.
A ( n , K ) D ( n , K ) D ( n , K ) ~ Password File size Enc Dec Enc Dec Enc Dec 3 1K 0.0021 0.0029 0.0030 0.0026 0.0039 0.0041 10K 0.0217 0.0253 0.0234 0.0249 0.0322 0.0366 50K 0.1030 0.1338 0.1034 0.1423 0.1572 0.1859 100K 0.2158 0.2701 0.2115 0.2683 0.3309 0.3800 500K 1.2202 1.3863 1.0432 1.3556 1.6161 1.9323 1M 2.1955 2.8346 2.1452 2.7285 3.2809 3.9029 10M 21.9597 27.4227 21.3803 26.6821 32.8819 38.3860 4 1K 0.0416 0.0033 0.0400 0.0032 0.0401 0.0047 10K 0.0311 0.0320 0.0302 0.0360 0.0420 0.0466 50K 0.1393 0.1639 0.1374 0.1580 0.2125 0.2366 100K 0.2800 0.3314 0.2738 0.3280 0.4259 0.4816 500K 1.4381 1.7109 1.3918 1.6541 2.1278 2.4159 1M 2.9271 3.5035 2.8457 3.4055 4.3633 4.9664 10M 29.5728 34.6022 28.6899 33.7773 43.7334 49.4341 5 1K 0.0402 0.0045 0.0336 0.0039 0.0437 0.0058 10K 0.0355 0.0395 0.0382 0.0440 0.0533 0.0596 50K 0.1764 0.2038 0.1718 0.1909 0.2589 0.2876 100K 0.3510 0.4097 0.3391 0.3922 0.5243 0.5781 500K 1.7778 2.0589 1.7237 2.0015 2.7088 3.0049 1M 3.6421 4.2418 3.5507 4.1302 5.4671 6.0630 10M 37.3170 42.0697 36.2427 40.9556 55.1103 60.4248  6 1K 0.0445 0.0053 0.0412 0.0046 0.0445 0.0069 10K 0.0426 0.0481 0.0453 0.0448 0.0705 0.0667 50K 0.2132 0.2371 0.1987 0.2325 0.3123 0.3462 100K 0.4176 0.4830 0.4069 0.4678 0.6303 0.6890 500K 2.1494 2.4572 2.0897 2.3724 3.2690 3.5826 1M 4.3851 4.9386 4.2630 4.8109 6.7762 7.2091 10M 47.8490 50.3557 42.6451 47.7372 65.8464 71.6511  7 1K 0.0434 0.0055 0.0435 0.0059 0.0487 0.0091 10K 0.0477 0.0540 0.0475 0.0533 0.0754 0.0848 50K 0.2437 0.2699 0.2324 0.2671 0.3651 0.3979 100K 0.4903 0.5457 0.4751 0.5275 0.7315 0.7938 500K 2.5089 2.8124 2.5655 2.7524 3.7086 4.0025 1M 5.0959 5.7679 5.1230 5.6692 7.5859 8.2276 10M 51.0014 56.3961 49.8712 54.9345 76.4318 87.4684Last section is the conclusion where we discuss the choice of our model. Here the reader can find remarks on multivariate cryptography and its connections with cryptographical applications of algebraic graph theory.RSA is one of the most popular cryptosystems. It is based on a number factorization problem and on Euler’s Theorem. Peter Shor discovered that the factorization problem can be effectively solved by using a theoretical quantum computer. This means RSA could not be a security tool in the future postquantum era. One of the research directions leading to a postquantum secure public key is the multivariate cryptography, which uses a polynomial maps of affine spaceKn defined over a finite commutative ring K into itself as encryption tools (see [8]). This is a young promising research area because of the current lack of known cryptosystems with the proven resistance against attacks with the use of Turing machines. Another important direction of Postquantum Cryptography is the study of Hyperelliptic Curves Cryptosystems. We have to say that classical elliptic curves encryption will be not secure in the postquantum era.Applications of algebraic graphs to cryptography started with symmetric algorithms based on explicit constructions of extremal graph theory and their directed analogues. The main idea is to convert an algebraic graph in a finite automaton and to use the pseudorandom walks on the graph as encryption tools. This approach can also be used for the key exchange protocols. Nowadays the idea of “symbolic walks” on algebraic graphs, when the walk on the graph depends on parameters given as special multivariate polynomials in variables depending from plainspace vector, appears in several public key cryptosystems.Multivariate cryptography started from the study of potential for the special quadratic encryption multivariate bijective map ofKn, where K is an extension of finite field Fq of characteristic 2. One of the first such cryptosystems was proposed by Imai and Matsumoto and cryptanalysis for that system was invented by J. Patarin. A survey on various modifications of this algorithm and corresponding cryptanalysis can be found in [8] or [9].One of the first uses of nonbijective map of multivariate cryptography was in theoil and vinegar cryptosystem proposed in [10] and analyzed in [11]. Nowadays, this general idea is strongly supported by publication [12] devoted to security analysis of direct attacks on modified unbalanced oil and vinegar systems. It looks like such systems and rainbow signature schemes may lead to promising Public Key Schemes of Multivariate Encryption defined over finite fields. Nonbijective multivariate sparse encryption maps of degree 3 and ≥3 based on walks on algebraic graphs D(n,K) defined over general commutative ring and their homomorphic images were proposed in [13]. Security of the corresponding cryptosystem rests on the idea of hidden discrete logarithm problem. U. Romańczuk-Polubiec and V. Ustimenko combine the idea of “oil and vinegar signature cryptosystem” with the idea of linguistic graph based map with partially invertible decomposition to introduce a new cryptosystem [13]. This algorithm can be implemented with the use of families D(n,K) and A(n,K) and natural homomorphism between them. Finally, in [14] “hidden RSA multivariate encryption” based on graphs D(n,K) were proposed.In this paper we modify the encryption map (private key) of the above-mentioned cryptosystem in terms of family of bivariate graphs defined over the commutative ringK. These maps have multivariate nature despite the “numerical implementation” in symmetric ciphers mode with the plainspace isomorphic to K∗×Kn-1.


## 2. Implementation of Algorithms Based on Bijective Maps

We worked on a software package that enables us to investigate strongly symmetric cases of stream ciphers based on graphsW(n,K), D(n,K), D(n,K)~, and A(n,K), where K is the arithmetic ring. Some cases are already implemented by our team at the level of prototype model.Few algorithms have been implemented in the past for very special cases under supervision of V. Ustimenko. The history of implementation of these algorithms was described in [1] with the full list of references. Below we present only a short version of this history.The first implementation ofD(n,K) encryption was done in 2000 at the University of South Pacific (USP, Fiji Islands). The research team was composed by Professor V. Ustimenko, PhD Dharmendra Sharma (currently professor of University of Canberra), and postgraduate students V. Gounder and R. Prasad. The work was supported by the University Research Committee of the University of South Pacific (USP) grant. During this work the implementation of asymmetric mode was investigated with the chosen case for K was F127, with 127 being the closest prime to the size of ASCII code alphabet. It means that one has to delete just thedelete service symbol and can encrypt arbitrary text files. The chosen string was αi(x)=x+di, where di are elements of the ring K=F127 chosen in pseudorandom fashion. So that was a case of shifting encryption.The affine transformationsL1 and L2 were simply identities. The implemented cipher on ordinary PC was rather robust in performance, but with average mixing properties. It has been used at USP digital network working for campuses and USP centers located in 11 island countries of South Pacific region. The package was also used by ORACLE based system of the bursary office. Recently group of students from Okanagan College (affiliated with the University of British Columbia) implemented that stream cipher on a cluster network of PC for a large data encryption.Another case withK=Z256 and graph D(n,K) was implemented under the Research Committee of Sultan Qaboos University (SQU, Oman) grant. The research team was composed of Professors Vasyl Ustimenko and Abderezak Tousane and students Rahma Al Habsi and Huda Al Naamani. The software uses one to one correspondence between elements of Z256 and symbols of binary alphabet. It allows encryption of various file types (with extension doc, jpg, htm, avi, pdf, …) in a way that encrypted file is presented in the same format as the plaintext. The symmetric algorithm was used in academic networks of SQU and Kiev Mohyla Academy.The systematic study of shifting encryption for cases of shifting encryptions ofD(n,K) was conducted at UMCS (Lublin, Poland). J. Kotorowicz used arithmetical rings Z27, Z28, Z216 for the implementation with various affine transformation τL and τR (see [15]). The encryption was essentially faster than in all previously known cases. The selected affine transformation leads to an encryption with very good mixing properties: the change of a single character of the plaintext or the change of a single character of the encryption string d1,d2,…,ds causes the change of at least 98% of the ciphertext characters. In the case of τR=τL-1 it can be proved that the order of A(n,K) and D(n,K) based encryption map grows with the growth of parameter n. The comparison of orders was completed through the study of cycle structures of A(n,K) and D(n,K) encryptions. The obtained results showed similarity in both cases.M. Klisowski implementedD(n,K) and A(n,K) shifting encryption on symbolic level in the cases of finite fields F27, F28, F216F232. In [16] A. Wróblewska proved that shifting D(n,K) encryption is given by a cubical multivariate map (see also [17]). Computer simulation results allow estimating time of generation of these maps as functions of parameter n and densities of such multivariate cubic encryption and decryption maps. Similar results for cases of Boolean rings of sizes 27, 28, 216, and 232 are obtained via computer simulations.The PhD thesis of M. Klisowski [18] contains the first results on D(n,K) and A(n,K) based multivariate maps which are not defined via shifting encryptions. He used symbolic strings of kind α1(x)=x+c1,α2(x)=x+c2,…,αs-1(x)=x+cs-1, αs(x)=x3+cs with constants ci,i=1,2,…,s for special fields Fq in which x3=b has unique solution. It was shown that such a choice makes direct linearization attacks impossible.The first implementation for the case of Wenger graph based encryption was completed at the University of Sao Paolo (USP, Brasil) (see [19] and further references). Professors V. Futorny and V. Ustimenko chose field F253 of which size is the closest from below prime to the size of binary alphabet. This research was partially supported by FAPESP foundation (grant for international cooperation with USP). Computer simulation demonstrated high speed of encryption. In [19] authors evaluated the diameter of graph W(n,Fq) and proved that the family of these graphs W(n,q), n≤q is a family of small world graphs.Professor Routo Terada (USP, Brasil) suggested to investigate the behaviour of these algorithms under linearization attacks. Computer simulation supports the conjecture on a good resistance of the encryption scheme to such attacks.The idea of using graphsA(n,K) in cryptography was proposed by U. Romańczuk-Polubiec and V. Ustimenko in [6].Some stream ciphers defined via graphsD(n,K)~ were proposed by M. Polak and V. Ustymenko in [7]. Furthermore, M. Polak compared LDPC codes corresponding to A(n,K), D(n,K), and D(n,K)~ in [20].


## 3. On the Idea of Nonbijective Maps Based on Eulerian Equations and Some Toy Examples

Let us consider the case of commutative ringZm, where m is composite number.Classical scheme of multivariate bijection map on affine spaceZmn is of the form T1FT2, where T1 and T2 are bijective maps of kind(1)x1,x2,…,xn→Ax1,x2,…,xn+d1,d2,…,dn, where A=(ai,j),i=1,2,…,n is nonsingular matrix with entries from Zm and F is a nonlinear bijective polynomial map of kind xi→fi(x1,x2,…,xn),i=1,2,…,n, fi∈Zm[x1,x2,…,xn]. Leonard Euler investigated maps η:x→xe, x∈Zm. He discovered that if x is a regular (gcd(x,m)=1) and e is mutually prime with the order ϕ(m) of multiplicative group of Zm, then the preimage of y=η(x) is unique. Eulerian theorem states that the solution of η(x)=y is x=yr, where d is multiplicative inverse of e in the group Zm∗, i.e., ed≡1(mod⁡m). Map ϕ defined on the set of positive integers is known asEuler function. Everybody knows that the security of RSA encryption rests on the Eulerian Theorem.The general idea of hidden Eulerian equation [21] suggests to use G=T1FT2, where T1 is monomial map xi→aixπ(i), where π is some permutation. Nonlinear map F is Eulerian map given by rule xi→aixiei+bi,i=1,2,…,n, where gcd(ai,m)=1, gcd(ei,ϕ(m))=1 and bi∈Zm.It is easy to see that Eulerian map from one variablex→xe=E(x), x∈Zm is far from being a bijection in the case of composite number. For example if m=8 and e=3, we have E(0)=0, E(1)=1, E(2)=0, E(3)=3, E(4)=0, E(5)=5, E(6)=0, and E(7)=7. However, we can use G as encryption function on the plainspace Ω. Notice that T1 and F preserve the subset Ω of the affine space Zmn. The restriction of composition T1F onto Ω is a bijection. So T1F sends plaintext x=(x1,x2,…,xn) to intermediate vector v=(v1,v2,…,vn). The image of G(x) coincides with T2(v)=y. For decryption, the correspondent applies T2-1 to the ciphertext to obtain v and then the plaintext as T1-1(F-1(v)). Notice that, for the computation of F-1(v), the correspondent has to use Euler theorem. As you see the plainspace of this scheme is smaller than cipherspace like in the well-known El Gamal method. The encryption map sends the Domain Ω onto G(Ω) of the same size, but the location of these codomains is hidden from adversaries, because the map T2 is hidden from him/her. The encryption scheme described above can be generalized in various ways. For instance, one can define Eulerian map as xi→aixiie+bi. Some modifications are suggested in [21] where even more general definition of Eulerian map is given and nonlinear multivariate bijection is used instead of affine map T1.Another idea is based on deformations of bijective nonlinear multivariate mapH of kind x1→h(x1), xi→hi(x1,x2,…,xn),i=2,3,…,n. We assume that correspondents are able to solve H(x)=c for x and refer to such multivariate transformation as the map with one-dimensional invariant subspace.We consider a mapH~ of kind x1→ax1e+b, x2→hi(x1,x2,…,xn),i=2,3,…,n, where gcd(e,ϕ(m))=1 and a∈Zm∗.Obviously,H~ sends Δ={x1,x2,…,xn∣x1∈Zm∗,xi∈Zm,i=2,…,n} to H~(Δ) of the same size. We consider the encryption map G of kind G=T1H~T2, where T2∈AGLn(Zm) and T1 is an affine map of kind x1→x1+x2+⋯+xn, xj→lj(x1,x2,…,xn), j=2,3,…,n, lj∈Zm[x1,x2,…,xn], deg⁡(lj)=1.So correspondents can use the plainspaceΩ={x∈Zmn∣x1+x2+⋯+xn∈Zm∗}. The map T1 sends plaintext x to the tuple v=(v1,v2,…,vn)∈Δ.The mapH~ transforms v into u=(u1,u2,…,un) with u1=av1e+b. Finally affine map T2 sends u to the ciphertext y. Decryption process: correspondent computes u as T2-1(y). He/she solves equation v1e=(u1-b)/a and gets v1. He investigates the map v1→h(v1), v2→u2,…, vn→un. Under the assumption that correspondents can compute the preimages of H they can get v=(v1,v2,…,vn) and the plaintext x=T1-1(v).Formally, our encryption map can be expressed asT1HCT2, where C is the map x1→a1(f-1(x))e+b, xj→xj,j=2,3,…,n. Clearly, representation of f-1 in polynomial map can be a hard task.In order to be able to use the above encryption, Alice has to compute the standard formE=T1H~T2 of kind xi→ei(x1,x2,…,en),i=1,2,…,n. She has to prove that E is computable in polynomial time. To hide parameter e Alice can select (2)H=h1x1,x2,…,xn,h2x1,x2,…,xn,…,hix1,x2,…,xn with deg⁡(hi)>e. Notice that in RSA algorithm the ring Zm and parameter e of the map x→xe, x∈Zm∗ are known. So one can use termhidden RSA for the presented scheme of multivariate public key algorithm. It means that correspondents may use m decomposed not only into two large prime numbers, but also into other composite modules.Let us assume that correspondents are going to useE for private key symmetric encryption. Then they do not need to compute and share the polynomial form of E. So in this case requirement d<deg⁡(E) is immaterial. Alice and Bob keep parameters a,e, and b together with matrices T1 and T2 as part of their private key. They have to present for everybody the algorithm of computation for the value of H in a given point (p1,p2,…,pn).Of course the polynomial form ofE is important to study the adversary attacks in the case of interception of many pairs of kind plaintext/ciphertxt (linearization, distinguish, TMD, and guess-and-determine attacks). Known methods of cryptanalysis dealing with bijective encryption have to be modified for attacks on nonbijective multivariate maps.Notice that(i)
H~ defined on Zmn has one-dimensional invariant subspace of tuples of kind (α,0,…,0).(ii)
The restriction ofH~ onto Δ={x=x1,x2,…,xn∣x1∈Zm∗,xi∈Zm,i=2,…,n} is an injective map.So the map of kindG=T1FT2, where nonlinear F:Zmn→Zmn satisfies (i) and (ii) can be used as encryption tool for the plainspace Ω. The cryptosystem of this kind with F defined in terms of algebraic graphs is proposed in [14].In this paper we used described above scheme with different core functionF to define family of graph based nonbijective stream ciphers. Finally we propose the following generalization of nonbijective encryption bases on the map F with the properties (i) and (ii). Instead of (ii) we consider the following property:(iii)
The restriction ofF onto Δ={x=(x1,x2,…,xn)∣x1∈Zm∗,xi∈Zm,i=2,…,n} is a bijective map.In fact, the totalityS=S(Δ,Zm) of all maps satisfying (i) and (iii) is a semigroup and the restrictions of elements from S onto Δ form a group.For example, the above defined mapH~ is an element of S in the case of b=0.It is easy to see that a map of kindG=F1F2…FsT2, s≥1 with nonlinear Fi:Zmn→Zmn where Fi∈S(Zm),i=1,2,…,s-1 and Fs satisfies properties (i) and (ii). It means that T1GT2 can be used for nonbijective multivariate encryption.Let us consider a toy example of generation of bijective maps with one-dimensional invariant subspace and transformations with properties (i) and (ii) and elements fromS via symbolic walks on algebraic graphs.Let us consider a commutative ringK and bipartite graph D(3,K) with the partition sets P={x1,x2,x3∣xi∈K,i=1,2,3} and L={(y1,y2,y3)∣yi∈K,i=1,2,3} and incidence relation (x1,x2,x3)I[y1,y2,y3]. We define colour ρ(v)∈K of the vertex v via rules ρ((x1,x2,x3))=x1 and ρ([y1,y2,y3])=y1. It is easy to see that for each vertex v there is exactly one neighbour u=Nα(v)K=Nα(v) (vIu) of chosen colour α. So let us consider the walk in the graph with starting point p=(p1,p2,p3) of length t (number of edges). The information on the walk can be given by sequence of elements α0=p1, α1, α2, …, αt which are colours of vertices of the walk. The walk consists of vertices v0=p, v1=Nα1(v0), v2=Nα2(v1), …, vt=Nαt(vt-1). If αi≠αi+2 for i=0,1,…,t-2, then the walk does not contain consecutive edges. The walks with starting line [l1,l2,l3] can be described in similar way. Notice that the description of walks is written uniformly for any commutative ring K.To introduce “symbolic walks” in the graphD(3,K) we need the infinite graph D(3,K[x1,x2,x3]) where K′=Kx1,x2,x3 is the ring of polynomials in variables x1,x2,x3 with coefficients from K. Points and lines of new graph are triples (f1,f2,f3), fi∈K[x1,x2,x3], i=1,2,3 and [g1,g2,g3], gi∈K[x1,x2,x3], i=1,2,3.We consider walks started from special point(x1,x2,x3), where xi are generic elements of K[x1,x2,x3]. Let a1, a2, …, at be special colours of vertices from the walk, taken from K[x1]. The walk contains v0=(x1,x2,x3), v1=Na1x1K′v0, v2=Na2x1K′v1, …, vt=Natx1K′vt-1. The final vertex of the walk is a triple of kind <at(x1),h1(x1,x2,x3),h2(x1,x2,x3)> where pair <,> stands for brackets (,) in the case of even t and parentheses [,] in the case of odd t.We join corresponding coordinates of initial and last vertex of the above symbolic walk by arrowsx1→at(x1), x2→h1(x1,x2,x3), and x3→h2(x1,x2,x3) and obtain the standard form of the transformation of K3 into itself. We use symbol H=Ha1,a2,…,at for the map corresponding to the sequence of colours a1(x1),a2(x1),…,at(x1). Notice that for the computation of this map we use only operations +, −, and × of commutative ring K′.Obviously, affine subspaceU={(a,0,0)∣a∈K} is an invariant subset for the action of H.We can check the following:(A)
In the case of bijective mapx1→a1(x1) the transformation Ha1,a2,…,at is also bijective map.In fact the preimage ofc=H(p1,p2,p3) can be computed fast as the final vertex of the following walk in the graph D(3,K). Let d=p1 be a solution of at(x1)=c1. u0=(c1,c2,c3), u1=Nat-1(d)((u0)), u2=Nat-2(d)((u1)), …, ut-1=Nat(d)((ut-1)), (p1,p2,p3)=Nd(ut-1).(B)
IfK=Zm and at(x1) is chosen as ax1r+b where a∈Zm∗ and gcd(r,ϕ(m))=1 then the map H=Ha1,a2,…,at satisfies the property (ii).LetH(p1,p2,p3)=(c1,c2,c3) and p1∈Zm∗. Then d=p1 can be computed as solution of ax1r+b=c1, i. e. d=(C1-b)s where rs=1mod⁡ϕ(m). The point p can be computed as final vertex of the walk described above.(C)
IfK=Zm and at(x1) is chosen as ax1r+b where a∈Zm∗ and gcd(r,ϕ(m))=1 then the map H=Ha1,a2,…,at satisfies the property (iii).(D)
Ifai(x1)=x1+bi for i=1,2,…,t then H=Ha1,a2,…,at is a bijective cubical map.You can play with “Sage” and check that property (D) holds for instance in the casesk=3,4 and 5.(E)
IfK=Zp where p is prime integer then the map Eb1,b2,b3=Hx1+b1,x1+b2,x1+b3 does not have fixed points if b2≠0, b1≠b3. Let us treat Eb1,b2,b3 as “encryption map” on K3 with the password (b1,b2,b3). Then different passwords produce distinct ciphertext. These properties follow from the fact that the girth (length of minimal cycle) of the graph D(3,Zp) is eight.(F)
Let us consider the encryption mapT1Eb1,b2,b3, where T1 is linear map that sends x1 to x1+x2+x+3 without change of x2 and x3. Then, changing a single character in the plaintext causes changing of vast majority of ciphertext characters. Similarly, changing a single character of the password causes the change of most characters of ciphertext.(G)
Let us consider some nonbijective Eulerian deformations for encryption scheme (F):
(G.1)
Let us takeK=Zm with composite m instead of Zp and H=Ha(x1)+b1,x1+b2,a(x1)+b3 where a(x1)=ax1r, a∈Zm∗, gcd(r,ϕ(m))=1 instead of E=Eb1,b2,b3 and denote this map as rEb1,b2,b3. We consider encryption map E1=E1(b1,b2,b3)=T1rEb1,b2,b3 on the plainspace Δ={(a,0,0)∣a∈K∗}.(G.2)
Let us consider Eulerian mapd(s):(x1,x2,x3)→(bx1s,x2,x3), b∈Zm∗, gcd(s,ϕ(m))=1 and change E1 for E2=T1d(s)E1.(G.3)
Let us consider Eulerian mapD(l,b):(x1,x2,x3)→(cx1l+b,x2,x3), c∈Zm∗, gcd(l,ϕ(m))=1, b∈Zm and consider encryption E3=T1d(s)E1(b1,b2,0)D(l,b3).Assume that ring elementsa,b,c and integers r,s,l are internal parameters of encryption algorithms E1,E2,E3 working with the same plainspace and the same keyspace of tuples (b1,b2,b3). Symbolic computation with “Sage” allows to compare degrees of maps E1,E2,E3. Computer simulations demonstrates the similarity of mixing properties of Ei, i=1,2,3, with mixing properties of E.


## 4. On the Class of Bivariate Graphs

LetK be a commutative ring. We define T(n,K) as a bipartite graph with the set of vertices V(T)=P∪L, P∩L=∅. We call P=Kn a set of points and L=Kn a set of lines (two copies of a Cartesian power of K are used). We will use two types of brackets to distinguish points (p)∈P and lines [l]∈L:(3)p=p1,p2,…,pn∈P,l=l1,l2,…,ln∈L.pi, li (1≤i≤n) are elements of K. We say that vertex (p) (point (p)) is incident with the vertex [l] (line [l]) and we write (p)IT[l], if the following relations between their coordinates hold:(4)p2-l2=e21p1l1p3-l3=e31p1l2+e32l1p2⋮ps-ls=es1p1lis+es2l1pjs⋮pn-ln=en1p1lin+en2l1pjnwhere e21,es1,es2∈{0,1,-1}, 1≤is<s, 1≤js<s. So the incidence relations for graph T=T(n,K) are given by condition (p)IT[l]. The set of edges consists of all pairs {(p),[l]} for which (p)IT[l]. Let us consider the case of finite commutative ring K, with K=k. As it instantly follows from the definition, the order of our bipartite graph is VT=2kn and the number of edges is ET=kn·k=kn+1. Graphs T=T(n,K) are k-regular. In fact, the neighbour of a given point (p) is given by the above equations, where parameters p1,p2,…,pn are fixed elements of the ring and symbols l1,l2,…,ln are variables. It is easy to see that if we set l1 then the choice uniformly establishes values l2,l3…,ln. So each point has precisely k neighbours. In a similar way we observe that the neighbourhood of any line also contains k neighbours. Notice that the order and degree of our graph defined via strings is, js, e21, es1, es2, where s=2,3,…,n, does not depend on the strings.Let us consider some examples.


### 4.1. Wenger GraphsW(n,K)

In 1991 Wenger defined the family of bipartite,p-regular graphs Hn(p), where p is prime number [5]. In [4] Lazebnik and Ustimenko introduced straight forward generalization W(n,q) of these graphs via change of Fp to Fq, where q is a prime power. They used special Lie algebra and proved that the family of bipartite, q-regular graphs W(n,q), n≥2. Graphs W(n,q) are defined for all prime powers and Hn(p)=W(n,p) are defined only for primes.The set of vertices of infinite incidence structure(P,L,I) is V=P∪L and the set of edges E consists of all pairs {(p),[l]} for which (p)I[l]. Bipartite graphs W(n,q) have partition sets Pn (collection of points) and Ln (collection of lines) isomorphic to vector space Fqn, where n∈N+. Let us use the following notations for points and lines in graph W(n,q):(5)p=p1,p2,p3,…,pn∈P,l=l1,,l2,l3,…,ln∈L. The point (p) is incident with the line [l], and we write (p)IW[l], if the following relations between their coordinates hold:(6)li-pi=p1li-1,for 2≤i≤n. The graphs W(n,Fq) have cycles of length 8.One can change finite fieldK for general commutative ring K and work with graph W(n,K).


### 4.2. GraphsA(n,K)

GraphsA(n,K) are formally appearing as tools for the study of D(n,K) properties by V. Ustimenko. Later on the graphs E(n,K) were presented with another name as an independent family A(n,q) for the first time in [6] for cryptographic applications.Let us use the following notations for points and lines in the graphA(n,K):(7)p=p1,p2,p3,…,pn∈P,l=l1,,l2,l3,…,ln∈L. The point (p) is incident with the line [l], and we write (p)IA[l], if the following relations between their coordinates hold:(8)l2-p2=l1p1l3-p3=p1l2l4-p4=l1p3li-pi=p1li-1for  oddili-pi=l1pi-1for  evenifor 3≤i≤n.


### 4.3. GraphsD(n,K)

The following interpretation of a family of graphsD(n,K) in case K=Fq can be found in [4]. By ID we denote the incidence relation for this graph. Let us use the following notations for points and lines:(9)p=p1,p2,p3,…,pn∈P,l=l1,,l2,l3,…,ln∈L. Two types of brackets allow us to distinguish points from lines. Points and lines are elements of two copies of the vector space over K. Point (p) is incident with the line [l], and we write (p)ID[l], if the following relations between their coordinates hold:(10)l2-p2=l1p1l3-p3=p1l2l4-p4=l1p2li-pi=p1li-2forimod⁡4≡2orimod⁡4≡3li-pi=l1pi-2forimod⁡4≡0orimod⁡4≡1where 3≤i≤n.The set of vertices isV=P∪L and the set of edges E consists of all pairs {(p),[l]} for which (p)ID[l]. Bipartite graphs D(n,K) have partition sets P (collection of points) and L (collection of lines) isomorphic to vector space Kn, where n∈N+.


### 4.4. GraphsD(n,K)~

Formal definitions for the family of graphsD(n,K)~ were presented in [7].Construction of projective limits graphs ofD(n,K)~ appears in papers motivated by results on embeddings of Chevalley group geometries in the corresponding Lie algebras and construction of blow-up for an incidence system of Weyl groups. Moreover, this structure is the base for construction of family of graphs D(n,K) (see [7]).Let us use the analogical notations for points and lines in graphD(K)~:(11)p=p1,p2,p3,…,pn∈P,l=l1,,l2,l3,…,ln∈L.In the incidence structure(P,L,I)~ the point (p) is incident with the line [l], and we write (p)ID~[l], if the following relations between their coordinates hold:(12)l2-p2=l1p1l3-p3=p1l2l4-p4=l1p2l5-p5=l1p3-p1l4li-pi=p1li-1forimod⁡3≡0li-pi=l1pi-2forimod⁡3≡1li-pi=l1pi-2-p1li-1forimod⁡3≡2for 3≤i≤n.Graphs from familiesD(n,K) and D(n,K)~ are bipartite, k-regular, where K=k. The girth of graphs from the described families increases with the growth of n. In fact D(n,q) is a family of graphs of large girth and there is a conjecture that D(n,q)~ is another family of graphs of a large girth.All graphs from the considered families arek-regular and bipartite and the set of vertices is V=P∪L, P∩L=∅. They are sparse graphs.It is clear that there is a natural homomorphism ofT(n+1,K) onto T(n,K) of “deleting the last coordinate” that sends (x1,x2,…,xn,xn+1) to (x1,x2,…,xn) and [y1,y2,…,yn,yn+1] to [y1,y2,…,yn]. It means that there is a well-defined projective limit T(K) of graphs T(n,K), n→∞. Bivariate graphs form a special subclass of so calledlinguistic graphs for which natural projective limits are defined in a similar way.Recall that the girthg=g(Γ) of the graph Γ is the length of its minimal cycle.Let us assume that the girthg(n) of graphs T(n,K) is unbounded. The obvious inequality g(n+1)≥g(n) holds. It means that projective limit T(K) has to be a K-regular forest. We have such situation in cases of graphs A(n,Fq) and D(n,Fq). If q≥2 then A(Fq) is a single tree presented by the above equations. Graph D(Fq) is an infinite forest containing infinitely many trees.Projective limitW(Fq) of Wenger graphs is an infinite connected graph containing cycles of length 8.


## 4.1. Wenger GraphsW(n,K)

In 1991 Wenger defined the family of bipartite,p-regular graphs Hn(p), where p is prime number [5]. In [4] Lazebnik and Ustimenko introduced straight forward generalization W(n,q) of these graphs via change of Fp to Fq, where q is a prime power. They used special Lie algebra and proved that the family of bipartite, q-regular graphs W(n,q), n≥2. Graphs W(n,q) are defined for all prime powers and Hn(p)=W(n,p) are defined only for primes.The set of vertices of infinite incidence structure(P,L,I) is V=P∪L and the set of edges E consists of all pairs {(p),[l]} for which (p)I[l]. Bipartite graphs W(n,q) have partition sets Pn (collection of points) and Ln (collection of lines) isomorphic to vector space Fqn, where n∈N+. Let us use the following notations for points and lines in graph W(n,q):(5)p=p1,p2,p3,…,pn∈P,l=l1,,l2,l3,…,ln∈L. The point (p) is incident with the line [l], and we write (p)IW[l], if the following relations between their coordinates hold:(6)li-pi=p1li-1,for 2≤i≤n. The graphs W(n,Fq) have cycles of length 8.One can change finite fieldK for general commutative ring K and work with graph W(n,K).


## 4.2. GraphsA(n,K)

GraphsA(n,K) are formally appearing as tools for the study of D(n,K) properties by V. Ustimenko. Later on the graphs E(n,K) were presented with another name as an independent family A(n,q) for the first time in [6] for cryptographic applications.Let us use the following notations for points and lines in the graphA(n,K):(7)p=p1,p2,p3,…,pn∈P,l=l1,,l2,l3,…,ln∈L. The point (p) is incident with the line [l], and we write (p)IA[l], if the following relations between their coordinates hold:(8)l2-p2=l1p1l3-p3=p1l2l4-p4=l1p3li-pi=p1li-1for  oddili-pi=l1pi-1for  evenifor 3≤i≤n.


## 4.3. GraphsD(n,K)

The following interpretation of a family of graphsD(n,K) in case K=Fq can be found in [4]. By ID we denote the incidence relation for this graph. Let us use the following notations for points and lines:(9)p=p1,p2,p3,…,pn∈P,l=l1,,l2,l3,…,ln∈L. Two types of brackets allow us to distinguish points from lines. Points and lines are elements of two copies of the vector space over K. Point (p) is incident with the line [l], and we write (p)ID[l], if the following relations between their coordinates hold:(10)l2-p2=l1p1l3-p3=p1l2l4-p4=l1p2li-pi=p1li-2forimod⁡4≡2orimod⁡4≡3li-pi=l1pi-2forimod⁡4≡0orimod⁡4≡1where 3≤i≤n.The set of vertices isV=P∪L and the set of edges E consists of all pairs {(p),[l]} for which (p)ID[l]. Bipartite graphs D(n,K) have partition sets P (collection of points) and L (collection of lines) isomorphic to vector space Kn, where n∈N+.


## 4.4. GraphsD(n,K)~

Formal definitions for the family of graphsD(n,K)~ were presented in [7].Construction of projective limits graphs ofD(n,K)~ appears in papers motivated by results on embeddings of Chevalley group geometries in the corresponding Lie algebras and construction of blow-up for an incidence system of Weyl groups. Moreover, this structure is the base for construction of family of graphs D(n,K) (see [7]).Let us use the analogical notations for points and lines in graphD(K)~:(11)p=p1,p2,p3,…,pn∈P,l=l1,,l2,l3,…,ln∈L.In the incidence structure(P,L,I)~ the point (p) is incident with the line [l], and we write (p)ID~[l], if the following relations between their coordinates hold:(12)l2-p2=l1p1l3-p3=p1l2l4-p4=l1p2l5-p5=l1p3-p1l4li-pi=p1li-1forimod⁡3≡0li-pi=l1pi-2forimod⁡3≡1li-pi=l1pi-2-p1li-1forimod⁡3≡2for 3≤i≤n.Graphs from familiesD(n,K) and D(n,K)~ are bipartite, k-regular, where K=k. The girth of graphs from the described families increases with the growth of n. In fact D(n,q) is a family of graphs of large girth and there is a conjecture that D(n,q)~ is another family of graphs of a large girth.All graphs from the considered families arek-regular and bipartite and the set of vertices is V=P∪L, P∩L=∅. They are sparse graphs.It is clear that there is a natural homomorphism ofT(n+1,K) onto T(n,K) of “deleting the last coordinate” that sends (x1,x2,…,xn,xn+1) to (x1,x2,…,xn) and [y1,y2,…,yn,yn+1] to [y1,y2,…,yn]. It means that there is a well-defined projective limit T(K) of graphs T(n,K), n→∞. Bivariate graphs form a special subclass of so calledlinguistic graphs for which natural projective limits are defined in a similar way.Recall that the girthg=g(Γ) of the graph Γ is the length of its minimal cycle.Let us assume that the girthg(n) of graphs T(n,K) is unbounded. The obvious inequality g(n+1)≥g(n) holds. It means that projective limit T(K) has to be a K-regular forest. We have such situation in cases of graphs A(n,Fq) and D(n,Fq). If q≥2 then A(Fq) is a single tree presented by the above equations. Graph D(Fq) is an infinite forest containing infinitely many trees.Projective limitW(Fq) of Wenger graphs is an infinite connected graph containing cycles of length 8.


## 5. General Encryption Algorithm No. 1

We can convert graphT(n,K) to finite automaton in the following way. Let v=(v1,v2,v3,v4,…,vn)∈V(T(n,K)) (or v=[v1,v2,v3,v4,…,vn]∈V(T(n,K))) and Nα(v) be the operator of taking neighbour of vertex v where the first coordinate is α:(13)Nαv1,v2,v3,v4,…,vn→α,∗,∗,∗,…,∗,Nαv1,v2,v3,v4,…,vn→α,∗,∗,∗,…,∗, where α∈K. The remaining coordinates can be determined uniquely using relations describing the chosen graph T(n,K).We convertT(n,K) to finite automaton via joining v an Nα(v) by directed arrow with weight α. We assume that all vertices of the graph are accepting states.A bit more interesting object is a symbolic bivariate automaton. Leta(x)=(α1(x),α2(x),…,αs(x)) be a string of elements from K[x] (totality of polynomials in variable x with coefficients from K).We introduce operatorNa(x)s(v), where v is a point or a line with coordinates v1,v2,…,vn, of taking the last vertex u of the path v, v1=Nα1(v1)(v), v2=Nα2(v1)(v1), …, vs=Nαs(v1)(vs-1)=u.We refer toNa(x)s as a computation of the symbolic automaton with the string(14)ax=α1x,α2x,…,αsxαi∈K[x], i=1,…,s, and initial state v=(v1,v2,v3,v4,…,vn)∈T(n,K) (or v=[v1,v2,v3,v4,…,vn]∈T(n,K)). We can consider Fs(v)=Na(v1)s(v) as a map on P∪L.It is easy to see that the restriction of this map onP is a polynomial transformation of P=Kn into P (parameter s is even) or L (parameter s is odd) of kind (15)x1→f1x1,x2,…,xn,x2→f2x1,x2,…,xn,⋮xn→fnx1,x2,…,xn.Notice that generallyFs is not a bijection. Let us consider an invertibility condition for Fs.Proposition 1.
Let the equations of kindαs(x)=b, b∈K have exactly one solution. Then map Fs is invertible.Proof.
It is easy to check that ifFs(x¯)=y¯ then Fs-1(y¯)=x¯. It is easy to see that f1(x1,x2,…,xn)=αs(x1). Let p be some point from Pn and Fn(p)=(c1,c2,…,cn) (point or line). Then the equation αs(x1)=c1 has a unique solution η. So we can compute η1=α1(η), η2=α2(η), …, ηs-1=αs-1(η).
We can compute the chainc=(c1,c2,…,cn), Nηs-1(c)=c1, Nηs-2(c1)=c2, …, Nη1(cs-2)=cs-1, Nη((cs-1))=cs=(p1,p2,…,pn) with η=p1. So Fn is a bijection.Notice thatNa(x)s for a(x) of kind α1(x)=β1(x), α2(x)=β2(α1(x)), α3=β3(α2(x)), …, αs(x)=βs(αs-1(x)) is a composition of N1β1(x), N1β2(x), …, N1βs(x). In this case invertibility of each βi(x), i=1,2,…,s, guarantees the bijectivity of Na(x)s. We refer to such case asrecurrently defined string.LetL1 and L2 be sparse affine bijective transformation of the affine space (free module in other terminology) Kn(16)L1=TA,b:x¯→x¯A+b,L2=TC,d:x¯→x¯C+d,where A=ai,j and C=ci,j are n×n matrices with ai,j,ci,j∈K. It is clear that (17)L1-1=TA,b-1=TA-1,-bA-1,L2-1=TC,d-1=TC-1,-dC-1.LetFn be a polynomial map of Kn to itself. We refer to Gn=L1FnL2 asaffine deformation of Fn.


### 5.1. Symmetric Cipher No. 1

We can use the data on the graphT(n,K), the symbolic computation given by the string a=a(x) of polynomials α1(x), α2(x), …, αs(x), where αs(x) is a bijective map of K to itself and affine transformations L1 and L2 in the following encryption scheme.Correspondents Alice and Bob agree on a private encryption key(18)Kp=L1,L2,α=α1,α2,…,αs, and keep the key in secret. Messages are written using characters from the alphabet K. So the plainspace is Kn and its elements must be treated as points (or lines) of the graph. To encrypt they use the composition(19)L1∘Nas∘L2. Notice that the computation has to be executed in numerical level:(1)
Correspondent Alice writes plaintextp=(p1,p2,…,pn) and computes(20)L1p=v1,v2,…,vn=vand treatsv as point of the bivariate graph T(n,K).(2)
She computes parametersμi=αi(v1) for i=1,2,…,s.(3)
She computesp0 as L1(p), p1 as Nμ1(p0), p2 as Nμ2(p1), …, ps as Nμs(ps-1).(4)
She computes the ciphertextc as L2(ps).Alice and Bob can use their knowledge about triple (L1, L2, a) for the decryption. Let us assume that Bob receives the ciphertext c from Alice. To decrypt the ciphertext Bob proceeds as follows:(1)
He has to computec0 as L2-1(c).(2)
He treats the string of coordinates of this tuple as a vertex of the graph, which is a point in case of evens or the line in case of odd s with coordinates c10, c20, …, cn0.(3)
Bob must find a solutionη of αs(x)=c10 and form a string η0=η, η1=α1(η), η2=α2(η), …, ηs-1=αs-1(η).(4)
He computesc1 as Nηs-1(c0), c2 as Nηs-2(c1), …, cs as Nη0(cs-1).(5)
He computes the plaintextp as L1-1(cs).Remark 2.
In the case of identity mapsL1 and L2 one can try Dijkstra’s algorithm for finding the shortest path between plaintext and ciphertext. Notice that its complexity is O(vlog⁡v), but here v is exponential qn. Therefore we get worse complexity even than brute force search via the key space.In the case of recurrently defined symbolic computation as above the encryption bijective map isFs=L1N1β1(x)N1β1(x)…N1βs(x)L2. As we already see, this encryption transformation is equivalent to L1Nsa(x)L2, where a(x)=(β1(x),β2(β1(x)),…,βs(βs-1(…(β1(x))))). Recurrently defined symbolic computation is an example of the polynomial map with an invertible decomposition. It has various applications in the development of multivariate key exchange protocols and asymmetric multivariate algorithm. The most popular case of implementation is related to graphs D(n,K) and A(n,K) (see [15, 17, 18]), where K is a finite field of arithmetical rings Zm and strings of kind β1=x+d1, β2=x+d2, …, βs=x+ds, where di+di+1, i=1,2,…,s-2 are regular elements of the ring K. We refer to such case as shifting encryption.Let us consider the case of strong symmetric encryption, when the function isαs(x)=ax+b, with a regular (invertible) element of K. In this case it is easy to show that degrees of encryption map Fn and decryption map Fn-1 are the same. The advantage of this case is its universality. One can implement it in case of arbitrary chosen finite ring K.


## 5.1. Symmetric Cipher No. 1

We can use the data on the graphT(n,K), the symbolic computation given by the string a=a(x) of polynomials α1(x), α2(x), …, αs(x), where αs(x) is a bijective map of K to itself and affine transformations L1 and L2 in the following encryption scheme.Correspondents Alice and Bob agree on a private encryption key(18)Kp=L1,L2,α=α1,α2,…,αs, and keep the key in secret. Messages are written using characters from the alphabet K. So the plainspace is Kn and its elements must be treated as points (or lines) of the graph. To encrypt they use the composition(19)L1∘Nas∘L2. Notice that the computation has to be executed in numerical level:(1)
Correspondent Alice writes plaintextp=(p1,p2,…,pn) and computes(20)L1p=v1,v2,…,vn=vand treatsv as point of the bivariate graph T(n,K).(2)
She computes parametersμi=αi(v1) for i=1,2,…,s.(3)
She computesp0 as L1(p), p1 as Nμ1(p0), p2 as Nμ2(p1), …, ps as Nμs(ps-1).(4)
She computes the ciphertextc as L2(ps).Alice and Bob can use their knowledge about triple (L1, L2, a) for the decryption. Let us assume that Bob receives the ciphertext c from Alice. To decrypt the ciphertext Bob proceeds as follows:(1)
He has to computec0 as L2-1(c).(2)
He treats the string of coordinates of this tuple as a vertex of the graph, which is a point in case of evens or the line in case of odd s with coordinates c10, c20, …, cn0.(3)
Bob must find a solutionη of αs(x)=c10 and form a string η0=η, η1=α1(η), η2=α2(η), …, ηs-1=αs-1(η).(4)
He computesc1 as Nηs-1(c0), c2 as Nηs-2(c1), …, cs as Nη0(cs-1).(5)
He computes the plaintextp as L1-1(cs).Remark 2.
In the case of identity mapsL1 and L2 one can try Dijkstra’s algorithm for finding the shortest path between plaintext and ciphertext. Notice that its complexity is O(vlog⁡v), but here v is exponential qn. Therefore we get worse complexity even than brute force search via the key space.In the case of recurrently defined symbolic computation as above the encryption bijective map isFs=L1N1β1(x)N1β1(x)…N1βs(x)L2. As we already see, this encryption transformation is equivalent to L1Nsa(x)L2, where a(x)=(β1(x),β2(β1(x)),…,βs(βs-1(…(β1(x))))). Recurrently defined symbolic computation is an example of the polynomial map with an invertible decomposition. It has various applications in the development of multivariate key exchange protocols and asymmetric multivariate algorithm. The most popular case of implementation is related to graphs D(n,K) and A(n,K) (see [15, 17, 18]), where K is a finite field of arithmetical rings Zm and strings of kind β1=x+d1, β2=x+d2, …, βs=x+ds, where di+di+1, i=1,2,…,s-2 are regular elements of the ring K. We refer to such case as shifting encryption.Let us consider the case of strong symmetric encryption, when the function isαs(x)=ax+b, with a regular (invertible) element of K. In this case it is easy to show that degrees of encryption map Fn and decryption map Fn-1 are the same. The advantage of this case is its universality. One can implement it in case of arbitrary chosen finite ring K.


## 6. On Properties of Bivariate Graph Based Bijective Encryption Maps

The girthG of simple graph G is the length of its shortest cycle. It is a known fact that the girth of the graph D(n,Fq) is ≥n+5. So in the case of shifting encryption the map with the password x+d1, x+d2, …, x+ds, s<n+5 the encryption map Fn has no fixed points. So ciphertext is always different from the plaintext. Let us consider deformed shifting encryption of kind τLFnτR. We assume that affine maps τL and τR are fixed. Correspondents are able to change string d1,d2,…,ds for another one.We assume thatdi+di+1≠0 for i=1,2,…,s-2. Such choice means that encryption map corresponds to the path of length s. The inequality g(D(n,q))≥n+5 implies that different strings of length s<(n+5)/2 produce different ciphertexts. So even in the case when τL and τR are known to adversary the complexity of attacks without an access to unencrypted information is bounded from below by q(n+5)/2.LetM be a multiplicative subset of general commutative ring K, i.e., M is closed under the ring multiplication and it does not contain 0. We say that a string d1,d2,…,ds is M-regular if di+di+1∈M for i=1,2,…,s-2. It was proven that different M-regular strings of length s<(n+5)/2 produce distinct ciphertexts from the same plaintext. So in the case of K=k, M=m the resistance to attacks without access to unencrypted data is bounded from below by mk(n+5)/2-1.It was proven that graphsA(n,Fq) form a family of graphs of increasing girth h(n) that tends to infinity as n grows. The speed of growth of h(n) needs further evaluation. It was proven also that different M-regular strings of length s<n produce different encryption maps.Results onM-regular strings of length restricted maps are obtained in terms of dynamical systems corresponding to graphs D(n,K) and A(n,K).Let us assume that mapsτL and τR are identities and consider the groups of transformations GD(n,K) and GA(n,K) generated by shifting encryption maps corresponding to strings of even length. In [16] it was proven that all elements of GD(n,K) are cubical transformations of affine spaces Pn and Ln. Similar result for GA(n,K) is stated in [6]. As it follows instantly from this result transformation Fn′=τLFnτR and its inverse are cubical transformations.The cryptanalytic corollary of this statement is justification of linearization attacks on stream ciphers corresponding to stream ciphers based on graphsD(n,K) and A(n,K).Let correspondents use the transformationFn′. The adversary has knowledge on the general scheme of open algorithm but not on the data for τL and τR or on the shifting string. So he knows about cubic nature of encryption. We assume that he has access to the unencrypted information and is able to intercept quite many pairs of kind (p,c), where p is plaintext and c corresponding ciphertext.Then adversary writesGn, which is a formal cubical map in standard form with the unknown coefficients in front of monomial terms. He or she is able to solve system of O(n3) equations of kind Gn(c)=p and restore the map Gn. So adversary could control the communication channel. The complexity of such direct linearization attack is O(n10).


## 7. On the Implementation of Graph Based Stream Cipher Based on Nonbijective Maps

Let us describe an implemented algorithm, which can run in the case of arbitrary commutative ringK and arbitrary bivariate graph T(n,K). We slightly modify the above described symmetric algorithm based on bivariate graphs T(n,K) which is not a case of shifting encryption. Firstly, we take a symbolic computation for string a=a(x)=(α1(x),α2(x),…,αs(x)), with αi(x)=xd+ds, i=1,2,…,s where d is mutually prime with the order of K∗. So equation xd+ds=c, x∈K∗ has at most one solution. We take L1 as an affine bijective transformation of kind x1→x1+x2+⋯+xn, x2→l2(x1,x2,…,xn), x3→l3(x1,x2,…,xn), …, xn→ln(x1,x2,…,xn), where li are linear functions from K[x1,x2,…,xn]. Correspondents will use the plainspace (21)Ω=x1,x2,…,xn∣x1+x2+⋯+xn∈K∗,xi∈K,i=1,2,…,n.They will useL1Na(x)sL2 as encryption map. To execute computation in time O(n) they take finite parameter s and use loaded tables for αi(x), i=1,2,…,s (one-dimensional arrays ai(x), x∈K∗). So they will compute L1(p)=v=(v1,v2,…,vn), form sequence μi=αi(v1), i=1,2,…,s and compute recurrently vi=Nμi(vi-1), i=1,2,…,s. They form the ciphertext c as L2(vs).To decrypt they will takec0=(c10,c20,…,cn0) as L2-1(c) and find a solution η for the equation xd+ds=c10. Loaded table of values for αs-1 will allow to find η fast. Next they form a string η0=η, η1=α1(η), η2=α2(η), …, ηs-1=αs-1(η). So users take string c1=Nηs-1(c0), c2=Nηs-2(c1), …, cs=Nη0(cs-1). Finally they get plaintext as L-1(cs).The case of this symmetric algorithm appears as a private key for a cryptosystem introduced in [14] with the plainspace Zmn.We selected string of polynomials asαi=xd+di, di∈K, i=1,2,…,s and special linear transformations L1 and L2, given by the lists of linear forms.We can theoretically evaluate degrees of encryptiondenc and decryption ddec. In cases of graphs D(n,K) and A(n,K), these parameters are bounded below by some constants depending from parameters αi, i=1,2,…,s. We can select string of parameters and get ddec large enough to make cryptanalysis a difficult task. In case D(n,K)~ the degrees are even larger; they have size O(n). Notice that direct linearization attacks are formally impossible because the encryption map is not a bijective one.The implementation of the algorithms in the present work was done using the Python programming language, in particular version 2.7. The code does not use any out-of-the-box libraries for facilitating operations with matrices. The tests for measuring the processing time have been executed on a machine with Intel Core2 Duo CPU 9600 1.60GHz x 2, RAM memory 4.8 GB, operating with Ubuntu 16.04 LTS. The complexity of the algorithms is of orderO(sn), where s is the length of the password. In particular, we implemented this stream cipher for the case K=Z256 and αi(x)=x3+di (d=3 and ddec=43), i=1,2,…,s without using loaded tables for functions. Table 1 represents encoding and decoding time for three types of graphs and for different files size and length of passwords. A description of the implementation of “nonlinear part” of encryption process; i.e., computation of Nas is given in [1]. We recommend a password for which d2 and di-di+2, i=1,2,…,s-2 are regular elements of the ring.


## 8. General Encryption Algorithm No. 2 with the Usage of Nonlinear Colour Jump Function

We generalize Encryption Algorithm No. 1 for creation of multivariate transformation ofKn based on the bivariate graph T(n,K) and its extension over K[x1,x2,…,xn].The extension of graphT(n,K) is T(n,K[x1,x2,…,xn]), which has two partition sets P (points) and L (lines) isomorphic to (K[x1,x2,…,xn])n. In this infinite graph the incidence relation I are given by the same equation as in the graph T(n,K) but over the ring K[x1,x2,…,xn].Let us consider a special vertex of the graphT(n,K[x1,x2,…,xn]) kind (x1,x2,…,xn), where xi, i=1,…,n, are generations of K[x1,x2,…,xn] over K. We usethe colour jump operator, which transforms point (x1,x2,…,xn) to point (g(x1),x2,…,xn) from T(n,K[x1,x2,…,xn]).We createthe jump fusionFsΞ:Kn→Kn of nonlinear colour jump operator Ξg with modification previously defined Fs in the following way:(1) First step, we useΞg to point x:(22)x=x1,x2,x3…,xn→Ξgx1,x2…,xn=gx1,x2,x3,…,xn=x′wemakeajump and we treat x′ as the point of the graph T(n,K[x1,x2,…,xn]).(2) In the next steps of jump fusion, we modifiedFs differently in the cases of even and odd parameter s(2.1) Ifs=2r+1, we use symbolic key defined by polynomials α1(x1), α2(x1)=β1(g(x1)), α3(x1), α4(x1)=β2(g(x1)), …, α2r(x1)=βr(g(x1)), α2r+1(x1), where αi,βi∈K[x] and α2r+1 is a bijection.(2.2) Ifs=2r, we use symbolic key defined by polynomials α1(x1), α2(x1)=β1(g(x1)), α3(x1), α4(x1)=β2(g(x1)), …, α2r(x1)=βr(g(x1)), where αi,βi∈K[x] and α2r is a bijection.(3) We form a path in the graphT(n,K[x1,x2,…,xn]) of(23)x′Iv1Iv2I…Ivs, where ρ(vi)=αi(x1), i=1,2,…,s.(4) Final vertex of the path is(24)vs=αsx1,h2,h2,…,hn, where hi=K[x1,x2,…,xn].The jump fusionFsΞ is the map(25)x1→αsx1,x2→h2x1,x2,…,xn,⋮xn→hnx1,x2,…,xn.If the jump is trivial, i.e.,Ξg(x1,x2…,xn)=(x1,x2,x3,…,xn)=x then FsΞ=Fs.In the case of affine deformation ofFnΞ by affine bijective transformation L1 and L2 of Kn our map (26)x1→w1x1,x2,…,xn,x2→w2x1,x2,…,xn,⋮xn→wnx1,x2,…,xn,where wi∈K[x1,x2,x3,…,xn].


### 8.1. Symmetric Cipher No. 2 with the Jump Operator

LetT(n,K) be bivariate graph with partition sets P (points) and L (lines) isomorphic to Kn. We considerthe colour jump operatorΞg, g∈K[x] in the set if points P, which transforms (x1,x2,…,xn) to point (g(x1),x2,…,xn).Let us modify Symmetric Cipher No. 1 in the following way. The correspondents Alice and Bob use the data on the graphT(n,K), with the colour jump operator Ξg, the symbolic computation given by the string a=a(x) of polynomials α1(x), α2(x), …, αs(x), where αs(x) is a bijective map of K to itself and affine transformations L1 and L2 in the following encryption scheme.Thus, correspondents Alice and Bob agree on the private encryption key(27)Kp=L1,L2,Ξg,ag=α1,α2,…,αs, where polynomials α1(x), α2(x), …, αs(x) are defined differently depending on the length of the password s, i.e., (i)
ifs=2r+1 then μ1=α1(x), μ2=α2(x)=β1(g(x)), μ3=α3(x), μ4=α4(x)=β2(g(x)), …, μ2r=α2r(x)=βr(g(x)), μ2r+1=α2r+1(x) and αi,βi∈K[x],(ii)
ifs=2r then μ1=α1(x), μ2=α2(x)=β1(g(x)), μ3=α3(x), μ4=α4(x)=β2(g(x)), …, μ2r-1=α2r-1(x)μ2r=α2r(x)=βr(g(x)), and αi,βi∈K[x]Notice that the computation has to be executed in numerical level also in this scheme:(1)
Correspondent Alice writes plaintextp=(p1,p2,…,pn)∈Ω and computes(28)L1p=v1,v2,…,vn=v.(2)
In the next step she uses the colour jump operator and computes(29)Ξgv=gv1,v2,…,vn=v′and treatsv′ as point of the bivariate graph T(n,K).(3)
She computes parametersμi=αi(v1) for i=1,2,…,s with properly defined αi.(4)
She computesp1 as Nμ1(v′), p2 as Nμ2(p1), …, ps as Nμs(ps-1).(5)
Finally, she computes the ciphertextc as L2(ps).Alice and Bob can use knowledge about their private key (L1, L2, Ξg, ag) for the decryption.Let us assume that Bob receives the ciphertextc from Alice. To decrypt the ciphertext Bob proceeds as follows:(1)
He has to computec0 as L2-1(c).(2)
He treats the string of coordinates of this tuple as a vertex of the graph, which is a point in case of evens or the line in case of odd s with coordinates c10, c20, …, cn0.(3)
Bob must find a solutionη of αs(x)=c10 and form a string η0=g(η), η1=α1(η), η2=α2(η), …, ηs-1=αs-1(η).(4)
He computesc1 as Nηs-1(c0), c2 as Nηs-2(c1), …, cs as Nη0(cs-1)=(c0s,c1s,c2s,…,cns).(5)
Next, he computes(30)Ξ-1cs=η,c1s,c2s,…,cns=cs′.(6)
Finally, he computes the plaintextp as L1-1(cs′).


## 8.1. Symmetric Cipher No. 2 with the Jump Operator

LetT(n,K) be bivariate graph with partition sets P (points) and L (lines) isomorphic to Kn. We considerthe colour jump operatorΞg, g∈K[x] in the set if points P, which transforms (x1,x2,…,xn) to point (g(x1),x2,…,xn).Let us modify Symmetric Cipher No. 1 in the following way. The correspondents Alice and Bob use the data on the graphT(n,K), with the colour jump operator Ξg, the symbolic computation given by the string a=a(x) of polynomials α1(x), α2(x), …, αs(x), where αs(x) is a bijective map of K to itself and affine transformations L1 and L2 in the following encryption scheme.Thus, correspondents Alice and Bob agree on the private encryption key(27)Kp=L1,L2,Ξg,ag=α1,α2,…,αs, where polynomials α1(x), α2(x), …, αs(x) are defined differently depending on the length of the password s, i.e., (i)
ifs=2r+1 then μ1=α1(x), μ2=α2(x)=β1(g(x)), μ3=α3(x), μ4=α4(x)=β2(g(x)), …, μ2r=α2r(x)=βr(g(x)), μ2r+1=α2r+1(x) and αi,βi∈K[x],(ii)
ifs=2r then μ1=α1(x), μ2=α2(x)=β1(g(x)), μ3=α3(x), μ4=α4(x)=β2(g(x)), …, μ2r-1=α2r-1(x)μ2r=α2r(x)=βr(g(x)), and αi,βi∈K[x]Notice that the computation has to be executed in numerical level also in this scheme:(1)
Correspondent Alice writes plaintextp=(p1,p2,…,pn)∈Ω and computes(28)L1p=v1,v2,…,vn=v.(2)
In the next step she uses the colour jump operator and computes(29)Ξgv=gv1,v2,…,vn=v′and treatsv′ as point of the bivariate graph T(n,K).(3)
She computes parametersμi=αi(v1) for i=1,2,…,s with properly defined αi.(4)
She computesp1 as Nμ1(v′), p2 as Nμ2(p1), …, ps as Nμs(ps-1).(5)
Finally, she computes the ciphertextc as L2(ps).Alice and Bob can use knowledge about their private key (L1, L2, Ξg, ag) for the decryption.Let us assume that Bob receives the ciphertextc from Alice. To decrypt the ciphertext Bob proceeds as follows:(1)
He has to computec0 as L2-1(c).(2)
He treats the string of coordinates of this tuple as a vertex of the graph, which is a point in case of evens or the line in case of odd s with coordinates c10, c20, …, cn0.(3)
Bob must find a solutionη of αs(x)=c10 and form a string η0=g(η), η1=α1(η), η2=α2(η), …, ηs-1=αs-1(η).(4)
He computesc1 as Nηs-1(c0), c2 as Nηs-2(c1), …, cs as Nη0(cs-1)=(c0s,c1s,c2s,…,cns).(5)
Next, he computes(30)Ξ-1cs=η,c1s,c2s,…,cns=cs′.(6)
Finally, he computes the plaintextp as L1-1(cs′).


## 9. On the Implementation of Graph Based Stream Cipher Based on Nonbijective Maps with the Use of Nonlinear Colour Jump Operator

In this section we describe an implementation of general Encryption Algorithm No. 2 with the use of nonlinear colour jump functionΞg in the case of rings K=Zm and K=Fq and graph T(n,K).We take a bijective transformationx1→x1+x2+x3+⋯+xs, xi→li(x1,x2,…,xn) (i=1,2,…,n), which is computable in time O(n). For example linear forms l2=x2+x3+⋯+xn, l3=x3+x4+⋯+xn, …, ln=xn can be chosen. We select L2 as bijective affine transformation computable in time O(n).


### 9.1. Case I: Lets Be an Odd Number s=2r+1

To define jump of the colour correspondents can take an arbitraryg∈K[x]. The value of g on given element of commutative ring is computable for O(n) elementary steps. According to the point (2.1) in Section 8, they select α1(x) as axd+d1, α3(x) as axd+d3, …, αs(x)=axd+ds, β1(x)=x+b1, β2(x)=x+b2, …, βr(x)=x+br, where gcd(d,ϕ(m))=1 for K=Zm and gcd(d,q-1)=1 for K=Fq. Correspondents are working with the plainspace Ω={x∣x1+x2+⋯+xn∈K∗} in the case K=Zm and Fqn in which the encryption map is a bijection. We assume that parameters a, di-di-2, bi-bi-1 are regular ring elements.Decryption. Correspondent Bob takes obtained ciphertext c and computes L2-1(c)=[c10,c20,…,cn]=c0. He solves the equation ayd+d2r+1=c10 in unknown y. Let η be the solution. Bob computes η1=α1(η), η2=β1(g(η)), …, η2r-1=α2r-1(η), ηs-1=η2r=βr(g(η)).He forms the pathc0, Nη2r(c0)=c1, Nη2r-1(c1)=c2, …, Nη1(c2r-1)=c2r, Ng(η)(c2r)=c2r+1=(c1s,c2s,…,cns) with c1s=g(η) and next he uses jump operator Ξg(cs)=(η,c2s,…,cns)=cs′. Finally Bob computes the plaintext as L1-1(cs′).


### 9.2. Case II: Lets Be an Even Number s=2r

Correspondents takeg(x)=txe+o to conduct jump operator Ξg, where gcd(e,ϕ(m))=1 for K=Zm and gcd(e,q-1)=1 for K=Fq and t is regular element of K. They select α1(x)=f(x), where f(x) is an arbitrary element of K[x] of degree d, e.g., f(x)=axd. They work also with α2i-1(x)=f(x)+di, i=1,2,…,r and α2i(x)=x+bi, i=1,2,…,r (see the point (2.2) in Section 8). Similarly to previous case, parameters t, di-di-1, bi-bi-1 are regular ring elements.Decryption. Correspondent Bob takes obtained ciphertext c and computes L2-1=[c10,c20,…,cn0]=c0. He solves the equation tye+o+dr=c10. Let η be the solution. He computes η1=f(η), η2=α2(g(η)), a3=f(w)+b1, a4=α4(g(η)), …, η2r-1=f(η)+br.Bob computes the pathc0, Nη2r-1(c0)=c1, Nη2r-2(c1)=c2, …, Nη1(c2r-1)=c2r-2, Ng(η)(c2r-2)=c2r-1, and next he uses the jump operator Ξg(cs)=(η,c2s,…,cns)=cs′. Finally Bob computes the plaintext as L1-1(cs′).Example 3.
Let s=3 (case I). Correspondents will use the plainspace(31)Ω=x1,x2,x3,x4∣x1+x2+x3+x4∈F11∗,xi∈F11,i=1,2,3,4 and private encryption key(32)Kp=L1,L2,Ξgx=gx1,x2,x3,x4,ag=α1,α2,α3, where g(x)=x3+x+1, α1(x)=3x3+2, α2=β1(g(x)) with β1(x)=x+1 and α3(x)=3x3+5. Notice that ϕ(11)=10, gcd(3,10)=1, and d3-d1=5-2=3 is regular element. Let(33)L1x1,x2,x3,x4=x1+x2+x3+x4,x2+x3+x4,x3+x4,x4 and L2 be an identity map. Let us use graph D(4,F11) and users should do all calculations in modular arithmetic defined for F11. (1)
Alice writes plaintextp=(1,2,5,0) (p∈Ω since gcd(1+2+5+0,11)=1) and computes L1(p)=L1(1,2,5,0)=(8,7,5,0)=(v1,v2,v3,v4)=v.(2)
She computesg(v1)=g(8)=83+8+1=4 and(34)Ξgv=gv1,v2,v3,v4=4,7,5,0=v′.(3)
μ1=α1(v1)=α1(8)=3·83+2=9, μ2=α2(v1)=β1(g(v1))=β1(g(8))=β1(4)=4+1=5 and μ3=α3(8)=3·83+5=1.(4)
She getsv′=(4,7,5,0)→Nμ1(v′)=[9,10,1,8]=p1→Nμ2(p1)=(5,9,6,4)=p2→Nμ3(p2)=[1,3,10,2]=p3.(5)
Finally,L2(p3)=L2([1,3,10,2])=[1,3,10,2]=c is the ciphertext.
Bob knows the keyKp and the encryption scheme. Bob can decrypt the ciphertext c=[1,3,10,2] in the following steps: (1)
He computesL2-1(c)=L2-1([1,3,10,2])=[1,3,10,2]=[c10,c20,c30,c40]=c0.(2)
s is odd and Bob treats [1,3,10,2] as a vertex (line) in the graph D(4,F11).(3)
He writes the equation3x3+5=c10 and then rewrites it as 3x3=c10-5 (3, x are regular; left side is from F11∗ so c1-5 has to be regular). He writes x3=(1-5)·3-1 (regular) and uses the Euler theorem to find d (a multiplicative inverse of 3mod⁡ϕ(11), i.e., 7).Thenη=[(1-5)3-1]7=[7·4]7=67=8 is the unique solution. He forms a string of elements η0=g(η)=g(8)=4, η1=α1(η)=9 and η2=α2(η)=5.(4)
He getsc0=[1,3,10,2]→Nη2(c0)(5,9,6,4)→Nη1(c0)[9,10,1,8]=c2→,Nη0(c2)=(4,7,5,0)=(c13,c23,c33)=c3.(5)
He computes(35)Ξg-1c3=η,c23,c33=8,7,5,0=c3′(6)
Finally, he computes the plaintextp=L1-1(c3′)=(1,2,5,0).


### 9.3. Degree Estimates

In the casesT(n,K)=W(n,K) and T(n,K)=D~(n,K) the implementations of Algorithm No. 1 and Algorithm No. 2 use encryption map of degree O(n).The encryption and decryption map have multivariate nature. Let us assume thatdeg⁡(g) (odd s) and deg⁡(f) (even s) are given by linear function of kind cn+b, c>0. Then in the case of graphs D(n,K) and A(n,K) the degrees of encryption and decryption maps are bounded below by cn+b+2 and bounded above by 3(cn+b) because the shifting encryption is a cubical map.


## 9.1. Case I: Lets Be an Odd Number s=2r+1

To define jump of the colour correspondents can take an arbitraryg∈K[x]. The value of g on given element of commutative ring is computable for O(n) elementary steps. According to the point (2.1) in Section 8, they select α1(x) as axd+d1, α3(x) as axd+d3, …, αs(x)=axd+ds, β1(x)=x+b1, β2(x)=x+b2, …, βr(x)=x+br, where gcd(d,ϕ(m))=1 for K=Zm and gcd(d,q-1)=1 for K=Fq. Correspondents are working with the plainspace Ω={x∣x1+x2+⋯+xn∈K∗} in the case K=Zm and Fqn in which the encryption map is a bijection. We assume that parameters a, di-di-2, bi-bi-1 are regular ring elements.Decryption. Correspondent Bob takes obtained ciphertext c and computes L2-1(c)=[c10,c20,…,cn]=c0. He solves the equation ayd+d2r+1=c10 in unknown y. Let η be the solution. Bob computes η1=α1(η), η2=β1(g(η)), …, η2r-1=α2r-1(η), ηs-1=η2r=βr(g(η)).He forms the pathc0, Nη2r(c0)=c1, Nη2r-1(c1)=c2, …, Nη1(c2r-1)=c2r, Ng(η)(c2r)=c2r+1=(c1s,c2s,…,cns) with c1s=g(η) and next he uses jump operator Ξg(cs)=(η,c2s,…,cns)=cs′. Finally Bob computes the plaintext as L1-1(cs′).


## 9.2. Case II: Lets Be an Even Number s=2r

Correspondents takeg(x)=txe+o to conduct jump operator Ξg, where gcd(e,ϕ(m))=1 for K=Zm and gcd(e,q-1)=1 for K=Fq and t is regular element of K. They select α1(x)=f(x), where f(x) is an arbitrary element of K[x] of degree d, e.g., f(x)=axd. They work also with α2i-1(x)=f(x)+di, i=1,2,…,r and α2i(x)=x+bi, i=1,2,…,r (see the point (2.2) in Section 8). Similarly to previous case, parameters t, di-di-1, bi-bi-1 are regular ring elements.Decryption. Correspondent Bob takes obtained ciphertext c and computes L2-1=[c10,c20,…,cn0]=c0. He solves the equation tye+o+dr=c10. Let η be the solution. He computes η1=f(η), η2=α2(g(η)), a3=f(w)+b1, a4=α4(g(η)), …, η2r-1=f(η)+br.Bob computes the pathc0, Nη2r-1(c0)=c1, Nη2r-2(c1)=c2, …, Nη1(c2r-1)=c2r-2, Ng(η)(c2r-2)=c2r-1, and next he uses the jump operator Ξg(cs)=(η,c2s,…,cns)=cs′. Finally Bob computes the plaintext as L1-1(cs′).Example 3.
Let s=3 (case I). Correspondents will use the plainspace(31)Ω=x1,x2,x3,x4∣x1+x2+x3+x4∈F11∗,xi∈F11,i=1,2,3,4 and private encryption key(32)Kp=L1,L2,Ξgx=gx1,x2,x3,x4,ag=α1,α2,α3, where g(x)=x3+x+1, α1(x)=3x3+2, α2=β1(g(x)) with β1(x)=x+1 and α3(x)=3x3+5. Notice that ϕ(11)=10, gcd(3,10)=1, and d3-d1=5-2=3 is regular element. Let(33)L1x1,x2,x3,x4=x1+x2+x3+x4,x2+x3+x4,x3+x4,x4 and L2 be an identity map. Let us use graph D(4,F11) and users should do all calculations in modular arithmetic defined for F11. (1)
Alice writes plaintextp=(1,2,5,0) (p∈Ω since gcd(1+2+5+0,11)=1) and computes L1(p)=L1(1,2,5,0)=(8,7,5,0)=(v1,v2,v3,v4)=v.(2)
She computesg(v1)=g(8)=83+8+1=4 and(34)Ξgv=gv1,v2,v3,v4=4,7,5,0=v′.(3)
μ1=α1(v1)=α1(8)=3·83+2=9, μ2=α2(v1)=β1(g(v1))=β1(g(8))=β1(4)=4+1=5 and μ3=α3(8)=3·83+5=1.(4)
She getsv′=(4,7,5,0)→Nμ1(v′)=[9,10,1,8]=p1→Nμ2(p1)=(5,9,6,4)=p2→Nμ3(p2)=[1,3,10,2]=p3.(5)
Finally,L2(p3)=L2([1,3,10,2])=[1,3,10,2]=c is the ciphertext.
Bob knows the keyKp and the encryption scheme. Bob can decrypt the ciphertext c=[1,3,10,2] in the following steps: (1)
He computesL2-1(c)=L2-1([1,3,10,2])=[1,3,10,2]=[c10,c20,c30,c40]=c0.(2)
s is odd and Bob treats [1,3,10,2] as a vertex (line) in the graph D(4,F11).(3)
He writes the equation3x3+5=c10 and then rewrites it as 3x3=c10-5 (3, x are regular; left side is from F11∗ so c1-5 has to be regular). He writes x3=(1-5)·3-1 (regular) and uses the Euler theorem to find d (a multiplicative inverse of 3mod⁡ϕ(11), i.e., 7).Thenη=[(1-5)3-1]7=[7·4]7=67=8 is the unique solution. He forms a string of elements η0=g(η)=g(8)=4, η1=α1(η)=9 and η2=α2(η)=5.(4)
He getsc0=[1,3,10,2]→Nη2(c0)(5,9,6,4)→Nη1(c0)[9,10,1,8]=c2→,Nη0(c2)=(4,7,5,0)=(c13,c23,c33)=c3.(5)
He computes(35)Ξg-1c3=η,c23,c33=8,7,5,0=c3′(6)
Finally, he computes the plaintextp=L1-1(c3′)=(1,2,5,0).


## 9.3. Degree Estimates

In the casesT(n,K)=W(n,K) and T(n,K)=D~(n,K) the implementations of Algorithm No. 1 and Algorithm No. 2 use encryption map of degree O(n).The encryption and decryption map have multivariate nature. Let us assume thatdeg⁡(g) (odd s) and deg⁡(f) (even s) are given by linear function of kind cn+b, c>0. Then in the case of graphs D(n,K) and A(n,K) the degrees of encryption and decryption maps are bounded below by cn+b+2 and bounded above by 3(cn+b) because the shifting encryption is a cubical map.


## 10. Summary

The paper presents a class of stream ciphers defined in terms of graphs given by equations over the finite commutative ringK. The algorithm has multivariate nature: plaintext is a tuple from the free module Kn, key string is also an element of Km, and the encryption map is polynomial transformation of Kn into itself. Users have options to vary parameters n and m and ring K. If the parameter m is bounded by a constant, then the speed of numerical recurrent of encryption is O(n). The key can be given as a sequence of polynomials in a single variable x. We observe results on simplest case of key strings x+d1, x+d2, …, x+ds obtained by theoretical studies and via computer simulation in case of finite fields or arithmetical rings of kind Z2m. In case of graphs D(n,K) and A(n,K) simple conditions on di ensure that different keys produce distinct ciphertexts and allow estimating the complexity of adversary attacks without access to plaintext. In the above-mentioned case encryption and decryption maps are cubical and adversary after the interception of O(n3) pairs of kind plaintext-ciphertext can conduct a linearization attack in time O(n10). In case of D(n,K)~ the degree of both maps grows linearly with the growth of parameter n, which makes the search for the inverse map via linearization attacks a difficult task. Additionally, authors started investigation of bijective and nonbijective encryption maps with keys of kind xd+d1, xd+d2, …, xd+ds, where d>1.In the nonbijective case the plainspace is large subset ofKn and the adversary has to restore the multivariate encryption transformation E and search for polynomial map E′ such that EE′ fixes each plaintext. Known methods do not allow to solve this task in polynomial time. Special case with high degree E′ is implemented. Loaded tables for xd allow a fast encryption of text even in case of large parameter d.Our general Algorithm No. 2 uses encryption and decryption procedures of polynomial nature. Both procedures are approximated by maps of unbounded degree. This fact leads to resistance of the cipher to linearization attacks by an adversary.


## 11. Conclusion

The main purpose of this paper is to introduce stream ciphers with nonbijective encryption function of multivariate nature constructed in terms of algebraic graph theory. This class of encryption transformation has already been used as a tool of multivariate cryptography for the construction of public key candidates to be used in postquantum era. The idea of “hidden Eulerian equation” melted in large variety of coefficients of multivariate public rules was used as heuristic argument of security. We apply this idea in Symmetrical Cryptography which is not endangered by appearance of Quantum Cryptography and introduces robust stream ciphers resistant to linearization attacks. Authors agree that for practical uses further research is needed. Statistical evaluation of mixing properties via measuring of avalanche effect has to be done. We have to compare such properties in the case of Algorithm No. 1 and Algorithm No. 2 and bijective multivariate graph based encryption. Besides linearization attacks other tools have to be used like distinguish, Time Memory Data trade-off attacks, guess-and-determine attack, and various attacks of algebraic nature. Authors believe that the above-mentioned attacks which were developed to investigate bijective encryption have to be seriously modified to work with nonbijective ciphers. We hope that our algorithms will attract attention of cryptanalysts and they will test cryptanalytical instruments on such new families of ciphers. We have to compare such properties in the case of Algorithms No. 1 and No. 2 and bijective multivariate graph based encryption. Besides linearization attacks, other tools have to be used like Distinguishing attack, Time/memory/data trade-off attack, Guess-and-Determine attack, Resynchronization attack, and various attacks of algebraic nature (see [22–30]).



---

*Source: 2137561-2019-04-01.xml*