Meimei Zhao,Hongyu Wang,Bing Yao
Graphic Groups, Graph Homomorphisms, and Graphic Group Lattices in Asymmetric Topology Cryptography
graphic group,mixed graphic group lattice,graphic coloring,graph homomorphism,graphic category,network encryption
Using asymmetric topology cryptography to encrypt networks on the basis of topology coding is a new topic of cryptography, which consists of two major elements, i.e., topological structures and mathematical constraints. The topological signature of asymmetric topology cryptography is stored in the computer by matrices that can produce number-based strings for application. By means of algebra, we introduce every-zero mixed graphic groups, graphic lattices, and various graph-type homomorphisms and graphic lattices based on mixed graphic groups into cloud computing technology. The whole network encryption will be realized by various graphic groups.
Graphic Groups, Graph Homomorphisms, and Graphic Group Lattices in Asymmetric Topology Cryptography

Using asymmetric topology cryptography to encrypt networks on the basis of topology coding is a new topic of cryptography, which consists of two major elements, i.e., topological structures and mathematical constraints. The topological signature of asymmetric topology cryptography is stored in the computer by matrices that can produce number-based strings for application. By means of algebra, we introduce every-zero mixed graphic groups, graphic lattices, and various graph-type homomorphisms and graphic lattices based on mixed graphic groups into cloud computing technology. The whole network encryption will be realized by various graphic groups.

Cryptography is the core technology and basic support to ensure network and information security. As is well known, modern cryptography and its mathematical theories, such as lattice cryptography, are used as a kind of cryptography to resist quantum computing attacks. From Ref. [1], one can learn more about the importance and research status of lattice cryptography in the design of mathematical problems as well as its development and applications. Xiaogang Wen, an academician of the United States, pointed out in his article entitled “New revolution in physics modern mathematics in condensed matter physics” that “But since the quantum revolution, especially, the second quantum revolution, we are more and more aware that our world is not continuous, but discrete. We should look at the world from the perspective of algebra.” Indeed, the development of modern mathematics proceeds exactly from continuous to discrete as well as from analysis to algebra. Modern mathematics also asserts the notion that discrete algebra is more essential than continuous analysis. Group theory and, in particular, non-Abelian groups provide plenty of supply of complex and varied problems for cryptography. Over the past few decades, group-based cryptography has been extensively studied. For example, in 1999 Anshel and coauthors proposed the commutator key-exchange protocol based on the braid groups [2]. In 2004, Eick and Kahrobaei proposed the polycyclic groups as a new platform for cryptography [3]. These polycyclic groups are a natural generalization of cyclic groups with more complex algorithmic theory. In 2008, Ostrovsky and Skeith III determined sufficient and necessary conditions for the existence of a fully homomorphic encryption scheme (over a non-zero ring) if and only if homomorphic encryption exists over any finite non-Abelian simple group [4]. Since 2016, graph groups have been proposed by Flores, Kahrobaei, and Koberda for various cryptographic protocols as several of the algorithmic problems in these graph groups are NP-complete, which provides quantum-resistant cryptosystems (see, Section 7 of Ref. [5] for more detail). Moreover, in 2019 Kahrobaei and coauthors proposed the nilpotent groups for making multi-linear maps [6]. In 2021, Anshel and coauthors presented the so-called WalnutDSA™ [7], a group-based quantum-resistant public-key digital signature method on the basis of the one-way function E-multiplication. It can provide very efficient means of validating digital signatures, as the authors claimed [7], which is essential for low-powered and constrained devices. Just very recently, a complete overview of the actual state of group-based cryptography in the quantum era was updated by Kahrobaei, Flores, and Noce [8], in which some important encryption groups such as polycyclic groups and graph groups, as well as relevant combinatorial algebraic problems, are reviewed in detail. The advantages of asymmetric encryption are as follows: higher security, the public key is public, and the private key is saved by oneself instead of sharing with others. In Ref. [9], we proposed the graphic group based on the Abelian additive operation of finite modulus in 2017, called every-zero graphic group. Graphic groups were further investigated in detail [10,11,12,13,14]. The mixed graphic group was introduced for the first time in Ref. [15] and then employed to encrypt networks in whole. Moreover, the infinite graphic group was also introduced [16]. Cryptographical graphs should possess the following characteristics: (1) they can be conveniently used in daily activities; (2) they are characterized by strong security, i.e., they are difficult to crack; (3) graphs and colorings (resp. labelings) are available for making topological key-pairs. In the present work, our goal is to propose some techniques of asymmetric topology cryptography for encrypting networks. The present paper is structured as follows. After introducing basic concepts and definitions in Section 1.2, in the following section we shall focus on graphic groups by introducing mixed graphic groups and some particular mixed graphic groups such as infinite mixed graphic groups and their homomorphisms. In Section 3, some graphic lattices will be built up by several every-zero mixed graphic groups for encrypting networks. In Section 4, we will discuss the whole network encryption, such as encrypting tree-like networks.

