A novel application on mutually orthogonal graph squares and graph-orthogonal arrays

Abbreviations: MOLS: Mutually orthogonal Latin squares; MOGS: Mutually orthogonal graph squares; BIBD: Balanced incomplete block designs; $kF$: $k$ isolated copies of graph $F$; ${K}_{m}$: Complete graph with $m$ vertices; ${K}_{m, n}$: Complete bipartite graph with size $m+n$ where vertices are classified into two sets with sizes $m$ and $n$; ${P}_{m}$: Path graph on $m$ vertices; $E\left(G\right)$: Edge set of graph $G$; $V\left(G\right)$: Vertex set of graph $G$; $G$∪$H$: Disjoint union of graphs $G$ and $H$; ${P}_{I}$ or ${P}_{0}$: Probability of successful impersonation attacks; ${P}_{s}$ or ${P}_{1}$: Probability of successful substitution attacks; ${X}_{n}$: The set {1, 2, …, $n$}; $L(x, y)$: Entry in row $x$ and column $y$ of square matrix $L$

1.   Introduction

Nowadays, information technology is widely used in almost all disciplines around the world. Convenience to people's lives has been brought due to the unprecedented revolution of network technology. At the same time, a huge and tough problem also arises in front of human beings-information security issues, such as information leakage, viruses, tampering, and so on. Since ancient times, people have realized the importance of protecting the confidentiality of sensitive messages. Cryptology (secret writing) has been an established problem. This science was mainly concerned with diplomatic and military applications for a long period. In the modern era, storing and transmitting information has become cheap and simple based on strong techniques of information. There is a way by which a huge amount of information can be transferred, but almost anyone can access it. Security communications have several problems such as data integrity, confidentiality authentication, secret sharing, hidden information, and non-repudiation. Such problems can be solved by steganography and cryptography. Some means and methods are used to prevent information from being stolen or damaged to ensure information security. In this section, we just introduce a brief overview of previous works and a summary of our contributions. In 1948, a mathematical theory of communication was presented by Shannon ^[1]. This topic gave birth to information theory. In 1974, the authors of ^[2] proposed authentication codes. Simmons introduced the authentication code model described in ^[3,4,5,6]. Cryptology is associated with many new problems. For instance, an adversary can read transmitted messages and change them. Also, an adversary could intervene illegally to construct and send a fraudulent message to a receiver, and he or she hopes that the receiver takes a wrong decision.

A receiver may be worried about changing the content of a message by an adversary in transmission. Also, a receiver is worried about knowing a real sender. Authentication of messages takes care of these two major points. In modern times, the two important aspects of information security are authentication and secrecy problems. Authentication protection can be obtained by an authentication scheme, while secrecy protection can be obtained by a secrecy scheme. Authentication and secrecy are two independent aspects of information security. In some situations, secrecy may be essential, and in other situations, it is not essential. Moreover, secrecy may or may not be taken into account in the authentication scheme. Authentication is responsible for the protection of messages from tampering and impersonating by a deceptive adversary, and secrecy protects sensitive messages from eavesdropping.

An adversary can cheat a receiver. Before a transmitter sends any message to a receiver, an adversary can send a bogus message to a receiver, and a receiver will accept it as a genuine message. This may lead to a wrong decision taken by a receiver. What an adversary did, in this case, is called an impersonation attack. Also, an adversary can launch another kind of attack called a substitution attack. Also, an adversary can launch another kind of attack called a substitution attack. In a substitution attack, an adversary can change the content of an observed message. And a receiver also accepts it; this will lead to a different action from what a transmitter intended. Authentication code prevents these attacks. The probability of a successful impersonation attack is denoted by ${P}_{I}$ or ${P}_{0},$ and the probability of a successful substitution attack is denoted by ${P}_{s}$ or ${P}_{1}.$

There is a wide and considerable literature on authentication codes. The authors in ^[7] constructed authentication codes using groups. Some linear authentication codes were constructed in ^[8]. Bipartite graphs were used to construct authentication codes with secrecy ^[9]. From geometries over finite fields, several authors constructed Cartesian authentication codes, see, for example, ^{[10,11,12,13,14,15,16,17]}. Authentication codes without splitting were studied in several papers ^{[18,19,20,21,22,23,24,25,26]}, while De Soete handled authentication codes with splitting in ^[27]. Optimal authentication codes also were intensively studied ^{[5,24,28,29,30]}. In authentication codes, "optimal" means that the number of keys (encoding rules) and deception probabilities are as small as possible. Combinatorial structures such as difference sets, BIBDs, external BIBDs (EBIBDs), splitting BIBDs, and external difference families (EDFs) were used for constructing optimal authentication codes. And also, in a reverse way, optimal authentication codes were used to construct some of the aforementioned combinatorial structures. In this paper, we propose a new combinatorial structure based on MOGS which correspond to mutually orthogonal edge decompositions of complete bipartite graphs by several graphs such as paths, stars, disjoint union of graphs, and so on. Additional background material for this field may be found in ^{[31,32,33,34,35,36]}.

The main contributions made in this manuscript are the following: The decomposition of complete bipartite graph ${K}_{n, n}$ can be constructed by a large number of graphs such as stars, paths, cycles, and so forth. We tried to find mutually orthogonal decompositions of${K}_{n, n}.$These decompositions can be converted to MOGS. Then these graph squares are used to construct graph-orthogonal arrays. By these graph-orthogonal arrays, we can construct a large number of authentication codes where there is a large number of graphs that can be used for decompositions of complete bipartite graph ${K}_{n, n}$. Hence, if an opponent knows the used code generated by a certain graph, then we can use another graph for the construction of an authentication code. Also, for each graph, we will get a code with new characteristics. Our work is considered a directed application for graph decompositions of ${K}_{n, n}$ in coding theory. This is a new proposal, and it will open a new horizon for research in this direction, and it will be the beginning of a lot of future work. This proposal leads to the construction of Cartesian authentication codes with splitting and non-splitting. In both cases, we prove that the constructed authentication codes are perfect. There is a special case of MOGS called mutually orthogonal Latin squares (MOLS) which are used for constructing optimal authentication codes. Also, we use Latin squares to construct secure authentication codes.

