Asymptotically Secure Network Code for Active Attacks and its Application to Network Quantum Key Distribution
Masahito Hayashi Ning Cai
cs.IT cs.NI math.IT







M. Hayashi 
and N. Cai: 
Asymptotically Secure Network Code for Active Attacks 



Asymptotically Secure Network Code for Active Attacks 
and its Application to Network Quantum Key Distribution


    Masahito Hayashi Fellow, IEEE

and Ning Cai Fellow, IEEE
The work of M. Hayashi was supported in part by
the Japan Society of the Promotion of Science (JSPS) Grant-in-Aid 
for Scientific Research (B) Grant 16KT0017 and
for Scientific Research (A) Grant 17H01280 and
for Scientific Research (C) Grant 16K00014,
in part by the Okawa Research Grant, and 
in part by the Kayamori Foundation of Informational Science Advancement.
The material in this paper was presented in part at the 2017 IEEE International Symposium on Information Theory (ISIT 2017),   Aachen (Germany), 25-30 June 2017 <cit.>.
Masahito Hayashi is with the Graduate School of Mathematics, Nagoya University, Nagoya, 464-8602, Japan. 
He is also with 
Shenzhen Institute for Quantum Science and Engineering, Southern University of Science and Technology,
Shenzhen, 518055, China,
Center for Quantum Computing, Peng Cheng Laboratory, Shenzhen 518000, China,
and the Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, 117542, Singapore
(e-mail:masahito@math.nagoya-u.ac.jp).




Ning Cai is with the School of Information Science and Technology, ShanghaiTech University, Middle Huaxia Road no 393,
Pudong, Shanghai  201210, China
(e-mail: ningcai@shanghaitech.edu.cn). 
    version of December 30, 2023
=======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================






When there exists a malicious attacker in the network, we need to be careful of eavesdropping and
contamination. This problem is crucial for network communication when the network is realized by
a partially trusted relay of quantum key distribution. We discuss the asymptotic rate in a linear network
with the secrecy and robustness conditions when the above type of attacker exists. Also, under the
same setting, we discuss the asymptotic rate in a linear network when we impose the secrecy condition
alone. Then, we apply these results to the network composed of a partially trusted relay of quantum key
distribution, which enables us to realize secure long-distance communication via short-distance quantum
key distribution.



 

secure network coding,
sequential injection,

active attack,
universal code,
asymptotic rate




§ INTRODUCTION

Secure information transmission over a network is an important topic
because there is a risk that a part of the network is broken, contaminated, and/or 
eavesdropped in a large network system.
Cai and Yeung <cit.> started the study of 
secure network coding, which offers a method securely transmitting information from the authorized sender to the authorized receiver.
The demand for such a type of secure communication is increasing beyond the areas of information theory and communication theory. 
For example, to realize rigorous security, quantum key distribution is actively studied <cit.>.
Its commercial use has been well developed for limited transmission distance <cit.>.
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, 
they often consider using quantum repeater <cit.>.
However, it is also difficult to realize quantum repeater.
Hence, it is natural to establish a network whose edges are realized by 
secure communication by one-time-pad use of keys generated  by 
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 
connected by an edge.
The secure keys shared by two nodes realize a secure channel between the two nodes.
Hence, the application of the network coding to the network composed of these secure channels
yields a scheme to realize secure communication between two distinct parties across a long distance.
However, there is a possibility that a part of the nodes are occupied by Eve.
Hence, we need to use secure network coding instead of network coding.
To resolve this problem,
the pioneering papers <cit.> studied this type of information transmission for the case of partially trusted routing networks. 
This paper addresses a general network including routing networks, 
in which a part of the nodes are attacked and 
the attacked nodes cannot be identified by the sender and the receiver like the Byzantine setting.
The network topology is not known to the sender and the receiver.

In the above type of network, there are two types of attacks.
In the first type of attack, the malicious adversary, Eve, wiretaps  a subset E_E of all the channels in a network,
which was studied by the first paper by Cai and Yeung <cit.>.
Using the universal hashing lemma <cit.>, 
the papers <cit.> showed the existence of a secrecy code that works universally for any type of eavesdropper 
when the cardinality of E_E is bounded.
In particular, the paper <cit.> discussed a concrete construction of such a universally secure code, which is more practical.
As another type of attack on information transmission via a network,
a malicious adversary contaminates the communication by 
changing the information on a subset E_A of all the channels in the network.
Using an error correction, the papers <cit.> proposed a method to protect the message from contamination.
That is, we require that the authorized receiver correctly recovers the message, which is called robustness.
Now, for simplicity, we consider the unicast setting.
When the transmission rate from the authorized sender, Alice, to the authorized receiver, Bob, is m_0
and the rate of noise injected by Eve is m_1,
using the results published in <cit.>,
the study <cit.> showed that
there exists a sequence of asymptotically correctable codes with the rate
m_0-m_1 if the rate of information leakage to Eve is less than m_0-m_1.

However, there is a possibility that the malicious adversary combines eavesdropping and contamination.
That is, contaminating a part of the channels, the malicious adversary might improve the ability of eavesdropping
while a parallel network offers no such a possibility <cit.>.
In fact, in arbitrarily varying channel model,
noise injection is allowed after Eve's eavesdropping, but  
Eve does not eavesdrop the channel after Eve's noise injection <cit.><cit.>.
The studies <cit.> discussed the secrecy
when Eve eavesdrops the information transmitted on the channels in E_E after noises are injected in E_A,
but they assume that Eve does not know the information of the injected noise. 

In contrast, this paper discusses the secrecy when Eve 
adds artificial information to the information transmitted on the channels in E_A, 
eavesdrops the information transmitted on the channels in E_E, and 
estimates the original message from the eavesdropped information and the information of the injected noises.
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 <cit.> 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.
Fortunately, the previous paper <cit.>
showed that an active attack has the same performance as the passive attack in the case of linear codes.

The aim of this paper is as follows.
First, we give a formulation of our setting with
a general set E_E of eavesdropping nodes
and a general set E_A of noise-injection nodes.
Then, we state that no strategy can improve Eve's information
when every operation in the network is linear,
which is a brief review of the result of <cit.>.
Next, 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, given linear operations on the intermediate nodes with a certain order,
our protocol controls only the encoder in the sender and the decoder in the receiver.
Since we address the static Byzantine setting,
the sender and the receiver do not know the two sets E_E and E_A, 
i.e., what edges are attacked,
while they know the channel parameter m_0 and the upper bounds of m_1 and m_2.
Although intermediate nodes make linear operation over a single transmission,
the sender and the decoder are allowed to make coding operations across several transmissions.
Such a coding is called a non-local code to distinguish operations over a single transmission.
We show the existence of such a secure protocol with rate m_0-m_1-m_2.
Since our non-local code depends only on the number m_0, 
the upper bounds of m_1 and m_2,
and the dimensions of the input and the output,
it works universally.
Also, 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, 
we do not need to impose robustness, but need the correctness only for passive attack
because we can make error verification <cit.>.
In such a case, we show the existence of a secure protocol with the rate m_0-m_2.

Then, we apply these two types of asymptotic analyses to network quantum key distribution. 
Since public communication is allowed in quantum key distribution, 
the latter setting is more useful for the security analysis in
network quantum key distribution.

Further, although the above discussion addresses the unicast setting, 
we explain how to extend this setting to the multiple multicast case including the multiple unicast case.




The remaining part of this paper is organized as follows.
Section <ref> formulates our problem and shows the 
impossibility of Eve's eavesdropping under a linear network,
which is a brief review of the result by <cit.>.
Section <ref> discusses the asymptotic setting,
and show the achievability of the asymptotic rate m_0-m_1-m_2.
Section <ref> discusses the asymptotic setting with secrecy without robustness.
Using the result of Section <ref>,
Section <ref> considers the application of obtained results to 
network quantum key distribution
Section <ref> applies the obtained result to multiple multicast networks.
In Section <ref>, we state the conclusion.










§ SECRECY IN FINITE-LENGTH SETTING
S2

