Secure network coding with adaptive and active attack^††thanks: Supported in part by the National Natural Science Foundation of China under Grant 62171212.

Network coding is a key technology for communication over a network. Secure network coding protects our communication from various attacks. However, the majority of existing studies addressed deterministic and passive attacks, and did not care about the effect of adaptive changes on attacked edges and active modification on the information on attacked edge [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]. The communication over a network has a risk that an adversary, Eve, can improve her ability by using adaptive and active operations. In several joint papers [15, 16, 17, 18, 19], Ning Cai and the author jointly studied how adaptive and active operations can improve Eve’s performance. This paper reviews these joint studies. Since the original paper [19] contains complicated descriptions and a certain error, this paper presents the corrected contents based on its correction [20]. In addition, the paper [19] discussed the difference between the existence and the non-existence of random number at intermediate nodes. Also, the paper [19] treated the correctness and the secrecy in an asymmetric way. In this paper, we adopt the base $2$ of the logarithm.

The outline of this paper is the following. This paper explains why such an asymmetric treatment is reasonable by citing the recent paper [21] in Section 2. Then, Section 2 introduces these two kinds of formulations based on the existence and the non-existence of random number at intermediate nodes. Section 3 analyzes $r$-wiretap network based on the above mentioned formulations. Section 4 introduces two kinds of unconventional attack models, adaptive attack and active attack. Section 5 explains that secure communication is impossible in one-hop relay network under the non-existence of random number at intermediate nodes even when neither adaptive attack nor active attack is allowed for Eve. Section 6 introduces non-linear codes to resolve this problem. Section 8 shows adaptive attacks the above non-linear codes over one-hop relay network. Section 7 shows active attacks the above non-linear codes over one-hop relay network. Section 9 presents the usage of vector-linear code over one-hop relay network. Section 10 derives the capacities under adaptive and active attacks over unicast relay network. Section 11 makes conclusion.

Secure network coding has two kinds of security measures. One is the correctness of the decoding message, and the other is the secrecy of the transmitted message. Also, secure network coding considers the set of possible attacks. The usual setting requires the correctness and the secrecy when one of possible attack is done. However, when this requirement is imposed to our code, it is often difficult to realize a larger transmission rate. To realize a better transmission rate, it is possible to discount the requirement as follows. The discounted setting requires the secrecy when one of possible attack is done, but it requires the correctness only when no attack is made. This requirement is useful when the sender, Alice, and the receiver, Bob, share a small size of secret random number and they can use public channel due to the following reason.

As explained in [21], this discounted setting is reasonable as follows even for the message transmission. In this case, after the communication, Alice and Bob can apply error verification by using a small size of secret random number and public channel [21, Section VI], [22, Section VIII], [23, Section III-C-2)]. If an error is detected, they abort the protocol. Since the attack is limited to an element of the set of possible attacks, the requirement guarantees that the secrecy of the message is kept even in this case. Once the error verification is passed, the error verification guarantees the correctness. As explained in [21, Section VI], [22, Section VIII], [23, Section III-C-2)], when the size of the transmitted message is $n$ bits, the error verification consumes a polynomial amount of resources with respect to $\log n$. Thus, the error verification does not affect the transmission rate of the whole protocol. Due to this reason, this paper focuses on the discounted setting.

This paper adopts two kinds of formulations for our codes depending on the resources on intermediate nodes. In the first formulation, an arbitrary node including an intermediate node can generate an arbitrary random number. In the second formulation, only the source node and the destination node can generate an arbitrary random number so that an intermediate node cannot. This paper adopts both formulations for our codes.

This paper considers two kinds of linear codes. When transmitted information on each edge in a code is given as a single element, i.e., a scalar, of a finite field $\mathbb{F}_{q}$ or a quotient ring $\mathbb{Z}_{d}$ and a coding operation on each node is given as linear operations over input or incoming information, the code is called a scalar-linear code. When transmitted information on each edge in a code is given as a vector on a finite field $\mathbb{F}_{q}$ or a quotient ring $\mathbb{Z}_{d}$ and a coding operation on each node is given as linear operations over input or incoming information, the code is called a vector-linear code. The paper [18] showed the following lemma.