The remaining part of the paper is organized into the following six sections. Detailed definitions and basic results on graph-orthogonal arrays and MOGS are found in Subsection 2.1, while Subsection 2.2 describes basic theorems and definitions of authentication schemes and the probability of successful deceptions. Section 3 studies the construction of general perfect non-splitting Cartesian authentication codes based on MOGS. Section 4 studies the construction of general perfect splitting Cartesian authentication codes based on MOGS. The focus of Section 5 is on the construction of optimal authentication codes based on MOLS that are considered a special case of MOGS. Authentication codes with confidentiality based on graph squares are presented in Section 6. Finally, some concluding remarks are given in Section 7.

2.   Preliminaries

2.1.   Related definitions and theorems of graph-orthogonal arrays and MOGS

In this subsection, we present definitions of graph-orthogonal arrays and MOGS, along with a few basic results.

Definition 1 (^[37]). Assume that $G$is a subgraph of ${K}_{n, n}$ with size $n$. A square matrix $L$of order $n$is called a $G$-square if each element in ${X}_{n} = \left\{\mathrm{1, 2}, .., n\right\}$appears precisely $n$times in $L$, and all the graphs ${G}_{i}$where $E\left({G}_{i}\right) = \left\{\left({x}_{0}, {y}_{1}\right):L\left({x}_{0}, {y}_{1}\right) = i, i\in {X}_{n}\right\}$ are isomorphic to $G.$The index set for the rows of $L$ is the set ${X}_{n}\times \left\{0\right\}$ and the index set for the columns of L is the set ${X}_{n}\times \left\{1\right\}$. Each $G$-square of order $n$ represents an edge decomposition of ${K}_{n, n}$ by the graph $G.$

Example 1. An edge decomposition of ${K}_{3, 3}$ by ${K}_{1, 3}$ is shown in Figure 1. There is a $G$-square L of order 3 corresponding to this decomposition, where $G$ is isomorphic to ${K}_{1, 3}.$ Here n = 3, ${X}_{3} = \left\{\mathrm{1, 2}, 3\right\}.$ The ${K}_{1, 3}$-square can be represented as sollows:

From L, it is clear that the rows are indexed by ${X}_{3}\times \left\{0\right\} = \left\{{1}_{0}, {2}_{0}, {3}_{0}\right\},$the columns are indexed by ${X}_{3}\times \left\{1\right\} = \left\{{1}_{1}, {2}_{1}, {3}_{1}\right\},$ and each element in ${X}_{3} = \left\{\mathrm{1, 2}, 3\right\}$ appears precisely 3 times in L. From Figure 1, the edge set and the vertex set for ${G}_{1}, {G}_{2},$ and ${G}_{2}$ are as follows:

Definition 2 (^[37]). Let ${L}_{1}$ be a G-square of order $n$ with entries from a set $A$ and ${M}_{2}$ be a G-square of order $n$ with entries from a set $B$. Then ${L}_{1}$ and ${L}_{2}$ are orthogonal if, for every $a\in A$ and for every $b\in B$, there is exactly one cell $\left({x}_{0}, {y}_{1}\right)$ such that ${L}_{1}\left({x}_{0}, {y}_{1}\right) = a$ and ${L}_{2}\left({x}_{0}, {y}_{1}\right) = b$. A set of $k$ G-squares of order $n$, say ${L}_{1}, \dots, {L}_{k}$, are called mutually orthogonal (pairwise orthogonal) G-squares (MOGS) if ${L}_{i}$ and ${L}_{j}$ are orthogonal for all $1\le i < j\le k.$

Notice that in this paper, we consider $A = B = {X}_{n}.$

Example 2. Three MOGS for the graph ${P}_{4}$ are represented by the squares ${L}_{1},$ ${L}_{2},$ and ${L}_{3}$. Also, three MOGS for the graph ${P}_{3}\cup {K}_{\mathrm{1, 1}}$ are represented by the squares ${M}_{1},$ ${M}_{2},$ and ${M}_{3}$. See Figure 2 for more illustration.

The superimposition of ${L}_{1}$ and ${L}_{2}$ is as follows:

All the ordered pairs are different and equivalent to ${X}_{3}\times {X}_{3} = \left\{\mathrm{1, 2}, 3\right\}\times \left\{\mathrm{1, 2}, 3\right\}.$ Hence, ${L}_{1}$ and ${L}_{2}$ are orthogonal. Similarly, the orthogonality between ${L}_{1}$and ${L}_{3}$, ${L}_{2}$and ${L}_{3}$, ${M}_{1}$ and ${M}_{2}$, ${M}_{1}$ and ${M}_{3}$, ${M}_{2}$ and ${M}_{3}$ can be shown.

Theorem 1 (^[38]). For every bipartite graph $G$ with $n\ge$2 edges, we have $N\left(n, G\right)\le n$, where $N\left(n, G\right)$ refers to the maximal number of $G$-squares in the largest possible set of mutually orthogonal G-squares of order $n.$

There are several results on MOGS in the literature. For a survey on MOGS, see ^{[37,38,39,40,41,42,43,44,45]}.

Definition 3 (^[46]). Suppose $B$ is a symbol set with cardinality $\left|B\right| = m\ge 1,$ $\mu,$ and $\lambda \ge 2$ are integers. An orthogonal array $A$ is an ${\mu m}^{2}\times \lambda$array with entries from $B$ such that within any two columns from $A$, every ordered pair of symbols from $B$ occurs in exactly $\mu$ rows of $A$, denoted as $OA\left(m, \lambda, \mu \right)$.

Definition 4. If we have $\lambda$ mutually orthogonal $m\times m$ $G$-squares, then by converting each $G$-square to an ${m}^{2}\times 1$ array by juxtaposing the $m$ columns of the $G$-square, then we have $\lambda$ arrays with ${m}^{2}\times 1$ dimension, then by combining these arrays we get an ${m}^{2}\times \lambda$ array which is called a graph-orthogonal array $G$-$OA\left(m, \lambda, 1\right)$.