Although the paper <cit.> discusses 
the formulation of a channel model of network 
with eavesdropping and contamination more rigorously,
this section briefly explains this model in the case of an acyclic network with well synchronization.
We consider the unicast setting.
Assume that the authorized sender, Alice, and the authorized receiver, Bob,
are linked via an acyclic network with the set of edges E, where the operations on all nodes are linear on the finite field _q with prime power q.
Alice inputs the input variable X[In this paper, we denote the vector on _q by a bold letter.
But, we use a non-bold letter to describe a scalar and a matrix.]
 in _q^m_3 and Bob receives the output variable Y_B in _q^m_4.
We also assume that the malicious adversary, Eve, wiretaps the information Y_E in 
_q^m_6
on the edges of a subset E_E⊂ E.
Now, we fix the topology and dynamics (operations on the intermediate nodes) of the network.
When we assume all operations on the intermediate nodes are linear,
there exist matrices K_B ∈_q^m_4× m_3 

and K_E ∈_q^m_6× m_3

such that the variables X, Y_B, and Y_E satisfy their relations

    Y_B=K_B  X,    Y_E=K_E  X.E2

That is, the matrices K_B and K_E are decided from the network topology and dynamics.
We call this attack the passive attack.




To address the active attack, we consider stronger Eve, i.e., we assume that Eve adds an error Z in _q^m_1  on the edges of a subset E_A⊂ E.
Using matrices H_B ∈_q^m_4× m_1 
and H_E ∈_q^m_6× m_1, 
we rewrite the above relations as

    Y_B=K_B  X+ H_B  Z,    Y_E=K_E  X+ H_E  Z, E4

which is called the wiretap and addition model.
We set the parameter m_0 as 

    K_B= m_0 ,
    
    1-6


and assume the ranks of H_B and K_E as

    H_B= m_1,   K_E= m_2 .
    1-6X

Hence, the channel parameters are summarized as Table <ref>.




Now, to consider the 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 done with this order.
In this representation, the elements 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 η. 
The causality yields that

    H_E;j,i=0  when η(i) ≥ζ(j). E14

It is natural that Eve can choose the information to be added in the edge e(i) ∈ E_A
based on the information obtained previously on the edges in the subset 
{e(ζ(j)) ∈ E_E|ζ( j) ≤η(i)}.
That is, the added error Z is given as a function α of Y_E,
which can be regarded as Eve's strategy. 
We call this attack the active attack with the strategy α.


Now, we consider the n-transmission setting, in which, Alice uses the same network n times to send the message to Bob.
Alice's input variable (Eve's added variable) is given as 
a matrix X^n=( X_1, …,  X_n) ∈_q^m_3× n (a matrix Z^n=( Z_1, …,  Z_n) ∈_q^m_1× n),
and Bob's (Eve's) received variable is given as 
a matrix Y_B^n∈_q^m_4× n (a matrix Y_E^n∈_q^m_2× n).
We assume that the topology and dynamics of the network 
and the edge attacked by Eve
are not changed during n transmissions.
In particular, the operations on intermediate nodes are not changed.
Then, their relation is given as

    Y_B^n   =K_B X^n+ H_B Z^n, F1n
    
    Y_E^n   =K_E X^n+ H_E Z^n. F2n

Notice that the relations (<ref>) and (<ref>) with H_E=0
(only the relation (<ref>)) were treated as the starting point of the paper
<cit.> (the papers <cit.>).

To discuss the secrecy and the robustness, we formulate a code.
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 _q^m_3× n, and the decoder is given as ψ_n from _q^m_4× n to M.
Our code is the pair (ϕ_n,ψ_n), and is denoted by Φ_n.
Since the code pair of ϕ_n and ψ_n is across n transmission,
it is called a non-local code to distinguish operations over a single transmission.
Then, we denote the message and  the scramble random number by 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,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_E^n,Z^n) between M and Eve's information Y_E^n and Z^n
Since the variable Z^n is given as a function of Y_E^n,
we have I(M; Y_E^n,Z^n)=I(M; Y_E^n).
Since the leaked information is given as a function of 
Φ_n,K,H,α in this situation, 
we denote it by I(M;Y_E^n)[Φ_n,K,H,α].
When we always choose Z^n=0, the attack is the same as the passive attack.
This strategy is denoted by 0.




and chooses her strategy dependently of the position.

Now, we have the following theorem <cit.>.
T1
For any Eve's strategy α, 
Eve's information Y_E^n with strategy α
and that with strategy 0 can be simulated by each other.
Hence, we have the equation

    I(M;Y_E^n)[Φ_n,K,H,0]
    =
    I(M;Y_E^n)[Φ_n,K,H,α].



While the paper <cit.> showed this theorem in a more general setting
with more rigorous description of the problem setting,
we briefly give its proof in Appendix <ref>.
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 the secrecy under the passive attack.



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 into account 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 α^n,
we assume condition (<ref>).
(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_6) because it does not affect Eve's information.
Then, even when we fix the matrices K_E,H_E,
the number of choices of α^n is 

    q^∑_i: η(i) < ζ(m_6) q^T_i, F17

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_6) q^T_i on (<ref>).
For a generic natural number n,
the number of choices of α^n is

    q^n∑_i: η(i) < ζ(m_6) q^n T_iF18.






§ ASYMPTOTIC SETTING WITH SECRECY AND ROBUSTNESS
S3
In this section, under the model given in Section <ref>,
we consider the asymptotic setting by taking account of robustness as well as secrecy
while Eve's strategy α is assumed to satisfy the uniqueness condition.
We previously assumed that 
the matrices K_B, K_E, H_B, and H_E, i.e., 
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 rank of the information injected by Eve are limited to m_2 and m_1, respectively.
Indeed, when the original network is given by the graph (V,E) and
Eve eavesdrops at most m_6' edges and injects the noise at most m_5' edges,
we have m_2 ≤ m_6' and m_1≤ m_5'.
This evaluation is still valid even in the wiretap and replacement model.
Therefore, it is natural to assume the upper bounds of these dimensions.
(See Remark <ref>.)

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 a certain distribution.
However, our problem 
is different from the conventional error correction 
because the decoding error probability depends on the strategy α^n.
Hence, we denote it by P_e[Φ_n,K,H,α^n].

Then, the following proposition is known.


T2
Assume that 
m_2+m_1< m_0.
There exists a sequence of non-local codes Φ_n of block-length l_n on a finite field _q

whose message set is _q^k_n such that

    lim_n →∞k_n/l_n = m_0-m_1
       lim_n →∞max_K,Hmax_α^n 
    P_e[Φ_n, K,H,α^n]=0,

where the maximum is taken with respect to
(K_B,H_B,K_E,H_E) ∈_q^m_4× m_3×_q^m_4× m_5×_q^m_6× m_3×_q^m_6× m_5 with conditions (<ref>) and 
(<ref>).
Here, there is no restriction for the choice of m_5 and m_6.


The existing proof of Proposition <ref>
is given as a combination of several results.
Each part of the existing proof is hard to read because it omits the detail derivation. 
Hence, for readers' convenience, 
we give its alternative proof in Appendix <ref>, which has an improvement over the existing proof. 
Combining Theorem <ref> and Proposition <ref>, we obtain the following theorem.
T3
We assume that
m_2+m_1< m_0.

There exists a sequence of non-local codes Φ_n 
of block-length l_n on finite field _q

whose message set is _q^k_n such that

    lim_n →∞k_n/l_n = m_0-m_1-m_2
       lim_n →∞max_K,Hmax_α^n 
    P_e[Φ_n,K,H,α^n]=0 H3-181
       
    max_K,Hmax_α^n 
    I(M;Y_E^n)[Φ_n,K,H,α^n]=0, H3-182

where the maximum is taken in the same way as with Proposition <ref>.



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 

    Pr{ f_R(x)=y}≤| Y|/| X|

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 <cit.>

    H_1+s(X|Z):= -1/slog∑_z ∈ Z P_Z(z) ∑_x ∈ X P_X|Z(x|z)^1+s,

which is often denoted by H_1+s^↑(X|Z) in <cit.>.
When X obeys the uniform distribution, we have 

    H_1+s(X|Z) ≥log  | X|/| Z|. F15



<cit.><cit.>T4

    I(f_R(X);Z|R) ≤e^s log | Y|- H_1+s(X|Z)/s