In the present paper, the terminologies and notations from Refs. [17,18,19], as well as the following notations, will be used. Throughout this paper, let G be a non-trivial simple undirected graph with vertex set and edge set . A graph G is a -graph if and . A tree is a connected acyclic graph, in which a leaf is a vertex of degree one and any two vertices are connected by a unique path. A simple graph is called a complete graph if each pair of distinct vertices is joined by an edge in the graph. A complete graph of n vertices is denoted as . A bipartite graph H holds with such that each edge holds and . The cardinality of a set X is denoted as ; indicates a set with integers holding ; denotes an odd-integer set with odd numbers holding true; and represents the set of all non-negative integers. A graph labeling is an assignment of integers to the vertices or edges, or both, subject to certain conditions. In fact, graph labeling was first introduced in the mid 1960s, and since then approximately 200 graph-labeling techniques have been investigated [20]. In addition, the statement “a W-constraint proper total coloring (resp. labeling)” means one of various graph labelings, or one of various graph colorings hereafter. Graph colorings and labelings that are not defined here can be found in Refs. [20,21]. Motivated by the algebraic category, here we propose the graphic category as follows: Definition 1. A graphic category consists of (i) A set of graphs admitting total colorings; (ii) A set of morphisms from A to B for two graphs , which is denoted as . For two morphisms and , the morphism is called composition, and it satisfies the following two axioms: (1) Associativity law. For morphisms , , and , we have ; (2) Identity law. For any morphism , we have , where and . Definition 2. A set S of graphs admitting X-constraint total colorings is called the X-constraint every-zero mixed graphic group, if there is an Abelian additive operation “” on the elements of S in the following way: arbitrarily take an element as the zero. We define the operation as follows: with computed by with and any preappointed zero . Definition 3 (See also Ref. [22]). Suppose that a -graph G admits a W-constraint total coloring ; a colored Topcode-matrix of the graph G is defined as holding the W-constraint for . Moreover, if G is a bipartite graph with the vertex set and , we stipulate and such that in Equation (3), where “W-constraint” is a mathematical constraint, or a group of mathematical constraints.