Proposition 1 (^[40]). If we have $\lambda$ mutually orthogonal $m\times m$ $G$-squares based on $m$ symbols, then, we can obtain a $G$-orthogonal array $G$-$OA\left(m, \lambda, 1\right).$

Proof. The construction technique is as follows. Convert each of the $\lambda$ mutually orthogonal $m\times m$ $G$-squares to an ${m}^{2}\times 1$ array by juxtaposing the $m$ columns of the $G$-square. Then, these arrays are combined to construct an ${m}^{2}\times \lambda$ array. Since there are $\lambda$ mutually orthogonal $G$-squares based on $m$ symbols, the number of the levels equals $m. \mathrm{Furthermore}$, since the $\lambda$ $G$-squares are mutually orthogonal, then the superimposition of any two columns of the ${m}^{2}\times \lambda$ array gives ${X}_{m}\times {X}_{m},$ $i.e.$, the ${m}^{2}\times \lambda$ array has strength two. Every ordered pair of symbols from ${X}_{m}$ occurs in exactly one row of $G$-$OA\left(m, \lambda, 1\right).$

Example 3. We have 3 MOGS ${A}_{1}, {A}_{2},$ and ${A}_{3}$ ($4{K}_{2}$-squares)$.$ Then$,$ there is an $4{K}_{2}$-$OA\left(\mathrm{4, 3}, 1\right)$ that can be represented by $\mathcal{A}$,

In what follows, we assume that the probability distribution of sources and encoding rules is uniform.

2.2.   Basic theorems and definitions of authentication codes

A transmitter, receiver, and adversary are three participants in the authentication model considered in this paper. A sequence of source states can be conveyed to a receiver by a transmitter. An adversary can deceive a receiver by impersonating a transmitter and sending fraudulent messages or tampering with messages sent to a receiver. Transmitter and receiver must cooperate to deal with a spoofing attack by an adversary. Both sender and receiver must trust each other in this model.

In what follows, the set of all sources states that a transmitter will send to a receiver will be denoted by $\mathcal{G}$. Source states are encoded based on one encoding rule for protecting source states from an adversary attack. The set of all encoding rules will be denoted by $\mathcal{H}.$ The set of all possible encoded messages will be denoted by $\mathcal{R}$. The one-to-one mapping $h\in \mathcal{H}$ is a mapping from $\mathcal{G}$ to $\mathcal{R}$. There is always an agreement between the transmitter and the receiver on an encoding rule $h$ before the transmission process. The encoding rule $h$ is considered a secret to an adversary. The source states are encoded using $h$ by a transmitter. Then, through an insecure public channel, encoded messages are transferred. A receiver receives a message sent by a transmitter and checks whether it belongs to the range$h\left(\mathcal{G}\right)$. Only messages belonging to the range$h\left(\mathcal{G}\right)$ will be accepted as authentic. It is assumed that the adversary is fully familiar with the system, including all encoding rules. But, the particular encoding rule known by a transmitter and a receiver is unknown to an adversary. If the fraudulent message of the adversary is compatible with the used encoding rule, then the adversary is successful in his attack. The possibility of successful deception by an adversary can be decreased by repeatedly alternating the used encoding rule. Formally, the authentication code can be defined as follows.

Definition 5 (^[47]). Suppose $\mathcal{G},$ $\mathcal{H},$ and $\mathcal{R}$ are three non-empty finite sets, where $\mathcal{G}$ is the set of source states, $\mathcal{H}$the set of encoding rules, and $\mathcal{R}$the set of encoded messages. Suppose $\phi :\mathcal{G}\times \mathcal{H}\to \mathcal{R}$ is a map, then the four tuple$(\mathcal{G}, \mathcal{H}, \mathcal{R}; \phi$) is called an authentication code, if

(i) the map $\phi$ is surjective and

(ii) for any $r\in \mathcal{R}$ and $h\in \mathcal{H},$ if there is an element $g\in \mathcal{G}$ satisfying $\phi \left(g, h\right) = r,$ then such an element $g$ is uniquely determined by the given $r$ and $h$.

Now, we show the parameters of an authentication code as follows: $\left|\mathcal{G}\right| = \alpha,$ $\left|\mathcal{H}\right| = \beta,$ and $\left|\mathcal{R}\right| = \gamma.$ Hence, the authentication code can be denoted by $AC\left(\alpha, \beta, \gamma \right).$ For the authentication code, we can construct a $\beta \times \alpha$ encoding matrix $\left(A\right)$. Rows of $A$ correspond to the encoding rule of an authentication code, and columns of $A$ correspond to the source of an authentication code.

Definition 6 (^[47]). Let $g\in \mathcal{G},$ put $\mathcal{R}\left(g\right) = \{r\in \mathcal{R}|r = h\left(g\right)$ for some $h\in \mathcal{H}\}.$ The set $\mathcal{R}$ represents messages that can be used to transmit the source state $g.$ If $\mathcal{R}\left({g}_{1}\right)$ and $\mathcal{R}\left({g}_{2}\right)$ are disjointed, for any two source states ${g}_{1}$ and ${g}_{2}$, the authentication codes, in this case, are called Cartesian codes. Cartesian codes have no secrecy since one may know the source state once the transmitted message is observed.

In a simplified way, Cartesian authentication codes can be redefined as follows: regardless of the used encoding rule, if you know the message$r$, you can know the corresponding source $g$, so the Cartesian authentication codes are without secrecy.

Definition 7 (^[47]). Let $(\mathcal{G}, \mathcal{H}, \mathcal{R}; \phi$) be an authentication code. This authentication code is called non-Cartesian if for any $r\in \mathcal{R}$ and $h\in \mathcal{H},$ there is a unique $g\in \mathcal{G}$ such that $\phi \left(g, h\right) = r.$ Non-Cartesian authentication codes are with secrecy.