for s ∈ (0,1].

Theorem <ref>
We choose a sequence of non-local codes {Φ_n=(ϕ_n,ψ_n)}  given in Corollary <ref>.

We fix k̅_n:= k_n- m_2l_n- ⌈√(l_n)⌉.
Now, we choose a universal2 linear surjective random hash function f_R from _q^k_n to _q^k̅_n.


To construct our non-local code, we consider a virtual protocol as follows. 
First, Alice sends a larger message M by using the non-local 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 by M̅ so that Alice and Bob share the information  M̅ with a probability of close to 1.

Since the conditional mutual information between
M̅ and Y_E^l_n depends on Φ_n,K,H,α^n,
we denote it by I(M̅;Y_E^l_n|R)[Φ_n,K,H,α^n].
Theorem <ref> shows I(M̅;Y_E^l_n|R)[Φ_n,K,H,α^n]=
 I(M̅;Y_E^l_n|R)[Φ_n,K,H,0], which does not depend on K_B,H_B ,H_E and depends only on K_E.
Now, we evaluate this leaked information via a similar idea to that reported in <cit.>.
Since inequality (<ref>) implies that 
H_1+s(M|Y_E^l_n) ≥( k_n -l_n m_2) log q,
Proposition <ref> yields

    I(M̅;Y_E^l_n|R)[Φ_n,K,H,0]
    ≤   e^s (k̅_nlog q - H_1+s(M|Y_E^l_n))/s
    ≤   q^s (k̅_n- k_n +l_n m_2)/s≤q^-s ⌈√(l_n)⌉/s.

We set s=1.
For each matrix K_E ∈_q^m_6× m_3 satisfying K_E= m_2,
Markov inequality guarantees that the inequality

    I(M̅;Y_E^l_n)[Φ_n,K,H,0]|_R=r≤ q^- ⌈√(l_n)⌉ +c+1F20a

holds at least with probability 1-q^-c-1.
Since the number of matrices K_E satisfying K_E=m_2 is upper bounded by q^m_6m_3,
there exists a matrix K_E ∈_q^m_6× m_3 such that
K_E= m_2 and (<ref>) does not hold
at most with probability q^m_6m_3 q^-c-1.
Hence, (<ref>) holds for any matrix K_E ∈_q^m_6× m_3 satisfying K_E= m_2
at least with probability 1-q^m_6m_3 q^-c-1.
Letting c be m_6m_3, we have

    I(M̅;Y_E^l_n)[Φ_n,K,H,0]|_R=r≤ q^- ⌈√(l_n)⌉ +m_6m_3+1F20

for any matrix K_E ∈_q^m_6× m_3 satisfying K_E= m_2
at least with probability 1-1/q.
Therefore, there exists a suitable hash function f_r such that

    I(M̅;Y_E^l_n)[Φ_n,K,H,0]|_R=r≤ q^- ⌈√(l_n)⌉ +m_6m_3+1,

which goes to zero as n goes to infinity because 
m_6m_3+1 is a constant.
Since the code on our network is linear,
Eve observes a subspace of input information
_q^k̅_n.
Hence, the amount of leaked information is an integer times log q.
Hence, as discussed in  <cit.>,
when l_n is sufficiently large, there exists a suitable hash function f_r such that

    I(M̅;Y_E^l_n)[Φ_n,K,H,0]|_R=r
    =0.


Now, we return to the construction of non-local codes.
We choose the sets M and L as
_q^k̅_n and _q^m_2l_n+ ⌈√(l_n)⌉, respectively.
Since the linearity and the surjectivity of f_r implies that
|f_r^-1(x)|=q^m_2l_n+ ⌈√(l_n)⌉ for any element x∈ M,
we can define the invertible function f̅_r from M× L
to the domain of f_r, i.e., _q^k_n such that f̅_r^-1 (f_r^-1(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 non-local encoder as ϕ̅_n:= ϕ_n ∘f̅_r,
and our non-local decoder as ψ̅_n:= f_r∘ψ_n.
The sequence of non-local codes {(ϕ̅_n,ψ̅_n)}
satisfies the desired requirements.


R-Dim
If we replace the condition (<ref>) by the condition

    H_B≤ m_1,   K_E≤ m_2 ,
    1-6X2

the Proposition <ref> and Theorem <ref> still hold due to the following reason.
For (K_B,H_B,K_E,H_E) to satisfy (<ref>) and (<ref>), 
there exists (K_B',H_B',K_E',H_E') to satisfy (<ref>) and (<ref>) such that 
P_e[Φ_n, K,H,α^n] ≤ P_e[Φ_n, K',H',α^n]
and
I(M;Y_E^n)[Φ_n,K,H,α^n]≤
I(M;Y_E^n)[Φ_n,K',H',α^n].
Hence,
the Proposition <ref> and Theorem <ref> still hold under this modification.



We discuss an efficient construction of our non-local code from a non-local code 
(ϕ_n,ψ_n) given in Corollary <ref> with q=2.
A modified form of the Toeplitz matrices is also shown to be 
a universal2 linear surjective hash function, 
which is given by a concatenation (T(S), I) of the 
(m_2 l_n+ ⌈√(l_n)⌉) ×k̅_n Toeplitz matrix T(S) and 
the k̅_n ×k̅_n identity matrix I <cit.>,
where S is the random seed used to decide the Toeplitz matrix and belongs to _2^k_n-1.
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_nlog l_n). 

When the random seed S is fixed, 
the encoder for our non-local code is given as follows.
By using the scramble random variable L ∈_2^m_2 l_n+ ⌈√(l_n)⌉),
the encoder ϕ̅_n is given as ϕ_n( 
(
[      I - T(S);      0      I ])
(
[ M; L ])
)
because 
(I,T(S))
(
[      I - T(S);      0      I ])
= (I, 0).
(The multiplication of Toeplitz matrix T(S) can be performed as a part of a circulant matrix. 
For example, the reference <cit.>
provides a method to give a circulant matrix.).
A more efficient construction for univeral2 hash function is discussed in <cit.>.
Hence, the decoder ψ̅_n is given as Y_B^l_n↦ (I,T(S)) ψ_n(Y_B^l_n).





Here, we clarify the difference between our results and the setting of the preceding papers <cit.>, which consider correctness and secrecy.
Their secrecy analysis is different from our analysis
although the non-local code construction in <cit.> does not depend on the concrete form of 
matrices K_B, K_E, H_B, H_E, which is similar to our non-local code construction.

While the papers <cit.> considered correctness when the error exists,
it discusses the secrecy only when there is no error.
Similarly, the paper <cit.> considers a different active adversary model, in which,
it discusses
the node-repair and data-reconstruction operations
even in the presence of such an attack
while the model of passive eavesdroppers in the paper <cit.> 
discusses the secrecy with respect to the message to be transmitted.
Indeed, the papers <cit.> provided a statement similar to Theorem <ref>.
However, it showed only Eq. (<ref>) and 
lim_n →∞max_K,H
I(M;Y_E^n)[Φ_n,K,H,0]=0
instead of (<ref>)
by combining Proposition <ref> and the result of the paper <cit.>. 
To show (<ref>), we need to employ Theorem <ref>.
If we do not apply Theorem <ref> in step (<ref>) in our proof of Theorem <ref>,
we have to multiply the number of choices of strategy α^n.
As a generalization of (<ref>), this number is given in (<ref>),
which grows up double-exponentially. 
Hence, our proof of Theorem <ref> does not work without the use of Theorem <ref>.


While the papers <cit.><cit.> consider the secrecy when the error exists,
it addresses the amount of leaked information only when the eavesdropper does not know the information of the noise.
That is, they evaluate the mutual information between M and Y_E^n.
However, our analysis evaluates the leaked information when the eavesdropper knows the information about the noise.
That is, we address the mutual information between M and the pair (Y_E^n,Z^n).









§ ASYMPTOTIC SETTING WITH SECRECY
S5
When Alice and Bob can communicate via public channel,
the verification of correctness can be done by a universal2 hash function <cit.><cit.>.
When we employ a modified Toeplitz matrix as a universal2 hash function
and m_2 bits are exchanged for the verification,
it has only calculation complexity O(m_2 log m_2).
Due to this step, 
we can guarantee the correctness with probability 1-2^-m_2, which is called the significance level<cit.>.
Hence, in this case, we consider the case when only the secrecy is imposed and the robustness is not imposed.