Wang et al. have defined the mixed graphic group [15]; here, we present an improved definition of the mixed graphic group as follows: Definition 4. Suppose that a -graph G admits a W-constraint proper total coloring , such that two color sets and hold a collection of restrictions. We define a colored graph set with , we define a W-constraint proper total coloring for every vertex , and for each edge . Lemma 1. Each colored graph set defined in Definition 4 forms an every-zero mixed graphic group based on the Abelian additive operation defined in Definition 2. Proof. By Definitions 2 and 4, we define the Abelian additive operation “” on the colored graph set under a preappointed zero as follows, for each element , where and . As , we have , and thus Equation (4) is equivalent to As , we have , and Equation (4) is also equivalent to Especially, as , we have in Equation (4), and thus we obtain for . When , and in Equation (4), we have for . We show the following facts on the colored graph set : (i) Zero. Each graph can be determined as zero such that . (ii) Uniqueness. For and , we have the facts and under the zero . (iii) Inverse. Each graph has its own inverse holding determined by for each element . (iv) Associative law. Under the zero , each triple holds (v) Commutative law. Each pair of holds under the zero . The proof of the lemma is complete. □ Remark 1. Regarding the proof of Lemma 1, there are (i) By Equations (5) and (6) shown in the proof of Lemma 1, we have with , and with . Thus, we obtain a formula (ii) We call the mixed graphic group every-zero mixed graphic group based on the Abelian additive operation “” defined in Equation (4), denote it as , and we present its matrix expression as follows: (iii) The every-zero mixed graphic group contains graphs in total. There are two particular every-zero graphic subgroups, and , based on the Abelian additive operation. In fact, contains at least every-zero graphic subgroups. Figure 1 shows an every-zero mixed graphic group based on a colored graph set , where and for vertex colors, whereas for edge colors. By using the colored graphs shown in Figure 1, one can readily verify Equation (11): for vertices and edges. Theorem 1. Each every-zero mixed graphic group defined in Remark 1; Definitions 3 and 4 form a graphic category based on a preappointed zero defined in Definition 1. Proof. We define a graphic morphism from to by the Abelian additive operation based on a preappointed zero , that is, . Notice that , so . For , we define the composition of two graphic morphisms as follows: and So, we have Since for and for , the identity law in Definition 1 holds true. The associativity law stands for graphic morphisms. In general, by using Equations (13) and (14) repeatedly, we can obtain a graphic morphism composition as follows: and the graphic morphism triangular law. We claim that the every-zero mixed graphic group forms a graphic category based on the graphic morphism set for the preappointed zero . □ Theorem 2. Each every-zero mixed graphic group defined in Definitions 3 and 4 forms m graphic categories such as , shown in the proof of Theorem 1, for each , where m is the number of elements of the every-zero mixed graphic group . Theorem 3. A Topcode-matrix group based on an every-zero mixed graphic group defined in Definitions 3 and 4 forms a Topcode-matrix category defined in Definitions 1 and 3. Remark 2. (i) We take three Topcode-matrices where the Topcode-matrix set is made by the Topcode-matrices of the colored graphs of the every-zero mixed graphic group shown in Figure 1. Let be zero; we compute under the edge modular and the vertex modular . By using the Abelian additive operation “”, it is not hard to verify the Topcode-matrix set forms a Topcode-matrix group. (ii) From Definition 3, each Topcode-matrix generates number-based strings for real application. As can be seen from Equation (17), the Topcode-matrix can induce the following number-based strings: for encrypting digital files of information networks. (iii) Notice that a Topcode-matrix corresponds to two or more graphs, which are mutually not isomorphic from each other in general; see Figure 2 for examples. Coloring a connected graph with the elements of a Topcode-matrix group is a new topic in the Topcode-matrix category. Theorem 4. For two every-zero mixed graphic groups and defined in Remark 1, suppose that and , and there are graph homomorphisms defined by such that each edge corresponds to an edge for . Then, we obtain an every-zero mixed graphic group homomorphism,

In Ref. [23], the authors introduced several matching colorings (resp. labelings) of graphs and also pointed out matching diversity: configuration matching partition, coloring matching partition, set matching partition, matching chain, one-vs.-more and more-vs.-more styles of matching partitions, configuration-vs.-configuration, configuration-vs.-labeling, labeling-vs.-labeling and (configuration, labeling)-vs.-(configuration, labeling), etc. Moreover, Wang et al. [15,24] introduced the twin odd-graceful labelings: Suppose is an odd-graceful labeling of a -graph G with p vertices and q edges, and is a labeling of another graph H with vertices and edges such that each edge has its own color defined as and the edge color set ; we say is a twin odd-graceful labeling, and H a twin odd-graceful matching of G. Figure 3 shows some examples of the twin odd-graceful matchings. By the notation of Remark 1, we can obtain a twin odd-graceful mixed graphic groups and based on a twin odd-graceful labeling . Notice that , or , in general.

