{'fraction_non_alphanumeric': 0.050528717833784965, 'fraction_numerical': 0.016645952608952547, 'mean_word_length': 3.790824792581747, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 31, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Secrecy and Robustness for Active Attack in Secure Network Coding and its Application to Network Quantum Key Distribution

In the network coding, we discuss the effect of sequential error injection on information leakage. We show that there is no improvement when the network is composed of linear operations. However, when the network contains non-linear operations, we find a counterexample to improve Eve's obtained information. Furthermore, we discuss the asymptotic rate in a linear network under the secrecy and robustness conditions as well as under the secrecy condition alone. Finally, we apply our results to network quantum key distribution, which clarifies the type of network that enables us to realize secure long distance communication via short distance quantum key distribution.

arbitrarily varying channel model considers noise injection after Eve's eavesdropping, Eve does not eavesdrop the channel after Eve's noise injection [41], [44] [42, Table I]. In this paper, we discuss the secrecy when Eve eavesdrops the information transmitted on the channels in E E , and adds artificial information to the information transmitted on the channels in E A sequentially based on the obtained information. We call this type of attack an active attack and call an attack without contamination a passive attack. Specially, we call each of Eve's active operations a strategy. Indeed, while the paper [37] discusses robustness for an active attack, it discusses secrecy only for a passive attack. When E A = E E and any active attack is available for Eve, she is allowed to arbitrarily modify the information on the channels in E A sequentially based on the obtained information. The aim of this paper is as follows. Firstly, we show that no strategy can improve Eve's information when any operation in the network is linear. Then, to clarify the necessity of the linearity assumption, we provide a counterexample of the non-linear coding of the binary case on a relay network (Fig. 1), in which, there exists a strategy to improve Eve's information. A concrete description of this non-linear code on the relay network ( Fig. 1) will be given in the main body of this paper. In this example, even if Eve eavesdrops one edge before and after the intermediate node as a passive attack, she cannot recover the original message. However, when she makes an active attack before the intermediate node, she can recover the original message. This example shows the importance of the assumption of linearity. Similar unexpected properties for a nonlinear network error correcting code was reported in [36]. Then, we show that the network code is limited to this counterexample when we impose several natural secrecy conditions to the code on the relay network ( Fig. 1) in the binary case. This discussion shows that no code can guarantee the security over this type of active attack on the relay network ( Fig. 1) in the binary case. However, in the ternary case, there exists a code that Eve cannot completely recover the message even with this type of active attack on the relay network ( Fig. 1). To discuss this problem, we introduce a new concept an "anti-Latin square", which is an opposite concept to a Latin square.
Furthermore, we discuss a code that satisfies the need for secrecy and robustness when the transmission rate from Alice to Bob is m 0 , the rate of noise injected by Eve is m 1 , and the rate of information leakage to Eve is m 2 . In the asymptotic setting, we show the existence of such a secure protocol with the rate m 0 − m 1 − m 2 . We discuss the asymptotic performance when only secrecy is considered. When Alice and Bob share a small number of initial secret keys and can communicate with each other via a public channel, robustness is unnecessary. In such a case, we show the existence of a secure protocol with the rate m 0 − m 2 .
However, it is very difficult to directly connect two distinct parties over long distances via quantum key distribution. To realize long distance communication with quantum key distribution over short distances, this paper considers a method to connect them via a network composed of quantum key distribution over short distances. That is, we generate many pairs of shared secure keys on intermediate nodes by quantum key distribution, where each pair is composed of two nodes close to each other. The secure keys shared by two nodes realize a secure channel between the two nodes. Applying the method of network coding to these secure channels, we realize secure communication between two distinct parties across a long distance. We call this method network quantum key distribution. When all the nodes are trusted, quantum key distribution guarantees the security of all the channels between the nodes. However, there is a possibility that a part of nodes are occupied by Eve. For the security analysis of this case, we apply our results to the network composed of these channels.

C. Organization
The remaining part of this paper is organized as follows. Section II formulates our problem and shows the impossibility of Eve's eavesdropping under a linear network. Section III discusses the asymptotic setting, and show the achievability of the asymptotic rate m 0 − m 1 − m 2 . Section IV discusses the asymptotic setting only with secrecy. Section V gives a counterexample in the non-linear case. In Section VI, we show that our network code is limited to this counterexample when we impose natural conditions on our network code. In Section VII, we present a code in the non-binary case that prevents Eve from completely recovering the message even with this type of active attack. Section VIII shows the optimality of this code in a specific formulation. Finally, Section IX considers the application of obtained results to network quantum key distribution II. SECRECY IN FINITE-LENGTH SETTING We consider the unicast setting of network coding, whose network is given as a graph (V, E) with direction, where the set V of vertices expresses the set of nodes and the set E of edges expresses the set of packets, i.e., the set of communication channels. When a packet transmits information from a vertex u ∈ V to another vertex v ∈ V , it is written as (u, v) ∈ E. We use k to denote the number of edges |E|. The transmission on the edge is performed in the order of the numbers assigned to the edges. Each transmission sends only one element of F q , where F q is a finite field whose order is a power q of the prime p.
The authorized sender, Alice, intends to send her message to the authorized receiver, Bob, via the network given by the graph (V, E), where the operations on all nodes are linear on the finite filed F q with prime power q. Alice inputs the input variable X in F m 3 q and Bob receives the output variable Y B in F m 4 q . We also assume that the malicious adversary, Eve, wiretaps the information Y E in F m 2 q on the edges of a subset E E ⊂ E. Now, we fix the topology and dynamics (operations on the intermediate nodes) of the network, including the places of attached edges. When we assume that all operations on the intermediate nodes are linear on F m 3 q , since the operations on all nodes are linear, there exist matrices K B ∈ F m 4 ×m 3 q and K E ∈ F m 2 ×m 3 q such that the variables X, Y B , and Y E satisfy their relations That is, the matrices K B and K E are decided from the network topology and dynamics. We call this attack a passive attack.
To address an active attack, we consider stronger Eve, i.e., we assume that Eve adds an error Z in F m 1 q to the edges of a subset E A ⊂ E. Using matrices H B ∈ F m 4 ×m 1 q and H E ∈ F m 2 ×m 1 q , we rewrite the above relations as which is called the wiretap and addition attack model. Also, we set the parameter m 0 as Also, we assume the ranks of H B and K E as Then, the parameters are summarized in Table I.   TABLE I  CHANNEL PARAMETERS   m0 Rank of the channel from Alice to Bob, i.e., rank KB m1 Dimension of Eve's input (rank HB) m2 Dimension of Eve's output (rank KE) m3 Dimension of Alice's input m4 Dimension of Bob's input Now, to consider time ordering among the edges in E, we assign the integers to the edges in E such that E = {e(1), . . . , e(k)}. We assume that the information transmission on each edge is performed in this order. In this representation, the components of Z and Y E are arranged in this order. Hence, the elements of the subsets E E and E A are expressed as E E = {e(ζ(1)), . . . , e(ζ(m 2 ))} and E A = {e(η(1)), . . . , e(η(m 1 ))} by using two strictly increasing functions ζ and η. For example, when the order of the communications is guaranteed, the causality yields However, since Eve might intercept the information before the previous information is received, condition (6) does not necessarily hold. Hence, we do not assume condition (6). Since Eve can choose the information to be added on the edge e(i) ∈ E A based on the obtained information Y E , the added error Z i is given as a function α i of Y E . Thus, the set α = (α i ) of the functions can be regarded as Eve's strategy, and we call this attack an active attack with strategy α. Now, we consider the n-transmission setting, where, Alice uses the same network n times to send a message to Bob. Alice's input variable (Eve's added variable) is given as a matrix X n ∈ F m 3 ×n q (a matrix Z n ∈ F m 1 ×n q ), and Bob's (Eve's) received variable is given as a matrix Y n B ∈ F m 4 ×n q (a matrix Y n E ∈ F m 2 ×n q ). We assume that the topology and dynamics of the network and the edge attacked by Eve do not change during n transmissions. Their relation is given as We formulate a code to discuss the secrecy. Let M and L be the message set and the set of values of the scramble random number. Then, an encoder is given as a function φ n from M × L to F m 3 ×n q , and the decoder is given as ψ n from F m 4 ×n q to M. Our code is the pair (φ n , ψ n ), and is denoted by Φ n . Then, we denote the message and the scramble random number as M and L. The cardinality of M is called the size of the code and is denoted by |Φ n |.
Here, we treat K B , K E , H B , and H E as deterministic values, and denote the pairs (K B , K E ) and (H B , H E ) by K and H, respectively. In the following, we fix Φ n , K, H, α. As a measure of the leaked information, we adopt the mutual information I(M; Y n E , Z n ) between M and Eve's information Y n E and Z n Since the variable Z n is given as a function of Y n E , we have I(M; Y n E , Z n ) = I(M; Y n E ). Since the leaked information is given as a function of Φ n , K, H, α in this situation, we denote it by I(M; Y n E )[Φ n , K, H, α]. If we always choose Z n = 0, the attack is the same as the passive attack. This strategy is denoted by α = 0. When K, H are treated as random variables independent of M, L, the leaked information is given as the expectation of I(M; Y n E )[Φ n , K, H, α]. This probabilistic setting expresses a situation where Eve cannot necessarily choose her position to attack by herself while she knows the position, and she chooses her strategy depending on the position. Now, we have the following theorem. Theorem 1. For any Eve's strategy α, Eve's information Y n E with strategy α and that with strategy 0 can be simulated by each other. Hence, we have the equation This theorem shows that the information leakage of the active attack with the strategy α is the same as the information leakage of the passive attack. Hence, to guarantee the secrecy under an arbitrary active attack, it is sufficient to show secrecy under the passive attack. Proof: We define two random variables Y n E,p := K E X n and Y n E,a := K E X n + H E Z n . Eve can simulate her outcome Y n E,a under the strategy α by using Y n E,p , H E , and Z n . Thus, we have I(M; Y n E,p ) ≥ I(M; Y n E,a , Z n ) = I(M; Y n E,a ). Conversely, since Y n E,p is given as a function of Y n E,a , Z n , and H E , we have the opposite inequality.
Remark 1 (Number of choices). To compare passive and active attacks, we count the number of choices of both attacks. While the passive attack is characterized by the matrix K E , the information leaked to Eve in the passive attack depends only on the kernel of the matrix K E . To characterize the information leaked to Eve, we consider two matrices to be equivalent when their kernels are the same. In a passive attack, when we fix the rank of K E (the dimension of leaked information), by taking account into the equivalent class, the number of possible choices is upper bounded by q m 2 (m 3 −m 2 ) . With an active attack, this calculation is more complicated. For simplicity, we consider the case with n = 1. To consider the minimum number of choices of α, we assume condition (6). (When we do not make this assumption, the number of choices is larger.) We do not count the choice for the inputs on the edge η(i) with η(i) ≥ ζ(m 2 ) because it does not affect Eve's information. Then, even when we fix the matrices K E , H E , the number of choices of α is where T i := max{j|η(i) ≥ ζ(j)}. Notice that T i = i when E A = E E . If we count the choice on the remaining edges, we need to multiply q i:η(i)≥ζ(m 2 ) q T i on (10). For a generic natural number n, the number of choices of α is However, when the set E A is the same as the set E E , it is allowed to employ the wiretap and addition attack model (2) and (3) because any strategy with the model (12) and (13) can be written as a strategy with the wiretap and addition attack model (2) and ( III. ASYMPTOTIC SETTING WITH SECRECY AND ROBUSTNESS Next, under the same assumption as that in Section II, we consider the asymptotic setting by taking account of robustness as well as secrecy. We previously assumed that the topology and dynamics of the network and the edge attacked by Eve do not change during n transmissions. Now, we assume that Eve knows these matrices and that Alice and Bob know none of them because Alice and Bob often do not know the topology and/nor dynamics of the network and/nor the places of the edges attacked by Eve. However, due to the limitation of Eve's ability, we assume that the dimension of the information leaked to Eve and the dimension of the information injected by Eve are limited to m 2 and m 1 , respectively.
When Eve adds the error Z n , there is a possibility that Bob cannot recover the original information M. This problem is called robustness, and may be regarded as a kind of error correction. Under the conventional error correction, the error Z n is treated as a random variable subject to the distribution. However, our problem is different from the conventional error correction because the decoding error probability depends on the strategy α. Hence, we denote it by P e [Φ n , K, H, α]. Since any algebraic operation on the finite field F q can be regarded as an algebraic operation on a t-dimensional algebraic extension F q ′ of the finite field F q , where q ′ = q t . The matrices K B , H B , K E , H E on F q can be regarded as matrices on F q ′ . By choosing n := tn ′ , the matrices which also satisfy (7) and (8) by regarding the same matrices Theorem 2. We assume the following two conditions. The inequality m 2 + m 1 < m 0 holds. The size q ′ of the finite field increases such that where the maximum is taken with respect to The optimality of the rate m 0 − m 1 was also shown in [19], [20]. Combining the results in [14], [12], [13], [15], we can construct a sequence of codes to satisfy (14) and, instead of (15), the condition where E K,H denotes the expectation under the uniform distribution on the set of all of matrices satisfying the conditions (4). More precisely, the papers [12, Section IX][13, Section VIII] constructed a sequence of codes to satisfy (14) and (16) under the condition m 2 + 2m 1 < m 0 . This is because the condition m 2 + 2m 1 < m 0 is stronger than the condition m 2 + m 1 < m 0 , which is the assumption of Theorem 2. To show (16) under the weaker condition m 2 + m 1 < m 0 , the papers [12, Section VII][13, Section VI][15, Section IV-C] constructed a sequence of codes to satisfy (14) and (16) when Alice can send Bob secret information whose size is asymptotically negligible in comparison with n ′ . Then, under the weaker condition m 2 + m 1 < m 0 , the paper [14, Section III] provides a protocol for secure transmission of random variables with an asymptotically negligible length in comparison with n ′ .
Proposition 1 ([14, Section III]). We assume the inequality m 2 + m 1 < m 0 . Then, there exists a sequence of codes Φ n of block-length n whose message set is F kn q such that lim where the maximum is taken in the same way as Theorem 2.
Therefore, attaching the protocol of Proposition 1 to the above sequence of codes proposed in [12, Section VII][13, Section VI][15, Section IV-C], we obtain (16) under the weaker condition m 2 +m 1 < m 0 . Hence, to show Theorem 2, we need to improve the statement in [12, Section VII][13, Section VI][15, Section IV-C] because we need to replace E K,H in (16) by max K,H . For this purpose, we prove the following lemma instead of the statement in [12, Section VII][13, Section VI][15, Section IV-C]. Then, attaching the protocol of Proposition 1 to the following lemma, instead of (16), we obtain Theorem 2.
Lemma 1. We assume the following two conditions. Alice can send Bob secret information whose size is asymptotically negligible in comparison with n ′ . The size q ′ of the finite field increases such that (15) and (14) hod. Before our proof of Lemma 1, we prepare two lemmas. The first lemma can be easily shown by the discussion of linear algebra.

Lemma 2.
For integers a 1 + a 2 = a 0 , we assume that an a 0 × a 1 matrix A 1 and an a 0 × a 2 matrix A 2 satisfy the condition We choose vectors for any x ∈ F a 1 q ′ and y ∈ F a 2 q ′ . (B2) The rank of the matrix Therefore, it is impossible to find an a 1 × a 0 matrix A 3 satisfying (21) unless condition (B2) holds.

Proof of Lemma 1:
Step (1): Code construction First, we provide our code when we use the channel n ′ times based on the finite field F q ′ . Our message is given as a (m 0 − m 1 ) × n ′ matrix M, which satisfies condition (14) asymptotically. We fix an integer m, which will be decided later. We independently choose m random variables V 1 , . . . , V m subject to the uniform distribution on F q ′ . Also, we randomly choose the m 3 × m 3 matrix U 0 among all m 3 × m 3 invertible matrices.
Then, we define the n ′ × m matrix U 1 as U 1;i,j := (V j ) i with i = 1, . . . , n ′ and j = 1, . . . , m. We also where 0 is the (m 3 − m 0 + m 1 ) × n ′ zero matrix. As secret information with a negligible rate, Alice sends Bob the information V 1 , . . . , V m , U 2 . Then, Alice inserts the m 3 × n ′ matrix X n ′ as the input of n ′ times use of the channel.
Then, Bob receives the Since the ranks of K B U 0 X n ′ and H B are m 0 − m 1 and m 1 , respectively, the rank of the matrix Y n ′ B is m 0 at most. We denote the rank bym 0 . We choosem 0 linearly independent row vectors from the row vectors of Y n ′ B . We denote thē m 0 × n ′ matrix composed of them 0 independent row vectors byȲ n ′ B . Similarly, we denote the matrices composed of thesem ′ 0 row vectors of the matrices K B and H B byK B andH B , respectively. Then, using the standard Gaussian elimination, Bob finds a matrix U 3 to satisfy the equation which is equivalent to Finally, Bob recovers the informationM : Step (2): Analysis of performance There are two conditions if the above protocol is to work well.
(C1) The relation Im( where Im(f ) denotes the image of the function f , and P m 0 −m 1 is the projection onto the space composed of vectors whose m 0 −m 1 +1th . . . m 0 -th components are zero.
where rank denotes the rank of the matrix. Due to Lemma 2, when conditions (C1) and (C2) hold, there uniquely exists a matrix U 3 that satisfies equation (23). Using the matrix U 3 , Bob can decode the message M. Now, we evaluate the probability that condition (C2) holds. Condition (C2) holds if and only if at least. Finally, we evaluate the probability that condition (C1) holds. When the following condition (C1') holds, condition (C1) holds.
(C1') The relation Im( holds. Hence, we show that condition (C1') holds with a probability close to 1. For a fixed K B , H B , the probability of condition Therefore, when q ′ is sufficiently large, we obtain the desired statement by choosing m := m 0 + 1.

Remark 4. Our proof is different from the proof presented in [12, Section VII][13, Section VI][15, Section
IV-C]. First, they did not introduce the random matrix U 0 . In their proof, U 0 is fixed to the identity matrix. Hence, they cannot guarantee condition (C1) with U 0 = I for an arbitrary K B , H B with high probability. That is, it is possible for Eve to choose the matrix H B to break condition (C1) with U 0 = I. To satisfy condition (15), U 0 must be randomly chosen. Second, they suggested that (m 0 − m 1 )m 0 + 1 be chosen as m because they employ the concept of list decoding. However, our discussion allows us to choose a much smaller value m 0 + 1 as m. This fact shows that our evaluation is better than their evaluation in this sense. Note that our evaluation does not use list decoding.
Theorem 2 requires a finite field F q ′ with an infinitely large q ′ . The paper [16, Appendix D] discussed the construction of F 2 t whose multiplication and inverse multiplication have calculation complexity O(t log t) 1 .
By choosing t n ′ = ⌈ (m 0 +1) log n ′ log q ⌉ and l n ′ := t n ′ n ′ , Proposition 2 can be rewritten as follows.
Corollary 1. Assume that m 2 + m 1 < m 0 . There exists a sequence of codes Φ ln of block-length l n on a finite field F q whose message set is F kn q such that where the maximum is taken in the same way as with Proposition 2.
Combining Theorem 1 and Corollary 1, we obtain the following theorem.
Theorem 3. We assume that m 2 + m 1 < m 0 . There exists a sequence of codes Φ n of block-length l n on finite field F q whose message set is F kn q such that where the maximum is taken in the same way as with Proposition 2.
Before our proof, we prepare basic facts about information-theoretic security. We focus on a random hash function f R from X to Y with random variable R deciding the function f R . It is called universal2 when for any x ∈ X and y ∈ Y. For s ∈ (0, 1], we define the conditional Rényi entropy H 1+s (X|Z) for the joint distribution P XZ as [4] H 1+s (X|Z) : which is often denoted by H ↑ 1+s (X|Z) in [17], [18]. When X obeys the uniform distribution, we have

Proposition 2. [2], [3][4, Theorem 1]
for s ∈ (0, 1]. Proof: We choose a sequence of codes {Φ n = (φ n , ψ n )} given in Corollary 1. We fixk n := k n − m 2 l n − ⌈ √ l n ⌉. Now, we choose a universal2 linear random hash function f R from F kn q to Fk n q . To construct our code, we consider a virtual protocol as follows. First, Alice sends a larger message M by using the code Φ n , and Bob recovers it. Second, Alice randomly chooses R deciding the hash function f R and sends it to Bob via a public channel. Finally, Alice and Bob apply the hash function f R to their message, and denote the result value byM so that Alice and Bob share the informationM with a probability of close to 1.  [5]. Since Inequality (33) implies that H 1+s (M|Y ln E ) ≥ (k n − l n m 2 ) log q, Proposition 2 yields We set s = 1. Since the number of matrices K E satisfying rank K E = m 2 is bounded by q m 2 (m 3 −m 2 ) , Markov inequality guarantees that the inequality holds for any matrix K E ∈ F m 2 ×m 3 q satisfying rank K E = m 2 at least with probability 1 − 1 q . Therefore, there exists a suitable hash function f r such that which goes to zero as n goes to infinity because m 2 (m 3 − m 2 ) + 1 is a constant. Now, we return to the construction of real codes. We choose the sets M and L as Fk n q and F m 2 ln+⌈ √ ln⌉ q , respectively. Since the linearity and the surjectivity of f r implies that |f −1 r (x)| = q m 2 ln+⌈ √ ln⌉ for any element x ∈ M, we can define the invertible functionf r from M × L to the domain of f r , i.e., F kn q such thatf −1 r (f −1 r (x)) = {x} × L for any element x ∈ M. This condition implies that f r •f r (x, y) = x for (x, y) ∈ M × L. Then, we define our encoder asφ n := φ n •f r , and our decoder asφ n := f r • φ n . The sequence of codes {(φ n ,ψ n )} satisfies the desired requirements.
Remark 5 (Efficient code construction). We discuss an efficient construction of our code from a code (φ n , ψ n ) given in Corollary 1 with q = 2. A modified form of the Toeplitz matrices is also shown to be universal 2 , which is given by a concatenation (T (S), I) of the (m 2 l n + ⌈ √ l n ⌉) ×k n Toeplitz matrix T (S) and thek n ×k n identity matrix I [16], where S is the random seed used to decide the Toeplitz matrix and belongs to F kn−1 2 . The (modified) Toeplitz matrices are particularly useful in practice, because there exists an efficient multiplication algorithm using the fast Fourier transform algorithm with complexity O(l n log l n ).
When the random seed S is fixed, the encoder for our code is given as follows. By using the scramble . A more efficient construction for univeral2 hash function is discussed in [16]. Hence, the decoderψ n is given as Y ln B → (I, T (S))ψ n (Y ln B ). Remark 6. If we do not apply Theorem 1 in step (36) in our proof of Theorem 3, we have to multiply the number of choices of strategy α. As a generalization of (10), this number is given in (11), which grows up double-exponentially. Hence, our proof of Theorem 3 does not work without the use of Theorem 1. Indeed, the paper [37] provided the same statement as Theorem 3. However, it showed only Eq. (30) and lim n→∞ max K,H max α I(M; Y n E )[Φ n , K, H, 0] = 0 instead of (30) by combining Proposition (2) and the result of the paper [43]. To show (30), we need to employ Theorem 1.
IV. ASYMPTOTIC SETTING WITH SECRECY Now, we assume that Alice and Bob can communicate with each other by using a public channel, which allows Alice and Bob to communicate with each other without any error, but the secrecy is not guaranteed. In this case, when Alice and Bob share a sufficient number of secret random variables, they can communicate with each other securely. To share such secret random variables, they can send them via the secure network coding. Now, we consider this problem in an asymptotic setting, where the secrecy condition (30) is definitely required. However, robustness (29) is not necessary because they can check whether or not the transmitted random number is correct by using an error verification test with a public channel after the transmission [52, Section VIII] [51, Step 4 of Protocol 2]. Instead of (37), we impose the following condition.
Indeed, it is not easy to check whether H and α are 0 even when the error verification test is passed. Hence, we cannot relax the secrecy condition (30). We use the following theorem to analyze of this problem.
Theorem 4. Assume that m 3 = m 4 = m 0 . There exists a sequence of codes Φ n of block-length l n on finite field F q whose message set is F kn q such that where the maximum is taken with respect to Indeed, it is trivial from the converse part of the conventional wire-tap channel [28], [29] that there is no code surpassing the rate m 0 − m 2 .
To show the above theorem, we prepare the following proposition.
Proposition 3 ([6, Theorem 7], [7]). We assume that m 3 = m 4 = m 0 and K B = I. There exists a sequence of codes Φ n of block-length n on finite field F q whose message set is F kn q such that where the maximum is taken with respect to K E ∈ F m 2 ×m 0 q .
Note that P e [Φ n , K, 0, α] does not depend on K E . Using the above proposition, we can easily show the following corollary.
where the maximum is taken with respect to (K B , K E ) ∈ F m 4 ×m 3 q × F m 2 ×m 3 q with (4).

Proof of Corollary 2:
We construct our code using a code give in Proposition 3. In the encoding, Alice attaches the initial m 0 vectors I m 0 := (δ i,j ) 1≤,i,j≤m 0 to the original encoded information X n . In the decoding, Bob's initial m 0 vectors form a matrix K B . Then, Bob applies K −1 B to the remaining vectors, and applies the original decoder to the obtained vectors. This code has the same performance as the original code. Since the size of the overhead is constant, this code satisfies the desired performance.
V. NON-LINEAR COUNTEREXAMPLE To clarify the impossibility of Theorem 1 under a non-linear network, we show a counterexample composed of non-linear operations. We consider the network given in Fig. 1, whose edges are E = {e(1), e(2), e(3), e(4)}. Each edge e(i) is assumed to send the binary information Y i . The intermediate node performs a non-linear operation as To send the binary information M ∈ F 2 , we prepare the binary uniform scramble random variable L ∈ F 2 . We consider the following code. The encoder φ is given as The decoder ψ is given as ψ(Y 3 , Y 4 ) := Y 3 + Y 4 . Since Y 3 and Y 4 are given as follows under this code; the decoder can recover M whatever the value of L. Now, we consider the leaked information for the passive attack. Eve is allowed to attack two edges of E except for the pairs {e(1), e(2)} and {e (3), e(4)}. As shown in Appendix A, the mutual information and the l 1 norm security measure of these cases are calculated as where the l 1 norm security measure d 1 (X|Y ) is defined as d 1 (X|Y ) := y x | 1 |X | P Y (y) − P XY (xy)| by using the cardinality |X | of the set of outcomes of the variable X. In this section, we choose 2 as the base of the logarithm. Now, we consider the active attack with E A = E E for the above four cases.  (2), e(4)}, Eve has no advantageous active attack. We adopt a weak secrecy criterion in this section to allow us to observe the difference from the linear case. When Y E is Eve's information and I(M; Y E ) < 1 for all of Eve's possible attacks, we say that the code is secure. Otherwise, it is called insecure. That is, when there exists no functionψ such that ψ(Y E ) = M, our code is secure. When Eve is allowed to use the above passive attack, (51) shows that the code is secure. When Eve is allowed to use the above active attack, the above calculation shows that the code is insecure. Therefore, this example is a counterexample of Theorem 1.

Remark 7. Our analysis covers the optimal codes. As another encoder, we can consider
Replacing M + L by L, the analysis can be reduced to the presented analysis. Other encoders clearly leak the message M to e(1) or e(2).
In this model, Eve can completely contaminate the message M. When Eve takes choice (i), and replaces Y 3 by Y 3 +1, Bob's decoded message is M +1. Under choice (ii), Eve can totally contaminate the message M in a similar way.

VI. UNIQUENESS OF NETWORK CODE GIVEN IN SECTION V
We have provided an example where Eve's active attack improves her performance. However, at the first glance, it is very artificial. In this section, we show that the example is a unique network code under several natural conditions. Now, we consider the transmission of one bit information M by using the network given in Fig. 1. Here, we are allowed to choose an arbitrary deterministic function ϕ from F 2 2 to F 2 2 as our coding operation on the intermediate node. Then, our encoder is given as a stochastic map φ from F 2 to F 2 2 , and our decoder is given as a deterministic function ψ from F 2 2 to F 2 . In this section, we call the triplet (φ, ϕ, ψ) a code over the network of Fig. 1. Then, we have the following theorem. Here, we should remark that only this section and the next consider the choice of our coding operation on the intermediate node, while this operation is fixed in other sections.
Theorem 5. Assume that a code (φ, ϕ, ψ) satisfies the following conditions. Let Y 1 and Y 2 be the random variable generated by the encoder φ when M is subject to the uniform distribution. We define the random variables There is no deterministic functionψ from F 2 2 to F 2 satisfying one of the following conditions.
Since the total number of attacks is the same as the transmission rate from Alice to Bob, no liner code works in this scheme. Hence, we need to introduce a non-linear coding operation in the intermediate node. Theorem 5 shows that such a non-linear coding operation is limited to (47) and (48).
The combination of Theorem 5 and the discussion in Section V implies that there is no code over the network in Fig. 1 to guarantee the secrecy for an active attack. However, this theorem assumes a deterministic coding operation on the intermediate node. If we are allowed to use a randomized operation on the intermediate node such as an encoder, we can construct a code whose secrecy holds even against Eve's active attack in this situation as follows. In the first step, we employ the code given in (49). Using another scramble random variable L ′ , the intermediate node performs the following coding operation: Then, Eve cannot recover the message M from . This example shows that the deterministic condition for ϕ is crucial in Theorem 5. Proof: Step (1): To satisfy condition (a), we need to recover the message M from (Y 1 , Y 2 ) from a deterministic function f . Functions from F 2 2 to F 2 as classified as follows.
The cases in (57) are not secure. The cases in (58) are reduced to the case M = Y 1 + Y 2 . The cases in (59) and (60) are reduced to the case M = Y 1 Y 2 . Hence, we consider only these two cases.
Step (2): Now, we consider the case M = Y 1 + Y 2 . When Y 3 or Y 4 is given as a non-zero linear function of Y 1 and Y 2 , we denote the random variable as Y * . Hence, Y 1 or Y 2 is linearly independent of Y * . We denote the linearly independent variable as Y * * . When Eve eavesdrops Y * and Y * * , she can recover Y 1 and Y 2 and so she can also recover M. To satisfy condition (b), we need to avoid such an attack, which requires both Y 3 and Y 4 to be non-linear functions of (Y 1 , Y 2 ). They are given as two of the functions given in (59) and (60). Since any function in (60) is deterministically given from a function given in (59), we consider only functions in (59). Under this constraint, if and only if (Y 3 , Y 4 ) are given as the pair The latter case is the same as (47) and (48). In the former case, we obtain (47) and (48) by replacing Y 1 and Y 2 by Y 1 + 1 and Y 2 + 1.
Step (3): Now, we consider the case where M = Y 1 Y 2 . For the same reason as with Step (2), condition (b) requires both Y 3 and Y 4 to be non-linear functions of (Y 1 , Y 2 ). Thus, we consider only functions in (59). For secrecy, i.e., to satisfy (b), we cannot use Y 1 Y 2 . Hence, we need to choose two from (Y 1 + 1)(Y 2 + 1), (Y 1 + 1)Y 2 , and Y 1 (Y 2 + 1). However, no two of them can recover M. To observe this fact, we consider cases with (Y 1 + 1)Y 2 and Y 1 (Y 2 + 1). In these cases, when (Y 1 , Y 2 ) = (0, 0) or (1, 1), both values are zero. That is, we cannot distinguish (0, 0) and (1, 1). Hence, we cannot recover M from (Y 1 + 1)Y 2 and Y 1 (Y 2 + 1), i.e., condition (a) does not hold. We can show this fact in other pairs in the same way. Therefore, there is no operation satisfying the required conditions when M = Y 1 Y 2 .
VII. SECURE NETWORK CODING OVER ACTIVE ATTACK Now, we construct a secure network coding against any active attack given in Section V on the network given in Fig. 1 when the message and the information at the edges are given as an element of Z d . Here, we define our code (φ, ϕ, ψ) in the same way as in Section VI. That is, the coding operation ϕ on the intermediate node has no additional scramble random variable. Now, we seek a code that satisfies the following conditions.
(a) (Recoverability) Bob can recover the message M from Y 3 and Y 4 when Eve does not make any replacement. (b) (Secrecy) No active attackψ from Z 3 d to Z d satisfies one of the following conditions.
where Y ′ 1 and Y ′ 2 are the information replaced by Eve at the edges e(1) and e(2), and Y 3 and Y 4 are the information at the edges e(3) and e(4). For simplicity, in this section, we employ a scramble variable L taking values in Z d . Hence, we assume that the encoder φ is given as a pair of functions (φ (1) , φ (2) ) that maps two random variables (M, L) to the two variables (Y 1 , Y 2 ). That is, the encoder φ forms a function from Z 2 d to itself. Now, we fix the function φ as follows For a coding operation ϕ, we define the functions ϕ (3) and ϕ (4) as Then, we regard the functions ϕ (3) and ϕ (4) as matrices as follows, i,j := ϕ (4) (i, j).
To discuss condition (b), we introduce an anti-Latin square. A matrix a i,j on Z d is called an anti-Latin square when each row and each column have duplicate elements as which is the opposite requirement to a Latin square. Therefore, under condition (63), conditions (a) and (b) are rewritten as (a') For each a ∈ Z d and j = j ′ ∈ Z d , the relation ϕ (4) The matrices ϕ (3) and ϕ (4) are an anti-Latin squares. The equivalence between conditions (a) and (a') is trivial. We show the equivalence between (b) and (b'). Assume that Eve eavesdrops and contaminates Y 1 and eavesdrops Y 3 . Choosing the replaced information Y ′ 1 , Eve can choose a row of the matrix ϕ (3) . To prevent Eve from recovering M perfectly, all the rows of the matrix ϕ (3) need to have duplicate elements. Hence, to satisfy condition (b), both matrices ϕ (3) and ϕ (4) need to satisfy this duplication requirement for all rows and columns.
Indeed, it is trivial to find anti-Latin squares. However, they need to satisfy condition (a') as well. Condition (b') forbids a linear operation on the intermediate node in the finite field case. A pair of anti-Latin squares is called decodable when it satisfies condition (a'). That is, a decodable pair of anti-Latin squares gives a code on the network given in Fig. 1 satisfying conditions (a) Then, we have which satisfy condition (a'). Hence, the functions ϕ (3) and ϕ (4) give a pair of anti-Latin squares. Next, we consider the even case with d These constructions are generalized to the case with a general even number d = 2m with m ≥ 2 as follows. The functions ϕ (3) and ϕ (4) are defined as Then, we have which satisfy condition (a'). Hence, the functions ϕ (3) and ϕ (4) give a pair of anti-Latin squares.
In summary, since these examples work with d ≥ 3, we can conclude that there exists a secure code over the active attacks given in Section V on the network of Fig. 1 when d ≥ 3. Furthermore, when ϕ is given by these pairs of anti-Latin squares, Bob can decode L as well as M while the code given by (66) nor (67) cannot. That is, these systematic constructions work well whenever the encoder φ = (φ (1) , φ (2) ) is a one-to-one function on Z 2 d to satisfy the condition {i|∃j, φ (1) Next, we discuss the mutual information under the given code. Since Y i is independent of M and H(Y j |MY i ) = 0, we have When d is odd, we have for any y i with i = 1, 2 and j = 3, 4. When d ≥ 4 and d is even, we have for any y 1 , y 2 . In summary, when d is large, we have VIII. LOWER BOUND OF LEAKED INFORMATION Here, we discuss the lower bound of leaked information under the network given in Fig. 1 with conditions (C1-3).
(C2) The coding operation on the intermediate node is deterministic.
(C3) Alice can use scramble random variable L. Now, we assume that the cardinality of information transmitted in each edge is d. Then, we have the following theorem.
Theorem 6. Any network code satisfies the inequality for i = 1, 2.
Theorem 6 shows that where the maximum is chosen from i = 1, 2 and j = 3, 4. That is, to realize max i,j I(M; Y i Y j ) = 0, the message M needs to satisfy This upper bound is almost equal to the RHS of (101) when d is large.
where (a) follows from the fact that Y 3 Y 4 is decided by Y 1 Y 2 . Thus, we obtain

IX. APPLICATION TO NETWORK QUANTUM KEY DISTRIBUTION
In this section, to realize long distance communication with quantum key distribution, we consider a network of quantum key distribution as follows. The authorized sender, Alice, is connected to the authorized receiver, Bob, via the network given by the graph (V, E) with |E| = k. For every edge (u, v) ∈ E, the distant nodes u and v generate secure common keys by quantum key distribution. That is, k pairs of secure keys are generated by quantum key distribution. We call the secure transmission via this network network quantum key distribution. When all nodes are authenticated, Alice can securely send her message X to Bob by using these linear operations in the following way. However, it is very difficult to guarantee security when a part of nodes are occupied by Eve. The main problem with network quantum key distribution is the latter case.
For simplicity, we first consider the former case. We assume that all nodes are secure and proper linear operations are performed on all nodes. First, we consider the network coding using the graph (V, E) with these linear operations. Let X i be the random variable to be transmitted on the i-th edge. Let Z i be the secure keys generated in the i-th edge by quantum key distribution. When X i is directly transmitted, this information transmission is not secure. To realize security, Y i := X i + Z i is transmitted on the i-th edge, instead. Then, a secure transmission from Alice to Bob can be realized.
However, when some intermediate nodes are occupied by Eve, the security is not trivial. Such a model is often called a node adversary model while the model introduced in Section II is called an edge adversary model. To investigate the security in the node adversary model, we convert a given node adversary model to a special case of the edge adversary model as in [44]. In an edge adversary model, Eve wiretaps and contaminates the information only on the edges E E . To apply the model to the current situation, we consider that all the edges linked to the nodes occupied by Eve are wiretapped and controlled by Eve. When these occupied nodes communicate each other, Eve's attack is active attack. That is, analysis for active attack is essential. Therefore, we can apply Theorem 3 to the security analysis of the direct transmission of secret message via network quantum key distribution. In quantum key distribution, it is usual to assume that Alice and Bob share secure random numbers whose lengths are asymptotically negligible in block-length n. In this case, to generate secure keys, we can employ Theorem 4.
For example, we consider the following network given in Fig. 2, which has nodes n(1), . . . , n(8) as intermediates nodes. This network connects Alice and Bob with rank 4. The ranks of K E and H B of typical cases are summarized in Table II  rank 2 per single use of the network. In the former case, since 4 − 2 − 2 = 0, Theorem 3 cannot guarantee that Alice securely transmits her message to Bob.
As another example, we consider the network given in Fig. 3, in which, the nodes connect the next nodes and the nodes after the next. Assume that we have pairs of secret keys in the network of Fig. 3. We suppose that n(1) intends to communicate with n(8) securely. They make the network as n(1) → n(12) → n(10) → n(8), n(1) → n(11) → n(9) → n(8), n(1) → n(3) → n(5) → n(7) → n(8), n(1) → n(2) → n(4) → n(6) → n(8), which connects n(1) and n(8) with rank 4. When Eve occupies one intermediate node, the ranks of K E and H B are one. In the latter case, Theorem 4 guarantees that Alice in n(1) can securely transmit a random number with rank 3 per single use of the network. In the former case, Theorem 3 guarantees that Alice in n(1) securely transmits her message to Bob with rank 2 per single use of the network. When Eve occupies two intermediate nodes, the ranks of K E and H B are at most two. In the latter case, Theorem 4 guarantees that Alice in n(1) can securely transmit a random number with rank 2 per single use of the network. In the former case, Theorem 3 cannot guarantee that Alice in n(1) securely transmits her message to Bob. This method can be generalized to the case when Alice and Bob are n(i) and n(j) with |i − j| ≥ 2(mod 12).
Indeed, this idea can be generalized to the cyclic network even when the number of nodes is odd. Further, this network can be generalized to the following network of quantum key distribution with two integers k > l > 0. The set of nodes is given as {n(i)} k i=1 , and the set of edges is given as {(n(i), n(j))} |i−j|≤l( mod k) . Now, we set Alice and Bob as n(i) and n(j) with |i − j| ≥ l( mod k). Then, they can make 2l paths connecting n(i) and n(j) without duplication in the intermediate nodes. Then, even when 2l − 1 nodes are occupied by Eve, Alice and Bob can securely share a secret random number due to Theorem 4.

X. CONCLUSION
We have discussed how sequential error injection affects the information leaked to Eve. As the result, we have shown that there is no improvement when the network is composed of linear operations. However, when the network contains non-linear operations, we have found a counterexample that improves the information obtained by Eve. Moreover, we have shown the achievability of the asymptotic rate m 0 − m 1 − m 2 for a linear network under the secrecy and robustness conditions when the transmission rate from Alice to Bob is m 0 , the rate of noise injected by Eve is m 1 , and the rate of information leakage to Eve is m 2 . The converse part of this rate is an interesting open problem. In addition, we have derived the asymptotically optimal transmission rate when we are concerned about secrecy were Eve to inject noise into the network.
We have also discussed security over such active attacks on codes with a non-linear operation on the intermediate node in the network of Fig. 1. In the binary case, when we impose our code to a certain security condition without an active attack, as shown in Section VI, our code is limited to the non-linear code given in Section V. Unfortunately, the non-linear code given in Section V is insecure under active attacks. To meet this kind of security condition, the coding operation on the intermediate node needs to be non-linear. To characterize this kind of security, we introduce a new concept an "anti-Latin square", which is an opposite concept to a Latin square. That is, such a secure code can be given as a decodable pair of anti-Latin squares while the concept of "decodable" is also introduced in Section VII. We have also shown the existence of a decodable pair of d × d anti-Latin squares when d ≥ 3. This fact shows that there exists a secure code over active attacks in the sense described in Section V except for the binary case.
Further, we have applied our results to network quantum key distribution. Then, we have clarified what type of network will enable us to realize secure long distance communication based on short distance quantum key distribution. However, when we consider only the case given in Fig. 3, we can employ a classical (non-quantum) secret sharing protocol [30] instead of network coding because all of communications of this case are routing. In particular, cheater-identifiable secret sharing against rushing cheaters [31], [32], [33], [34], [35] enables us to share secure keys without using public channels or prior shared randomness.
In this way, this paper has discussed the application of secure network coding to a network model whose communications on the edges are realized by quantum key distribution. Replacing the role of quantum key distribution by physical layer security, we can consider a secure network based on physical layer security. In particular, we can use secure wireless communication [45], [46], [47], [48], [49], [50], [51] as a typical form of physical layer security, which provides us with a secure network based on secure wireless communication. A crucial weak point of physical layer security is the possibility that the eavesdropper might break the assumption of the model. Such an attack might be realized in the following cases. (1) The eavesdropper concentrates his/her resources on one point. (2) The eavesdropper luckily encounters a situation that the assumption is broken. When we combine physical layer security and secure network coding in the above way, to eavesdrop our information, the eavesdropper needs to break the model of physical layer security in multiple communication channels. In case (1), to realize this condition, the eavesdropper has to distribute his/her resources, which increases the difficulty of eavesdropping. For case (2), the eavesdropper must be lucky in multiple communication channels, and this probability is very small. In this way, this kind of combination is particularly useful. ACKNOWLEDGMENTS MH and NC are very grateful to Dr. Wangmei Guo for helpful discussions and comments. MH is thankful to Prof. Sidharth Jaggi regarding the relation between conditions (15) and (16). The studies reported here were supported in part by the JSPS Grant-in-Aid for Scientific Research ( where the remaining conditional probabilities are zero. Therefore, =P Y 1 ,Y 3 (0, 0) · 0 + (P Y 1 ,Y 3 (1, 0) + P Y 1 ,Y 3 (1, 1)) · 1 = 1 2 .