To consider the relation between two kinds of formulations for our codes, we consider an acyclic network with a single source and a single terminal, where Eve is allowed to select an arbitrary $r$-subset channels to access, which is called $r$-wiretap network [1, 2, 24, 25]. We define the first capacity $C_{1}$ as the maximum transmission rate when random number generation is allowed in an arbitrary intermediate node. We define the second capacity $C_{2}$ as the maximum transmission rate when random number generation is not allowed in an arbitrary intermediate node. For our analysis on the capacities of the given network, we introduce two kinds of minimum cuts. A node is called a pseudo source node when the node has only outgoing edges but has no original message to be transmitted. Since a pseudo source node is not the source node nor the terminal node, it is classified as an intermediate node. The first kind of minimum cut $\mathop{\rm mincut}\nolimits_{1}$ is the minimum number of edges crossing a line separating the source and terminal nodes. The second kind of minimum cut $\mathop{\rm mincut}\nolimits_{2}$ is the minimum number of edges crossing a line separating the source and terminal nodes when we remove all edges outgoing from pseudo source nodes. Edges out-going from pseudo source nodes are counted in $\mathop{\rm mincut}\nolimits_{1}$, but are not counted in $\mathop{\rm mincut}\nolimits_{2}$.

As a special case analysis, we have the following corollary.

The network given in Fig. 1 shows that a network has different rates $\mathop{\rm mincut}\nolimits_{1}$ and $\mathop{\rm mincut}\nolimits_{2}$. This network has a linear code to realize $\mathop{\rm mincut}\nolimits_{1}-r$ when $r=2$, which implies the equality of the second inequality in (2). Since $C_{1}=1$ and $C_{2}=0$, $C_{1}$ is strictly larger $C_{2}$.

This paper aims to discuss two unconventional types of attacks when the network model has a multiple-layer structure, like a one-hop relay network. When a one-hop relay network is given, a conventional type of attack is given as Fig. 4. One is an active attack as Fig. 4. In order to get more information, the eavesdropper changes the information on attacked edges. That is, after the above modification on the first attacked edge, the eavesdropper, Eve, may have a possibility to get more information via the second attack. Such an attack is called an active attack. If the attack is not an active attack, it is called a passive attack.

To discuss an active attack, we need to be careful for the causality and the time-ordering. The paper [18] carefully handled this problem, and showed the following theorem, which guarantees that an arbitrary active attack cannot improve Eve’s information when the code is linear.

Although the paper [26] addressed a part of active attacks, its treatment is limited to a limited class of active attacks. The paper [16] covers a more general class of active attacks.

The second is an adaptive attack as Fig. 4. In order to get more information, Eve changes what edge is to be attacked according the information on the previous attacks. Such an attack is called an adaptive attack. If the attack is not an adaptive attack, it is called a deterministic attack. That is, a conventional attack is called a deterministic and passive attack.

First, we consider a one-hop relay network as Fig. 4. This network has only one intermediate node in addition to the source node and the destination node. The intermediate node connects with the source node via two edges, i.e., two channels, $e(1)$ and $e(2)$. Also, the intermediate node connects with the destination node via two edges, i.e., two channels, $e(3)$ and $e(4)$. The aim of this network is the following. Alice intends to her message from the source node to Bob at the destination node. Here, we consider two types of attacks by an adversary, Eve. In the passive attack, Eve can eavesdrop on two edges in total, i.e., she can eavesdrop on one edge among $e(1)$ and $e(2)$, and can another edge among $e(3)$ and $e(4)$. In the active attack, Eve is allowed to change it to get more information.

Here, for the secrecy, we adopt imperfect secrecy as follows. When $M$ is the message and Eve’s information $Z_{E}$ satisfies the condition $I(M;Z_{E})=0$ for all of Eve’s possible attacks, the code is called perfectly secret. When the condition $I(M;Z_{E})<\log d$ holds for all of Eve’s possible attacks, the code is called imperfectly secret [27] (or weakly secret). Otherwise, it is called insecure. In other words, our code is imperfectly secret, when there exists no function $\tilde{\psi}$ such that $\tilde{\psi}(Z_{E})=M$. Also, we say that the code is perfectly secret, when $Z_{E}$ is Eve’s information and $I(M;Z_{E})=0$ for all Eve’s possible attacks.

We choose $L\in\mathbb{Z}_{d}$ as the uniform scramble random variable generated at the source node. Suppose that the intermediate node generates another uniform scramble random variable $L^{\prime}\in\mathbb{Z}_{p}$. We introduce a scalar-linear code as follows.

Then, the intermediate node applies the code $\varphi$ as

The decoder $\psi$ is written as $\psi({Y}_{3},{Y}_{4}):={Y}_{4}-{Y}_{3}$, which equals $Y_{2}-Y_{1}+L^{\prime}-L^{\prime}=M+L-L+L^{\prime}-L^{\prime}=M$. This code satisfies the correctness. The pair $(Y_{1},Y_{3})$ is independent of $M$. Similarly, the pairs $(Y_{1},Y_{4})$, $(Y_{2},Y_{3})$, and $(Y_{2},Y_{4})$ are independent of $M$. Thus, this code is perfectly secret for passive attacks, and has the transmission rate $\log d$.