Definition 8 (^[46]). Let $(\mathcal{G}, \mathcal{H}, \mathcal{R}; \phi$) be an authentication code. This authentication code is said to have splitting if, under the same encoding rule $h\in \mathcal{H},$ more than one message corresponds to a source state $g\in \mathcal{G}.$

Definition 9 (^[47]). Let $(\mathcal{G}, \mathcal{H}, \mathcal{R}; \phi$) be an authentication code. This authentication code is said to have no splitting if $g$ can only correspond to one message $r$ under the action of $h.$

Definition 10 (^[47]). The Cartesian authentication code $(\mathcal{G}, \mathcal{H}, \mathcal{R}; \phi$) is called an optimal Cartesian authentication code if $\left|\mathcal{G}\right| = \alpha +1,$ $\left|\mathcal{H}\right| = {\alpha }^{2},$ $\left|\mathcal{R}\right| = \alpha \left(\alpha +1\right)$ and ${P}_{0} = {P}_{1} = \frac{1}{\alpha }$.

Definition 11 (^[47]). For the authentication code $(\mathcal{G}, \mathcal{H}, \mathcal{R}; \phi$), if ${\mathrm{log}}_{2}{P}_{0} = {\mathrm{log}}_{2}{P}_{1} = -$I($\mathcal{R}$; $\mathcal{H}$), then the authentication code, in this case, is perfect, where

where $H\left(\mathcal{R}\right)$ is the entropy of $\mathcal{R},$ $H\left(\mathcal{R}|\mathcal{H}\right)$ is the entropy of $\mathcal{R}|\mathcal{H}$, and $P$ refers to the probability.

In perfect authentication codes, it can be seen that ${P}_{0}$ and ${P}_{1}$ are the minimum. For the probability of a successful impersonation attack ${P}_{0}$, there is an agreement between a sender and a receiver about the encoding rule $h$ in advance.

In impersonation attacks, an adversary does not know which authentication tag each source corresponds to under this encoding rule $h.$ Hence, an adversary arbitrarily selects a source $g$ and an authenticator $a\in T$($T$ refers to the set of authentication tags). Impersonation attacks succeed if the message $\left(g, a\right)$ satisfies $h\left(g\right) = a$, and ${P}_{0}$ can be expressed as follows:

For the probability of a successful substitution attack ${P}_{1},$ there is an agreement between a sender and a receiver about the encoding rule $h$ that acts on the message $r.$ A message $r = \left(g, a\right)$ is transmitted by a transmitter to a receiver, where $h\left(g\right) = a\in T.$ Then, a message $\stackrel{´}{r} = \left(\stackrel{´}{g}, \stackrel{´}{a}\right)$ is sent by an adversary to replace the message $r = \left(g, a\right)$, where $h\left(\stackrel{´}{g}\right) = \stackrel{´}{a}\in T,$ $\stackrel{´}{g}\ne g$. That is, $h$ is in the set $\left\{h\in \mathcal{H}|h\left(g\right) = a, h\left(\stackrel{´}{g}\right) = \stackrel{´}{a}\right\}$, and the substitution attack is successful. The probability of substitution attack ${P}_{1}$ can be expressed as follows:

An authentication code enables a sender to encode a message using a secret key. Then, by the same key, a designated receiver can decode the message. Flow diagrams for the encoding and decoding for authentication codes are shown in Figures 3 and 4, respectively ^[48].

3.   MOGS and general non-splitting Cartesian authentication codes

In this section, we will use MOGS and graph-orthogonal arrays to construct general non-splitting Cartesian authentication codes. We first construct a graph-orthogonal array by $k$ MOGS of order $n$. Then there is a mapping between the graph-orthogonal array and the message set by using the property of the graph-orthogonal array. And an encoding matrix for the Cartesian authentication code is obtained. Secondly, we get a perfect Cartesian authentication code when we obtain an encoding matrix by a graph-orthogonal array. Besides that, in this paper, some new Cartesian authentication codes can also be obtained by transforming a graph-orthogonal array in column order, or partition of a message set or changing the mapping between a message set and an authentication tag. Thus, it can be said that the used construction method has global significance from a theoretical point of view. For more illustration, see Figure 5 that shows a flow chart for the proposed algorithm in this paper. Also, a pseudo code for the proposed algorithm can be described as follows:

Input: Complete bipartite graph ${K}_{n, n}.$

Output: Authentication code.

1. Constructing $k$mutually orthogonal edge decompositions of ${K}_{n, n}$ by $G.$

2. Generating $k$ mutually orthogonal $G$ squares of order $n$.

3. Constructing a $G$-orthogonal array $OA\left(n, k, 1\right)$.

4. Generating an authentication code using the $OA\left(n, k, 1\right)$.

5. End.

Suppose we have $k$ MOGS of order $n:$ ${M}_{1}, {M}_{2}, \dots, {M}_{k}.$ From Theorem 1, $k\le n$. Suppose ${M}_{\alpha }^{\omega }$refer to the $\omega \, {\text{th}}$column of ${M}_{\alpha }.$ Based on Proposition 1, the following graph-orthogonal array can be constructed.

The graph-orthogonal array $Z$ is an orthogonal array $OA\left(n, k, 1\right)$. The matrix $Z$ will be used as an encoding matrix for the authentication tag.

Let $Z = \left({A}_{1}, {A}_{2}, \dots, {A}_{k}\right)$, where ${A}_{\alpha }\left(1\le \alpha \le k\right)$ is the $\alpha$th column of $Z.$ Now, n different symbols inside ${A}_{\alpha }$ can be represented by ${A}_{\alpha }\left(1\right), {A}_{\alpha }\left(2\right), \dots, {A}_{\alpha }\left(n\right).$ In the matrix Z, $\mathrm{1, 2}, \dots, n$ are n different authentication tags, and the messages set $\mathcal{R}$ consists of $nk$ ordered pairs $\left(g, a\right),$ where $g\in \mathcal{G}.$ Hence, the number of messages is |$\mathcal{R}| = nk.$ Then, $\mathcal{R}$ can be divided into ${\mathcal{R}}_{1}, {\mathcal{R}}_{2}, \dots, {\mathcal{R}}_{k},$ and