Suppose that a -graph G admits a W-constraint total coloring . Let and . We call the total coloring for each element totally dual W-constraint total coloring of the total coloring f. Notice that Then, is called a dual mixed graphic group of the mixed graphic group based on a pair of mutually dual W-constraint colorings f and g. Notice that these two mixed graphic groups are built up on the same graph G. Respectively, we call (i) for each vertex and for each edge vertex-dual W-constraint coloring of G, where and ; (ii) for each edge and for each vertex edge-dual W-constraint coloring of G, where and ; (iii) defined in (i) and (ii) ve-separately dual W-constraint coloring of the total coloring f. Figure 4 shows some examples for illustrating the four dual colorings mentioned above.

If a -graph G is bipartite and admits a set-ordered graceful labeling f, there is a dozen of labelings equivalent to f [21,25], and thus we obtain a dozen matching mixed graphic groups and with for . For example, these labelings are odd-graceful labeling, odd-elegant labeling, edge-magic total labeling, image-labeling, 6C-labeling, odd-6C-labeling, even-odd separable 6C-labeling, and so on (see Ref. [23] for details). Here, we refer to the mixed graphic group as a private-key, and each mixed graphic group with as a public-key in encrypting networks. The complement of a simple graph G is the simple graph with vertex set , and two vertices are adjacent in if and only if they are not adjacent in G. So, we have and as a pair of matching mixed graphic groups, where admits a W-constraint coloring g. In general, for a graph with and , we have and as a pair of matching mixed graphic groups based on the graph , where H admits a W-constraint coloring h. Figure 5 shows the complementary graph of a given graph and some labellings generated from a given set-ordered graceful labelling of the graph .

From Definition 4, we obtain an every-zero infinite mixed graphic group with based on a -graph G admitting a W-constraint proper total coloring f and , where “” is the Abelian additive operation “” under a preappointed zero for any pair of graphs . Remark 3. The elements of an every-zero infinite mixed graphic group defined in Equation (19) can fully tile each integer point of the -plane. Moreover, contains infinite every-zero mixed graphic groups having finite elements, such as and . Additionally, contains infinite every-zero mixed graphic groups having infinite elements. is also a graphic category under the graphic morphism composition defined in Equation (16). Particular every-zero mixed graphic groups having infinite elements, or finite elements can be used easily to randomly encrypt networks. Theorem 5. (i) Suppose that the coloring f of the -graph G based on an every-zero infinite mixed graphic group is equivalent to another -constraint total coloring g of the -graph G based on an every-zero infinite mixed graphic group . If a mapping exists such that for , then we obtain an every-zero infinite mixed graphic group homomorphism, (ii) Suppose a graph homomorphism from a -graph G to a connected graph H based on a mapping such that each edge corresponds to an edge , and vice versa. Suppose that the -graph G admits a W-constraint total coloring f, and the graph H admits a -constraint total coloring h. Then, we obtain an every-zero infinite mixed graphic group homomorphism as follows: Notice that, in general, .