That is, we impose the following condition.

    lim_n →∞max_K P_e[Φ_n, K,0,0]
    =lim_n →∞max_K,H P_e[Φ_n, K,H,0]=0.
    H3-18K

However, even when the verification of correctness is passed,
there is a possibility that Eve can make an active attack to satisfy 

    P_e[Φ_n, K,H,α^n]=0.
    H3-30

Hence, as the secrecy, we impose the following condition.

    max_K,Hmax_α^n 
    I(M;Y_E^n)[Φ_n,K,H,α^n]=047-2 .

Here, both maximums are taken with respect to
(K_E,H_E) ∈_q^m_6× m_3×_q^m_6× m_5 with (<ref>) and (<ref>).
We notice that the situation of the correctness (<ref>)
is different from the situation of the secrecy (<ref>).
Indeed, it is possible to restrict the range of α^n
by imposing the condition (<ref>).
However, since it is not so easy to handle the condition (<ref>),
the maximum for α^n
is addressed without the restriction (<ref>).
That is, the correctness (<ref>) addresses only the case with passive attack,
but the secrecy (<ref>) addresses the cases with active attack.


This setting appears when we consider quantum key distribution, as explained in Section <ref>.
Then, we have the following theorem to analyze this problem.

T3B

There exists a sequence of non-local codes Φ_n 
of block-length l_n on finite field _q

whose message set is _q^k_n such that conditions (<ref>) and (<ref>) and

    lim_n →∞k_n/l_n = m_0-m_247-1

holds.


From the definition, we see that
P_e[Φ_n, K,0,0]=P_e[Φ_n, K,H,0].
Also, note that P_e[Φ_n, K,0,α^n] does not depend on K_E.
Further, the rate m_0-m_2 is asymptotically optimal, 
i.e., there is no non-local code surpassing the rate m_0-m_2,
which follows from the converse part of the conventional wire-tap channel <cit.>. 


To show the above theorem, as a special case of Theorem <ref> with m_1=0, 
we prepare the following corollary.

T2E

There exists a sequence of non-local codes Φ_n 
of block-length l_n on finite field _q

whose message set is _q^k_n such that

    lim_n →∞k_n/l_n = m_0-m_2
       
    max_K
    I(M;Y_E^n)[Φ_n,K,0,0]=0,
       lim_n →∞max_K 
    P_e[Φ_n, K,0,0]=0,

where the maximum is taken with respect to
(K_B,K_E) ∈_q^m_4× m_3×_q^m_6× m_3 under the conditions (<ref>) and (<ref>).


Combining Corollary <ref> and Theorem <ref>,
we obtain Theorem <ref>.


Here, we compare existing results with Corollary <ref>.
As a similar result to Corollary <ref>, the following proposition is known.
Since Corollary <ref> does not require the assumptions m_3=m_4=m_0 and K_B=I,
Corollary <ref> is slightly advantageous.
Hence, Theorem <ref> is a stronger statement than the following existing statement.

T2D
We assume that m_3=m_4=m_0 and K_B=I.
There exists a sequence of non-local codes Φ_n 
of block-length n on finite field _q

whose message set is _q^k_n such that

    lim_n →∞k_n/n = m_0-m_2
       lim_n →∞max_K
    I(M;Y_E^n)[Φ_n,K,0,0]=0,
       lim_n →∞ 
    P_e[Φ_n, K,0,0]=0,

where the maximum is taken with respect to
K_E ∈_q^m_6× m_3 with condition (<ref>).








§ APPLICATION TO NETWORK QUANTUM KEY DISTRIBUTION
S6

In this section, to realize long-distance communication with quantum key distribution,
using the result in Sections <ref> and <ref>,
we consider a network of quantum key distribution.
Although the existing studies <cit.> discussed a similar case over routing networks,
they did not discuss the relation with network code including active attacks.

Assume  that the authorized sender, Alice, is connected to the authorized receiver, Bob,
via the network given by the graph (V, E) with |E|=k.
A linear operation is fixed in each node so that 
we have the relation Y_B=K_B X with Alice's input X and Bob's output Y_B.
Then, if secure information transmission is available on each edge,
secure communication from Alice to Bob can be realized.
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.
In the following, 
we discuss how we can make secure message transmission from Alice to Bob
by using these k pairs of secure keys with public channels.
This kind of secure communication is called network quantum key distribution.

First, we consider the case when all nodes are authenticated.
In this case, Alice can securely send her message X to Bob in the following way.



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 in each edge is realized.
Hence, due to the above relation Y_B=K_B X, 
secure communication from Alice to Bob can be realized.

However, it is very difficult to guarantee security when a part of the nodes are occupied by Eve.
Such a model is often called a node adversary model  
while the model introduced in Section <ref> is called an edge adversary model.
The main problem with network quantum key distribution is the realization of secure communication from Alice to Bob 
under a node 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 <cit.>.
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 with each other, Eve's attack is an active attack.
That is, analysis for active attack is essential.
Therefore, we can apply Theorem <ref> 
to the security analysis of 
the direct transmission of the 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
because the asymptotically negligible keys are needed for 
authentication for the public channel.
In this case, to generate secure keys with length O(n), 
we can employ Theorem <ref>,
where the asymptotically negligible keys are used for an error verification test.





For example, we consider the network given in Fig. <ref>, which has nodes
v(1), …, v(8) as intermediates nodes.
Fig. <ref> expresses the information flow on each edge in this network.
This network connects Alice and Bob with rank 4.
The ranks of K_E and H_B of typical cases
are summarized in Table <ref>.
Also, Section II-D of <cit.> discusses the same network. 





When the number of nodes occupied by Eve is limited to 1,
the ranks of K_E and H_B are upper bounded by 2.
In the latter case, Theorem <ref> guarantees that
Alice can securely transmit a random number with rank 2 per single use of the network.
In the former case, since 4-2-2=0, Theorem <ref> cannot guarantee that Alice  securely transmits her message to Bob.