Even when Eve selects the attacked edge $e(3)$ or $e(4)$ based on the observation on the first attack, Eve gets no information for the message $M$. Hence, this code is secret even for an adaptive attack. Due to the linearity, even when Eve changes the information on the first attacked edge, Eve cannot improve her performance due to Theorem 4.1. Thus, this code is secret even for an adaptive and active attack.

However, when the intermediate node cannot generate a uniform scramble random variable, no scalar-linear code is imperfectly secret over a quotient ring $\mathbb{Z}_{d}$ for passive attacks, as shown in [17, Theorem 1]. In other words, for an arbitrary scalar-linear code over a quotient ring $\mathbb{Z}_{d}$, Eve has a passive attack to recover the message $M$ perfectly.

To realize imperfect secrecy without random number generation on the intermediate node, we introduce the following non-linear code. For simplicity, it is assumed that Alice transmits only the message $M\in\mathbb{Z}_{d}$ and an arbitrary edge can transmit only one binary information. We consider the following code, which requires the binary uniform scramble random variable $L\in\mathbb{Z}_{d}$ at the source node.

The encoder $\phi$ is given in the same way as (4). Then, our non-linear code $\varphi$ in the intermediate node is given as

The decoder $\psi$ is given as $\psi({Y}_{3},{Y}_{4}):={Y}_{3}+{Y}_{4}$. In this code, ${Y}_{3}$ and ${Y}_{4}$ have the following form;

Thus, the decoder recovers $M$ as $Y_{4}-Y_{3}$ nevertheless the value of $L$. We call the above code the standard non-linear code.

Consider the case when Eve eavesdrops $Y_{1}=L$ in the first step. Suppose that Eve eavesdrops $Y_{3}$ in the second step. When $L$ is invertible, she can recover $M$ by $Y_{1}^{-1}Y_{3}$. But, when $L$ is not invertible, she cannot recover $M$ because the map $M\mapsto LM$ is not one-to-one. Suppose that Eve eavesdrops $Y_{4}$ in the second step When $L+1$ is invertible, she can recover $M$ by $(Y_{1}+1)^{-1}Y_{4}$. But, when $L+1$ is not invertible, she cannot recover $M$ because the map $M\mapsto(L+1)M$ is not one-to-one.

Consider the case when Eve eavesdrops $Y_{2}=M+L$ in the first step. Suppose that Eve eavesdrops $Y_{3}$ in the second step. To recover $M$, she needs to find $M$ to satisfy $Y_{3}=Y_{2}M-M^{2}$. However, the map $M\mapsto Y_{2}M-M^{2}$ is not always one-to-one. For example, when $d=2$ and $Y_{2}=1$, $Y_{2}M-M^{2}$ is always zero. Also, when $d>2$ and $Y_{2}=0$, $Y_{2}M-M^{2}$ has the same value with $M=1,-1$. Thus, Eve cannot recover the original information $M$. Suppose that Eve eavesdrops $Y_{4}$ in the second step. To recover $M$, she needs to find $M$ to satisfy $Y_{4}=Y_{2}M+M-M^{2}$. Similarly, the map $M\mapsto Y_{2}M+M-M^{2}$ is not always one-to-one. For example, when $d=2$ and $Y_{2}=0$, $Y_{2}M+M-M^{2}$ is always zero. Also, when $d>2$ and $Y_{2}=-1$, $Y_{2}M+M-M^{2}$ has the same value with $M=1,-1$. In this way, we find that this code is imperfectly secret for deterministic and passive attacks. That is, there exists a secret code over deterministic and passive attacks.

When $d=2$, The reference [17, Appendix] calculated the mutual information, i.e., the amount of information leakage as follows.

Further, as shown in Lemma 2 with $d=2$, when Eve cannot recover the message $M$ perfectly with an arbitrary deterministic and passive attack in the code, the network code is limited to the standard non-linear code or a code equivalent to the standard non-linear code.

However, the above theorem does not holds when $d>2$. In this case, the paper [17] proposed another non-linear code. For this aim, the paper [17] introduced an anti-Latin square. A matrix $(a_{i,j})$ on $\mathbb{Z}_{d}$ is called an anti-Latin square when each row and each column have duplicate elements, which is the opposite requirement to a Latin square. For example, the following shows $3\times 3$ and $4\times 4$ anti-Latin square matrices.