The $n$ different messages in ${\mathcal{R}}_{\alpha }\left(1\le \alpha \le k\right)$ can be represented by ${\mathcal{R}}_{\alpha }\left(1\right), {\mathcal{R}}_{\alpha }\left(2\right), \dots, {\mathcal{R}}_{\alpha }\left(n\right)$ respectively. Define the mapping

Therefore, $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{k}))$ is a non-splitting Cartesian authentication code if the probability distribution of encoding rules and sources is uniform.

Example 4. We have three mutually orthogonal $\left({P}_{4}\cup 2{P}_{2}\right)$-squares ${M}_{1}, {M}_{2},$ and ${M}_{3}$ which are defined as follows:

Hence,

It is clear that $Z$ is a $\left({P}_{4}\cup 2{P}_{2}\right)$-orthogonal array $\left({P}_{4}\cup 2{P}_{2}\right)$-$OA\left(\mathrm{5, 3}, 1\right).$ Let $Z = \left({A}_{1}, {A}_{2}, {A}_{3}\right)$, where ${A}_{\alpha }\left(1\le \alpha \le 3\right)$ is the $\alpha$th column of $Z.$ Now, $5$ different symbols inside ${A}_{\alpha }$ can be represented by ${A}_{\alpha }\left(1\right), {A}_{\alpha }\left(2\right), \dots, {A}_{\alpha }\left(5\right).$ In the matrix $Z,$symbols $\mathrm{1, 2}, \dots, 5$ are $5$ different authentication tags, and the messages set $\mathcal{R}$ consists of $15$ ordered pairs $\left(g, a\right),$ where $g\in \mathcal{G}.$ Hence, the number of messages is $\left|\mathcal{R}\right| = 15.$ Then, $\mathcal{R}$ can be divided into ${\mathcal{R}}_{1}, {\mathcal{R}}_{2}, {\mathcal{R}}_{3},$ and

The $5$ different messages in ${\mathcal{R}}_{\alpha }\left(1\le \alpha \le 3\right)$ can be represented by ${\mathcal{R}}_{\alpha }\left(1\right), {\mathcal{R}}_{\alpha }\left(2\right), \dots, {\mathcal{R}}_{\alpha }\left(5\right)$ respectively. Define the mapping

Therefore, $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, {\psi }_{3}))$ is a non-splitting Cartesian authentication code if the probability distribution of encoding rules and sources is uniform.

For more illustration, let the set of source states be $\mathcal{G} = \left\{i, j, k\right\},$ then the set of encoded messages

for example, if a receiver receives $\left(i, 1\right)$, then he or she can deduce that the original message is $i$ because $1$ belongs to the set of authentication tags $\left\{\mathrm{1, 2}, \mathrm{3, 4}, 5\right\}.$

Theorem 2. The above constructed Cartesian authentication code is a non-splitting authentication code and has the following parameters $\left|\mathcal{G}\right| = k, \left|\mathcal{H}\right| = {n}^{2}, \left|\mathcal{R}\right| = nk.$ Also, ${P}_{0} = {P}_{1} = \frac{1}{n}$.

Proof. As shown above, the graph-orthogonal array $Z$ is used as an encoding matrix of an authentication tag. Encoding rules are represented by rows of $Z,$ and sources are represented by columns of $Z.$ The graph-orthogonal array $Z$ is an ${n}^{2}\times k$ matrix. Hence, the number of sources is $k$, the number of encoding rules is ${n}^{2}$, and the number of messages is $\left|\mathcal{R}\right| = nk$.

(i) For the impersonation attack, from the graph-orthogonal array $Z,$ we can see that each encoding rule corresponds to $k$ different messages. Suppose a sender uses the encoding rule ${h}_{0}$ to send a message to a receiver. It is known that by the encoding rule ${h}_{0}, k$ messages can be obtained. Now, if one of these $k$ messages is used by an adversary, then the adversary succeeds in his impersonation attack. In this code, the number of all messages is $nk.$ Therefore, the probability of a successful impersonation attack is:

(ii) For the substitution attack, suppose a message $r = \left(g, a\right)$ is sent by a sender to a receiver, because the graph-orthogonal array $OA\left(n, k, 1\right)$ is used as an encoding matrix of an authentication tag, so by the superimposition of any two columns of this matrix, we conclude that every ordered pair of ${n}^{2}$ ordered pairs appears exactly once. Therefore, in the column of the source $g,$ the authentication tag $a$ appears exactly $n$ times and corresponds to $n$ different encoding rules, so we obtain

Suppose that an adversary sends a message $\stackrel{´}{r} = \left(\stackrel{´}{g}, \stackrel{´}{a}\right)$ ($\stackrel{´}{g}\ne g$) to a receiver. We know from the used encoding matrix that the authentication tags $a$ and $\stackrel{´}{a}$ can only appear in one row simultaneously in the two columns of the sources $g$ and $\stackrel{´}{g}$, so we get

Hence

Now, we want to prove that the constructed Cartesian authentication code, in this case, is a non-splitting authentication code. It is clear from the above construction that if we have the encoding rule $h$ and the source $g$, then $g$ and $h$ can be mapped to only one message $r$, so we obtain a non-splitting authentication code.

Theorem 3. The Cartesian authentication code $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{k})),$ which is constructed by $k$ mutually orthogonal $n\times n$ $G$-squares, is a perfect Cartesian authentication code.

Proof. For the authentication code $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{k})),$ let ${Z}_{{n}^{2}\times k}$ be an encoding matrix. The row of $Z$ represents the encoding rule and the column of $Z$ represents the source. An element ${z}_{x, y}$ is in the position $\left(x, y\right)$ of $Z.$ The element ${z}_{x, y}$shows that the source ${g}_{y}$ is encoded into the messages $r = {z}_{x, y}$with the encoding rules ${h}_{x}$, where $1\le x\le {n}^{2};$ $1\le y\le k$.

