On algebraic graph theory and non-bijectivemultivariate maps in cryptography

Special family of non-bijective multivariate maps Fn of Zmⁿ into itself is constructed for n = 2,3, ... and composite m.The map F is injective on Ωn = {x|x1+x2+: : : xn ∈ Zm*} and solution of the equation Fn(x) = b, x ∈ Ωn can be reduced to the solution of equation zr = α, z ∈ Zm*, (r, φ(m)) = 1. Th...

Full description

Saved in:

Bibliographic Details
Published in:	Algebra and Discrete Mathematics
Date:	2015
Main Author:	Ustimenko, V.
Format:	Article
Language:	English
Published:	Інститут прикладної математики і механіки НАН України 2015
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/158006
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	On algebraic graph theory and non-bijectivemultivariate maps in cryptography / V. Ustimenko // Algebra and Discrete Mathematics. — 2015. — Vol. 20, № 1. — С. 152–170. — Бібліогр.: 33 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-158006
record_format	dspace
spelling	Ustimenko, V. 2019-06-22T12:34:11Z 2019-06-22T12:34:11Z 2015 On algebraic graph theory and non-bijectivemultivariate maps in cryptography / V. Ustimenko // Algebra and Discrete Mathematics. — 2015. — Vol. 20, № 1. — С. 152–170. — Бібліогр.: 33 назв. — англ. 1726-3255 https://nasplib.isofts.kiev.ua/handle/123456789/158006 Special family of non-bijective multivariate maps Fn of Zmⁿ into itself is constructed for n = 2,3, ... and composite m.The map F is injective on Ωn = {x\|x1+x2+: : : xn ∈ Zm} and solution of the equation Fn(x) = b, x ∈ Ωn can be reduced to the solution of equation zr = α, z ∈ Zm, (r, φ(m)) = 1. The “hidden RSA cryptosystem” is proposed. Similar construction is suggested for the case Ωn = Zm*ⁿ. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics On algebraic graph theory and non-bijectivemultivariate maps in cryptography Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	On algebraic graph theory and non-bijectivemultivariate maps in cryptography
spellingShingle	On algebraic graph theory and non-bijectivemultivariate maps in cryptography Ustimenko, V.
title_short	On algebraic graph theory and non-bijectivemultivariate maps in cryptography
title_full	On algebraic graph theory and non-bijectivemultivariate maps in cryptography
title_fullStr	On algebraic graph theory and non-bijectivemultivariate maps in cryptography
title_full_unstemmed	On algebraic graph theory and non-bijectivemultivariate maps in cryptography
title_sort	on algebraic graph theory and non-bijectivemultivariate maps in cryptography
author	Ustimenko, V.
author_facet	Ustimenko, V.
publishDate	2015
language	English
container_title	Algebra and Discrete Mathematics
publisher	Інститут прикладної математики і механіки НАН України
format	Article
description	Special family of non-bijective multivariate maps Fn of Zmⁿ into itself is constructed for n = 2,3, ... and composite m.The map F is injective on Ωn = {x\|x1+x2+: : : xn ∈ Zm} and solution of the equation Fn(x) = b, x ∈ Ωn can be reduced to the solution of equation zr = α, z ∈ Zm, (r, φ(m)) = 1. The “hidden RSA cryptosystem” is proposed. Similar construction is suggested for the case Ωn = Zm*ⁿ.
issn	1726-3255
url	https://nasplib.isofts.kiev.ua/handle/123456789/158006
citation_txt	On algebraic graph theory and non-bijectivemultivariate maps in cryptography / V. Ustimenko // Algebra and Discrete Mathematics. — 2015. — Vol. 20, № 1. — С. 152–170. — Бібліогр.: 33 назв. — англ.
work_keys_str_mv	AT ustimenkov onalgebraicgraphtheoryandnonbijectivemultivariatemapsincryptography
first_indexed	2025-11-26T00:08:40Z
last_indexed	2025-11-26T00:08:40Z
_version_	1850590176699482112
fulltext	Algebra and Discrete Mathematics RESEARCH ARTICLE Volume 20 (2015). Number 1, pp. 152–170 © Journal “Algebra and Discrete Mathematics” On algebraic graph theory and non-bijective multivariate maps in cryptography Vasyl Ustimenko Communicated by R. I. Grigorchuk This paper is dedicated to the glorious 60-th anniversary of Efim Zelmanov whose research is an inspirational example of continuous fruitful serving to Algebra Abstract. Special family of non-bijective multivariate maps Fn of Zm n into itself is constructed for n = 2, 3, . . . and composite m. The map Fn is injective on Ωn = {x\|x1 + x2 + . . . xn ∈ Zm ∗} and solution of the equation Fn(x) = b, x ∈ Ωn can be reduced to the solution of equation zr = α, z ∈ Zm ∗, (r, φ(m)) = 1. The “hidden RSA cryptosystem” is proposed. Similar construction is suggested for the case Ωn = Zm ∗n . 1. Introduction The RSA is one of the most popular cryptosystems. It is based on a number factorisation problem and Euler Theorem. Peter Shor discovered that factorisation problem can be effectively solved with the usage of theoretical quantum computer. It means that RSA could not be a security tool in the future postquantum era. One of the research directions which can lead to a postquantum secure public key is the Multivariate Cryptog- raphy which uses polynomial maps of affine space Kn defined over a finite commutative ring into itself as encryption tools (see [1]). This is a young promising research area with the current lack of known cryptosystems Key words and phrases: multivariate cryptography, linguistic graphs, hidden Eulerian equation, hidden discrete logarithm problem. V. Ustimenko 153 with the proven resistence against attacks with the use of Turing machines. Other important direction of Postquantum Cryptography is a study of Super-elliptic Curves cryptosystems. Applications of Algebraic Graph Theory to Multivariate Cryptography were observed in my talk at Central European Conference on Cryptology 2014 (Alfred Renyi Institute, Budapest) [2]. This talk was dedicated to algorithms based on bijective maps of affine spaces into themselves. Applications of algebraic graphs to cryptography started from symmetric algorithms based on explicit constructions of extremal graph theory and their directed analogs (see survey [3], [4]). The main idea is to convert an algebraic graph in finite automaton and use the preudorandom walks on the graph as encryption tools. This approach can be also 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 on plainspace vector brings several public key cryptosystems. Other source of graphs suitable for cryptography is connected with finite geometries and their flag system (see [3], [5], [6] and further references). This paper presents new cryptoalgorithm in terms of Algebraic Com- binatorics which use non-bijective transformations of Kn. Multivariate cryptography started from studies of potential for the special quadratic encryption multivariate bijective map of Kn, where K is an extention of finite field Fq of characteristic 2. One of the first such cryptosystems was proposed by Imai and Matsumoto, cryptanalysis for this system was invented by J. Patarin [1], [7]. The survey on various modifications of this algorithm and corresponding cryptanalysis the reader can find in [1]. Bijective multivariate sparse encryption maps of rather high degree based on walks in algebraic graphs were proposed in [8]. One of the first usage of non bijective map of multivariate cryptography was in oil and vinegar crptosystem proposed in [9] and analysed in [10]. Nowadays this general idea is strongly supported by the publication [11] dedicated to security analysis of direct attacks on modified unbalanced oil and vinegar systems. It looks like such systems and rainbow signatures schemes may lead to promising Public Key Schemes of Multivariate Encryption defined over finite fields. Non bijective 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 [12]. The paper is dedicated to other constructions of non bijective maps. We introduce the concept of family of multivariate maps F = Fn of 154 On algebraic graph theory in cryptography the free modules Kn onto itself decomposed into transition functions F 1, F 2, . . . , F s(n) of special symbolic vertex automata of linguistic graphs. In case K = Zm, where m is composite, it allows us to construct partially invertible Fn respectively to subsets Ωn of Zm n. It means that the restric- tion of F on Ωn is injective and the decomposition above allows us to solve the equation F (x)) = b for unknown (x) ∈ Ωn and b ∈ F (Ωn) in polyno- mial time. We are interested in the case of Eulerian maps Fn when the solution of the equation can be reduced to the study of equations of kind zr = d, where z in Zm ∗ and (r, φ(m)) = 1. We construct infinite families of maps of kind Hn = τ1Fnτ2, where τi are bijective affine transformations of Zm n, with Eulerian Fn of bounded degree such that Hn is partially invertible for Ωn = Zm ∗n and Ωn = {x ∈ Zm n\|x1 + x2 + . . . xn ∈ Zm ∗}. So the following scheme of a cryptosystem can be used. Alice (the public key owner) uses special linguistic graph Ln(Zm), its symbolic automaton with a special symbolic key to generate the Eulerian map Fn and the list of transition functions F 1, F 2, . . . , F s(n) of the symbolic computation. She chooses appropriate bijective affine transformations τ1 and τ2 and creates a deformation Hn = τ1Fnτ2 which is partially invertible for Ωn as above. Alice writes the following standard form for Hn: x1 → h1(x1, x2, . . . , xn), x2 → h2(x1, x2, . . . , xn), . . . , xn → hn(x1, x2, . . . , xn) where polynomials hi(x1, x2, . . . , xn), i = 1, 2, . . . , n are given by their lists of monomial terms with respect to the chosen order. She announces the form and the plainspace Ωn in public way. Notice that Alice keeps the transition functions generating Fn and deformation rule Hn = τ1Fnτ2 in secret. Cryptanalytic knows only the list of hi and the graph Ln(Zm). Public user (Bob) writes his message (p1, p2, . . . , pn) from the plainspace Ωn. He computes the ciphertext c = (c1, c2, . . . , cn), ci = hi(p1, p2, . . . , pn), i = 1, 2, . . . , n and sends it to Alice. Alice solves the equation Fn(x1, x2, . . . , xn) = (c1, c2, . . . , cn) due to her knowledge of symbolic key of the automaton. So she reads the plaintext. Notice that to make this scheme feasible we need to care about polynomiality of generation time, bound for the degree of Hn, Eulerian nature of the map Fn. We achieve it via special choice of linguistic graph (well known graphs D(n, K)) and some restriction on symbolic keys. Section 2 is dedicated to linguistic graphs and related to them au- tomata. In Section 3 the reader can find information on chosen linguistic V. Ustimenko 155 graph D(n, K). The properties af chosen computation of vertex automa- ton for graph D(n, Zm) are justified in section 4. Last section gives precise descryption of cryptosystem. 2. Linguistic graphs and their vertex automata The missing definitions of graph-theoretical concepts which appear in this paper can be found in [13]. All graphs we consider are simple , i.e. undirected without loops and multiple edges. Let V (G) and E(G) denote the set of vertices and the set of edges of G respectively. Then \|V (G)\| is called the order of G, and \|E(G)\| is called the size of G. When it is convenient we shall identify G with the corresponding anti-reflexive binary relation on V (G), i.e. E(G) is a subset of V (G) × V (G) and write v G u for the adjacent vertices u and v (or neighbours). We assume that V (G) is a finite or an infinite set. The majority of examples will be locally finite graphs G, i.e. each vertex v has finite number of neighbours (x ∈ V (G), such that x G v). We refer to \|{x ∈ V (G)\|x G v}\| as degree of the vertex v. The sequence of distinct vertices v0, v1, . . . , vt, such that vi G vi+1 for i = 1, . . . , t − 1 is a path in the graph. The path in G is called simple if all its vertices are distinct. The graph is connected if each two of its vertices are joined by some path. The length of the path is a number of its edges. The distance between two vertices u and v of the graph, denoted by dist(u, v), is the length of the shortest path between them. The diameter of the graph, denoted by diam(G), is the maximal distance between two vertices u and v of the graph. Let Cm denote the cycle of length m, i.e. the sequence of distinct vertices v0, . . . , vm such that vi G vi+1, i = 1, . . . , m − 1 and vm G v1. The girth of a graph G, denoted by g = g(G), is the length of the shortest cycle in G. The incidence structure is the set V with partition sets P (points) and L (lines) and symmetric binary relation I such that the incidence of two elements implies that one of them is a point and another one is a line. We shall identify I with the simple graph of this incidence relation (bipartite graph). We refer to a triple consisting of set V , its partition V = P ∪ L and symmetric and antireflexive binary relation I (incidence) on the set V , such that xIy implies x ∈ P , y ∈ L or x ∈ L and y ∈ P as incidence structure. The pair {x, y}, x ∈ P , y ∈ L such that xIy is called a flag of incidence structure I. Let K be a finite commutative ring. We refer to an incidence structure with a point set P = Ps,m = Ks+m and a line set L = Lr,m = Kr+m as 156 On algebraic graph theory in cryptography linguistic incidence structure Im if point (x) = (x1, x2, . . . , xs, xs+1, xs+2, . . . , xs+m) is incident to line [y] = [y1, y2, . . . , yr, yr+1, yr+2 . . . , yr+m] if and only if the following relations hold ξ1xs+1 + ζ1yr+1 = f1(x1, x2, . . . , xs, y1, y2, . . . , yr) ξ2xs+2 + ζ2yr+2 = f2(x1, x2, . . . , xs, xs+1, y1, y2, . . . , yr, yr+1) . . . ξmxs+m + ζmyr+m = fm(x1, x2, . . . , xs+m−1, y1, y2, . . . , yr+m−1) where ξj and ζj , j = 1, 2, . . . , m are not zero divisors, and fj are multi- variate polynomials with coefficients from K. Brackets and parenthesis allow us to distinguish points from lines (see [14]). The colour ρ(x) = ρ((x)) (ρ(y) = ρ([y])) of point (x) (line [y]) is defined as projection of an element (x) ([y]) from a free module on its initial s (relatively r) coordinates. As it follows from the definition of linguistic incidence structure for each vertex of incidence graph there exists unique neighbour of a chosen colour. We also consider a linguistic incidence structures defined by infinite number of equations. We refer to ρ((x)) = (x1, x2, . . . , xs) for (x) = (x1, x2, . . . , xs+m) and ρ([y]) = (y1, y2, . . . , yr) for [y1, y2, . . . , ys+m] as the colour of the point and the colour of the line respectively. For each b ∈ Kr and (p) = (p1, p2, . . . , ps+m) there is a unique neighbour of the point [l] = Nb(p) with the colour b. Similarly for each b ∈ Ks and [l] = [l1, l2, . . . , lr+m] there is a unique neighbour of the line [p] = Nb([l]) with the colour b. Let S(Kn) be the semigroup of all polynomial maps from Kn into Kn, where K is a commutative ring. Assume that the transformation F (n) ∈ S(Kn) is written in the form xj → f(n)j(x1, x2, . . . , xn) where each f(n)j , j = 1, 2, . . . , n is determined by the list of all monomial terms with the respect to some chosen order. Let us refer to the sequence of maps F (n) from S(Kn), n = 2, 3, . . . as a family of bounded degree, if the degree of each transformation F (n) is bounded by some constant d, d > 0. Let τ(n)L and τ(n)R be affine transformations of kind x → xA + b, where x ∈ Kn, b ∈ Kn, A = (aij), 1 6 i, j 6 n. We assume, that the transformations τL(i) and τR(i) are invertible. V. Ustimenko 157 We refer to the sequence of G(n) = τL(n)F (n)τR(n) as the deformation of the family F (n), n = 2, 3, . . . . Notice that deg g(n) = deg f(n), but densities of the maps can be different. In fact densities of g(n) heavily depend on the choices of an affine transformation τL. Let us convert the bipartite graph of incidence relation I = Im to vertex automaton V A(Im) in the following way. We announce that vertices of the graph are states of V A(Im). If (p)I[l)] and [l] = Nb(p) then we draw an arrow from (p) to [l] with the weight b ∈ Kr. If (p)I[l)] and [p] = Nb(p) then we draw an arrow from [l] to (p) with the weight b ∈ Ks. We assume that all vertices of the bipartite graph are accepting states. Let us assume that r = s = 1 in all further considerations. We assume that graph Im has connectivity invariants d1(x), d2(x), . . . , dt(x) which are multivariate functions from Ks+m into K such that for two vertices v1 and v2 (points or lines) from the same connected component of the graph equalities di(v2) = di(v1), i = 1, 2, . . . , t hold. We consider symbolic vertex automaton SV (Im) correspond- ing to Im defined in the following way. Its states are divided into points (f1, f2, . . . , fm+1) and lines [g1, g2, . . . , gm+1] where fi ∈ K[x1, x2, . . . , x1+m] and gi ∈ K[x1, x2, . . . , x1+m], i = 1, 2, . . . , m + 1. There are two options for an by initial state: symbolic point (x1, x2, . . . , x1+m) or symbolic line [x1, x2, . . . , x1+m]. The computation of SV (Im) is given by its symbolic key hj ∈ K[z1, z2, . . . , z1+t], j = 1, 2, . . . , k and its initial state (point for example) in the fol- lowing way. One has to form the specialisation of a symbolic key h̃j = h(x1, d1(x), d2(x), . . . , dt(x)) ∈ K[x1, x2, . . . x1+m] and compute the chain (x1, x2, . . . , x1+m), Nh̃1(x1,x2,...,x1+m)(x) = v1, Nh̃2(x1,x2,...,x1+m)(v1) = v2, Nh̃3(x1,x2,...,x1+m)(v2) = v3, . . . , Nh̃k(x1,x2,...,x1+m)(vk−1) = vk via symbolic computations. We refer to F = vk as a result of symbolic computation with the given symbolic key and refer to a chain (x), vj , j = 1, 2, . . . , k as decomposition of vk into transition function of symbolic automaton SV (Im). We identify vk with the corresponding multivariate map from S(Km+1). 158 On algebraic graph theory in cryptography We refer to the deformation rule G = τLvkτR and the chain vi, i = 1, 2, . . . , k as decomposition of G of rank k into transition function of symbolic vertex automaton of the graph Im. We say that G is symbolically decomposed via linguistic graph Im. Notice that for F = (f1, f2, . . . , fm+1) polynomial f1 coincides with hk(x1, d1(x), d2(x), . . . , dt(x). Let us investigate the equation F (p1, p2, . . . , pm+1) = (b1, b2, . . . , bm+1). Assume that (b1, b2, . . . , bm+1) is an element of image of F and pi are variables. Then hk(p1, d1(p), d2(p), . . . , dt(p)) = b1. We can rewrite it as hk(p1, d1(b), d2(b), . . . , dt(b)) = b1. Notice that here we use the fact that vertices (p1, p2, . . . , pm+1) and (b1, b2, . . . , bm+1) (points or lines) are in the same connected component of the graph. Let us assume that for the subset Ω of K the equation hk(p1, d1(b), d2(b), . . . , dt(b)) = b1, p1 ∈ Ω has at most one solution. If b ∈ F (Ω × Km) then we can find the solution p1 = p∗ 1. After that we can compute βk−1 = hk−1(p∗ 1, d1(b), d2(b), . . . , dt(b)), βk−2 = hk−2(p∗ 1, d1(b), d2(b), . . . , dt(b)), . . . β1 = hk−2(p∗ 1, d1(b), d2(b), . . . , dt(b)). It allows us to compute uk−1 = Nβk−1 (b1, b2, . . . , bm+1), uk−2 = Nβk−2 (uk−1), . . . u1 = Nβk−2 (u2), (p∗ 1, p∗ 2, . . . , p∗ m+1) = Np∗ 1 (u1). So the restriction of the map F on Ω × Km is injective. The equation F (x) = b, where x ∈ Ω × Km, b ∈ F (Ω × Km) has a unique solution. Let F ′ = τLFτR be the deformation of F and T = τL −1(Ω × Km). Then the equation F ′(x) = b for x ∈ T and b ∈ F ′(T ) has a unique solution. We say that the multivariate transformation F ′ of Km+1 is partially invertible on T . Such maps F ′ together with deformation rule τLFτR and decomposition of F via transition functions of symbolic vertex automaton of linguistic graph can be used in symmetric cryptography. Let us consider two general examples in case K = Zl, l > 2. V. Ustimenko 159 Example. Correspondents (Alice and Bob) take a linguistic graph Im in cases r = s = 1 as above. Assume that they know the list of con- nectivity invariants di(x1, x2, . . . , xm+1), i = 1, 2, . . . , t. They choose the type of an initial state. Without loss of generality we can take point (x1, x2, . . . , xm+1). They set the length of computation of vertex symbolic automaton k and symbolic key h1(z1, z2, . . . , zt+1), h2(z1, z2, . . . , zt+1), . . . hk(z1, z2, . . . , zt+1), where hk = axr + f(z2, z3, . . . , zt+1), a ∈ Zl ∗, (r, φ(l)) = 1. They choose affine transformation τL of kind x1 → x1 + x2 + . . . xm+1, xj → lj(x1, x2, . . . , xm+1), where lj(x1, x2, . . . , xm+1) are general linear transformation of Zl m+1 into Zl for j = 2, 3, . . . , m + 1, and general bijective affine transformation τR. We assume that the graph Im, its connectivity invariants, and the plainspace T = {(x1, x2, . . . , xm+1) ∈ Zl m+1\|x1 + x2 + · · · + xn ∈ Zl ∗} are known to public. Cryptanalytic knows the general algorithm which depends on some unknown τL, τR and some symbolic key. Correspondents share the symbolic key hi(x1, x2, . . . , xt+1), i = 1, 2, . . . , k and affine transformations τL and τR as above. Alice writes her plaintext p = (p1, p2, . . . , pm+1). She computes the tuple τL(p) = (u1, u2, . . . , um+1) = u. She computes values of connectivity invariants βi = di(u1, u2, . . . , um+1), i = 1, 2, . . . , t. After that Alice gets the values of symbolic keys γ1 = h1(u1, β1, β2, . . . , βt), γ2 = h2(u1, β1, β2, . . . , βt), . . . , γk = hk(u1, β1, β2, . . . , βt). If chosen k is odd she takes the chain (u), Nγ1 (u) = [u1], Nγ2 ([u1]) = (u2), . . . , Nγk ((uk−1)) = [uk]. She takes τR(uk) = c as ciphertext. Notice that in case of even K Alice gets Nγk ([uk−1]) = (uk). Let us consider the decryption process. For simplicity we take the case when k is odd. Bob takes c. He computes τR −1(c) = uk. He takes [uk] = [b1, b2, . . . , bn]. Bob computes parameters βi as di([b1, b2, . . . , bn]) for i = 1, 2, . . . , t. Bob looks at expression axr + f(z2, z3, . . . , zt+1) and writes the equation axr + f(β1, β2, . . . , βt) = b1. So he computes xr = 160 On algebraic graph theory in cryptography (b1 − f(β1, β2, . . . , βt))a −1 = α. So Bob gets u1 as αr′ where r′ is a multiplicative inverse in Zφ(l). Now, Bob computes γi = hi(u1, β1, β2, . . . , βt), i = 1, 2, . . . , k − 1. So he gets Nγk−1 ([uk]) = (uk−1), Nγk−2 ((uk−1)) = [uk−2], . . . , Nγ1 ((u2)) = [u1], Nu1 ([u1]) = (u). Finally Bob obtains τL −1(u) = (p1, p2, . . . , ps). Remark 1. It is easy to see that the scheme above can be easily modi- fied in various ways. For instance, correspondents can use T = Zl ∗m+1 and take τL as linear monomial transformation (x1, x2, . . . , xm+1) → (λ1x1, λ2x2, . . . , λm+1xm+1), where (λ1, λ2, . . . , λm+1) ∈ Zl ∗m+1. Remark 2. The above scheme can produce rather fast symmetric en- cryption algorithm in case of various linguistic graphs. It is easy to define linguistic graph Im such that the neighbour of each vertex can be com- puted in time O(m). We can take an empty list of connectivity invariants (parameter t is zero). Assume that we work with sparse affine transforma- tion τL and τR which can be completed in O(m) elementary steps. Then the encryption algorithm above takes O(m) operations. Towards public key algorithm. Alice can take a linguistic graph Im in case r = s = 1 as above. She knows the list of connectivity invariants di(x1, x2, . . . , xm+1), i = 1, 2, . . . , t. She chooses the type of initial state. Without loss of generality we can take point (x1, x2, . . . , xm+1). Alice chooses the length k of computation of vertex symbolic automaton k and symbolic key h1(z1, z2, . . . , zt+1), h2(z1, z2, . . . , zt+1), . . . , hk(z1, z2, . . . , zt+1), where hk = axr + f(z2, z3, . . . , zt+1), a ∈ Zl ∗, (r, φ(l)) = 1. She chooses affine transformation τL of kind x1 → x1 + x2 + . . . xm+1, xj → lj(x1, x2, . . . , xm+1), where lj(x1, x2, . . . , xm+1) are general linear transformation of Zl m+1 into Zl for j = 2, 3, . . . , m + 1, and general bijective affine transformation τR. Alice takes the initial state x = (x1, x2, . . . , xm+1). She computes the tuple τL(x) = (v1, v2, . . . , vm+1) = v, where vi are linear expressions in variables x1, x2, . . . , xm+1. Notice that v1 = x1+x2+· · ·+xm+1. After that V. Ustimenko 161 Alice takes computation of symbolic vertex automaton with symbolic key hi, i = 1, 2, . . . , k starting in a new initial state (v1, v2, . . . , vm+1). It means that Alice uses symbolic computations for the constructions of multivariate invariants dt(v1, v2, . . . , vm+1) = d′ t(x1, x2, . . . , xm+1), i = 1, 2, . . . , t. She computes h̃1 = h1(v1, d′ 2, . . . , d′ t+1), h̃2 = h2(v1, d′ 2, . . . , d′ t+1), . . . h̃k = hk(v1, d′ 2, . . . , d′ t+1). Alice computes the chain of elements from Zl[x1, x2, . . . , xm+1]m+1 (vertices of symbolic automaton, points and lines). The point v = (v1, v2, . . . , vm+1), line [v1] = Nh̃1 (v), point (v2) = Nh̃2 ([v1]), . . . , (vk−1) = N ˜hk−1 ((vk−2)), [vk] = Nh̃k (vk−1). For simplicity we take odd k. Alice treats F = vk as multivariate map and computes G = FτR (composition of two maps). Assume that Alice can complete all steps as above in polynomial time and get a resulting map G of finite degree. Then she can write the standard form of G: x1 → g1(x1, x2, . . . , xm+1), x2 → g2(x1, x2, . . . , xm+1), . . . , xm+1 → gm+1(x1, x2, . . . , xm+1), where gi, i = 1, 2, . . . , m + 1 are given by the lists of their monomial terms with respect to some standard order. Then Alice can announce the public rules gi ∈ Zl[x1, x2, . . . , xm+1], i = 1, 2, . . . , m+1 to all of her correspondents together with the plainspace Ωm+1 = {x ∈ Zl m+1\|x1 + x2 + · · · + xm ∈ Zl ∗}. Public user (Bob) writes a message (p1, p2, . . . , pm+1) ∈ Ωm+1 and computes the ciphertext (c1, c2, . . . , cm+1) where ci = gi(p1, p2, . . . , pm+1), i = 1, 2, . . . , m + 1 and sends it to Alice. Alice knows the deformation rule G = τLFτR and the symbolic key which gives the decomposition of F into transition functions of the symbolic vertex automaton of the graph. So she can use the decryption process of symmetric encryption algorithm above and restore the plaintext (p1, p2, . . . , pm+1). Remark 3. Similarly to symmetric algorithm Alice can change Ωm+1 for T = Zl ∗m+1 and take τL as linear monomial transformation (x1, x2, . . . , xm+1) → (λ1x1, λ2x2, . . . , λm+1xm+1), where (λ1, λ2, . . . , λm+1) ∈ Zl ∗m+1. Remark 4. One can assume that cryptanalytic knows the family of graphs Im defined over Zl, where l is known composite number. We introduce free symbolic computation of odd case k for the general linguistic graph Im over commutative ring K in case r = s = 1 as the 162 On algebraic graph theory in cryptography sequence x = (x1, x2, . . . , xm+1) (initial state), line Nz1 (x) = [u1], u1 ∈ K[z1, x1, x2, . . . , xm+1]m+1, Nz2 ([u1]) = (u2), u2 ∈ K[z1, z2, x1, x2, . . . , xm+1]m+1, . . . Nzk ((uk−1)) = [uk)], uk ∈ K[z1, z2, . . . , zk, x1, x2, . . . , xm+1]m+1. 3. On some extremal algebraic graphs Recall that the girth is the length of minimal cycle in the simple graph. Studies of maximal size ex(C3, C4, . . . , C2m, v) of the simple graph on v vertices without cycles of length 3, 4, . . . , 2m, i. e. graphs of girth > 2m, form an important direction of Extremal Graph Theory. As it follows from the famous Even Circuit Theorem by P. Erdős’ we have inequality ex(C3, C4, . . . , C2n, v) 6 cv1+1/n, where c is a certain constant. The bound is known to be sharp only for 2n = 4, 6, 8. The first general lower bounds of kind ex(v, C3, C4, . . . Cn) = Ω(v1+c/n), where c is some constant < 1/2 were obtained in the 50th by Erdős’ via studies of families of graphs of a large girth, i.e. infinite families of simple regular graphs Γi of degree ki and order vi such that g(Γi) > clogki vi, where c is the independent of i constant. Erdős’ proved the existence of such a family with arbitrary large but bounded degree ki = k with c = 1/4 by his famous probabilistic method. One of the first examples of the family of graphs of large girth is the family of algebraic graphs CD(n, q) (see [15] and further references). Graphs CD(n, q) appear as connected components of graphs D(n, q) defined via system of quadratic equations [16]. Graphs D(n, q) and CD(n, q) have been used in symmetric cryptog- raphy together with their natural analogs D(n, K) and CD(n, K) over general finite commutative rings K since 1998 (see [17]). The theory of directed graphs and language of dynamical system were very useful for studies of public key and private key algorithms based on graphs D(n, K), CD(n, K) (see [18–25] and further references). There are several implementations of symmetric algorithms for cases of fields ([26], [27], [30]) and arithmetical rings ([28], [29]). Some comparison of bijective multivariate maps based on D(n, K) and other graphs A(n, K) are considered in [31]. V. Ustimenko 163 4. Graphs D(n, K) and new algorithms related to them Let P and L be two copies of Cartesian power K N, where K is the commutative ring and N is the set of positive integer numbers. Elements of P will be called points and these of L lines. To distinguish points from lines we use parentheses and brackets. If x ∈ V , then (x) ∈ P and [x] ∈ L. It will also be advantageous to adopt the notation for co-ordinates of points and lines introduced in [16] for the case of general commutative ring K: (p) = (p0,1, p1,1, p1,2, p2,1, p2,2, p′ 2,2, p2,3, . . . , pi,i, p′ i,i, pi,i+1, pi+1,i, . . .), [l] = [l1,0, l1,1, l1,2, l2,1, l2,2, l′2,2, l2,3, . . . , li,i, l′i,i, li,i+1, li+1,i, . . .]. The elements of P and L can be thought as infinite ordered tuples of elements from K, such that only finite number of components are different from zero. We now define a linguistic incidence structure (P, L, I) defined by infinite system of equations as follows. We say the point (p) is incident with the line [l], and we write (p)I[l], if the following relations between their co-ordinates hold: li,i − pi,i = l1,0pi−1,i, l′i,i − p′ i,i = li,i−1p0,1, li,i+1 − pi,i+1 = li,ip0,1, li+1,i − pi+1,i = l1,0p′ i,i. (1) (These four relations are defined for i > 1, p′ 1,1 = p1,1, l′1,1 = l1,1). The incidence structure (P, L, I) we denote as D(K). We speak now of the incidence graph of (P, L, I), which has the vertex set P ∪ L and edge set consisting of all pairs {(p), [l]} for which (p)I[l]. For each positive integer k > 2 we obtain a symplectic quotient (Pk, Lk, Ik) as follows. Firstly, Pk and Lk are obtained from P and L, respectively, by simply projecting each vector into its k initial coordinates. The incidence Ik is then defined by imposing the first k−1 incidence relations and ignoring all others. The incidence graph corresponding to the structure (Pk, Lk, Ik) is denoted by D(k,K) (see [17]). To facilitate notation in the future results on "connectivity invariants", it will be convenient for us to define p−1,0 = l0,−1 = p1,0 = l0,1 = 0, p0,0 = l0,0 = −1, p′ 0,0 = l′0,0 = −1, p′ 1,1 = p1,1, l′1,1 = l1,1 and to assume that (1) are defined for i > 0. 164 On algebraic graph theory in cryptography Notice, that for i = 0, the four conditions (6) are satisfied by every point and line, and, for i = 1, the first two equations coincide and give l1,1 − p1,1 = l1,0p0,1. Let k > 6, t = [(k + 2)/4], and let u = (uα, u11, · · · , utt, u′ tt, ut,t+1, ut+1,t, · · · ) be a vertex of D(k,K) (α ∈ {(1, 0), (0, 1)}, it does not matter whether u is a point or a line). For every r, 2 6 r 6 t, let ar = ar(u) = ∑ i=0,r (uiiu ′ r−i,r−i − ui,i+1ur−i,r−i−1), and a = a(u) = (a2, a3, · · · , at). Similarly, we assume a = a(u) = (a2, a3, · · · , at, . . . ) for the vertex u of infinite graph D(K). Let ηn (η) be the equivalence relation: uηnv ⇔ a(u) = a(v) (uτv ⇔ a(u) = a(v)) on the vertex set of graph D(k,K) (D(K)), respectively. Proposition 1 (see [19] and further references). (i) For any t − 1 ring elements xt ∈ K, 2 6 t 6 [(k + 2)/4], there exists a vertex v of D(n,K) for which a(v) = (x2, . . . , xt) = (x). (ii) The equivalence class Cn for the equivalence relation τ on the set K n∪K n is an isomorphic to the affine variety K t∪K t , t = [4/3n]+1 for n = 0, 2, 3 mod 4, t = [4/3n] + 2 for n = 1 mod 4. (iii) the vertex set Cn is the union of several connected components of D(n,K). Let C be the equivalence class on τ on the vertex set D(K), then the induced subgraph with the vertex set C is the union of several connected components of D(K). We shall use notation C(t,K) (C(K)) for the induced subgraph of D(n,K) (D(K)) with the vertex set Cn (vertex set C respectively). The graph C(t,K) in the case of K = Fq coincides with CD(n, q) which was introduced in [17]. The following statement was proven in [32]. Theorem 1. Let K be commutative ring with unity of characteristic d, d 6= 2. Then graphs C(t,K), t > 6 and C(K) are connected. If K = Fq, q is odd, then graph C(Fq) is a q-regular tree. In cases char(K) = 2 the questions of the description of connected components of C(t,K) and C(K) are open. V. Ustimenko 165 5. The cryptosystem We can rewrite result of [33] in the following form. Proposition 2. Let Fn be a regular computation of free symbolic automa- ton of linguistic graph D(n, Zl) and α1, α2, . . . , αk, where k is even, are fixed elements of Zl. Then the map F̃n corresponding to a specialisation of z2 = y+α1, z3 = z1 +α1, z4 = y+α3, z5 = z1 +α5, . . . , zk−1 = z1 +αk−1, zk = y + αk is cubical multivariate map from K[z1, y, x1, x2, . . . , xn]m+1. Remark 5. Similar proposition is true for odd k. The map F̃n corre- sponding to a specialisation of z2 = y + α1, z3 = z1 + α1, z4 = y + α3, z5 = z1 + α5, . . . , zk−1 = y + αk−1, zk = z1 + αk is cubical transformation of Zl n. Proposition 3. Let Fn be a regular computation of an odd length s of a symbolic vertex automaton of D(n.K) corresponding to symbolic key h(z1, z2, . . . , zt)+α1, z1 +α2, h(z1, z2, . . . , zt)+α3, z1 +α4. . . . , z1 +αs−1, h(z1, z2, . . . , zt) + αs, where h ∈ K[z1, z2, . . . , zt] has finite degree and αi, i = 1, 2, . . . , s are constants from K. Then the degree of Fn is bounded by 3 deg h(x01, a2(x), a3(x), . . . , at(x)). We say that the map Fn of Zl n to itself is Eulerian partially invertible map on the domain Ωn = {x\|λ1x1 + λ2x2 + · · · + λnxn + αn+1 ∈ Zl ∗} if it is partially invertible on Ωn and solution of equation Fn(x) = b, x ∈ Ω and b ∈ Fn(Ωn) can be reduced to a solution of zr = a, z ∈ Zl ∗, r 6= 1, (r, φ(l)) = 1. Theorem 2. Let K = Zl, n be a natural number > 2, s is an odd number > 3. For each domain of kind Ωn = {x\|λ1x1 + λ2x2 + · · · + λnxn + λn+1 ∈ Zl ∗} in Zl n, where λi 6= 0, i = 1, 2, . . . , n there is Eulerian map Fn of finite degree which has a symbolic decomposition of rank s. If l is a prime number, then Eulerian map Fn is a bijection. Proof. Let us consider a symbolic vertex automaton constructed for the family of graphs D(n, Zl). Let a2(x), a3(x), . . . , at(x), t = [(n + 2)/4] be the list of quadratic connectivity invariants of the graph. We shall use polynomials from Zl[u1, u2, . . . , ut] to form special symbolic key. For f ∈ Zl[u1, u2, . . . , ut] we define f̃ as f(z1, a2(z), a3(z), . . . , at(z), where (z) = (z1, z2, . . . , zn) is initial point of the symbolic vertex automaton of graph D(n, Zl). We avoid double indexes for points and lines here. We have a free choice to take H ∈ Zl[u1, u2, . . . , ut] to form a sequence of 166 On algebraic graph theory in cryptography weights α1(z) = H̃ +β1, α2(z) = z1 +β2, α3(z) = H̃ +β3 , α4(z) = z1 +β4, . . . , αs−1(z) = z1 +βs−1, αs(z) = H̃ +βs, where βi, i = 1, 2, . . . , s are fixed elements of Zl. Let F = Fn : Zl n → Zl n be the multivariate map generated by symbolic computation above. We assume that H(u1, u2, . . . , ut) is written in the form u1 r + S(u2, u3, . . . , ut), where S is arbitrary element of Zl[u2, u3, . . . , ut] and r, r 6= 1 is a parameter such that (r, φ(m)) = 1. Symbol φ standardly stands for Euler function. Let us consider non- singular linear transformation τL : Zl n → Zl n of kind z1 → λ1z1 + λ2z2 + · · · + λnzn + λn+1, z2 → l2(z1, z2, . . . , zn), z3 → l3(z1, z2, . . . , zn), . . . zn → ln(z1, z2, . . . , zn), where li are linear expressions from Zl[z1, z2, . . . , zn] of general kind. We form a composition Gn = τLFn. Assume that z = (z1, z2, . . . , zn) is an element of Ωn. Let us identify τL(z) = (y1, y2, . . . , yn) with the point of the graph D(n, Zl). Notice that y1 ∈ Zl ∗. Let us show that the reimage of Gn(z) is uniquely determined. We write the equation Gn(z) = (b1, b2, . . . , bn). It is clear that b1 = y1 r + S(u2, u3, . . . , ut) + βs. Notice that tuples y (point) and b (line) are located in the same connected component of the graph. So we have ai(y) = ai(b) = γi, i = 2, 3, . . . , t. Thus y1 r + S(γ2, γ3, . . . , γt) + βs = b1. Ler r′ be the multiplicative inverse of r in Zφ(l). We have y1 = (b1 − S(γ2, γ3, . . . , γt) − βs)r′ = α. The knowledge of parameter α allows us to compute all coordinates of tuple y. Really, we can compute values αs−1 = α + βs−1, αs−2 = H(α, γ2, γ3, . . . , γt)+βs−2, αs−3 = α+βs−3, . . . , α1 = H(α, γ2, γ3, . . . , γt)+ β1, α0 = α. The value of y can be computed recursively ys−1 = Nαs−1 ([b]), ys−2 = Nαs−2 ((ys−1)), . . . y1 = Nα1 ((y2)), y0 = Nα((y1)) = (y1, y2, . . . , yn). The tuple z equals τl −1(y0). The Proposition 3 establishes that the degree of Gn or Fn is bounded by 3 deg(H̃(z)). If d = deg(S̃) > r then the degree of Gn is bounded by 3d. Notice, that in case of prime l the equation y1 r +S(γ2, γ3, . . . , γt)+βs = b1, r 6= 0 mod p−1 is always solvable for y1. So maps Fn and Gn are bijections. Remark 6. In the theorem above we can change domain Ωn for Zl ∗n. V. Ustimenko 167 Really we have to change a transformation τL in the proof for a linear monomial map (x1, x2, . . . , xn) → (λ1xπ(1), λ2xπ(2), . . . , λnxπ(n)), where λi, i = 1, 2, . . . , n are elements of Zl ∗ and π is a permutation from Sn. The cryptosystem. Assume that Alice is the holder of a public key based on the family of maps used in the constructive proof of the previous theorem. So she takes l, l > 2 and parameter r, such that (r, φ(l)) = 1. She chooses the odd length s, s > 3 of symbolic key for practical use we set size O(n) for value of s. For example, Alice chooses the area Ωn = {x\|x1 + x2 + · · · + xn ∈ Zl ∗} which will be a domain for Eulerian map of G = Zl n. Alice has a rather wide choice to pick the function S ∈ Zl[u2, u3, . . . , ut], t = [(n + 2)/4] and parameters β1, β2, . . . , βs to form the symbolic key. She has set l1 = x1 + x2 + . . . , xn and may choose various linear functions li ∈ Zl[x1, x3, . . . , xn], i = 2, 3, . . . , n to form bijective affine map τl of Zl n to itself. Finally, she has a free choice for another affine map τR. So in polynomial time Alice generates map Fn via computation of symbolic vertex automaton of linguistic graph D(n, Zl) with the symbolic key: α1(z) = H̃ + β1, α2(z) = z1 + β2, α3(z) = H̃ + β3, α4(z) = z1 + β4, . . . , αs−1(z) = z1 + βs−1, αs(z) = H̃ + βs, where βi, i = 1, 2, . . . , s are fixed elements of Zl. She computes the deformation Gn = τLFnτR in standard form x1 → g1(x1, x2, . . . , xn), x2 → g2(x1, x2, . . . , xn), . . . , xn → gn(x1, x2, . . . , xn), where gi, i = 1, 2, . . . , n are given by list of their monomial terms in some chosen order. Notice, that the degree of Gn is bounded by constant. Alice announces the public the standard form of Gn and keeps data described above in secret. Cryptanalytic knows used graph and general form of a symbolic key. Assume that a public user (Bob) creates an open text p=(p1,p2,. . . ,pn). He computes Gn((p1, p2, . . . , pn)) = (c1, c2, . . . , cn). Bounded degree of Gn insures that the computation of ciphertext can be computed in a polynomial time O(nc) for some positive constant c. The knowledge of deformation rule Gn = τLFnτR and the docompo- sition of Fn into transition functions of symbolic vertex automaton of D(n, Zl) allows her to decrypt in polynomial time with the algorithm described in a previous section. Remark 7. Alice can use Zl ∗n instead of Ωn = {x\|x1+x2+· · ·+xn ∈ Zl ∗}. In this case τL has to be chosen as monomial transformation. Remark 8. In case of prime l we can change function H + bs for much more sophisticated expression. For instance Z(x2, x3, . . . , xt)f(x1)+ 168 On algebraic graph theory in cryptography S(x2, x3, . . . , xt) where Z(x2, x3, . . . , xt) = 0 has no solution but f(x1) = d has exactly one solution in variable x1 for each d. Let h(x) ∈ Zp[x] has no linear divisors. Then Z(x2, x3, . . . , xt) = h(M(x2, x3, . . . , xt))) is always different from zero for each M ∈ K[x2, x3, . . . , xt]. The simplest case where we can use M(x2, x3, . . . , xt)(x1 r) + S(x2, x3, . . . , xt), where (r, p−1) = 1 and the equation M(x2, x3, . . . , xt) = 0 has no solution. We say that such a cryptosystem is based on hidden discrete logarithm problem. For general parameter l we use the term hidden Eulerian equation. We can use recurrent expressions Mk(. . . (M2(M1(x2, x3, . . . , xt)(x1 r1) + S1(x2, x3, . . . , xt)) r2 +S2(x2, x3, . . . , xt)) + . . . Mk−1(x2, x3, . . . , xt)(x1 rk−1) +Sk−1(x2, x3, . . . , xt)) rk + Sk(x2, x3, . . . , xt)), where Mi(x2, x3, . . . , xt) = 0 have no solutions for each i = 1, 2, . . . , k. References [1] J. Ding, J. E. Gower, D. S. Schmidt, Multivariate Public Key Cryptosystems, 260. Springer, Advances in Information Security, v. 25, (2006). [2] V. A. Ustimenko, Explicit constructions of extremal graphs and new multivari- ate cryptosystems, Studia Scientiarum Mathematicarum Hungarica, Special issue “Proceedings of The Central European Conference, 2014, Budapest”,volume 52, issue, June 2015, pp. 185-204. [3] V. A. Ustimenko, Graphs with Special Arcs and Cryptography, Acta Applicandae Mathematicae, vol. 71, N2, November 2002, 117-153. [4] V. Ustimenko, On the extremal graph theory for directed graphs and its crypto- graphical applications, In: T. Shaska, W.C. Huffman, D. Joener and V. Ustimenko. Advances in Coding Theory and Cryptography. Series on Coding and Cryptology, V. 3, 2007, P. 181–200. [5] V. A. Ustimenko, On the flag geometry of simple group of Lie type and Multivariate Cryptography, Algebra and Discrete Mathematics. V. 19. No 1. 2015. P. 130-144. [6] V. Ustimenko, On walks of variable length in Schubert incidence systems and multivariate flow ciphers, Dopovidi of Nathional Acad. Sci. of Ukraine, 2014, No 3, P. 55 - 150. [7] N. Koblitz, Algebraic aspects of cryptography, Springer (1998). [8] V. Ustimenko, On Multivariate Cryptosystems Based on Computable Maps with Invertible Decompositions, Annales of UMCS, Informatica, volume 14 (2014) , Special issue “Proceedings of International Conference Cryptography and Security Systems”, pp. 7-18. [9] J. Patarin, The Oil and Vinegar digital signatures, Dagstuhl Workshop on Cryp- tography. 1997. V. Ustimenko 169 [10] Kipnis A., Shamir A., Cryptanalisis of the Oil and Vinegar Signature Scheme, Advances in Cryptology - Crypto 96, Lecture Notes in Computer Science, V. 1462, 1996, P. 257–266. [11] S. Bulygin, A. Petzoldt, and J. Buchmann, Towards provable security of the unbalanced oil and vinegar signature scheme under direct attacks, In Guang Gong and Kishan Chand Gupta, editors, “Progress in Cryptology - INDOCRYPT”, Guang Gong and Kishan Chand Gupta, editors, Lecture notes in Computer Science, V. 6498, 2010. P. 17–32. [12] U. Romanczuk-Polubiec, V. Ustimenko, On two windows multivariate cryptosystem depending on random parameters, Algebra and Discrete Mathematics, 2015, V. 19. No. 1. P. 101–129. [13] F. Harary, Graph Theory, Addison-Wesley Publishing Co, Reading, MA (1966). [14] V. Ustimenko, Maximality of affine group, hidden graph cryptosystem and graph’s stream ciphers, Journal of Algebra and Discrete Mathematics, 2005, v.1, pp 51-65. [15] F.Lazebnik , V. Ustimenko and A.J.Woldar, A new series of dense graphs of high girth, Bulletin of the AMS 32 (1) (1995), 73-79. [16] F. Lazebnik, V. Ustimenko, Explicit construction of graphs with arbitrary large girth and of large size, Discrete Applied Mathematics 60 (1995), 275-284. [17] V. Ustimenko, Coordinatisation of Trees and their Quotients, in the Voronoj’s Impact on Modern Science, Kiev, Institute of Mathematics, 1998, vol. 2, 125-152. [18] V. Ustimenko, CRYPTIM: Graphs as Tools for Symmetric Encryption, Lecture Notes in Computer Science, Springer, LNCS 2227, Proceedings of AAECC-14 Symposium on Applied Algebra, Algebraic Algorithms and Error Correction Codes, November 2001, p. 278-286. [19] V. Ustimenko, Linguistic Dynamical Systems, Graphs of Large Girth and Cryptog- raphy, Journal of Mathematical Sciences, Springer, vol.140, N3 (2007) pp. 412-434. [20] V. Ustimenko, On the graph based cryptography and symbolic computations, Serdica Journal of Computing, Proceedings of International Conference on Application of Computer Algebra, ACA-2006, Varna, N1 (2007). [21] V. Ustimenko, U. Romanczuk, On Extremal Graph Theory, Explicit Algebraic Constructions of Extremal Graphs and Corresponding Turing Encryption Machines, in "Artificial Intelligence, Evolutionary Computing and Metaheuristics ", In the footsteps of Alan Turing Series: Studies in Computational Intelligence, Vol. 427, Springer, January, 2013, 257-285. [22] V. Ustimenko, U. Romanczuk, On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography, in "Artificial Intel- ligence, Evolutionary Computing and Metaheuristics ", In the footsteps of Alan Turing Series: Studies in Computational Intelligence, Volume 427/2012, 257-285. [23] V. Ustimenko, On the cryptographical properties of extreme algebraic graphs, in “Algebraic Aspects of Digital Communications” IOS Press (Lectures of Advanced NATO Institute, NATO Science for Peace and Security Series - D: Information and Communication Security, Volume 24, July 2009, 296 pp. [24] U. Romanczuk-Polubiec, V. Ustimenko, On Multivariate Cryptosystems Based on Polynomially Compressed Maps with Invertible Decompositions, Cryptogra- phy and Security Systems, Third International Conference, CSS 2014, Lublin, 170 On algebraic graph theory in cryptography Poland, September 22-24, 2014. Proceedings, Communications in Computer and Information Science, 448, p. 23-37. [25] M. Klisowski, V. Ustimenko, Graph based cubical multivariate maps and their cryptographical applications, in “Advances on Superelliptic curves and their Applica- tionsions”, IOS Press, NATO Science for Peace and Security series –D: Information and Communication Security, 2015, v. 41, 201, pp. 305-327. [26] A. Tousene, V. Ustimenko, CRYPTALL - a System to Encrypt All types of Data, Notices of Kiev-Mohyla Academy, v. 23, 2004, pp. 12-15. [27] A. Touzene, V. Ustimenko, Graph Based Private Key Crypto System, International Journal on Computer Research, Nova Science Publisher, v. 13 (2006), issue 4, 12pp. [28] J. Kotorowicz, V. Ustimenko, On the implementation of cryptoalgorithms based on algebraic graphs over some commutative rings, Condenced Matters Physics, Special Issue: Proceedings of the international conferences “Infinite particle systems, Complex systems theory and its application", Kazimerz Dolny, Poland, 2006, 11 (no. 2(54)) (2008) 347–360. [29] V. Ustimenko, S. Kotorowicz, On the properties of Stream Ciphers Based on Ex- tremal Directed graphs, In "Cryptography Research Perspectives", Nova Publishers, Ronald E. Chen (the editor), 2008. [30] , A. Touzene, V. Ustimenko, Marwa AlRaisi, Imene Boudelioua, Performance of Algebraic Graphs Based Stream-Ciphers Using Large Finite Fields, Annalles UMCS Informatica AI X1, 2 (2011), 81-93. [31] V. A. Ustimenko, M. Klisowski, On the Comparison of Cryptographical Properties of Two Different Families of Graphs with Large Cycle Indicator, Mathematics in Computer Science, 2012, V. 6, Number 2, pp. 181-198. [32] V. A. Ustimenko, Algebraic groups and small world graphs of high girth, Albanian J. Math, vol3, N1 (2009), 25-33. [33] V. A. Ustimenko, A. Wroblevska, On the key exchange with nonlinear polynomial map of stable degree, arXiv:1304, 2920, v.1. Contact information V. Ustimenko University of Maria Curie Skłodowska in Lublin E-Mail(s): vasyl@hektor.umcs.lublin.pl Received by the editors: 30.09.2015 and in final form 30.09.2015.

On algebraic graph theory and non-bijectivemultivariate maps in cryptography

Institution

Similar Items