Using a pair of $d\times d$ anti-Latin square matrices $(a_{i,j})$ and $(b_{i,j})$, the paper [17] proposed a non-linear code as follows. The encoder $\phi$ is given in the same way as (4). Then, our non-linear code $\varphi$ in the intermediate node is given as

We call the above code the anti-Latin code of the pair of anti-Latin square matrices $(a_{i,j})$ and $(b_{i,j})$.

For example, when the pair $(a_{i,j})$ and $(b_{i,j})$ is chosen by the first and second matrices (or the the third and fourth matrices) in (25), the map $(Y_{1},Y_{2})\mapsto(a_{Y_{1},Y_{2}},b_{Y_{1},Y_{2}})$ is one-to-one. So, the anti-Latin code is uniquely decodable. To see the equivalent condition to the unique decodability, we define the set

When $Y_{4}=z$ and $M=m$, the set $\Xi_{z,m}(\varphi^{(3)},\varphi^{(4)})$ expresses the possible values of $Y_{4}$. Hence, the unique decodability is equivalent to the relation

Although there is no decodable anti-Latin code for $d=2$, a decodable anti-Latin code exists for $d>2$ as follows.

Next, we consider active attacks over a one-hop relay network, as Fig. 4. Eve has the following two active attacks for the standard non-linear code.

(i)

When Eve attacks on $e(1),e(3)$ and replaces $Y_{1}$ by $1$, we have $Y_{3}+1-Y_{1}=M$.

(ii)

When Eve attacks on $e(1),e(4)$ and replaces $Y_{1}$ by $0$, we have $Y_{4}-Y_{1}=M$.

Therefore, the code presented in Section 8 is insecure under active attacks.

Since Lemma 2 guarantees the non-existence of another imperfectly secret code over deterministic and passive attacks for $d=2$, the above discussion shows the non-existence of an imperfectly secret code over active attacks for $d=2$.

However, Lemma 2 does not hold for $d\neq 2$. In fact, any anti-Latin code is imperfectly secret even under active attacks as follows. Assume that Eve eavesdrops $e(1)$ and $e(3)$. Even when Eve replaces $Y_{1}$ by any value, any row vector of $a_{i,j}$ has duplicate elements. Hence, Eve has a possibility that she cannot recover the message from $Y_{1}$ and $Y_{3}$. The same discussion can be applied to other pairs of edges eavesdropped by Eve.

Next, we discuss adaptive attacks over one-hop relay network even when active modification is not allowed. Eve has the following adaptive attack to recover the message $M$, as Fig. 4.

(i)

First, Eve eavesdrops $e(1)$. When ${Y}_{1}=1$, she eavesdrops $e(3)$, and recovers $M$ as ${Y}_{3}+1={Y}_{2}-1+1=M$. When ${Y}_{1}=0$, she eavesdrops $e(4)$, and recovers $M$ as ${Y}_{4}={Y}_{2}=M$.

Thus, the non-linear code given in Section 6 is not imperfectly secret for adaptive attacks. Since Lemma 2 guarantees the non-existence of another imperfectly secret code over deterministic and passive attacks for $d=2$, there exists no imperfectly secure code over adaptive attacks in this network model with $d=2$. This fact shows that an adaptive attack is powerful for this kind of non-linear code with $d=2$ even when it has no active modification. In fact, when $d=2$, Eve also has the following adaptive attack to recover the message $M$.

(ii)

First, Eve eavesdrops $e(2)$. When ${Y}_{2}=1$, she eavesdrops $e(4)$ and recovers $M$ as ${Y}_{4}={Y}_{1}+1=M$. When ${Y}_{2}=0$, she eavesdrops $e(3)$ and recovers $M$ as ${Y}_{3}={Y}_{1}=M$.

However, Lemma 2 does not hold for $d\neq 2$. In fact, any anti-Latin code is imperfectly secret even under adaptive and active attacks as follows. Assume that Eve eavesdrops $e(1)$ at the first step. Even when Eve replaces $Y_{1}$ by any value, any row vector of $(a_{i,j})$ and any row vector of $(b_{i,j})$ have duplicate elements. When Eve observes such duplicate elements in the second observation, she cannot recover the message $M$. Hence, whichever $e(3)$ or $e(4)$ Eve eavesdrops in the second step, she has a possibility that she cannot recover the message $M$ from her observed information. The same discussion can be applied to the case when Eve eavesdrops $e(2)$ by considering column vectors of $(a_{i,j})$ and $(b_{i,j})$. Therefore, there exists an imperfectly secret code for under adaptive and active attacks when $d>2$.