(i) We have

(ii) The elements ${g}_{y}$ and ${h}_{x}$ are used to determine the element ${z}_{x, y}$ in the encoding matrix ${Z}_{{n}^{2}\times k}.$ It is clear that an encoding rule can encode $k$ sources (${g}_{y}, 1\le y\le k$) and a source can be affected by ${n}^{2}$ encoding rules (${h}_{x}, 1\le x\le {n}^{2}$), so after determining ${g}_{y}$, the distribution probability of ${h}_{x}$ is

If ${h}_{x}$ is determined, then the distribution probability of ${g}_{y}$ is

Now, the distribution probability of every element ${z}_{x, y}$ in the encoding matrix ${Z}_{{n}^{2}\times k}$ can be obtained as follows:

(iii) For the encoding matrix ${Z}_{{n}^{2}\times k}$, the same authentication tag occurs $n$ times in any column. Also, in each column, the same authentication tag is mapped into a message. Therefore, every message $r$ occurs $n$ times. We now can obtain

(iv) We know from ${Z}_{{n}^{2}\times k}$ that each encoding rule corresponds to $k$ messages. Hence, the distribution probability of the message $r$ given an encoding rule ${h}_{x}$ is

And

Also,

Since ${P}_{0} = {P}_{1} = \frac{1}{n}$, then ${\mathrm{log}}_{2}{P}_{0} = {\mathrm{log}}_{2}{P}_{1} = -{\mathrm{log}}_{2}n$.

Finally, we can deduce that ${\mathrm{log}}_{2}{P}_{0} = {\mathrm{log}}_{2}{P}_{1} = -I\left(\mathcal{R}; \mathcal{H}\right) = -{\mathrm{log}}_{2}n.$ From Definition 11, the Cartesian authentication code $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{k})),$ which is constructed by $k$ mutually orthogonal $n\times n$ $G$-squares, is a perfect Cartesian authentication code.

4.   MOGS and general splitting Cartesian authentication codes

In this section, we will construct a general splitting Cartesian authentication code based on graph-orthogonal arrays which are constructed by MOGS. There is a difference in this section from the previous section because, in this section, we divide the message set twice. If some or all sources and encoding rules are determined, then this message set can correspond to multiple messages. Thus this construction has the characteristic of splitting.

Let $Z = \left({A}_{1}, {A}_{2}, \dots, {A}_{k}\right)$, where ${A}_{\alpha }\left(1\le \alpha \le k\right)$ is the $\alpha$th column of $Z.$ Now, the $n$ different symbols inside ${A}_{\alpha }$ can be represented by ${A}_{\alpha }\left(1\right), {A}_{\alpha }\left(2\right), \dots, {A}_{\alpha }\left(n\right).$ Here, we divide the message set $\mathcal{R}$ into ${\mathcal{R}}_{1}, {\mathcal{R}}_{2}, \dots, {\mathcal{R}}_{k}$, where the following conditions are satisfied:

It is clear that

Now, we apply another division on each ${\mathcal{R}}_{\alpha }$ such that ${\mathcal{R}}_{\alpha } = \left\{{\mathcal{R}}_{\alpha }^{1}, {\mathcal{R}}_{\alpha }^{2}, \dots, {\mathcal{R}}_{\alpha }^{n}\right\}$ and

Define the mapping

Therefore, $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{k}))$ is a splitting Cartesian authentication code if the probability distribution of encoding rules and sources is uniform.

Example 5. We have three mutually orthogonal $\left({P}_{4}\cup 2{P}_{2}\right)$-squares ${M}_{1}, {M}_{2},$ and ${M}_{3}$ which are defined in Example 4. Hence,

Let $Z = \left({A}_{1}, {A}_{2}, {A}_{3}\right)$, where ${A}_{\alpha }\left(1\le \alpha \le 3\right)$ is the $\alpha$th column of $Z.$ Now, the $5$ different symbols inside ${A}_{\alpha }$ can be represented by ${A}_{\alpha }\left(1\right), {A}_{\alpha }\left(2\right), {\dots, A}_{\alpha }\left(5\right).$ Here, we divide the message set $\mathcal{R}$ into ${\mathcal{R}}_{1}, {\mathcal{R}}_{2}, {\mathcal{R}}_{3}$, where the following conditions are satisfied:

It is clear that

Now, we apply another division on each ${\mathcal{R}}_{\alpha }$ such that ${\mathcal{R}}_{\alpha } = \left\{{\mathcal{R}}_{\alpha }^{1}, {\mathcal{R}}_{\alpha }^{2}, \dots, {\mathcal{R}}_{\alpha }^{5}\right\}$ and

Define the mapping

Therefore, $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, {\psi }_{3}))$ is a splitting Cartesian authentication code if the probability distribution of encoding rules and sources is uniform.

Theorem 4. The above constructed Cartesian authentication code is a splitting authentication code and has the following parameters $\left|\mathcal{G}\right| = k, \left|\mathcal{H}\right| = {n}^{2}, \left|\mathcal{R}\right| = tn, t\ge k.$ Also, ${P}_{0} = {P}_{1} = \frac{1}{n}$.

Proof. As shown above, the graph-orthogonal array $Z$ is used as an encoding matrix of an authentication tag. Encoding rules are represented by the rows of $Z,$ sources are represented by the columns of $Z.$ The graph-orthogonal array $Z$ is a ${n}^{2}\times k$ matrix. Hence, the number of sources is $k$, the number of encoding rules is ${n}^{2}$, and the number of messages is $\left|\mathcal{R}\right| = tn, t\ge k$.