As another example, we consider the circle type network given in Fig. <ref>, in which, 
the nodes connect the next nodes and the nodes after the next.
Assume that we have pairs of secret keys in the circle type network of Fig. <ref>.
We suppose that v(1) intends to communicate with v(8) securely.
They make the network as
v(1) → v(12)→ v(10)→ v(8),
v(1) → v(11)→ v(9)→ v(8),
v(1) → v(3)→ v(5)→ v(7)→ v(8),
v(1) → v(2)→ v(4)→ v(6)→ v(8), which connects v(1) and v(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 <ref> guarantees that
Alice in v(1) can securely transmit a random number with rank 3 per single use of the network.
In the former case, 
Theorem <ref> guarantees that Alice in v(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 <ref> guarantees that
Alice in v(1) can securely transmit a random number with rank 2 per single use of the network.
In the former case, 
Theorem <ref> cannot guarantee that Alice in v(1) securely transmits her message to Bob.
This method can be generalized to the case when Alice and Bob are v(i) and v(j)
with |i-j|≥ 2 (  12).


Indeed, this idea can be generalized to this circle type 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 {v(i)}_i=1^k,
and the set of edges is given as {(v(i), v(j)) }_|i-j| ≤ l (  k).
Now, we set Alice and Bob as v(i) and v(j) with |i-j|≥ l (  k).
Then, they can make 2l paths connecting v(i) and v(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 <ref>.



§ APPLICATION TO MULTIPLE MULTICAST NETWORK
 S10
Before considering the multiple multicast network,
we consider the multicast case, in which a single user broadcasts his/her message to several receivers.
This setting can be applied to the multiple multicast network that can be realized by a combination of point-to-point quantum key distribution.
Remember the encoding and the decoding depend only on 
the integers m_0,m_1,m_2,m_3,m_4 in Theorem <ref>.
Assume that we have b receivers (receiver1, …, receiver b).
The integers m_2 and m_3 do not depend on receiver i.
Since m_0, m_1 and m_4 depend on receiver i,
they are written as m_0(i), m_1(i) and m_4(i).
Since each receiver can add an extra dimension,
we can consider that 
the dimension of observed information by each receiver is m̃_4:=max_i m_4(i).
Then, we choose 
m̃_0:= min_i m_0(i)
and m̃_1:= max_i m_1(i).
We apply Theorem <ref> to the case with m_0= m̃_0,
m_1= m̃_1, m_2, m_3, and m_4= m̃_4.
When the encoder of the obtained non-local code is used in the sender
and the decoder of the obtained non-local code is used in all the receivers,
the rate m̃_0-m̃_1-m_2.
 
Now, we proceed to the multiple multicast case, which contains multiple unicast case.
We consider how to apply our result to
a multiple multicast network with a senders and ∑_i=1^a b_i receivers, in which,
the senders and the receivers are labeled as i and (i,j) with 1≤ i≤ a and 1≤ j ≤ b_i, respectively.
Sender i intends to securely send the message to Receiver (i,j).
That is, Sender i wants to keep secrecy for Receiver (i',j) with i'≠ i.
In the one-time use of the network, 
Sender i sends m_3,i symbols X⃗_i of _q via m_3,i channels
and
Receiver (i,j) receives m_4,i,j symbols Y⃗_i,jof _q via m_4,i,j channels.
Without loss of generality, 
adding extra dimensions,
we can assume that 
m_4,i,j does not depend on j and is simplified to m_4,i due to the following reason.
That is, when m_4,i,j < max_j' m_4,i,j',
we can consider that Receiver (i,j) receives symbol 0 via max_j' m_4,i,j'- m_4,i,j channels.
If the codes in the network are designed perfectly, we have no cross-line nor no information leakage to unintended receivers.
In this section, we consider the case with a small amount of cross line and information leakage to unintended receivers due to errors on the design of the network.

We assume that these senders and receivers are connected via network composed of linear operations.
Then, using matrices K_i,j;i', we can describe their relations as

    Y⃗_i,j= ∑_i'=1^a K_i,j;i'X⃗_i'.

While the senders transmit their information repeatedly, 
we assume that the coefficient matrices K_i,j;i' do not change.
We assume that receivers do not  collude to recover the message from senders.
Now, we apply the model (<ref>) and (<ref>) to
 the secure communication transmission from Sender i to Receiver (i,j).
When we consider information leakage to Receiver (i”,j”) with i”≠ i,
we substitute X⃗_i, (X⃗_i')_i'≠ i, Y⃗_i,j and Y⃗_i”,j”
into X, Z, Y_B, and Y_E, respectively. 
We assume that the rank of information crossed from other senders is m_1,i,j
and the rank of leaked information to Receiver (i”,j”) is m_2,i;i”,j”.
We introduce the maximum ranks 
m_0,i:= max_j K_i,j;i, 
m_1,i:= max_jm_1,i,j, and  m_2,i := max_i”,j” m_2,i;i”,j”.
Sender i and Receiver (i,j) are assumed to know only the integers
m_0,i, m_1,i, m_2,i, m_3,i, m_4,i and have no other knowledge for the network structure.
We choose our non-local code by applying Theorem <ref> to
the case with 
m_0=m_0,i,
m_1=m_1,i,
m_2=m_2,i,
m_3=m_3,i, and 
m_4=m_4,i.
Since the non-local code does not depend on the choice of j and i”,j”, this non-local code works well in this situation.




§ CONCLUSION
SCon
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, as Theorem <ref>,
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, 
as Theorem <ref>,
we have discussed the secrecy and the asymptotic transmission rate 
when Eve has a possibility to inject noise into the network.


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. <ref>,
we can employ a classical (non-quantum) secret sharing protocol <cit.> instead of network coding 
because all of the communications of this case are routing.
In particular, cheater-identifiable secret sharing against rushing cheaters <cit.>
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 <cit.>
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 Prof. Masaki Owari, Dr. Go Kato, Dr. Wangmei Guo,
and Mr. Seunghoan Song

for helpful discussions and comments.





§ PROOF OF THEOREM <REF>
ApB
We define two random variables Y_E,p^n:=K_E X^n and 
Y_E,a^n:=K_E X^n+ H_E Z^n.
Eve can simulate her outcome Y_E,a^n under the strategy α
from Y_E,p^n, H_E, and Z^n.
So, we have 
I(M;Y_E,p^n) ≥ I(M;Y_E,a^n,Z^n)=I(M;Y_E,a^n).
Conversely, since Y_E,p^n is given as a function of Y_E,a^n, Z^n, and H_E,
we have the opposite inequality.




§ PROOF OF PROPOSITION <REF>
Ap1

To show Proposition <ref>, 
we regard any element of the finite field _q as
an element of a t-dimensional algebraic extension _q' 
of the finite field _q, where q'=q^t.
The matrices K_B,H_B,K_E,H_E on _q can be regarded as matrices on _q'.
By choosing l_n:=t n, the matrices X^l_n, Y_B^l_n, Y_E^l_n, Z^l_n on _q 
are converted to matrices X'^n, Y_B'^n, Y_E'^n, Z'^n on _q',
which also satisfy (<ref>) and (<ref>) by regarding 
the same matrices K_B,H_B,K_E,H_E on _q as matrices on _q'.
Then, the following proposition is known.


T2B
We assume the following two conditions for m_2, m_1, m_0 and a sequence of prime power q_n'.
The inequality m_2+m_1< m_0 holds.
The size q_n' of the finite field increases such that 
q_n'/n^m_0+1→∞. 


Then, there exists a sequence of non-local codes Φ_n 
of block-length n on finite field _q_n'

whose message set is _q_n'^k_n' such that

    lim_n →∞k_n'/n = m_0-m_1eqH4-27C
       lim_n →∞max_K,Hmax_α^n 
    P_e[Φ_n, K,H,α^n]=0 eqH4-27,

where the maximum is taken in the same way as with Proposition <ref>.


The optimality of the rate m_0-m_1 was also shown 
under the condition (<ref>) in <cit.>. 
By choosing t_n=⌈ (m_0+1)log n/log q⌉
and l_n:= t_nn,
Proposition <ref> implies Proposition <ref>.
Hence, we need to explain how to show Proposition <ref>. 

Combining the results in <cit.>,
we can construct a sequence of non-local codes to satisfy (<ref>) and (<ref>).
More precisely, the papers <cit.><cit.>
constructed a sequence of non-local codes to satisfy (<ref>) and (<ref>)
under  the condition m_2+2 m_1< m_0.
This is because the condition m_2+2 m_1< m_0 is stronger than 
the condition m_2+m_1< m_0, which is the assumption of Proposition <ref>.
To show (<ref>) under the weaker condition m_2+m_1< m_0, 
the papers 
by Jaggi, Langberg, Katti, Ho, Katabi, Médard, and Effros
<cit.><cit.><cit.>
constructed a sequence of non-local codes to satisfy (<ref>) and (<ref>),
when Alice can send Bob secret information whose size is asymptotically negligible 
in comparison with n, in the following way.


T2C
We assume the following three conditions.
The inequality m_0>m_1 holds.
Alice can send Bob secret information whose size is asymptotically negligible 
in comparison with n.
The size q_n' of the finite field increases such that 
q_n'/n^m_0+1→∞.



Then, there exists a sequence of non-local codes Φ_n 
of block-length n on finite field _q_n'

whose message set is _q_n'^k_n' 
such that the relations (<ref>) and (<ref>) hold. 


Then, under the weaker condition m_2+ m_1< m_0,
as the following proposition, the papers <cit.><cit.> provide a protocol for secure transmission of random variables with an asymptotically negligible length k_n in comparison with n, which is the requirement in Proposition <ref>.


T2BL
We assume the inequality m_2+m_1< m_0.
Then, there exists a sequence of non-local codes Φ_n of block-length n 

whose message set is _q^k_n such that

    lim_n →∞ k_n= ∞eqH4-27CY
       lim_n →∞max_K,Hmax_α^n 
    P_e[Φ_n, K,H,α^n]=0 eqH4-27Y,
       lim_n →∞max_K,H
    I(M;Y_E^n)[Φ_n,K,H,0]=0, H3-182Y

where the maximum is taken in the same way as Proposition <ref>.


Therefore, attaching the protocol of Proposition <ref> to the non-local codes given in 
Proposition <ref>,
we obtain (<ref>) under the weaker condition m_2+m_1< m_0.
However, their proof of Proposition <ref>
is very hard to read because it omits the detail derivation. 
In the following, we give an alternative proof of Proposition <ref>.

Before our proof of Proposition <ref>,
we prepare two lemmas.
The first lemma can be easily shown by the discussion of linear algebra.
In the following discussion, we simplify q_n' to q'.

L4-27
For integers a_0 ≤ a_1+a_2,a_1',a_2', 
we fix an a_1-dimensional subspace W_1 ⊂_q'^a_1' and 
an a_2-dimensional subspace W_2 ⊂_q'^a_2'.
We assume the following two conditions.


  (E1)
An a_0 × a_1' matrix A_1
and an a_0 × a_2' matrix A_2
satisfy 

    A_1|_W_1   ={0}, 
    
     A_1 ∩ A_2    = { 0 },

where (f) denotes the image of the function f.

  (E2)
We consider a subspace W_3 ⊂ W_1 ⊕ W_2.
For vectors
x_1, …, x_b ∈ W_1
and
y_1, …, y_b ∈ W_2 with b ≥ a_1+a_2,
(x_1,y_1), …, (x_b ,y_b) span W_3.

Then, we have the following statements.


  (E3)
There exists an a_1' × a_0 matrix A_3 such that
A_3 (A_1 x_i+ A_2 y_i)=x_i for i=1, …, b, i.e., 

    A_3 
    [A_1  A_2 ]
    [
    [ x_1 x_2   ⋯ x_b; y_1 y_2   ⋯ y_b ]]
    
    
    =   [
    [ x_1 x_2   ⋯ x_b ]].


  (E4)
The above matrix A_3 satisfies the relation

    A_3 (A_1 x+ A_2 y)=x 4-27F

for any (x,y) ∈ W_3.




Due to condition (E1), 
we choose a map A_4 from A_1 to W_1
such that A_4 A_1 is the identify on W_1.
Since W_1 is included in _q'^a_1',
A_4 can be regarded as a map from A_1 to _q'^a_1'.
Then, we choose a projection A_5 from _q'^a_0
to A_1 such that A_5 x=0 for x ∈ A_2.
Therefore, A_3:= A_5 A_4 satisfies the condition of (E3).
Further, (E2) guarantees (E4).




LJa
We independently choose m random variables 
V_1, …, V_m 
subject to the uniform distribution on _q'.
We define the n × m matrix U_1
as U_1;i,j:= (V_j)^i with i=1, …, n and j= 1,…, m.
Then,  

    { x U_1=x' U_1
    }≤(n/q')^m

for any x≠ x'∈_q'^n.


Proposition <ref>Step (1): Non-local code constructionFirst, we provide our non-local code when we use the channel n times based on the finite field _q'.
Our message is given as an (m_0-m_1) × n matrix M, which satisfies condition
(<ref>) asymptotically. 
Since the rank of H_B is m_1,
there exist an 
m_4× m_1 matrix Ĥ_B and 
an m_1× n matrix Ẑ^n such that

    Y_B^n
    =K_B U_0  X^n+H_B Z^n
    =K_B U_0  X^n+Ĥ_B Ẑ^n.TT

Then, we address Ĥ_B and Ẑ^n
instead of H_B and Z^n.

We fix an integer m:=m_0+1.
We independently choose m random variables 
V_1, …, V_m subject to the uniform distribution on _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 define the (m_0-m_1)× m matrix U_2:= M U_1.

Moreover, we define the m_3 × n matrix X^n:=
[
[ M; 0 ]], where 0 is the 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 inputs the m_3 × n matrix U_0 X^n 
as the input of n times use of the channel.

Then, Bob receives the m_4 × n matrix Y_B^n given in (<ref>)
as well as the secret information V_1, …, V_m,U_2.
Since the ranks of K_B U_0 X^n and Ĥ_B are m_0-m_1 and m_1 at most, respectively,
the rank of the matrix Y_B^n is m_0 at most. 
We denote the rank by m̅_0.
We choose m̅_0 linearly independent row vectors from the row vectors of Y_B^n.
We denote the m̅_0 × n matrix composed of the m̅_0 
independent row vectors by Y̅_B^n.
Similarly, we denote the matrices composed of these m̅_0 row vectors of 
the matrices K_B and Ĥ_B by
K̅_B and H̅_B, respectively.
Then, using the standard Gaussian elimination,
Bob finds a matrix U_3 to satisfy the equation

    U_3 Y̅_B^n U_1= U_2,
    4-27Y

which is equivalent to

    U_3 
     [
    K̅_BU_0 P_m_0-m_1 H̅_B 
    ]
     [
    [   M; Ẑ^n ]] U_1=M U_1,EEQ1

where 
P_m_0-m_1 is the imbedding
[
[ I; 0 ]]
from _q'^m_0-m_1 to 
_q'^m_3.
Notice that Bob can calculate 
U_1 from the secret information V_1, …, V_m.
Finally, Bob recovers the information M̂:=U_3 Y̅_B^n.
To check the condition (<ref>), Bob needs only 
Y̅_B^n,
U_2, and U_1, which can be computed from 
V_1, …, V_m.
 


Step (2): Analysis of performanceThere are two conditions if the above protocol is to work well.


  (F1)
The relations 
(K̅_B U_0 P_m_0-m_1)∩H̅_B= {0}
and K̅_B U_0 P_m_0-m_1|_ M ={0} hold.

  (F2)
The relation 
[
[   M; Ẑ^n ]]
 U_1
=[
[   M; Ẑ^n ]] holds,
where  denotes the rank of the matrix.






Assume that conditions (F1) and (F2) hold.
We apply Lemma <ref> to the case when
a_0= m̅_0,
a_1= M,
a_2= Ẑ^n,
W_1= M,
W_2= Ẑ^n,
A_1=K̅_B U_0 P_m_0-m_1,
A_2=H̅_B,
A_3= U_3.


Then, conditions (F1) and (F2) guarantee
conditions (E1) and (E2), respectively.
Then, due to condition (E3),
there exists a matrix U_3 that satisfies equation (<ref>), i.e., (<ref>).
Condition (E4) guarantees that
U_3 Y̅_B^n= M, i.e., 

Bob can decode the message M.

Now, we evaluate the probability that condition (F2) holds.
Condition (F2) holds if and only if 
z^T  [
[   M; Ẑ^n ]]
 U_1 ≠ 0 for any z ∈_q'^m_0
 satisfying the condition z^T  [
[   M; Ẑ^n ]]
≠ 0.
Applying Lemma <ref> to all of z (≠ 0)∈_q'^m_0,
we find that condition (F2) holds at least with probability 
1- q'^m_0 (n/q')^m
=1- n^m/q'^m-m_0=1- n^m_0+1/q'→ 1.

Finally, we evaluate the probability that condition (F1) holds.
As shown later, the following conditions (F1') and (F1”) imply condition (F1).


  (F1')
The relation (K_B U_0 P_m_0-m_1)∩Ĥ_B= {0} holds.

  (F1”)
The relation K_B U_0 P_m_0-m_1|_ M ={0} holds.

Hence, we show that conditions (F1') and (F1”) hold with a probability close to 1.
Condition (K_B U_0 P_m_0-m_1)∩Ĥ_B= {0} holds if and only if
U_0 P_m_0-m_1∩ K_B^-1 (Ĥ_B)= {0}.
For a fixed K_B,Ĥ_B, 
since K_B^-1 (Ĥ_B) ≤ m_3-m_0+m_1,
the probability of 
condition (K_B U_0 P_m_0-m_1)∩Ĥ_B= {0} is at least

    (1-q'^m_3-m_0+m_1-m_3)
    (1-q'^m_3-m_0+m_1-m_3+1)⋯
       · (1-q'^m_3-m_0+m_1-m_3+ m_0-m_1-1) 
    
    =   (1-q'^m_1-m_0)
    (1-q'^m_1-m_0+1)⋯
    (1-q'^-1)
    
    
    =    1-O(1/q').


The relation K_B U_0 P_m_0-m_1|_ M ={0} holds if and only if
no basis of U_0 P_m_0-m_1 M belongs to the space K_B.
Since K_B is an m_3-m_0-dimensional subspace of an m_3-dimensional space,
the probability of condition 
K_B U_0 P_m_0-m_1|_ M ={0} is

    (1-q'^-m_0)
    (1-q'^-m_0+1)⋯
    (1-q'^-m_0+m_7-1)
    
    =   1-O(q'^-m_0+m_7-1),

where m_7:=  P_m_0-m_1 M(=  U_0  P_m_0-m_1 M) 
= M=  M ≤ m_0-m_1.
Therefore, since q' is sufficiently large,
we obtain the desired statement.

Finally, we show that condition (F1') implies condition (F1).
Since the relation
(K̅_B U_0 P_m_0-m_1)∩H̅_B= {0}
can be shown easily from (F1'), we show only the relation
K̅_B U_0 P_m_0-m_1|_ M ={0} from (F1') and (F1”).
The choice of m̅_0 guarantees that 
there exists an invertible map U_4 from [K_B U Ĥ_B] to _q'^m̅_0 such that
U_4 [K_B U Ĥ_B]=[K̅_B U H̅_B]. 
Thus, 

    K̅_B U_0 P_m_0-m_1|_ M =
     U_4^-1K̅_B U_0 P_m_0-m_1|_ M
    
    =   K_B U_0 P_m_0-m_1|_ M ={0}.




Our proof is different from the proof presented in <cit.><cit.><cit.>.





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.




Proposition <ref> requires a finite field _q' with an infinitely large q'.
The paper <cit.> discussed the construction of _2^t whose
multiplication and inverse multiplication have calculation complexity O(t log t)[The multiplication of elements v and z of _2^t is essentially given in (124) of <cit.>
by using Fourier transform via a calculation on circulant matrices.
For the inverse multiplication of an element v of _2^t, 
we calculate F^-1[-Fv. *Fz] instead of 
F^-1[Fv. *Fz] in (124), where F is discrete Fourier transform.].



10
Cai2002
N. Cai and R. Yeung, “Secure network coding,” 
Proc. 2002 IEEE Int. Symp. Information Theory (ISIT 2002), Lausanne, Switzerland, July 2002, p. 323.
BB84
C. H. Bennett, G. Brassard,
“Quantum cryptography: public key distribution and coin tossing,”
Proc. IEEE International Conference on Computers, Systems and Signal Processing,
(Bangalore, India), pp. 175–179 (1984).

IDQ
http://www.idquantique.com/quantum-safe-crypto/qkd-overview/

BDCZ
H.-J. Briegel, W. D'́ur, J. I. Cirac, and P. Zoller,  
“Quantum repeaters: the role of imperfect local operations in quantum communication,” 
Phys. Rev. Lett. 81, 5932–5935 (1998).

DLCZ
L.-M. Duan, M. Lukin, J. I. Cirac, and P. Zoller, 
“Long-distance quantum communication with atomic ensembles and linear optics,”
Nature 414, 413–418 (2001).

SSRG
N. Sangouard, C. Simon,  H. de Riedmatten, and N. Gisin, 
“Quantum repeaters based on atomic ensembles and linear optics,” 
Rev. Mod. Phys. 83, 33 – 80 (2011).





 
 LWLZ
X. Liu, J. Wang, R. Li, and C. Zhang,
“Security Analysis of Stochastic Routing Scheme in Grid-Shaped Partially-Trusted Relay Quantum Key Distribution Network,”
Chinese Journal of Electronics, vol. 27, no. 2,  234 – 240, 2018.
  

WHZ
H. Wen, Z. Han, Y. Zhao, et al. 
“Multiple stochastic paths scheme on partially-trusted relay quantum key distribution network,”
Sci. China Ser. F-Inf. Sci. 52, 18 – 22 (2009).


bennett95privacy
C. H. Bennett, G. Brassard, C. Crépeau, and U. M. Maurer, 
“Generalized privacy amplification,” 
IEEE Trans. Inform. Theory, vol. 41, no. 6, pp. 1915–1923, (1995).

HILL
J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby,
“A Pseudorandom Generator from any One-way Function,”
SIAM J. Comput. 28, 1364 (1999). 

hayashi11
M. Hayashi, “Exponential decreasing rate of leaked information in universal
  random privacy amplification,” 
IEEE Trans. Inform. Theory, vol. 57, no. 6, pp. 3989–4001, (2011).

Matsumoto2011
R. Matsumoto and M. Hayashi, “Secure Multiplex Network Coding,” 
2011 International Symposium on Networking Coding (2011):
DOI: 10.1109/ISNETCOD.2011.5979076.

Matsumoto2011a
R. Matsumoto and M. Hayashi, 
“Universal Secure Multiplex Network Coding with Dependent and Non-Uniform Messages,” 
IEEE Trans. Inform. Theory, vol. 63, no. 6, pp. 3773 – 3782, (2017).

KMU1
J. Kurihara, T. Uyematsu, and R. Matsumoto, “Explicit construction
of universal strongly secure network coding via MRD codes,” 
in Proc. IEEE Int. Symp. Inf. Theory, 
Cambridge, MA, USA, Jul. 2012,
pp. 1483–1487.

KMU2
J. Kurihara, T. Uyematsu, and R. Matsumoto, 
“New parameters of
linear codes expressing security performance of universal secure network coding,” 
in Proc. 50th Annu. Allerton Conf. Commun., 
Control, Comput.,
Monticello, IL, USA, Oct. 2012, pp. 533-540. 

KMU
J. Kurihara, R. Matsumoto, and T. Uyematsu,
“Relative generalized rank weight of linear codes and its applications to network coding,”
IEEE Trans. Inform. Theory, vol. 61, no. 7, pp. 3912–3936 (2013).

Cai06a
R. W. Yeung and N. Cai,
“Network error correction, part 1: Basic concepts and upper bounds,”
Submitted to Communications in Information and Systems (2006).

Cai06
N. Cai and R. W. Yeung, 
“Network error correction, Part 2: Lower bounds,” 
Commun. Inf. and Syst., vol. 6, no. 1, 37-54, (2006).

HLKMEK T. Ho, B. Leong, R. Koetter, M. Médard, M. Effros, and D. R. Karger, 
“Byzantine modification detection for multicast networks using randomized network
coding,” 
Proc. 2004 IEEE Int. Symp. Information Theory (ISIT 2004), Chicago, IL, June/July 2004, p. 144.

JLHE
S. Jaggi, M. Langberg, T. Ho, and M. Effros, 
“Correction of adversarial errors in networks,” 
Proc. 2005 IEEE Int. Symp. Information Theory (ISIT 2005),
Adelaide, Australia, Sept. 2005, pp. 1455 – 1459.

JLKHKM
S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, and M. Médard, 
“Resilient network coding in the presence of byzantine adversaries,” 
in Proc. IEEE INFOCOM 2007, Anchorage, AK, May 2007, pp. 616 – 624.

Jaggi2008
S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, M. Medard, and M. Effros,
  “Resilient Network Coding in the Presence of Byzantine Adversaries,” 
IEEE Trans. Inform. Theory, vol. 54, no. 6, 2596–2603 (2008).

JL
S. Jaggi and M. Langberg, 
“Resilient network coding in the presence of eavesdropping byzantine adversaries,” 
Proc. 2007 IEEE Int. Symp. Information Theory (ISIT 2007), 
Nice, France, June 2007, pp. 541 – 545.

KSZBJ
S. Kadhe, A. Sprintson, Q. E. Zhang, M. Bakshi, and S. Jaggi,
“Reliable and secure communication over adversarial multipath networks: A survey,”
10th International Conference on Information, Communications and Signal Processing (ICICS), 2015. 

ZKBJS1
Q. Zhang, S. Kadhe, M. Bakshi, S. Jaggi, and A. Sprintson,
“Talking reliably, secretly, and efficiently: A “complete” characterization,”
2015 IEEE Information Theory Workshop (ITW), Jerusalem, Israel, April/May 2015.


ZKBJS2
Q. Zhang, S. Kadhe, M. Bakshi, S. Jaggi, and A. Sprintson,
“Coding against a limited-view adversary: The effect of causality and feedback,”
Proc. 2015 IEEE Int. Symp. Information Theory (ISIT 2015), Hong Kong, June 2015, pp. 2530 – 2534.

BBT 
D. Blackwell, L. Breiman, and A. J. Thomasian, 
“The capacities of certain channel classes under random coding,” 
Ann. Math. Statist., vol. 31, no. 3, pp. 558 – 567, 1960. 

Ahlswede
R. Ahlswede, 
“Elimination of correlation in random codes for arbitrarily varying channels,” 
Z. Wahrsch. Verw. Geb., vol. 44, no. 2, pp. 159 – 175, 1978. 


CN88
I. Csiszár and P. Narayan. 
“The capacity of the arbitrarily varying channel revisited: Positivity, constraints,”
IEEE Trans. Inform. Theory, vol. 34, no. 2, 181 – 193 (1988).

KJL
B. K. Dey, S. Jaggi, and M. Langberg
“Sufficiently Myopic Adversaries are Blind,”
https://arxiv.org/abs/1610.01287

TJBK
P. Tian, S. Jaggi, M. Bakshi, and O. Kosut,
“Arbitrarily Varying Networks: Capacity-achieving Computationally Efficient Codes,”
https://arxiv.org/abs/1605.01834.

Yao2014
H. Yao, D. Silva, S. Jaggi, and M. Langberg,
“Network Codes Resilient to Jamming and Eavesdropping,”
IEEE/ACM Transactions on Networking, vol. 22, no. 6, 1978 - 1987 (2014).

HOKC1
M. Hayashi, M. Owari, G. Kato, and N. Cai, 
“Reduction Theorem for Secrecy 
over Linear Network Code for Active Attacks”
arXiv:2003.11722 (2019).

Zhang
Q. Zhang, S. Kadhe, M. Bakshi, S. Jaggi and A. Sprintson,
“Coding against a Limited-view Adversary: The Effect of Causality and Feedback,”
Proc. 2015 IEEE International Symposium on Information Theory (ISIT)
14-19 June 2015.

Fung
C.-H. F. Fung, X. Ma, and H. F. Chau,
“Practical issues in quantum-key-distribution postprocessing,”
Phys. Rev. A 81, 012318 (2010).

TBH
M. Tomamichel, M. Berta, and M. Hayashi, 
“Relating different quantum generalizations of the conditional Renyi entropy,” 
J. Math. Phys., vol. 55, no. 8, 082206 (2014).

HW
M. Hayashi and S. Watanabe,
“Non-asymptotic and asymptotic analyses of information processing on Markov chains,”
Arxiv preprint, arXiv:1309.7528 (2013).

Hayashi-Tsurumaru
M. Hayashi and T. Tsurumaru, 
“More Efficient Privacy Amplification with Less Random Seeds via Dual Universal Hash Function,” 
IEEE Trans. Inform. Theory, vol. 62, no. 4, 2213 – 2232 (2016).

SK
D. Silva and F. R. Kschischang, 
“Universal Secure Network Coding via Rank-Metric Codes,”
IEEE Trans. Inform. Theory, Volume: 57, Issue:2, 1124 - 1135 (2011).

Rashmi
K. V. Rashmi, N. B. Shah, K. Ramchandran, and P. Vijay Kumar, 
“Information-Theoretically Secure Erasure Codes for Distributed Storage,”
IEEE Trans. Inform. Theory, vol. 64, no. 3, 1621 – 1646 (2018).

H17
M. Hayashi,
“Secure wireless communication under spatial and local Gaussian noise assumptions,”
Proc. 2017 IEEE Int. Symp. Information Theory (ISIT 2017), 
Aachen, Germany, June 2017, pp. 1698 – 1702; arXiv:1604.00635.

wyner75
A. D. Wyner, “The wire-tap channel,” 
Bell System Tech. J., 
vol. 54, no. 8, 1355–1387 (1975).

csiszar78
I. Csiszár and J. Körner, 
“Broadcast channels with confidential messages,” 
IEEE Trans. Inform. Theory, vol. 24, no. 3, 339–348 (1978).

Shamir
A. Shamir,
“How to share a secret,”
Communications of the ACM vol. 22, no. 11, 612–613 (1979).

PW91 
A. Adhikari, K. Morozov, S. Obana, P. S. Roy, K. Sakurai, and R. Xu,
“Efficient threshold secret sharing schemes secure against rushing cheaters,”
in Proc. the 9th International Conference on Information Theoretic Security (ICITS 2016), 
Lecture Notes in Computer Science 10015, pp.3–23, Springer (2016).

RAX
P. S. Roy, A. Adhikari, R. Xu, K. Morozov, and K. Sakurai,
“An efficient t-cheater identifiable secret sharing scheme with optimal cheater resiliency,”
eprint.iacr.org/2014/628.pdf

XMT1
R. Xu, K. Morozov, and T. Takagi, 
“On cheater identifiable secret sharing schemes secure against rushing adversary,” 
in Proc. the 8th International Workshop on Security (IWSEC 2013), Lecture Notes in Computer Science 8231, 
pp. 258–271, Springer (2013).

XMT2
R. Xu, K. Morozov, and T. Takagi,
“Cheater identifiable secret sharing schemes via multi-receiver authentication,” 
in Proc. the 9th International Workshop on Security (IWSEC 2014), Lecture Notes in Computer Science 8639,
72–87, Springer (2014). 

HK
M. Hayashi and T. Koshiba,
“Universal Construction of Cheater-Identifiable
Secret Sharing Against Rushing Cheaters without
Honest Majority,”
arXiv:1701.04470 (2017).

LPS
Y. Liang, H.V. Poor, and S. Shamai,
“Secure communication over fading channels,”
IEEE Trans. Inform. Theory, vol. 54, no. 6, 2470 – 2492 (2008).

BC11
M. Bloch and J. Barros
Physical-Layer Security: From Information Theory to Security Engineering,
Cambridge Univ Pr (2011).

SC
Y.-S. Shiu, S. Y. Chang, H.-C. Wu, S. C.-H. Huang, and H.-H. Chen, 
“Physical layer security in wireless networks: a tutorial,” 
IEEE Wireless Communications, vol. 18, no. 2, 66–74 (2011).

Trappe
W. Trappe, 
“The Challenges Facing Physical Layer Security,” 
IEEE Communications Magazine, vol. 53, no. 6, 16–20 (2015).

Zeng
K. Zeng, 
“Physical Layer Key Generation in Wireless Networks: Challenges and Opportunities,” 
IEEE Communications Magazine, vol. 53, no. 6, 33–39 (2015).

WX
H.-M. Wang and X.-G. Xia, 
“Enhancing Wireless Secrecy via Cooperation: Signal Design and Optimization,”
IEEE Communications Magazine, vol. 53, no. 12, 47–53 (2015).


RealisticChannel
Á. Vázquez-Castro and M. Hayashi,
“One-way and Two-way Physical Layer Security Protocols for the Gaussian
Satellite Channel”
Proc. 2019 IEEE International Conference on Communications (ICC): SAC Satellite
and Space Communications Track - Satellite and Space Communications, Shanghai, China, 
20–24 May (2019).

IFS1
A. Vazquez-Castro and M. Hayashi,
“Physical Layer Security for RF Satellite Channels in the Finite-length Regime,”
IEEE Trans. Inf. Forensics and Security, 
vol. 14, no. 4,  981 – 993, 2018.

IFS2
M. Hayashi and A. Vazquez-Castro,
“Physical Layer Security Protocol for Poisson Channels for Passive Man-in-the-middle Attack,”
IEEE Trans. Inf. Forensics and Security
(In press).

HOKC
M. Hayashi, M. Owari, G. Kato, and N. Cai, 
“Secrecy and Robustness for Active Attack in Secure Network Coding,”
Proc. 2017 IEEE Int. Symp. Information Theory (ISIT 2017), 
Aachen, Germany, 25-30 June 2017. pp. 1172 – 1177.