The discussion of this section is based on the paper [19]. But, it did not discuss adaptive attacks for anti-Latin codes.

To resolve this problem, we employ a vector-linear code. A vector-linear code can be realized when the network of Fig. 4 is used at least twice. Suppose that the source node generates three uniform scramble random variables $L_{1},L_{2},L_{3}\in\mathbb{Z}_{d}$. Using these variables, we define a vector-linear code as follows. The first transmission sends the following;

and the second transmission sends the following;

Then, the intermediate node applies the code $\varphi$ as

In this code, nothing is transmitted in the second layer at the second transmission. The decoder $\psi$ is given as $\psi({Y}_{3},{Y}_{4}):={Y}_{4}-{Y}_{3}$, which equals $Y_{2}-Y_{1}+Y_{2}^{\prime}-Y_{1}^{\prime}-(Y_{2}^{\prime}-Y_{1}^{\prime})=M+L_{1}-L_{1}=M$. Then, the pair $(Y_{1},Y_{3})$ is independent of $M$. Similarly, the pairs $(Y_{1},Y_{4})$, $(Y_{2},Y_{3})$, and $(Y_{2},Y_{4})$ are independent of $M$. Thus, this code is perfectly secret for deterministic attacks, and has the transmission rate $\frac{1}{2}\log d$. In the same reason as the above, this code is secret for adaptive attack. Then, due to the linearity, it is secure even for active and adaptive attacks.

The discussion until this section is summarized as Table 1.

We have reviewed several results under adaptive and active attacks over a one-hop relay network and unicast relay network. Also, we have reviewed the recent result for the difference between the existence and the non-existence of random number at intermediate nodes. These results show how to handle such unconventional attacks. Although the papers [17, 19] did not discuss the imperfect secrecy for an anti-Latin code under adaptive attacks, we have proved it in this paper. The paper [19] also generalized the result presented in Section 10 to a homogeneous multicast rely network. Although the review of this extension is omitted, the paper [19] presented a network code that works even with adaptive and active attack in these networks. However, the analysis on such unconventional attacks over a network is still limited. Further, it is desired to develop network codes for such unconventional attacks.

The paper [17] proposed the concept of an anti-Latin square, and no other paper discussed it. Based on Latin squares, the famous puzzle, Sudoku, has been invented and it has been enjoyed among many people. Since generating a pair of anti-Latin squares is not so trivial and is an interesting combinatorics problem, it can be expected to be developed into another puzzle. Also, it is expected that a more complicated combination of anti-Latin squares generates useful non-linear codes for more complicated network models. Although the decodability of an anti-Latin code is equivalent to (28), it is not clear whether this condition is equivalent to the condition that the map $(Y_{1},Y_{2})\mapsto(a_{Y_{1},Y_{2}},b_{Y_{1},Y_{2}})$ is one-to-one. That is, while the latter condition is its sufficient condition, its necessity is not clear. This problem is also an interesting open problem.

Finally, we propose other open problems. A subset $S$ of the set ${\cal A}(d)$ of $d\times d$ anti-Latin matrices is called mutual decodable when any two elements of $S$ form a decodable anti-Latin code. A subset $S\subset{\cal A}(d)$ is called mutual one-to-one when the map $(Y_{1},Y_{2})\mapsto(a_{Y_{1},Y_{2}},b_{Y_{1},Y_{2}})$ is one-to-one for any two elements $(a_{i,j})$ and $(b_{i,j})$ of $S$. Then, we define two numbers $A(d)$ and $B(d)$ as

The calculations of these values are another interesting open problem. For Latin squares, a similar problem has been studied as follows. Two Latin squares $(a_{i,j})$ and $(b_{i,j})$ is called orthogonal when the map $(i,j)\mapsto(a_{i,j},b_{i,j})$ is one-to-one. It is known that the maximum size of a set of $n\times n$ mutually orthogonal Latin squares is $n-1$ when $n$ is a prime or prime power [39, 40]. The general case of this maximum number has been actively studied in the area of combinatorics [41].

Indeed, a mutual decodable subset $S\subset{\cal A}(d)$ can be used to modify the one-hop relay network as follows. That is, the calculation of $A(d)$ has the following operational meaning. We modify the one-hop relay network by putting $|S|$ channels in the second step, and the code in the second step is defined by $|S|$ anti-Latin matrices. In this case, we assume the following. Eve is allowed to eavesdrop one edge in the first group and another edge in the second group, adaptively. The receiver accesses only two edges in the second group and the two edges are selected randomly. In this situation, the above code based on a pairwise-decodable subset $S$ is imperfectly secret and decodable.