(i) For the impersonation attack, from the graph-orthogonal array $Z,$ we can see that each encoding rule corresponds to $t$ messages. This is because of the division of the messages into $k$ parts in the beginning, where each source corresponds to ${t}_{\alpha }n$ messages, in the second division the messages are divided into the subsets ${\mathcal{R}}_{\alpha }^{1}, {\mathcal{R}}_{\alpha }^{2}, \dots, {\mathcal{R}}_{\alpha }^{n}$. Therefore, for a given one source and one encoding rule, we can obtain ${t}_{\alpha }$ messages, where $\sum _{\alpha = 1}^{k}{t}_{\alpha } = t$. And the previous is the result of the construction of one-to-one mapping of ${\mathcal{R}}_{\alpha }^{y}$ and each source corresponding to an authentication tag. Suppose a sender uses the encoding rule ${h}_{0}$ to send a message to a receiver. It is known that by the encoding rule ${h}_{0}, t$ messages can be obtained. Now, if one of these $t$ messages is used by an adversary, then the adversary succeeds in his impersonation attack. In this code, the number of all messages is $tn.$ Therefore, the probability of a successful impersonation attack is:

(ii) For the substitution attack, suppose a message $r = \left(g, a\right)$ is sent by a sender to a receiver, because the graph-orthogonal array $OA\left(n, k, 1\right)$ is used as an encoding matrix of an authentication tag, so by the superimposition of any two columns of this matrix, we conclude that every ordered pair of ${n}^{2}$ ordered pairs appears exactly once. Therefore, in the column of the source $g,$ the authentication tag $a$ appears exactly $n$ times and corresponds to $n$ different encoding rules, so we obtain

Suppose that an adversary sends a message $\stackrel{´}{r} = \left(\stackrel{´}{g}, \stackrel{´}{a}\right)$ ($\stackrel{´}{g}\ne g$) to a receiver. We know from the used encoding matrix that the authentication tags $a$ and $\stackrel{´}{a}$ can only appear in one row simultaneously in the two columns of the sources $g$ and $\stackrel{´}{g}$, so we get

Hence,

Now, we want to prove that the constructed Cartesian authentication code, in this case, is a splitting authentication code. It is clear from the above construction that if we have the encoding rule $h$ and the source $g$, then the authentication tag corresponded to $g$ and $h$ is ${A}_{\alpha }\left(y\right).$ From the mapping, we have ${A}_{\alpha }\left(y\right)\mapsto {\mathcal{R}}_{\alpha }^{y}$, $g$ is mapped under $h$ into a subset ${\mathcal{R}}_{\alpha }^{y}$, ${|\mathcal{R}}_{\alpha }^{y}| = {t}_{\alpha }$ and ${t}_{\alpha }\ge 1.$ Thus, there is a possibility to encode one or more messages, so the code is a splitting Cartesian authentication code.

Theorem 5. The splitting Cartesian authentication code $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{k})),$ which is constructed by $k$ mutually orthogonal $n\times n$ $G$-squares, is a perfect Cartesian authentication code.

Proof. For the authentication code $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{k})),$ let ${Z}_{{n}^{2}\times k}$ be the encoding matrix. The row of $Z$ represents encoding rules and the column of $Z$ represents sources. Let the source ${g}_{y}$ be encoded by the message ${r}_{x, y}$ with the encoding rule ${h}_{x},$ and $\left|{r}_{\left(x, y\right)}\right| = {t}_{y};$ ${r}_{\left(x, y, m\right)}$ represents the $m$th message of message set, and $1\le x\le {n}^{2}$; $1\le y\le k;$ $m$ = 1, 2, …, ${t}_{y}.$

(i) We have

(ii) It is clear that an encoding rule can encode $k$ sources (${g}_{y}, 1\le y\le k$) and a source can be affected by ${n}^{2}$ encoding rules (${h}_{x}, 1\le x\le {n}^{2}$), so after determining ${g}_{y}$, the distribution probability of ${h}_{x}$ is

If ${h}_{x}$ is determined, then the distribution probability of ${g}_{y}$ is

(iii) After determining ${h}_{x}$ and ${g}_{y}$, the probability distribution of the message ${r}_{\left(x, y, m\right)}$ is

And

Also,

Now, we can obtain

(iv) Let the message set corresponding to the source ${g}_{y}$ be ${\mathcal{R}}_{y}$, ${\mathcal{R}}_{y, v}$is the $v$th message of ${\mathcal{R}}_{y},$ then and the probability of ${\mathcal{R}}_{y, v}$ is

Now, we can deduce that

Since ${P}_{0} = {P}_{1} = \frac{1}{n}$, then ${\mathrm{log}}_{2}{P}_{0} = {\mathrm{log}}_{2}{P}_{1} = -{\mathrm{log}}_{2}n$.

Finally, we can deduce that ${\mathrm{log}}_{2}{P}_{0} = {\mathrm{log}}_{2}{P}_{1} = -I\left(\mathcal{R}; \mathcal{H}\right) = -{\mathrm{log}}_{2}n.$ From Definition 11, the splitting Cartesian authentication code $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{k})),$ which is constructed by $k$ mutually orthogonal $n\times n$ $G$-squares, is a perfect Cartesian authentication code.

5.   Optimal Cartesian authentication codes based on MOGS

In this section, we will handle a special case of MOGS which is called MOLS. If we have a set of mutually orthogonal G-squares of order $n,$ where ${G\cong nK}_{2}$, then this set is called a set of MOLS. It is known that for any prime power $n$, there exist $\left(n-1\right)$ MOLS of order $n$^[46]. Suppose we have $\left(n-1\right)$ MOLS of order n: ${M}_{1}, {M}_{2}, \dots, {M}_{n-1}.$ The entries in ${M}_{\alpha }$($\alpha = \mathrm{1, 2}, \dots, n-1$) belong to the set $\left\{\mathrm{1, 2}, \dots, n\right\}.$ Suppose ${M}_{\alpha }^{\omega }$refer to the column of ${M}_{\alpha },$ ${Z}_{0} = {\left(\mathrm{1, 2}, \dots, n\right)}^{T}, {Z}_{x} = {\left(x, x, \dots, x\right)}^{T}$and $x = \mathrm{1, 2}, \dots., n.$