Definition 5. Using an every-zero mixed graphic group defined in Remark 1 to encrypt a connected graph H by a mapping such that each edge holds under a preappointed zero , we obtain another graph L from the set , , by joining some vertices of the graphs and together with some vertices of the graph via edges, respectively. In Figure 6, we first use an edge coloring to color the edges of the uncolored graph H by the elements of the every-zero mixed graphic group shown in Figure 1, and then an edge-colored graph is obtained by expending this mixed graphic group edge coloring to the vertex set , which is followed by the totally colored graph . Moreover, the totally colored graph is a colored graph homomorphism to , that is, . From the proof of Lemma 1, we use the elements of an every-zero mixed graphic group based on the Abelian additive operation “” defined in Equation (4) to make a mixed graphic lattice base, i.e., where . Definition 6. With the notation of Equation (22), we can write the graph L in Definition 5 as and call the following set:under a preappointed zero mixed graphic group latticebased on a mixed graphic lattice base , where and is a set of graphs with vertex number and edge number . Moreover, we call the following set: mixed graphic -group latticesince each element of the mixed graphic lattice base can be referred to as zero under the Abelian additive operation. Remark 4. Regarding Definition 5, we have (i) In general, two graphs and are not isomorphic from each other for two different zeros . (ii) There are many different ways to join the graph with two graphs and by edges in Definition 5; in other words, the number of graphs of forming is two or more, see Figure 7. (iii) Since two graphs form two homomorphically equivalent graph homomorphisms , we obtain the following mixed graphic group lattice homomorphisms: This technology has great potential for cloud computation in the future of quantum computing.

In the following discussion, we will use traditional complementary graphs and G-complementary graphs to build up graphic lattices.

Let be the complement of a simple graph G; then, we say that is a complete-graphic matching. For a graph operation “”, we have a complementary mixed graphic lattice where the mixed graphic lattice base is defined in Equation (22), is the set of all complements of graphs of defined in Definition 6, and . Let be the complementary base of the mixed graphic lattice base with the complement of for . We obtain a complementary mixed graphic lattice with . Moreover, we obtain a totally complementary mixed graphic lattice as follows: with . We call and a matching of complementary mixed graphic lattices. However, for each graph of , the complementary graph of is not a graph of , in general.

A graph G has two proper subgraphs and such that , , and . Thereby, we call a G-matching. Accordingly, we have the G-complementary mixed graphic lattice like that defined in Equation (28).

In asymmetric topology cryptography, one would encrypt graphs (resp. networks) by mixed graphic groups, and we call these colorings mixed graphic group colorings. For the number of graphs of n vertices, Harary and Palmer [26] computed two graph numbers The large number of graphs, and of colorings in graph theory, can provide us with flexible and diverse asymmetric topology technology with stable security performance and can also increase the technical cost and intolerable time cost to the cracker. Encrypting networks in whole is an application of mixed graphic groups and mixed graphic group lattices.

Here, we present a proof for the following theorem, as shown partly in Ref. [16]: Theorem 6. For each graph L of a graphic -group lattice defined in Definition 5, Equations (23) and (24) form an every-zero mixed graphic group defined in Remark 1, where the graph L admits a total coloring α. Proof. Suppose that a -graph G admits a total coloring f and L is a graph of a graphic -group lattice , so as defined in Equation (23) and Definition 5. Notice that each graph defined in Remark 1 admits a W-constraint proper total coloring in Definition 4. Suppose the graph L admits a total coloring , then each edge holds , and , such that with and , under a preappointed zero . In the graph L, there is at least one edge between and , and there is at least one edge between and . Now, let us define a total coloring for the graph L as follows: (i) for each element if . (ii) For an edge holding and , we color this edge with . Next, we shall make the copies of the graph L with for and , where and , and then put the copies into a set . Moreover, we define a total coloring for each graph by setting (i) for each vertex ; (ii) for each edge ; (iii) For an edge holding and , we color this edge with . For a preappointed zero , we have the following Abelian additive operation “”: for any two graphs , such that holds true as and . We show that the set holds the following facts: (i) Zero. Every graph can be as zero such that for any graph of . (ii) Closure law. For each preappointed zero , we have (iii) Inverse. Every graph has its own inverse with and , such that . (iv) Associative law. . (v) Commutative law. . Thereby, the set forms an every-zero mixed graphic group, denoted as , and the set is a graphic category under the graphic morphism composition defined in Equation (16). We can define another total coloring for each graph by making (i) for each vertex ; (ii) for each edge ; (iii) For an edge holding and , we color this edge with , such that the set forms an every-zero mixed graphic group . The proof of the theorem is complete. □