Theorem 6 (^[47].(A set of $\left(n-1\right)$ MOLS of order $n$ is equivalent to an $OA\left(n, n+\mathrm{1, 1}\right)$.

Hence, the following graph-orthogonal array can be constructed based on Theorem 6.

The graph-orthogonal array $Z$ is an orthogonal array $OA\left(n, n+1, 1\right)$. The matrix $Z$ will be used as an encoding matrix for an authentication tag.

Theorem 7. If the non-splitting Cartesian authentication code $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{k})),$ constructed in Section 3, is constructed by $\left(n-1\right)$ MOLS of order $n,$ that is $k = n+1,$ then the code is an optimal Cartesian authentication code.

Proof. From Theorem 2, the parameters of this authentication code are $\left|\mathcal{G}\right| = k =$n+1, $\left|\mathcal{H}\right| = {n}^{2}, \left|\mathcal{R}\right| = n\left(n+1\right).$ Also, ${P}_{0} = {P}_{1} = \frac{1}{n}$. Hence, the authentication code is an optimal Cartesian authentication code from Definition 10.

Theorem 8. If the splitting Cartesian authentication code $(Z, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{k})),$ constructed in Section 4, is constructed by $\left(n-1\right)$ MOLS of order $n,$ that is $k = n+1,$ then the code is an optimal Cartesian authentication code.

Proof. From Theorem 4, the parameters of this authentication code are $\left|\mathcal{G}\right| = k =$n+1, $\left|\mathcal{H}\right| = {n}^{2}, \left|\mathcal{R}\right| = nt = n\left(n+1\right).$ Also, ${P}_{0} = {P}_{1} = \frac{1}{n}$. Hence, the authentication code is an optimal Cartesian authentication code from Definition 10.

6.   Authentication codes with confidentiality based on graph squares

An authentication code can be kept secret if an adversary finds a message transmitted through a channel, but this adversary cannot get any information about the source. Here, we will construct a security authentication code by using Latin squares that are considered as a special case of graph squares (G-squares) as mentioned above. The constructed authentication codes in Section 3 and Section 4 are without confidentiality. Suppose $C$ is the orthogonal array $OA\left(n, kn, k\right),$ where $C$ can be represented as $C = {\left({c}_{i, j}\right)}_{k{n}^{2}\times kn}$, where $i = 1, 2, \dots, k{n}^{2}, j = 1, 2, \dots, kn$. From Section 3, the parameters of the constructed authentication code by the orthogonal array $C$ are $\left|\mathcal{G}\right| = kn,$ $\left|\mathcal{H}\right| = {kn}^{2},$ $\left|\mathcal{R}\right| = n\left|\mathcal{G}\right| = {kn}^{2}$. Then, suppose that it is possible to construct the Cartesian authentication code $(C, \mathcal{R}, {(\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{kn})),$ where $C$ is the encoding matrix.

Now, we will use a Latin square to convert the constructed Cartesian authentication code to an authentication code with confidentiality. Suppose that the encoding matrix for the authentication code is $D = {\left({d}_{i, j}\right)}_{k{n}^{2}\times kn}$, $i = 1, 2, \dots, k{n}^{2}, j = 1, 2, \dots, kn$.

We make a partitioning to $D$ into the following blocks,

Suppose that we have any Latin square $S$of order $kn;$

For the element in row $x$ and column $y$ of the matrix $D$, the second subscript is replaced with the element in row $x$ and column ${s}_{x, y}$ of the Latin square $S$. Hence, for the matrix $D,$ the element in row $x$ and column $y$ is put in the position in row $x$ and column ${s}_{x, y},$ so the subblocks in rows of $D$ are rearranged and we get a matrix $\stackrel{´}{D}$. Finally, we obtain an authentication code with confidentiality $(\stackrel{´}{D}, C, \mathcal{R}, D, {S, (\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{kn})),$ where $\stackrel{´}{D}$ is its encoding matrix. It seems that the strength of the proposal is the huge growth in the number of Latin squares of a given order.

Theorem 9. The authentication code $(\stackrel{´}{D}, C, \mathcal{R}, D, {S, (\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{kn}))$ is a secure authentication code or with confidentiality.

Proof. It is clear that

Each column in $\stackrel{´}{D}$ contains all messages, and each message occurs precisely once in this column. Hence, the conditional distribution probability of source under the message is

Hence,

Consequently, the authentication code $(\stackrel{´}{D}, C, \mathcal{R}, D, {S, (\psi }_{1}, {\psi }_{2}, \dots, {\psi }_{kn}))$ is secure.

Example 6. Let the matrices $C, D,$and $S$ be represented by

Then, the matrix $\stackrel{´}{D}$ can be represented as follows:

For more illustration, if we choose the following Latin square

Then

It is clear that $\left|\mathcal{G}\right| = 4,$ $\left|\mathcal{H}\right| = 16,$ $\left|\mathcal{R}\right| = 16$, and $P\left(g\right) = P\left(g|r\right) = \frac{1}{4}.$

7.   Conclusions

This paper mainly studies how to use graph-orthogonal arrays and MOGS to construct non-splitting Cartesian authentication codes and splitting Cartesian authentication codes where the probability distribution of encoding rules and sources is uniform. We have calculated the probability of successful impersonation attack and substitution attack of the constructed non-splitting and splitting Cartesian authentication codes and have analyzed their performance. These codes are proved to be perfect and optimal Cartesian authentication codes with good performance. Our goal in this paper has been to develop message authentication schemes to provide a guarantee of integrity: that is, the assurance that a message was sent by its purported sender. By the way, this paper is the first one that deals with the construction of authentication codes by MOGS. In future work, we will try to study the properties of the authentication codes constructed by MOGS as the G-squares are different according to graph G. The graph G may be a path graph, cycle graph, tree graph, and so forth.

Acknowledgments

This Research was supported by Taif University Researchers Supporting Project Number (TURSP-2020/217), Taif University, Taif, Saudi Arabia.

Conflict of interest

The authors declare no conflict of interest.