As tree-like networks are easily accessible in real applications, have simple structures, and admit a lot of colorings, we will apply mixed graphic group colorings to encrypt tree-like networks. A tree T admits a mixed graphic group total coloring as defined in Remark 1, where . Theorem 7. A tree T with its maximum degree Δ admits a mixed graphic group total coloring θ from to a mixed graphic group defined in Remark 1 and , such that for any pair of adjacent edges and of T. Proof. We construct another tree by removing a leaf w of the tree T, where the leaf w is adjacent to the vertex z of T, and keep the maximum degree . Assume that the tree admits a mixed graphic group total coloring h from to a mixed graphic group defined in Remark 1 and , such that the colors for any pair of adjacent edges and of H. Let be the set of neighboring vertices of the vertex z in the tree T. We define a mixed graphic group total coloring as for , , and , such that under a preappointed zero . We obtain the proof of the theorem. □ Theorem 8. Each tree T of n edges admits amixed graphic group total coloring θ from to a mixed graphic group defined in Remark 1, such that the edge index set , where with for is a preappointed index set. Proof. Assume that any tree T of edges holds this theorem and T admits a mixed graphic group total coloring , such that each edge is colored with under a preappointed zero , and the edge index set is just We add a new vertex w to the tree T by joining w with any vertex x of T via a new edge . The resulting tree is denoted as . Obviously, the tree H has n vertices. We define a mixed graphic group total coloring , such that each element is colored with . For the vertex w and the edge of the tree , we set and such that with and , where the edge color set . Finally, we obtain the desired edge index set and the theorem follows from the induction. □ Corollary 1. If a connected graph H of n edges admits amixed graphic group total coloring θ from to a mixed graphic group defined in Remark 1, such that the edge index set , where with for is a preappointed edge index set, then the connected graph H corresponds to at least a tree T of n edges such that T holds Theorem 8, and there is a colored graph homomorphism . Theorem 9. The edges of a tree T can be colored arbitrarily by a mixed graphic group proper edge coloring φ from the edge set to a mixed graphic group defined in Remark 1, and then this mixed graphic group proper edge coloring φ can be expended to the vertex set , such that each edge holds under a preappointed zero . Proof. Let be a preappointed zero. Suppose that a tree T of p vertices admits a mixed graphic group edge coloring , and this coloring F has been expended to , such that for each edge , and for any pair of adjacent edges . We construct a new tree by adding a new vertex w to the tree T and a new edge with . For this new tree H, we define a mixed graphic group edge coloring with if , and the mixed graphic group edge coloring can be expended to , such that for each edge by the induction. Next, we take and holding with . Finally, we expend the mixed graphic group proper edge coloring to , such that for each edge , and for any pair of adjacent edges ; thus, the induction is complete. □

For the encryption of dynamic networks, we define the following every-zero dynamically mixed graphic group: an every-zero dynamically mixed graphic group is based on a dynamically colored graph set with for , where a -graph admits a W-constraint proper total coloring for , and each graph admits a W-constraint proper total coloring for every vertex , and for each edge . Obviously, for forms dynamically graphic categories. With the dynamically colored graph set , we have a dynamically mixed graphic lattice base as follows: where . For a graph operation “”, we have a dynamically mixed graphic lattice such that each network is encrypted to another graph for , where . As the graph operation “” in Equation (34) is the vertex-coinciding operation, an example is shown in Figure 8.

To summarize, in the present contribution we firstly defined the graphic category, generalized the mixed graphic groups, and proposed the graphic lattices and various graph-type homomorphisms, from which some useful results were obtained. Based on these results, we then discussed in detail how to encrypt networks in whole by using the mixed graphic groups and the mixed graphic group lattices. In the end, the graphic lattices for the encryption of the dynamic networks were introduced, and the vertex-coinciding operation in the dynamically mixed graphic lattice was illustrated on the basis of the every-zero mixed graphic groups.