Secure Network Code for Adaptive and Active Attacks with No-Randomness in Intermediate Nodes
Ning Cai Masahito Hayashi
cs.IT math.IT






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

Secure Network Code for Adaptive and Active Attacks with No-Randomness in Intermediate Nodes

MH 
was supported in part by 
the JSPS (Japan Society for the Promotion of Science) Grant-in-Aid for Scientific Research 
(A) No.17H01280, (B) No. 16KT0017, (C) No. 16K00014, 
and Kayamori Foundation of Informational Science Advancement.
    
Ning Cai, Fellow, IEEE and
Masahito Hayashi, Fellow, IEEE

Ning Cai is with the School of Information Science and Technology, ShanghaiTech University
(e-mail: ningcai@shanghaitech.edu.cn).
Masahito Hayashi is with the Graduate School of Mathematics, Nagoya University, Furocho, Chikusa-ku, Nagoya, 464-8602, Japan. 
He is also with 
Shenzhen Institute for Quantum Science and Engineering, Southern University of Science and Technology,
No.1088 Xueyuan Avenue, Nanshan District, Shenzhen, 518055, China,
the Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, 117542, Singapore,
and
Center for Quantum Computing, Peng Cheng Laboratory, Shenzhen 518000, China
(e-mail:masahito@math.nagoya-u.ac.jp).

    December 30, 2023
================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




In secure network coding, there is a possibility that
the eavesdropper can improve her performance
when 
she changes (contaminates) the information on the attacked edges (active attack)
and chooses the attacked edges adaptively (adaptive attack).
We analyze the security for network code over such types of attacks.
We show that active and adaptive attacks cannot improve the performance of the eavesdropper when the code is linear.
Further, we give a non-linear example, in which 
an adaptive attack improves the performance of the eavesdropper.
We derive the capacity for the unicast case and the capacity region for the multicast case or the multiple multicast case in several examples of relay networks, beyond the minimum cut theorem, 
when no additional random number is allowed as scramble variables in the intermediate nodes.
No prior study compared 
the difference of the capacity and the capacity region 
between the existence and the non-existence of randomness in the intermediate nodes 
under these network models
even with non-adaptive and non-active attacks.



 
secrecy analysis,
secure network coding,
adaptive attack,
active attack






§ INTRODUCTION
S1
Secure network coding is a method securely transmitting
information from the authorized sender to the authorized receiver. 
Cai and Yeung <cit.> discussed the secrecy for the malicious
adversary, Eve, wiretapping a subset E_E of all channels in the network. 
The papers <cit.> developed several types of secure network coding.
In particular, the papers <cit.> considered security for multiple unicast sessions within the context of network coding.

Combining the codes in <cit.> and <cit.>,
the paper <cit.> proposed a linear code to protect transmission from attacks of eavesdrop and injection of error (contamination) simultaneously.
Like traditional error correcting code and error correction network code (i.e. against Byzantine attack) in <cit.>, 
the paper <cit.> considered 
the robustness in the worst case, or equivalently 
it evaluated the error probability when the adversary to inject error knows the message to be sent. 
However, it discussed the secrecy independently of the robustness, i.e.,
it considered the secrecy only when the information on the network is not changed.
Also, the papers <cit.> showed the existence of a secrecy code that
universally works for any types of eavesdroppers under the size
constraint of E_E. 
In particular, the papers <cit.> constructed it by using the universal hashing lemma <cit.>.
Further, the papers <cit.> evaluated errors 
only when the information on a part of network is changed,
but they evaluated the secrecy only when the information on the network is not changed
or Eve did not know the replaced information.


On the other hand, as another model, we assume that the goal of Eve to inject error is to help having more information about the message. 
In this case, she may inject error according to the knowledge which she obtained from her previous action but not the message. 
This improvement for her ability of eavesdropping is an essential difference between the two models.
The recent paper <cit.> discussed this model, i.e.,
evaluated the secrecy as well as the error 
when Eve contaminates the eavesdropped information and knows the replaced information. 
(For the detailed relation, see Remark <ref>.)


The effects of Eve's contamination depend on the type of the network code.
It is well-known that linear network code is optimal for single source network <cit.>. 
But in many cases, linear codes are not optimal, or in other words, non-linear code has better performance, for example, in coding for multiple source network and classical error correcting code (which can be considered as error correction network coding for a two-node network, 
“point-to-point network)”. 
In several known examples of multiple source network, 
non-linear code can do better than linear one 
<cit.>.
As matter of fact, linear code has many advantages, e.g., easy for handle, lower complexity of encoding and decoding etc. 
When the code is linear, as shown in <cit.>,
any contamination (any active attack) does not improve her performance.
However, when the code is not linear, there exists only one example where the 
contamination improves her performance <cit.>.

0
Linear codes can be considered as a special case of non-linear codes. 
Our results, (which is no difficult to extended to general network with more than one source nodes and destinations,) reveals a new advantage, to protest active attack. 
As we discuss the before, the transmission rate could be reduced, 
when we apply a linear code against active attack to multiple source network. 
This reduction can be regarded as a cost paid for security.


Despite these developments, there are still some problems in existing studies.
Although these existing studies achieved the optimal rate with secrecy condition,
their optimality relies on the minimum cut theorem.
That is, they assumed that the eavesdropper may choose any r-subset channels to access, and did not address another type of conditions for the eavesdropper.
For example, the studies <cit.> optimized only the codes in the source and terminal nodes
and did not optimize the coding operations on the intermediate nodes.

Also, in other existing studies, 
the intermediate nodes do not have as complicated codes as the source and terminal nodes.
In this paper, to achieve the optimal rate beyond the minimum cut theorem,
we address the optimization of the coding operations on the intermediate nodes as well as on the source and terminal nodes.

Further, we consider a new type of attacks, adaptive attacks.
Assume that distinct numbers are assigned to the edges, 
and the communication on edges are done in the decreasing order for 
the assigned numbers.
Usually, Eve cannot decide the edges to be attacked depending on the previous observation.
Now, we allow Eve to choose the edges to be attacked 
based on the previous observations. 
Indeed, the channel discrimination,
it is known that such an adaptive strategy does not improve the asymptotic performance <cit.>.
Then, we find two characteristics for adaptive attacks, which are similar to the case of active attacks.
First, we find a non-linear code where an adaptive attack significantly improves Eve's performance.
Using this characteristic, we find an example of a non-asymptotic network model, which has 
no secure code for adaptive attacks, but has 
secure code for conventional attacks.
Second, we show that any adaptive attack cannot improve Eve's performance when the code is linear.
Using this fact, we derive the asymptotic performance in several typical network models in the following way
when Eve is allowed to use adaptive and active attacks.


In this paper, we discuss the asymptotic securely transmittable rate over the above attacks
not only for a unicast network but also for
a multiple multicast network, in which,
multiple senders are intended to send their different messages to different multiple receivers.
Under these settings, we define 
the capacity and the capacity regions for given network models,
and calculate them in several examples.
For the definition, we define two types of capacity regions depending on 
the requirement on the code on the intermediate nodes.
Usually, a secure network code employs scramble random numbers, 
which need to be physical random numbers different from pseudo random numbers.
In the first capacity region, we allow each node to introduce new scramble random numbers unlimitedly.
Here, the scramble random numbers of each node are not shared with other nodes 
and should be independent of random variables in other players and other nodes
before starting the transmission.
In the second capacity region, only source nodes are allowed to employ scramble random numbers
due to the following reason.
To realize physical random numbers as scramble random numbers, we need a physical device.
If the physical random number has sufficient quality, the physical device is expensive and/or 
consumes a non-negligible space because
it often needs high level quantum information technologies with advanced security analysis <cit.>.
It is not so difficult to prepare such devices in the source side.
However, it increases the cost to prepare devices in the intermediate nodes
because networks with such devices require more complicated maintenance than a conventional network.
Therefore, from the economical reason, it is natural to impose this constraint to our network code.
Unfortunately, only a few papers <cit.> discussed such a restriction.
Hence, this paper addresses the difference between the capacities with and without such a restriction by introducing 
the no-randomness capacity and the full-randomness capacity.
Further, as an intermediate case, 
by introducing the limited-randomness capacity,
we can consider the case when the number of available scramble random numbers in each intermediate node
is limited to a certain amount.
Then, the relation between our capacities and the existing studies is summarized as Table <ref>.
In addition, for both types of capacities and capacity regions, 
we define the linear codes version, in which, our codes are limited to linear codes.
We also show that the linear version of capacities and capacity regions
are the same as the original capacities and capacity regions under the above examples
because the optimal rate and rate regions in the original setting can be attained by linear codes.



The remaining parts of this paper is organized as follows.
Section <ref> gives the formulation of our network model. 
Section <ref> gives an example of network model, in which, an adaptive attack efficiently improves Eve's performance.
To discuss the asymptotic setting,
Section <ref> defines the capacity region.
Section <ref> discusses the relay network model and derives its capacity.
Section <ref> discusses the homogenous multicast network model and derives its capacity.
Section <ref> discusses the homogenous multiple multicast network model and derives its capacity.
In Section <ref>, we give an important lemma, which is used in the converse part in the above models.







§ ADAPTIVE AND ACTIVE ATTACK FOR GENERAL NETWORK
S4


 §.§ Formulation and reduction to non-adaptive attack
S4-1
Now, we give the most general formulation of network coding and adaptive and active attacks.
We consider an acyclic general network with multiple multicast setting as follows.

The network has a source nodes, b terminal nodes,
several intermediate nodes, and ℓ edges,
where each edge is assigned to a distinct number  from [ℓ]:= {1, …, ℓ}.
Hence, [ℓ] can be regarded as the set of edges.
Each edge transmits a single letter on a finite set X.
Our task is the following.
The i-th source node securely sends the message M_i,j to the j-th terminal node, where the messages are subject to independent uniform distribution.
Here, the tuple of all messages are denoted by M.

Next, we assume that as scramble random numbers, 
each intermediate node can use additional uniform random numbers, which are independent of other random variables. They might be realized as physical random numbers.
The i-th source node converts the pair of the messages (M_i,1, …, M_i,b)
and the scramble random numbers to the tuple of the letters on the outgoing edges.
Each intermediate node converts the pair of the letters on the incoming edges and the scramble random numbers to the tuple of the letters on the outgoing edges.
The j-th terminal node converts the pair of the letters on the incoming edges to the tuple of
the recovered messages (M̂_1,j, …, M̂_a,j).
We denote a network code by Φ.
We denote the cardinality of the message M_i,j by |Φ|_i,j.
When a=1, we simply denote it by |Φ|_j.
In particular, when a=b=1, we simply denote it by |Φ|.
We denote the set of codes by ℭ^0.

Now, we consider two conditions for our network code Φ.


  (C1) [Linearity]

Any message, any scramble random number, and
information on any edge can be given as elements of vector spaces over the finite field _q.
All of the conversions in source, intermediate, and terminal nodes are linear over _q, i.e., they are written as matrices whose entries are elements of _q.
Then, the code is called linear with respect to _q[This type of linear code is often called vector linear <cit.> because 
these random variables are given as elements of vector spaces over the finite field _q.
Although the paper <cit.> assumes that
all the messages, the scramble random numbers, and the variables on the edges have the same dimension,
we do not assume this condition.].

Here, to apply the linearity condition, 

we choose a subset of X whose cardinality is a power of q.
Then, the information on any edge can be given as an element of vector space over the finite field _q.
While all edges sent the information on the same set X,
the above subset might depend on the edge.
This is because the dimension of the information to be sent depends on the edge in general.
Since the cardinality of the set X is an arbitrary number, 
we can apply this linearity condition to the case when X is a given as the n-th power of a certain set.


  (C2) [No-randomness]
All of intermediate nodes have no scramble random numbers.


  (C2') [Limited-randomness]
Each limited intermediate node has limited scramble random numbers.
When each group is composed of one node,
as a typical example, we assume that the node in i-th group can use γ_i random numbers per transmission.


Next, we define Eve's attack.
The conventional attack is modeled by a collection 𝔄^0 of subset of [ℓ].
That is, in the conventional attack, 
Eve chooses a subset s∈𝔄^0,
and eavesdrops the edges in the subset s.
This types of attack is called a deterministic attack.
Hence, the set of deterministic attacks is identified with 𝔄^0.
The following discussion depends on the 
collection 𝔄^0 of subset of [ℓ].
That is, our problem is characterized by the structure of network and 
the collection 𝔄^0. 
Also, Eve can randomly choose her choice s.
Such an attack is written as a probability distribution P_S
and is called a randomized attack or a randomization of 𝔄^0.
We denote the set of randomized attacks by 
𝔄̅^0.

In this paper, we allow Eve to adaptively choose 
the edges to be eavesdropped.
For simplicity, we assume that all subsets in the collection 
𝔄^0 have the same cardinality ζ.
While Eve is allowed to eavesdrop ζ edges,
she can adaptively choose them as follows.
She chooses the first edge α_1 ∈ [ℓ] to be eavesdropped,
and obtains the information Z_1 ∈ X on the edge.
Based on the information Z_1, she chooses the second 
edge α_2(Z_1) ∈ [ℓ] to be eavesdropped
and obtains the information Z_2 ∈ X on the edge.
In this way, 
based on the information Z_1, …, Z_j-1, she chooses the j-th
edge α_j(Z_1,…, Z_j-1) ∈ [ℓ] to be eavesdropped
and obtains the information Z_j ∈ X on the edge.
Since the choice of the set
α={α_1, …, α_ζ} of attacked edges
is given as a function of ζ-1 outcomes z_1, …, z_ζ-1,
it is often written as 
α(z_1, …, z_ζ-1) to clarify this point.
Here, for any data z_1, …, z_ζ-1, 
α(z_1, …, z_ζ-1)
is required to belong to the family 𝔄^0.
This type of attack is called a general adaptive attack.
In this type of attack, the order of eavesdropped edges has no relation with the numbers assigned to the edges.
A general adaptive attack α=(α_1, …, α_ζ)
is called a time-ordered adaptive attack
when α_1< α_2(z_1)< … < α_ζ(z_1, …, z_ζ-1).
Although a general adaptive attack has less practical meaning than
a time-ordered adaptive attack, 
we consider a general adaptive attack due to its mathematical simplicity.
We denote the sets of 
time-ordered adaptive attacks and general adaptive attacks by 
𝔄^1 and 𝔄^2, respectively.
Similar to 𝔄̅^0,
the sets of their randomizations are written as 
𝔄̅^1 and 𝔄̅^2, respectively.
Now, we identify the set of deterministic attacks with the collection 𝔄^0.
Considering a constant function α, which does not depend on 
ζ-1 outcomes z_1, …, z_ζ-1,
we can consider the collection 𝔄^0 as a subset of 𝔄^1
while 𝔄^1 ⊂𝔄^2.


Next, we consider a more powerful attack than 
a time-ordered adaptive attack 
α=(α_1, …, α_ζ).
Although Eve decides the eavesdropped edges in the same way as
the time-ordered adaptive attack 
α=(α_1, …, α_ζ),
she is allowed to change the information Z_j on the j-th eavesdropped edge α_j(Z_1, …, Z_j-1)
to β_j(Z_1, …, Z_j), 
which is a function of her observations Z_1, …, Z_j.
This kind of attack is called an adaptive and active attack
and is written as
the pair (α,β) of 
α=(α_1, …, α_ζ)
and 
β=(β_1, …, β_ζ).
We denote the set of adaptive and active attacks (such functions) 
by 𝔄^3.
The sets of the randomizations 
are written as 
𝔄̅^3.
When α does not depends on her observations Z_1, …, Z_ζ-1,
α is a deterministic attack and 
the pair (α,β) is called an active attack.
Indeed, when active attack is made, the information on the network is changed.
However, in this paper, we do not care about the correctness of the recovered information
when active attack is made.
We consider the correctness in the decoding only when no active attack is made, i.e.,
we discuss only the secrecy when active attack is made.

Hence, we have the relations
𝔄^0⊂𝔄^1⊂𝔄^2,
𝔄^0 ⊂𝔄^1⊂𝔄^3,
and 
𝔄̅^0⊂𝔄̅^1⊂𝔄̅^2,
𝔄̅^0 ⊂𝔄̅^1⊂𝔄̅^3.
We also assume that there is no error in any edges except for the eavesdropped edge.
The classes of attacks are summarized as Table <ref>.





Under a code Φ and an attack (α,β) ∈𝔄^3,
we denote the mutual information between the messages and Eve's observations 
Z=(Z_1, …, Z_ζ)
by I(M;Z)_Φ,(α,β).
Also,
under an attack α∈𝔄^2
we denote it 
by 
I(M;Z)_Φ,α.
In addition, 
an attack P ∈𝔄̅^i with i=0,1,2,3,
we denote it by I(M;Z)_Φ,P.
Then, for any attack P ∈𝔄̅^i for i=0,1,2,3
and a network code Φ, we can choose an attack 
x∈𝔄^i
such that I(M;Z)_Φ,P≥  
I(M;Z)_Φ,x.
That is, we have

    max_P ∈𝔄̅^i
    I(M;Z)_Φ,P
    =
    max_x∈𝔄^i
    I(M;Z)_Φ,xER

 for i=0,1,2,3.

First, we consider the case when the network code is not necessarily linear. 
Then, we have the following theorem[
Even when the cardinality d of each channel is different from q,
this theorem still holds.]
when Y_i expresses the information on the edge i.


T7B
Assume that a network code Φ satisfies the following condition.
Given an arbitrary element 
s={s_1,…,s_ζ}∈𝔄^0, we have




    H(M| Y_s_1=z_1, …, Y_s_ζ=z_ζ)
    =
    H(M| Y_s_1, …, Y_s_ζ) 
    H8-17B

for any element (z_1, …, z_ζ).
Then, any general adaptive attack α∈𝔄^2 satisfies 

    I(M;Z)_Φ,α≤max_s∈𝔄^0
    I(M; Z)_s.H8-17

□
Theorem <ref> will be shown in the next subsection.
Since 
I(M; Z)_Φ,s=0 for any s∈𝔄^0
implies the condition (<ref>),
we have the following corollary.

T7C
When the relation 

    I(M; Z)_Φ,s=0 H8-17C

holds for an arbitrary element s∈𝔄^0, 
any general adaptive attack α∈𝔄^2 satisfies 

    I(M;Z)_Φ,α =0. H8-17D

□

This corollary guarantees that 
perfect security for any deterministic attack (<ref>) implies
perfect security for any general adaptive attack (<ref>)
without the linearity condition.
Notice that the mutual information leaked to wiretapper is not zero
in the counter example given  in Section <ref>.

In the case of linear network codes, we have the following lemma,
which will be shown in the next subsection.


L5-10
Let M be the message and L be the scramble random variable.
We assume that they are subject to the independent uniform distribution on M× L.
For a  linear function f_1 from M× L→ M, 
we define the variable X:=f_1(M,L) on M.
We choose a linear function g=(g_1,g_2) from 
M→ M× L
such that g(x) ∈  f_1^-1(x), i.e., f_1 (g(x))=x.
Then, 

    P_M,X(m,x)=P_M,X(m-g_1(x),0)5-10.

□









When the message M and the scramble random variable L
are subject to the independent uniform distribution,
applying Lemma <ref> to the case when X=(Y_s_1, …, Y_s_ζ), 
we have 

    H(M| Y_s_1=z_1, …, Y_s_ζ=z_ζ)
    
    
    =   
    H(M| Y_s_1=0, …, Y_s_ζ=0),

which implies the condition (<ref>).
Hence, Theorem <ref> guarantees the following theorem.

T7
Assume that a network code Φ is linear with respect to a certain finite field _q.
When the message M and the scramble random variable L
are subject to the independent uniform distribution,
any general adaptive attack α∈𝔄^2 satisfies 
(<ref>).
□

Further, we have the following proposition.
T8
Assume that a network code Φ is linear.
Any adaptive and active attack (α,β) ∈𝔄^3 satisfies 

    I(M;Z)_Φ,(α,β)= I(M;Z)_Φ,α.

□
Although the paper <cit.> shows Proposition <ref> only 
for an active attack,
the proof can be extended to an adaptive and active attack.
That is, the reduction from an adaptive and active attack 
(α,β) ∈𝔄^3
to an adaptive attack α∈𝔄^2
can be shown in the same way as <cit.>.
Therefore, 
when Φ is a linear code,
combing the above fact and (<ref>),
we find the relations

    max_α∈𝔄^3
    I(M;Z)_Φ,β
    =   max_(α,β) ∈𝔄^2
    I(M;Z)_Φ,β
    
    =   max_s∈𝔄^0
    I(M;Z)_Φ,s.ER9

That is, when a network code is linear,
we can restrict Eve's attacks to deterministic attacks.

Here, we remark the difference between our adaptive attack and the adaptive attack in 
<cit.>.
The paper <cit.> considers the following attack when 
the code has block length n and the sender sends information to the receiver n times.
The eavesdropper can change the nodes to be attacked on the i-th transmission 
by using the information obtained by the previous attacks.
However, in our setting, 
the eavesdropper can change the node to be attacked 
during one transmission from the sender to the receiver.
□

R9Here, we summarize the preceding studies <cit.> for the security analysis on the active attack, which makes contamination of the information on the network.

The secrecy analysis in <cit.>
is different from the analysis in <cit.>
although the non-local code construction in <cit.> does not depend on the concrete form of matrices corresponding to the network topology, 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.



Indeed, the papers <cit.> provided a statement similar to the main result of the paper <cit.>.
However, while it showed the correctness under the presence of the contamination in a certain class, 
it showed only the secrecy without contamination.
However, the paper <cit.> showed the secrecy as well as  
the correctness under the presence of the contamination in a certain class.

While the papers <cit.><cit.> considered the secrecy when the error exists,
it addressed the amount of leaked information only when the eavesdropper does not know the information of the noise.

However, the analysis in <cit.>
evaluated the leaked information when the eavesdropper knows the information of the noise.

Further, the paper <cit.>
gave an example where the contamination improves her performance,
which was shown in Section <ref>.
The code given in this example is imperfectly secure 
for the deterministic attack on any allowed pair of edges.
However, 
it is not unsecure for a certain active attack on the same allowed pair of edges.


□

R7There is a possibility that the randomness given in each node
is not uniform.
In this case, it is usual to apply univeral2 hash function <cit.>.
Then, the resultant variable is close to the uniform random variable.
That is, the variational distance between the distribution of the resultant variable
and the uniform distribution is upper bounded by ϵ <cit.>.
However, we cannot say that it is the uniform random variable.

To discuss such a case, we often employ another criterion, the variational distance criterion, 
in which, we focus on the variational distance D_V
between 
the joint distribution 
P_M,Z
and 
the product distribution P_M× P_Z
instead of the mutual information.

When the randomness given in each node is uniform,
we denote the resultant joint distribution 
and the mutual information 
by P_i,M,Z and
I(M;Z)_Φ,(α,β).

When the randomness given in each node is given in the above case,
we denote the resultant joint distribution 
by P_r,M,Z.
Since 
the variational distance between the distribution of the resultant variable
and the uniform distribution is upper bounded by ϵ,
information processing inequality guarantees that

    D_V(P_i,M,Z, P_r,M,Z)
    ≤ϵ.

Pinsker inequality guarantees 

    D_V(P_i,M,Z,P_M× P_Z)
    ≤√(1/2I(M;Z)_Φ,(α,β)).

Therefore,
the secrecy in the above case is evaluated as

    D_V(P_r,M,Z,P_M× P_Z)
    
    ≤   
    D_V(P_i,M,Z, P_r,M,Z)
    +
    D_V(P_i,M,Z,P_M× P_Z)
    
    ≤   ϵ+
    √(1/2I(M;Z)_Φ,(α,β)).

□


 §.§ Proofs of Theorem <ref> and Lemma <ref>


Theorem <ref>
We have

    H(M|Z)_Φ,α
    
    =    ∑_z_1∑_z_2⋯∑_z_ζ 
    P_Y_α_1, Y_2 (z_1),…, 
    Y_α_ζ (z_1,z_2, …, z_ζ-1)
       ·
    H(M| Y_α_1=z_1, 
    Y_α_2(z_s1)=z_2, …, 
    Y_α_ζ (z_1,z_2, …, z_ζ-1)=z_ζ)
    
    
    =    ∑_z_1∑_z_2⋯∑_z_ζ 
    P_Y_α_1, Y_2 (z_1),…, 
    Y_α_ζ (z_1,z_2, …, z_ζ-1)
       · H(M| Y_α_1, 
    Y_α_2(z_s1), …, 
    Y_α_ζ (z_1,z_2, …, z_ζ-1))
    
    ≥   min_s∈𝔄^0
    H(M| Y_s_1, …, Y_s_ζ).

This relation implies (<ref>).




Lemma <ref>
Given x,m, we have

    { l | f_1(m,l)=x}
    =
    { l | f_1(m- g_1(x),l-g_2(x))=0}.

So, we have

    |{ l | f_1(m,l)=x}|
    =
    |{ l | f_1(m- g_1(x),l)=0}|.

Hence, we have (<ref>).





§ NETWORK WITH POWERFUL ADAPTIVE ATTACK
S5
In this section, to consider when adaptive attack is more powerful than deterministic attack,
we address the single shot setting, in which, the sender sends only one element of _p,
which is called the scalar linearity.
This section mainly addresses the scalar linearity although Theorem <ref> holds under vector linearity.

It is known that there exists a linear imperfectly secure code 
over a finite field _q of a sufficiently large prime power q
when Eve may access a subset of channels that does not contain a cut between Alice and Bob 
even when the linear code does not employ private randomness in the intermediate nodes <cit.>[In contrast, the paper <cit.> discussed a similar code construction
by increasing n (vector linearity) while it did not increase the size of q.
The paper <cit.> extended this type of vector linearity setting 
 of imperfectly secure codes to the case with multi-source multicast.].
The rigorous definition of imperfectly secure code is given in the next paragraph.
Theorem <ref> guarantees that 
such a linear code is still imperfectly secure even for active and adaptive attack over the same network.
However, it is not clear whether there exists such a linear imperfectly secure code over a finite field _p of prime p.

The previous paper <cit.> showed that 
there exists no imperfectly secure code over active attacks under a toy network
while there exists an imperfectly secure code over deterministic attacks.
In that network model, non-linear code realizes the imperfect security over active attacks.
In this section, we show that there exists no imperfectly secure code over adaptive attacks
in the same network model.

The toy network model given in <cit.> is the network of Fig. <ref>, 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.
No scramble random variable is allowed in the intermediate node, 
which is the condition (C2).
Eve is allowed to attack two edges of E except for the pairs {e(1),e(2)} and {e(3),e(4)}.
That is, 𝔄^0=
{{e(1),e(3)},
{e(2),e(3)},
{e(1),e(4)},
{e(2),e(4)}}.
We adopt an imperfect security criterion in this section.
When Z_E is Eve's information and I(M;Z_E)<log p for all of Eve's possible attacks,
we say that the code is imperfectly secure <cit.> (or weakly secure).
Otherwise, it is called insecure.
That is, when there exists no function ψ̃ such that 
ψ̃(Z_E)=M, our code is imperfectly secure.
Also, 
when Z_E is Eve's information and I(M;Z_E)=0 for all of Eve's possible attacks,
we say that the code is perfectly secure.




Let L∈_p be the uniform scramble random variable generated in the source node.
Assume that the intermediate node generates another uniform scramble random variable L'∈_p.
The following scalar-linear code is perfectly secure.
The encoder ϕ is given as 

    Y_1:=L,   Y_2:=M+L. Eq3B

Then, the intermediate node makes the code φ as

    Y_3:= L',  Y_4:=Y_2-Y_1+L'. Eq2F

The decoder ψ is given as ψ(Y_3,Y_4):=Y_4-Y_3,
which equals Y_2-Y_1+L'-L'=M+L-L +L'-L'=M.
Then, the pair (Y_1,Y_3) is independent of M.
Similarly, the pairs (Y_1,Y_4), (Y_2,Y_3), and (Y_2,Y_4) are independent of M.
Hence, this code is perfectly secure for deterministic attack, and has the transmission rate log p.
Due to the linearity, it is secure even for active and adaptive attack.
However, when the intermediate node cannot generate another 
uniform scramble random variable,
as shown in <cit.>,
there is no imperfectly secure scalar-linear code over finite field _p with prime p for deterministic attacks.
In other words, no scalar-linear code over finite field _p can realize the situation that
Eve cannot recover the message M perfectly with deterministic attack.


To resolve this problem, there are two methods.
One is use of vector-linearity, and the other is use of non-linear code.
To use vector-linear code,
we consider the case when the network of Fig. <ref> is used twice.
Assume that the source node generates three uniform scramble random variables L_1,L_2,L_3∈_p.
Using these variable, we give a vector-linear code as follows.
The first transmission sends the following;

    Y_1:=L_1,   Y_2:=M+L_1, Eq3C

and the second transmission sends the following;

    Y_1':=L_2,   Y_2':=L_3+L_2, Eq3D

Then, the intermediate node makes the code φ as

    Y_3:= Y_2'-Y_1',  Y_4:=Y_2-Y_1+Y_2'-Y_1'. Eq2G

In this code, nothing is transmitted in the second layer at the second transmission.
The decoder ψ is given as ψ(Y_3,Y_4):=Y_4-Y_3,
which equals Y_2-Y_1+Y_2'-Y_1'-(Y_2'-Y_1')=M+L_1-L_1=M.
Then, the pair (Y_1,Y_3) is independent of M.
Similarly, the pairs (Y_1,Y_4), (Y_2,Y_3), and (Y_2,Y_4) are independent of M.
Hence, this code is perfectly secure for deterministic attack, and has the transmission rate 1/2log p.
Due to the linearity, it is secure even for active and adaptive attack.
In this code, 
the code in the second layer is composed of the message Y_2-Y_1
and the scramble Y_2'-Y_1'.
The secrecy of both are required in the transmission in the first layer.
Hence, totally three scramble variables are required in the source node.


As another solution, we discuss non-linear code as follows.
For this aim, we consider the case when the sender transmits only the binary message M ∈_2 and any edge can transmit only a binary information.
Now, we prepare the binary uniform scramble random variable L∈_2.
We consider the following code.
The encoder ϕ is given in the same way as (<ref>).
Then, we consider non-linear code φ in the intermediate node as

    Y_3   := Y_1(Y_2+Y_1)=Y_1(Y_2+1), Eq1
    Y_4   :=(Y_1+1)(Y_2+Y_1)
    =(Y_1+1)Y_2. Eq2

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;

    Y_3= LM,   Y_4=LM+M,

the decoder can recover M nevertheless the value of L.

The leaked information for the deterministic attack is calculated as follows.
As shown in <cit.>,
the mutual information and the l_1 norm security measure
of these cases are calculated to 

    I(M;Y_1,Y_3)= I(M;Y_1,Y_4) 
    
      =    I(M;Y_2,Y_3)=  I(M;Y_2,Y_4)=1/2,E9
        d_1(M|Y_1,Y_3)= d_1(M|Y_1,Y_4) 
    
      =    d_1(M|Y_2,Y_3)=  d_1(M|Y_2,Y_4)=1/2,E10

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 the base of the logarithm to be 2.
Therefore, we find that this code is secure for deterministic attacks.
That is, we find that there exists a secure code over deterministic attacks.
Further, as shown in Proposition <ref>, 
when Eve cannot recover the message M perfectly with any deterministic attack in the code,
the network code is limited to this code or a code equivalent to this code.
This fact shows that there exists no imperfectly secure code over active attacks.

 <cit.>T6
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 assume that the random variables (Y_3,Y_4):=φ (Y_1,Y_2)
satisfies the following conditions.


  (C1) The relation ψ (Y_3,Y_4)=M holds.

  (C2) There is no deterministic function ψ̃
from _2^2 to _2 satisfying one of the following conditions.

    ψ̃(Y_1,Y_3)=M,  ψ̃(Y_1,Y_4)=M, 
    ψ̃(Y_2,Y_3)=M,  ψ̃(Y_2,Y_4)=M.


Then, there exist functions
f_1,f_2,f_3,f_4 on _2 such that
Y_i':=f_i(Y_i) is given in (<ref>), (<ref>), and (<ref>)
with a scramble random variable L while the variable L might be correlated with M.
□



Now, we show that
there exists no imperfectly secure code even for adaptive attacks without active modification.
Due to the above observation, it is sufficient to show that
there exists an adaptive attack to recover the message M
for the above given code.
Here, we give two types of adaptive attacks to recover the message M as follows. 



  (i)
First, Eve eavesdrops e(1).
When Y_1=1, 
she eavesdrops e(3).
Then, she recovers M as Y_3=Y_2+1= Y_2+Y_1=M.
When Y_1=0, she eavesdrops e(4)
Then, she recovers M as Y_4=Y_2=Y_2+Y_1=M.


  (ii)
First, Eve eavesdrops e(2).
When Y_2=1, 
she eavesdrops e(4).
Then, she recovers M as Y_4=Y_1+1= Y_1+Y_2=M.
When Y_2=0, she eavesdrops e(3)
Then, she recovers M as Y_3=Y_1=Y_1+Y_2=M.


Therefore, we find that
this code is not imperfectly secure even for adaptive attacks without active modification.
That is, there exists no imperfectly secure code over adaptive attacks
in this network model.
This fact shows that an adaptive attack is powerful for this kind of non-linear code as an active attack
even when it has no active modification.
The discussion in this section is summarized as Table <ref>.







§ ASYMPTOTIC FORMULATION
 S5B

Next, given a network and the collection 𝔄^0,
we consider the capacity and the capacity region depending on 
the restrictions on the codes.
Due to (<ref>), in the following, we do not consider randomization of 
Eve's attack.
We assume that each edge transmits {1, …, d}^n
when we use channel at n times, 
where the number n is called the block-length.
Given integers n and d,
we apply the formulation (including the linearity) given in Section <ref>
to the case when X is given as {1,…, d  }^n.
In this sense, the linearity condition (C1) is defined with block-length n,
and Theorem <ref> can be applied in this discussion.
Then, dependently of the block length n, 
we denote 𝔄^i and ℭ^0

by 𝔄_n^i and ℭ_n^0, respectively,
although the collection 𝔄_n^0 does not depend on n.
First, we focus only on an adaptive attack α∈𝔄_n^2.
Since there is no noise,
we denote the decoding error probability depends only on our code
Φ∈ℭ_n^0.
Hence, we denote it by P_e(Φ).
Then, we impose the following two conditions to our code 
Φ∈ℭ_n^0.


  (C3)
[Reliability]
The relation P_e(Φ) =0.


  (C4)
[Secrecy]
The relation I(M;Z)_Φ,α  =0 holds for α∈𝔄_n^2.

We denote the set of codes satisfying the above two conditions by ℭ_n^1.
Additionally, we denote the set of codes satisfying 
the no-randomness condition (C2) as well as these two conditions by ℭ_n^2.
In the unicast case, i.e., the case with a=b=1,
we define the full-randomness capacity C_1 
and the no-randomness capacity C_2 as

    C_i    :=sup_nsup_Φ∈ℭ_n^i1/nlog | Φ| ,   i=1,2.

Here, we should remark that we impose no linearity condition for our code.
From the definition, we have the relation

    C_2 ≤ C_1
    E9-23.


In the multiple multicast case, we define the full-randomness capacity region C_1 
and the no-randomness capacity region C_2 as

    C_i' :=
    sup_nsup_Φ∈ℭ_n^i'{(1/nlog |Φ|_i,j)_i,j}
    ,   i'=1,2.


Similar to (<ref>), we have the relation

    C_2 ⊂ C_1
    E9-24.



Next, we consider the case when each node has limited randomness, which is given as the condition (C2').
Since this generalized case is complicated, we discuss this generalized setting only with the unicast case.
Further, we suppose that each group is composed of one node.
Then, as in the condition (C2'),
we assume that the node in i-th group can use γ_i random numbers T_i per transmission.
We denote the set of codes satisfying this condition with length n
by ℭ_n[ (γ_i)_i].
Then, we define the capacity C[ (γ_i)_i] 
with limited randomness as

    C[ (γ_i)_i]     :=sup_nsup_Φ∈ℭ_n[ (γ_i)_i ]1/nlog | Φ| .


To clarify the effect by the linearity restriction,
we denote the capacity and capacity region 
by C_i,L and C_i,L, respectively
when the linearity restriction (C1) is imposed to our codes. 
Then, we have the relation C_i,L≤ C_i and 
C_i,L⊂ C_i.
Also, the capacity with limited randomness with linearity restriction (C1) to our codes
is denoted by C[ (γ_i)_i]_L.

Restricting Eve's attack to the deterministic attacks 𝔄_n^0,
we define the above type of capacities and capacity regions, which are denoted by 
C_i,D, C_i,L,D,C[ (γ_i)_i]_D, C[ (γ_i)_i]_L,D, 
 C_i,D and C_i,L,D, respectively. 
Then, we have the relations 
C_i,L,D = C_i,L,
C_i,D≥ C_i,
C_i,L,D=  C_i,L, 
C_i,D⊃ C_i, 
and the similar relations.



Now, we address the case when an adaptive and active attack β∈𝔄_n^3 is allowed
for Eve.
In this case, we replace the condition (C4) by the following condition;


  (C4')
[Secrecy]
The relation I(M;Z)_Φ,β  =0 holds for β∈𝔄_n^3.

However, we do not replace (C3) by the following 
robustness condition;

    P_e(Φ,β) =0  for ∀β∈𝔄_n^3E5-10-A,

where P_e(Φ,β) is the decoding error probability 
with our code Φ when Eve makes the attack β. 
This situation can be justified in the following way when free public channel with no error is available.
In this case, to communicate each other securely, 
they need to share secret random variables.
To generate secret random variables,
they send secret random variables via the secure network coding.
The secrecy of the generated random variables is guaranteed by the secrecy condition (C4).
That is, condition (4) is definitely needed.
However, the robustness condition (<ref>)
is not necessary because they can check whether the transmitted random number is correct 
when the error verification test with the public channel is available after the transmission <cit.> <cit.> (See Remark <ref>.).
Hence, we impose the condition (C3) instead of (<ref>).
Replacing the condition (C4) by the condition (C4'), 
we define the above type of capacities and capacity regions, which are denoted by
C_i,AC, C_i,L,AC,C[ (γ_i)_i]_AC, C[ (γ_i)_i]_L,AC, 
 C_i,AC and C_i,L,AC, respectively. 
Then, we have the relations 
C_i,L,AC = C_i,L,
C_i,D≥ C_i,AC,
C_i,L,AC=  C_i,L,
C_i,D⊃ C_i,AC, and the similar relations.
In summary, 
for each i=1,2, 
we have

    C_i,L,AC= C_i,L= C_i,L,D⊂ C_i,AC⊂ C_i⊂ C_i,D.LLP





That is, when the equality C_i,D= C_i,L,D holds,
all the capacities have the same value. 
In other cases, we have similar relations.
 
R8When the public channel is available, 
the error verification can be done as follows.


Alice and Bob apply a universal2 hash function to their respective message with output length m_2.
They exchange their output of the universal2 hash function via the public channel.
If they are the same,
they consider that the message was transmitted correctly.
If they are different, they consider that 
the message was transmitted incorrectly.

As a typical example of a universal2 hash function,
we can use a modified Toeplitz matrix 
whose detail construction and evaluation of the complexity of its construction
are summarized in the recent paper <cit.>.
Its calculation complexity is O(m log m) when m is the input bit length.
Indeed, it was reported in paper <cit.> that
the above type hash function practically implemented with m=1 000 000
by a conventional personal computer.

Due to this step, we can guarantee the correctness with probability 1-2^-m_2, which is called the significance level<cit.>.
So, it is enough to choose m_2 depending on the required significance level.
This evaluation means that we do not need to increase the bit length m_2 for error verification
even when the length of message increases.

Here, one might care of the information leakage due to the information exchange on the public channel.
They can avoid such information leakage 
when they share m_2 bit common secret bits priorly. 
As above mentioned, the length m_2 of shared  
secret bits does not depend on the length of message.
Hence, when the length of message is very large,
the length m_2 of shared  
secret bits is negligible.
□


STNow, as a typical example, we consider a single source acyclic network where Eve may choose any r-subset channels to access, which we call r-wiretap network <cit.>.
That is, 𝔄^0 is given as {s⊂ [ℓ] :| s|=r}.
To discuss the capacities of the given network, we introduce two kinds of minimum cuts.
To define them,
we define a pseudo source node as a node that has only out-going edges but has no original message to be transmitted.
A pseudo source node is classified as an intermediate node because it is not the source node nor the terminal node.
The first type of minimum cut _1 is the minimum number of edges crossing a line separating
the source node and the terminal node.
The second type of minimum cut _2 is the minimum number of edges crossing a line separating
the source node and the terminal node with removing all edges out-going from pseudo source nodes.
That, while edges out-going from pseudo source nodes are ignored in _2,
they are counted in _1.
For r-wiretap network,
we have 

    C_2,L,AC=
    C_2,L=C_2,L,D=
    C_2,AC= C_2= C_2,D
    
    =   _2-r,E9-2
       _2-r≤
    C_1,L,AC=C_1,L=C_1,L,D≤
    C_1,AC
    ≤    C_1≤ C_1,D≤_1-r.E9-2B

When the network has no pseudo source node, 
_2=_1, which implies the equalities in (<ref>).
For example, the network given in Fig. <ref> shows a network has different rates _1 and _2. 
This network has a linear code to realize _1-r when r=1, which implies the equalities in (<ref>).



The relations (<ref>) and (<ref>) can be shown as follows. 
It was shown in <cit.> that 
the rate _2-r 
is achievable by a linear code where only source node generates randomness
when Eve is allowed to use deterministic attack.
However, any adaptive and active attack is reduced to deterministic attack under a linear code.
Hence, we obtain C_2,L,D≥_2-r.

Using a idea similar to <cit.>,
we show C_1,D≤_1-r. For this aim,
we choose edges crossing a line separating
the source node and the terminal node such that 
these edges contains the r eavesdropped edges.
Let Z be the variable on the r eavesdropped edges, 
and Y be the variable on the above edges crossing the separating line. 
Let M be the message to be securely transmitted.
Due to the security condition, we have I(M;Z)=0
When an edge has an information with cardinality d,
the receiver's information B satisfies

    I(M;B)≤
    I(M;Y)= I(M;YZ) 
    
    =    I(M;Z)+I(M;Y|Z)
    = I(M;Y|Z) ≤ H(Y|Z) 
    ≤    (_1-r) log d ,

which implies
C_1,D≤_1-r.
Therefore, using (<ref>) and (<ref>) and combining these facts, 
we obtain (<ref>).

When no intermediate node is allowed to generate randomness,
any pseudo source node plays no role.
Hence, the above discussion yields that
C_2,D≤_2-r.
Thus, we obtain (<ref>).


□

Ex2Next, we consider the case when 𝔄^0 is given by using the following group structure of the intermediate nodes.
The intermediate nodes are divided into c-1 groups, from the first group to the c-1-th group.
Here, a source nodes and b terminal nodes are regarded as
the 0-th group and the c-th group, respectively.
For i=1, …, c,
there are several edges between the i-1-th group and the i-th group.
We call the set of these edges the i-th edge group.
As seen later, this grouping of edges is essential to define the collection 𝔄^0.
Each intermediate node has incoming edges and outgoing edges.


Eve is assumed to eavesdrop a part of edges from the i-th edge group.
Eve's ability is characterized by the collection of subsets of the i-th edge group to be eavesdropped, which is called the i-th tapped-edge collection and is denoted by S_i.
When an intermediate node of i-th group is directly linked to an intermediate node of i+2-th group,
we consider that the intermediate node of i-th group is connected 
to intermediate node of i+1-th group with an edge that is not contained in any member of 
the i+1-th tapped-edge collection S_i+1.
Similarly, 
when an intermediate node of i-th group is directly linked to an intermediate node of i+i'-th group,
we can apply the same reduction.
Hence, without loss of generality, we can assume that
an outgoing edge of an intermediate node of i-th group is linked only to an intermediate node of i+1-th group.
Hence, the collection 𝔄^0
is given to be
S_1× S_2×⋯× S_c.

This example shows the following.
When the network model is composed of c-1 groups of intermediate nodes,
we can assume that the collection 𝔄^0
is given to be
S_1× S_2×⋯× S_c
without loss of generality.
□



§ RELAY NETWORK
S6




 §.§ Formulation and capacities

Now, as a special case of Example <ref>, we consider the relay network given in Fig. <ref> as a generalization of the network of Fig <ref>.
This network is a unicast network, and only one intermediate node in each intermediate group.
That is, it has c-1 intermediate nodes.

We have k_i edges between the i-1 and i-th nodes. 
In one channel use, each edge e(i,j) can transmit the information Y_i,j for i=1,…, c 
and j=1, …, k_i that takes values on {1, …, d}.





Here, we assume that Eve can eavesdrop r_i edges 
Y⃗_i,s_i:=(Y_i, s_i(1), …, Y_i, s_i(r_i))
among k_i edges 
Y_i:=(Y_i, j)_j=1, …, k_i
between the i-1 and i-th nodes.
In this notation, the function s_i expresses the edges eavesdropped by Eve.

That is, she can eavesdrop ∑_i=1^c r_i edges totally.
In this paper, we allow stronger attacks for Eve than conventional attacks,
i.e., adaptive attacks and active attacks.


Then, we have the following capacity theorem.
TT3
Defining

    h^1:=k_1 ,  
    h^j:= min( k_j ,
    k_j-1-r_j-1/k_j-1 h^j-1+γ_j 
    ),

we have

    C_1 =    
    C_1,L = 
    C_1,D = 
    C_1,L,D
    
    =    
    C_1,AC = 
    C_1,L,AC = 
    log d min_1 ≤ j ≤ c (k_j-r_j) Cap-1,
    
    
    C_2=    
    C_2,L= 
    C_2,D= 
    C_2,L,D
    =
    C_2,AC= 
    C_2,L,AC
    
    =    log d min_1 ≤ j ≤ c
    (k_j-r_j) 
    (k_j+1-r_j+1) ⋯ (k_c- r_c) /k_j+1⋯ k_c ,Cap-2

and

    C[ (γ_i)_i] =
    C[ (γ_i)_i]_L =
    C[ (γ_i)_i]_D =
    C[ (γ_i)_i]_L,D
    
    =   
    C[ (γ_i)_i]_AC 
    =
    C[ (γ_i)_i]_L,AC =
    log d min_1 ≤ j ≤ ck_j-r_j/k_jh^j .Cap-2B

□




When the randomness is allowed in the intermediate nodes,
in the network of Fig <ref>, the code given in (<ref>) and (<ref>) achieves the capacity 
C_1 as well as the capacities given in (<ref>).
In general,
the capacity C_1 is given as the rate of the bottleneck layer, which equals the minimum 
log d min_1 ≤ j ≤ c (k_j-r_j).
When the randomness is not allowed in the intermediate nodes,
the code given in (<ref>), (<ref>), and (<ref>) achieves the capacity 
C_2 as well as the capacities given in (<ref>).
In general,
the capacity C_2 is given as
the minium of the multiplication log d (k_j-r_j) 
(k_j+1-r_j+1) ⋯ (k_c- r_c) /k_j+1⋯ k_c with respect to j.
Therefore, when k_j and r_j are constants k and r,
the capacity C_2 is calculated to log d (k-r)^c/k^c-1.
When c goes to infinity, it converges to zero.


Here, we discuss the relation to existing results with respect to the difference between two capacities C_1
and C_2.
A larger part of existing studies discuss the capacity (or capacity region) with no restriction of
randomness generated in intermediate nodes.
For example, in r-wiretap network, which is a typical network model, as explained in Example <ref>, 
the capacity with no restriction can be achieved without use of randomness generated in intermediate nodes.
However, the paper <cit.> showed an example, in which 
randomness generated in intermediate nodes improves the capacity.
In this example, the source node is connected only with one edge.
Usually, the secure transmission can be done by use of the difference between information on different edges connected to the same node.
Hence, it is natural that randomness generated in intermediate nodes improves the capacity
when each source node is connected only to one edge.

The papers <cit.> addressed the difference between the existence and non-existence of 
randomness generated in intermediate nodes in another network
only for deterministic attacks.
However, they did not derive the capacities C_1,D and C_2,D exactly. Their analysis depends on special codes.
Therefore, our analysis is the first derivation of the difference between 
the capacities C_1,D and C_2,D except for the case when the source node is connected only with one edge.






 §.§ Converse part

For any j=1, …, c,
the rate of secure transmission from the j-1-th intermediate node to
the j-th intermediate node is log d (k_j-r_j).
Taking the minimum with respect to j,
we obtain C_1,D≤log d min_1 ≤ j ≤ c (k_j-r_j).

Next, we consider (<ref>).
For the amount of leaked information, we have the following theorem.
T1
Under the condition (C2), we have

    max_s_1, …, s_c I(M; Y⃗_1,s_1, …, 
    Y⃗_c,s_c) 
    ≥    H(M) 
    
       -
    ( log d )
    min_1 ≤ j ≤ c
    (k_j-r_j) 
    (k_j+1-r_j+1) ⋯ (k_c- r_c) /k_j+1⋯ k_c .
 
□ 

Therefore, to realize the condition 

    max_s_1, …, s_c I(M; Y⃗_1,s_1, …, 
    Y⃗_c,s_c) =0,
    Hd1

the message M needs to satisfy the condition

    H(M)≤log d
    min_1 ≤ j ≤ c
    (k_j-r_j) 
    (k_j+1-r_j+1) ⋯ (k_c- r_c) /k_j+1⋯ k_c .
    Hd3

When use the same network n times,
the condition (<ref>) requires the condition

    H(M)≤ n log d 
    min_1 ≤ j ≤ c
    (k_j-r_j) 
    (k_j+1-r_j+1) ⋯ (k_c- r_c) /k_j+1⋯ k_c ,Hd2

which implies 
    C_2,D≤log d min_1 ≤ j ≤ c
    (k_j-r_j) 
    (k_j+1-r_j+1) ⋯ (k_c- r_c) /k_j+1⋯ k_c .


Theorem <ref> can be generalized to the limited randomness case as follows.
Hence, it is sufficient to show Theorem <ref>.
T1B
Under the condition (C2'), we have

    max_s_1, …, s_c I(M; Y⃗_1,s_1, …, 
    Y⃗_c,s_c) 
    ≥    H(M) -
    log d min_1 ≤ j ≤ ck_j-r_j/k_jh^j .
 
□ 

Theorem <ref>
Now, we independently choose the sets S_1, S_2, …, S_c
subject to the uniform distribution.
We denote the expectation is with respect to this random choice by 𝔼.
We prove Theorem <ref> by using Lemma <ref>, which will be shown in the latter section.
Application of Lemma <ref> to X=(Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1)
shows the inequality

    𝔼
    H(Y⃗_j,S_j|Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1) 
    
    ≥   r_j/k_j𝔼H(Y_j|Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1)
    eq-02

for 1 ≤ j ≤ c.
Then we have for 1 ≤ j ≤ c,

    𝔼H(M|Y⃗_c,S_c,Y⃗_c-1, S_c-1…, Y⃗_2,S_2,Y⃗_1,S_1) 
    ≤   𝔼H(M|Y⃗_j,S_j,Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1)
    (a)≤   𝔼H(Y_j |Y⃗_j,S_j,Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1)
    
    =     𝔼 H( Y⃗_j,S_j^c |Y⃗_j,S_j,Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1)
    
    
    
    =     𝔼 H( Y_j | Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1)
    
       - 𝔼 H( Y⃗_j,S_j | Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1)
    
    (b)≤   k_j-r_j/k_j𝔼 H(Y_j|Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1),
    eq-03

where
(a) follows from the fact that
M is determined by the random variable Y_j,
and (b) follows from (<ref>).

Similarly, we  have 

    𝔼H(Y_j|Y⃗_j-1,S_j-1, Y⃗_j-2,S_j-2,…, Y⃗_2,S_2,Y⃗_1,S_1)
    (a)≤   𝔼H(Y_j-1,K_j|Y⃗_j-1,S_j-1, Y⃗_j-2,S_j-2,…, Y⃗_2,S_2,Y⃗_1,S_1)
    
    =    𝔼H(Y⃗_j-1,S_j-1^c,K_j|Y⃗_j-1,S_j-1, Y⃗_j-2,S_j-2,…, Y⃗_2,S_2,Y⃗_1,S_1)
    ≤   𝔼H(Y⃗_j-1,S_j-1^c|Y⃗_j-1,S_j-1, Y⃗_j-2,S_j-2,…, Y⃗_2,S_2,Y⃗_1,S_1)
    
        +γ_jlog d
    
    
    
    
    =    𝔼H(Y_j-1| Y⃗_j-2,S_j-2,…, Y⃗_2,S_2,Y⃗_1,S_1)
    
        -𝔼H(Y⃗_j-1,S_j-1| Y⃗_j-2,S_j-2,…, Y⃗_2,S_2,Y⃗_1,S_1)
    
         +γ_jlog d
    
    (b)≤   k_j-1-r_j-1/k_j-1𝔼H(Y_j-1|Y⃗_j-2,S_j-2, …, Y⃗_2,S_2,Y⃗_1,S_1)
    
        +γ_jlog d,

where 
(a) follows from the fact that
Y_j is determined by the random variables Y_j-1,K_j,
and 
(b) follows from (<ref>).

Now, we show

    𝔼H(Y_j|Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1) ≤  h^j  log d

by induction with respect to j.
Since H(Y_1)≤ k_1, (<ref>) holds for j=1.
Assume that

    𝔼H(Y_j-1|Y⃗_j-2,S_j-2, …, Y⃗_2,S_2,Y⃗_1,S_1) ≤  h^j-1log d.

Then (<ref>) implies that

    𝔼H(Y_j|Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1)
    
    =   k_j-1-r_j-1/k_j-1𝔼H(Y_j-1|Y⃗_j-2,S_j-2, …, Y⃗_2,S_2,Y⃗_1,S_1)
    
       + γ_j log d 
    ≤   k_j-1-r_j-1/k_j-1 h^j-1log d+  γ_jlog d, Eq3

Also, we have

    𝔼H(Y_j|Y⃗_j-1,S_j-1, …, Y⃗_2,S_2,Y⃗_1,S_1) 
    ≤  H(Y_j) ≤ k_jlog d.

Combining (<ref>) and (<ref>), we have (<ref>).

Therefore, combining (<ref>) and (<ref>),
we have

    𝔼H(M|Y⃗_c,S_c,Y⃗_c-1, S_c-1…, Y⃗_2,S_2,Y⃗_1,S_1) 
    
    ≤   k_j-r_j/k_j  h^j log d,

which is equivalent to

    𝔼I(M;Y⃗_c,S_c,Y⃗_c-1, S_c-1…, Y⃗_2,S_2,Y⃗_1,S_1) 
    ≥   
    H(M)- k_j-r_j/k_j  h^j log d.

Hence, we obtain the desired statement.




 §.§ Code construction to achieve capacity C_1,L,D
SS1

We give a code to achieve the capacity C_1,L,D.
The idea of our construction is the same as a Wiretap-II code
introduced by Ozarow and Wyner <cit.>. 
In wiretap channel II, 
a secure message is encoded to a codeword of n length and wiretapper may access any r components out of the n components. 
Then, this secure code for wiretap channel II is secure 
even for our setting.
However, this construction will be applied to a more general case 
with modification in the latter section.
To discuss such a more general case, we need to concretely describe 
our whole construction to keep the self-consistency in this section.
For simplicity, we assume that the integer d is a power q of a prime p.
The general case will be discussed later.
When we can make the desired code in the case with c=1,
we can employ the constructed code for the secure transmission code from 
the i-1-th intermediate node to the i-th intermediate node
because the i-1-th intermediate node can employ scramble random numbers T_i-1.
For this purpose, we prepare the following lemma.

L425
For any prime power q, any two natural numbers k>r,
there exist a natural integer n_k,r 
and r vectors v_1, …, v_r ∈_q^n_k,r^k
such that v_i,j=δ_i,j for j=1, …,m and 
the r × r matrix (v_i,s(j))_i,j is invertible
for any injective function s from {1, …, r} to 

{1, …, k}.
□

This lemma might be shown in the context of the wiretap channel II introduced by Ozarow and Wyner <cit.>. 
In the model of wiretap channel II,
a secrete message is encoded to a codeword in an n_k,r-length code. 
A wiretapper may take any r components 
out of k parallel channels but may have no information about the message. 
A linear code, e.g., a Reed-Solomon code can serve as the code. 
It is called a (k,r) code for wiretap channel II,
and satisfies the condition for Lemma <ref>.
Also, this leamma also can be regarded as a very simple and special case of the code in <cit.>.
For readers' convenience, we give its proof in Appendix <ref>.


Here, we make the desired code in the case with c=1.



We employ the finite filed _q' with q'=q^n_k,r.
That is, we need finite field of large size, whose efficient construction is discussed in <cit.>.
So, when we use the channel n:=n' n_k,r times,
our transmission can be regarded as n' times transmission on _q',
i.e., each edge can transmit up to n' symbols in _q'.
In the following, all random variables are treated as random variables taking values in _q'.

According to Lemma <ref>,
we choose r vectors v_1, …, v_r ∈_q^n_k,r^k.
Using r additional scramble random numbers L_1,…, L_r, 

we can transmit k-r random variables M_1,…, M_k-r 
by encoding the random variable Y⃗_j for the j-th edge by 

    Y_j:= 
    {[                       L_j               when  j ≤ r; M_j-r+ ∑_j'=1^rv_j',jL_j'        when  r+1 < j ≤ k. ].

Then, Bob recovers the original messages M_1,…, M_k-r as 

    M_j':= Y_j+r- ∑_j'=1^r v_j',jY_j'.


Assume that Eve eavesdrops r edges, the s(1)-th edge, …, the s(r)-th edge.
Due to the condition in Lemma <ref>, for any function s, 
the vectors (v_j',s(1))_1≤ j'≤ r, …, (v_j',s(r))_1≤ j'≤ r
are linearly independent.
So, ∑_j'=1^r v_j',s(1)L_j',…, ∑_j'=1^r v_j',s(r)L_j'
are r uniform random numbers 
even when we fixed the values of the random variables M_1,…, M_k-r.
Eve cannot obtain any information for  M_1,…, M_k-r.

Repeating n' times this procedure,
we can extend this method to the case when we transmit 
(k-r)n' random variables M_1,…, M_(k-r)n' with
r n' additional scramble random numbers L_1,…, L_r n'.
Therefore, the transmission rate of this code is
(k-r)log_2 q'/n_k,r=(k-r)log q.
Since  (M_1,…, M_(k-r)n') can be regarded as 
an element of a vector space over _q',
this operation is a linear code with respect to the finite field _q'.
Therefore, since it satisfies the linearity condition (C1),
the above security analysis over the deterministic attack
guarantees the security over the adaptive and active attack due to Theorem <ref>[
Theorem <ref> can be applied to a linear code with respect to any finite field.
Hence, we do not need to restrict our discussion to linear codes with respect to the finite field _q.].



Here, we make the desired code in the case with general c.
Based on Lemma <ref> with respective k_i and r_i, we choose n_k_i,r_i.
Then, we choose the finite filed _q' with q'=q^n, where 
n:=max_1 ≤ i ≤ cn_k_i,r_i.
So, when we use the channel n:=n' n times,
our transmission can be regarded as n' times transmission on _q'.
Therefore, we can transmit the minimum rate 
log q min_1 ≤ j ≤ c (k_j-r_j).
In this construction, the transmission on each step is given by a linear code over the finite field _q',
the whole operation is also given as a linear code over the finite field _q'.

Therefore, since it satisfies the linearity condition (C1),
Theorem <ref> guarantees the security over the adaptive and active attack.

The calculation complexity of this code can be evaluated as follows.
Node operations on node j are written as k_j × k_j matrix multiplications over _q'.
When we choose a suitable algebraic extension _q',
the multiplication over _q' has complexity O(nlogn).
Therefore, node operations on node j has complexity O(n' k_j^2 nlogn)=O(n k_j^2 logn).

Now, we consider the case that the integer d is not a power q of a prime p.
In this case, we have the following lemma.
LH3
We have 

    lim_n →∞1/nlogmax_q:  prime power{log q | q ≤ d^n}
    = log d.

□

Given a sufficiently large integer n,
we choose a prime power q:=_q:  prime power{log q | q ≤ d^n}.
We treat n uses of a channel as a single transmission of random variable taking values in _q.
Due to Lemma <ref>,
the code given above achieves the transmission rates
log d min_1 ≤ j ≤ c (k_j-r_j) 
when n goes to infinity.




 §.§ Code construction to achieve capacity C[(γ_i)_i]_L,D and C_2,L,D
S42B
Since the capacity C_2,L,D is a special case of C[(γ_i)_i]_L,D with γ_i=0,
we construct only a code to achieve the capacity C[(γ_i)_i]_L,D.
Similar to the previous section, we choose the finite filed _q' with 
q'=q^n and n:=max_1 ≤ i ≤ cn_k_i,r_i,
and
we consider the case of n:=n' n uses of the channel, i.e., 
each edge can transmit up to n' symbols in _q'.
In the following, all random variables are treated as random variables taking values in _q'.
For notational simplicity, we consider the case when
single use of each edge transmits an element of _q'.

To achieve the above purpose, we give a linear code with respect to _q' satisfying the following two conditions (D1) and (D2) by induction with respect to j.
Since the code satisfies the linearity condition (C1),
it is sufficient to consider the deterministic attack.



  (D1)
The code securely transmits the message M of h^j
symbols per single use of channel 
to the j-th node from the source node,
where h^j:=min_1≤ j' ≤ jk_j'-r_j'/k_j'h^j'.
That is, I(M; Y⃗_1,s_1, …, 
Y⃗_j,s_j) =0 for any (s_1, …, s_j)∈ S_1×⋯× S_j.


  (D2)
The j-th node receives secure random number T_j' of h^j-h^j
symbols per single use of channel, which contains
the random numbers generated from the 1st node to the j-1-th node,
where h^j:=k_j-r_j/k_jh^j.
That is,
the j-th node receives secure random number of h^j
symbols per single use of channel, i.e.,
I(M T_j'; Y⃗_1,s_1, …, 
Y⃗_j,s_j) =0 for any (s_1, …, s_j)∈ S_1×⋯× S_j.



Since h^1= h^1= (k_1-r_1),
the desired code with j=1 was constructed in Subsection <ref>.
We show the existence of the desired linear code with respect to _q'
by induction. 
That is, we assume the existence in the case of j-1 with block length n_j-1.
We find that 
h^j  =min
( (k_j-r_j) , k_j-r_j/k_j ( h^j-1 +γ_j )) 
and
h^j  =min
( (k_j-r_j), k_j-r_j/k_j ( h^j-1 +γ_j ),
h^j-1 ) 
for j ≥ 2.
We show the existence of such a code with j 
by classifying three cases.

(1) Case of h^j=h^j=(k_j-r_j):
To achieve the desired task,
the j-1-th node needs to securely transmit the message M of 
(k_j-r_j) symbols per single use of channel
to the j-th node,
which requires scramble random numbers T_j' of
r_j symbols per single use of channel
at the j-1-th node.
Since 
r_j≤h^j-1 +γ_j - (k_j-r_j),
the j-1-th node has sufficient 
scramble random numbers for this purpose.
We divide the scramble random numbers T_j'
into two parts T_j,1' and T_j,2', where
T_j,1' has γ_j symbols per single of channel 
and 
T_j,2' has (r_j -γ_j ) symbols per single of channel. 
Due to the assumption of induction,
the sender securely transmits M and T_j,2'
to the j-1-th node by a linear code with block length n',
where 
the first n' (k_j-r_j) symbols are  M,
the next n' (r_j -γ_j ) symbols are  T_j,2',
and the remaining symbols are fixed to zero.
That is,
I(M T_j,2'; Y⃗_1,s_1, …, 
Y⃗_j-1,s_j-1) =0 for any (s_1, …, s_j-1)∈ S_1×⋯× S_j-1.

Since T_j,1' is composed of n_j-1γ_j symbols
and is independent of other random variables,
we apply the code given in Subsection <ref> 
to the message M and the scramble random number T_j'.
Then, the j-1-th node securely transmits  
the message M to the j-th node by a desired linear code with respect to _q' of  block length n'.
Therefore,
I(M; Y⃗_j,s_j|Y⃗_1,s_1, …, 
Y⃗_j-1,s_j-1) =0 for any (j_1, …, s_j)∈ S_1×⋯× S_j.
Hence,
I(M; Y⃗_1,s_1, …, 
Y⃗_j,s_j) =0 for any (j_1, …, s_j)∈ S_1×⋯× S_j.

(2) Case of h^j=h^j=k_j-r_j/k_j ( h^j-1 +γ_j ):
To achieve the desired task,
the j-1-th node needs to securely transmit the message M of 
h^j=h^j symbols per single use of channel
to the j-th node,
which requires scramble random numbers T_j' of k_j-r_j/k_jh^j 
symbols per single use of channel
at the j-1-th node.
Since k_j-r_j/k_jh^j= r_j/k_j-r_jk_j-r_j/k_j ( h^j-1 +γ_j )  
=h^j-1 +γ_j - 
k_j-r_j/k_j ( h^j-1 +γ_j ),
the j-1-th node has sufficient scramble random numbers 
for the above purpose.
Therefore, similar to the case (1),
we can show the existence of the desired linear code with respect to
_q'.

(3) Case of h^j= h^j-1<h^j:
Since h^j is k_j-r_j or k_j-r_j/k_j ( h^j-1 +γ_j ),
due to the discussion with the above two cases (1) and (2),
the j-th node receives secure random number of h^j
symbols per single use of channel.
To achieve the desired task,
the j-1-th node needs to securely transmit the message M of 
h^j (≤ k_j-r_j) symbols per single use of channel
to the j-th node,
which requires scramble random numbers T_j' of k_j-r_j/k_jh^j 
symbols per single use of channel
at the j-1-th node.
Since r_j/k_j-r_jh^j=r_j/k_j-r_jh^j-1≤γ_j,
the j-1-th node has sufficient scramble random numbers 
for this purpose.
Therefore, similar to the case (1),
we can show the existence of the desired linear code with respect to
_q'.

Therefore, there exists a code that transmits the message with the rate h^c
to the source node from the source node.
Due to the same discussion as Section <ref>
node operations on node j has complexity 
O(n' k_j^2 nlogn)=O(n k_j^2 logn).


We consider how many uses of the channel can achieve the capacity when 
d is a prime power q
and the intermediate node cannot use additional random number, i.e., γ_i=0.
To answer this problem, we consider another proof in this special case.
When we set n':= k_2 ⋯ k_c and n:= n'  ·max_1 ≤ i ≤ cn_k_i,r_i,
we can achieve the capacity in the following way.
That is, our transmission can be regarded as 
n' times transmission on _q', i.e.,
n'  ·max_1 ≤ i ≤ cn_k_i,r_i times transmission of the original channel.

In the following construction, 
we employ k_1 ⋯  k_c random variables.
In this protocol, we securely transmit 
(k_1-r_1) ⋯ (k_i- r_i) k_i+1⋯ k_c random variable to 
the i-th node.
That is,
in the transmission from the i-1-th node to the i-th node,  
we transmit 
(k_1-r_1) ⋯  (k_i-1- r_i-1) r_i k_i+1⋯ k_c random numbers, in which,
(k_1-r_1) ⋯ (k_i- r_i) k_i+1⋯ k_c  random numbers
are securely transmitted and 
the remaining (k_1-r_1) ⋯  (k_i-1- r_i-1) r_i k_i+1⋯ k_c
random variables are treated as scramble random variables.
Such a transmission is possible by applying the method given Subsection <ref>
to the (k_1-r_1) ⋯ (k_i- r_i) k_i+1⋯ k_c random variables,
which are securely transmitted to the i-1-th node.
Using the above recursive construction, 
we can securely transmit ∏_i=1^c(k_i-r_i) random variables.

The single use of the channel between the i-1-th node and the i-th node
can securely transmit (k_i-r_i) random variables.
So, to realize this code, we need to use 
the channel between the i-1-th node and the i-th node 
at (k_1-r_1) ⋯ (k_i- r_i) k_i+1⋯ k_c/k_i-r_i
= (k_1-r_1) ⋯ (k_i-1- r_i-1) k_i+1⋯ k_c times. 
That is, to realize this code, we need to use this relay channel
max_1≤ i ≤ c (k_1-r_1) ⋯ (k_i-1- r_i-1) k_i+1⋯ k_c times. 
Overall, this code can transmit

    min_1≤ i ≤ c∏_i=1^c (k_i-r_i)/(k_1-r_1) ⋯ (k_i-1- r_i-1) k_i+1⋯ k_c
    
    =   min_1 ≤ j ≤ c
    (k_j-r_j) 
    (k_j+1-r_j+1) ⋯ (k_c- r_c) /k_j+1⋯ k_c

variables per single use of the relay channel.
That is, the transmission rate of this code is
log q min_1 ≤ j ≤ c
(k_j-r_j) 
(k_j+1-r_j+1) ⋯ (k_c- r_c) /k_j+1⋯ k_c.
Therefore, we can realize a code to satisfy the conditions (<ref>) and (<ref>) 
for the above given n.
□




 §.§ Scalar linearity
R2
Now, we show that this capacity cannot be attained under the scalar linearity condition. 
That is, we consider the special case to satisfy the following conditions.
The intermediate node cannot use additional random number, i.e., γ_i=0.
We can transmit only a single symbol of a finite filed _q' in each channel.
The coding operations are limited to linear operations over the finite filed _q'.
Since each channel can send only a scalar in _q',
this kind of linearity is called the scalar linearity<cit.>.
To distinguish the condition (C1) from the scalar linearity,
the condition (C1) is often called the vector linearity<cit.>.
Existing studies employ one of these constraints as Table <ref>.
Only a deterministic attack is allowed to the eavesdropper.
Under the above condition, 
the number of symbols transmitted securely is not greater than max (k_1-∑_j=1^c r_j,0), 
which can be shown as follows.

Due to the network structure, the sender can transmit only k symbols M_1, …, M_k
in _q', where 
the k symbols M_1, …, M_k is given as linear functions of the message and the scramble random variable.
First, we fix the linear coding operation on each nodes. 
In the first group of edges, Eve chooses r_1 edges such that 
the information on the r_1 edges are given as
∑_i=1^r_1 t_1,i',i M_i with i'=1,…,r_1
and {t⃗_1,i'} is linearly independent, where t⃗_1,i'=(t_1,i',i)_i=1^k for i'=1,…,r_1.
Similarly, 
when k_1 ≥ r_1+r_2,
in the second group of edges, Eve chooses r_2 edges such that 
the information on the r_2 edges are given as
∑_i=1^r_2 t_2,i',i M_i with i'=1,…,r_1
and {t⃗_1,i'}∪{t⃗_2,i'} is linearly independent, where t⃗_2,i'=(t_2,i',i)_i=1^k for i'=1,…,r_2.
When k_1 < r_1+r_2,
in the second group of edges, Eve chooses k_1-r_1 edges such that 
the information on the k_1-r_1 edges are given as
∑_i=1^k_1-r_1 t_2,i',i M_i with i'=1,…,r_1
and {t⃗_1,i'}∪{t⃗_2,i'} is linearly independent, where t⃗_2,i'=(t_2,i',i)_i=1^k for i'=1,…,k_1-r_1.
When k_1 > r_1+r_2,
we repeat this process up to the c-th group or 
j'-th group satisfying k_1-∑_j=1^j' r_j≤ 0.
Hence, the information with dimension max(k_1, ∑_j=1^c r_j) is leaked to the eavesdropper.
Therefore, the number of symbols transmitted securely is not greater than max (k_1-∑_j=1^c r_j,0).

This fact shows the following effect.
To achieve the capacity even with deterministic attacks,
each channel needs to transmit several symbols in the finite field _q'.
That is, we need to handle the vector space over the finite field _q'.
Furthermore, as a special case,
in the setting given in Section <ref>,
we find that we need to introduce a non-linear code to realize the situation that 
Eve cannot recover the message perfectly with deterministic attack.


We often increase the size q' of finite field _q'
in the scalar linearity while
we fix the size q of finite field _q and increase the dimension of the vector space in the vector linearity.
In the real communication, the data is given as a sequence of 
_2.
In this case, when q=2, the coding operation satisfying  
the vector linearity can be easily implemented
because the vector linearity reflects the structure of the data.
However, the coding operation satisfying  
the scalar linearity cannot be easily implemented
unless q' is a power of 2 because 
the scalar linearity does not reflect the structure of the data.
Only when q' is a power of 2,
the scalar linearity not be easily implemented.
However, even in this case, 
the scalar linearity has worse performance than the vector linearity
due to the above discussion
because the scalar linearity introduces a constraint that does not appear in the vector linearity.
Hence, it is better to impose the vector linearity.




 










§ IMPORTANT LEMMAS
S7
Here, for the latter discussion, we prepare important lemmas.
We denote the set {1, …, k} by [k],
and denote the collection of subsets S⊂ [k] with cardinality 
r by [k]  r.


Now, we consider the random variables
X,Y⃗_1, …, Y⃗_k.
For any subset S ⊂ [k], we denote the tuple of random variables
(Y⃗_s)_s ∈ S by Y⃗_S.

We can show the following two lemmas.

LH10
We have

    ∑_S ∈ [k]  r
    H(Y⃗_S| X)
    ≥    k-1  r-1
    H(Y⃗_[k]| X)
    
    
    =   r/k k  k-r
    H(Y⃗_[k]| X).

□

Lemma <ref> is known as Han's inequality <cit.>, and 
it can be shown by using Baranyai's Theorem <cit.>.
However, this paper shows Lemma <ref> by using our invented lemma, Lemma <ref>.
□


 Lemma-1
Let S_h be a collection of subsets of [k].
When any element of [k] is contained in exactly h members of S_h,
we have

    eq:Lemma-11∑_S ∈ S_h H(Y⃗_S|X) ≥ h H(Y⃗_[k]|X).

□

Lemma <ref>
We prove the lemma by induction in h. When h=1, it is trivial. 
Assume that the lemma holds for h-1. 
We pick a subcollection S':={S_1,S_2, …,S_f}⊂ S_h
such that ∪_i=1^f S_i= [k].
We define S_i' :=S _i ∩ (∪_j=1^i-1S_j) and
S_h-1=( S_h∖ S') ∪{S_2', …, S_f'}.

We can see that any element of [k] is contained in exactly h-1 members of S_h-1, from the following lines. 
Assume that an element a ∈ [k] is contained in exactly b members of 
S'.
Notice that a is contained by S_i, for each particular i, if and only if it is contained by exactly one of S_i∖[∪_j=1^i-1S_j] and S_i'. 
For any element a∈ [k], there uniquely exists an integer i such that
a∈ S_i∖[∪_j=1^i-1S_j].
So, the element a is contained in exactly b-1 members of 
{S_2', …, S_f'}. 
Therefore, 
the element a is contained in exactly h-b+(b-1)=h-1 members of 
S_h-1=( S_h∖ S') ∪{S_2', …, S_f'}.



Therefore,

    ∑_S ∈ S_h H(Y⃗_S|X) 
    =
    ∑_S ∈ S_h∖ S' H(Y⃗_S|X) 
    +
    ∑_i=1^f H(Y⃗_S_i|X) 
    
    =   ∑_S ∈ S_h∖ S' H(Y⃗_S|X) 
    +
    ∑_i=1^f H( Y⃗_S_i'|X) 
       +
    ∑_i=1^f H(Y⃗_S_i ∖ S_i'|   Y⃗_S_i'X) 
    (a)≥   ∑_S ∈ S_h-1 H(Y⃗_S|X) 
    +
    ∑_i=1^f H(Y⃗_S_i ∖ (∪_j=1^i-1S_j)|   Y⃗_∪_j=1^i-1S_jX) 
    (b)≥    
    (h-1) H(Y⃗_[k]|X)+  H(Y⃗_[k]|X)
    =h H(Y⃗_[k]|X),

where (a) follows from the relation 
S_i'⊂∪_j=1^i-1S_j
and (b)  follows from 
the relation ∪_i=1^f S_i=[k]
and the induction hypothesis, the fact that
∑_S ∈ S_h-1 H(Y⃗_S|X) ≥ (h-1) H(Y⃗_[k]|X).


Lemma <ref>
Now, we show Lemma <ref> by using Lemma <ref>.
Any element a ∈ [k] is contained in exactly k-1  r-1 members of 
[k]  r.
So, we apply Lemma <ref> 
to the case with S_h= [k]  r 
and h=k-1  r-1.
Hence, we have Eq. (<ref>).





§ HOMOGENEOUS MULTICAST RELAY NETWORK
 S8


 §.§ Formulation and capacity regions
multi1
Next, 
as a special case of Example <ref>, 
we consider the homogeneous multicast relay network (Fig. 4) defined as follows.
This network has one source node and b terminal nodes.
It has c-1 groups of intermediate nodes.
The i-th group has b_i intermediate nodes, and
the set of b terminal nodes is regarded as the c-th group,
and the source node is regarded as the 0-th group.
So, the numbers b_0 and b_c are defined to be 1 and b.
Each node of the i-the group is expressed as n(i,1), …, n(i,b_i).

Each node of the i-1-th group is connected to every node of the i-th group with k_i edges.
That is, there are b_i-1b_i k_i edges from the i-1-th group to the i-th group.
For each node of the i-th group,
Eve is assumed to wiretap r_i edges among b_i-1 k_i edges connected to the node of the i-th group
from nodes of the i-1-th group.
That is, Eve wiretaps r_i b_i edges among b_i-1b_i k_i edges
between the i-1-th group and the i-th group. 




Then, we have the following theorem for the no-randomness capacity region.
TH10

    C_2= 
     C_2,L= 
     C_2,D= 
     C_2,L,D= 
     C_2,AC= 
     C_2,L,AC
    
    =   {(R_1, …, R_b) | ∑_i'=1^b R_i'≤ A_1,
    R_i ≤ A_2  for  i=1,…, b }e5-6T

where

    A_1:=   (log d) min_1 ≤ j ≤ c((b_j-1 k_j -r_j) b_j
       ·(b_j k_j+1  -r_j+1) ⋯ (b_c-1k_c - r_c) /b_j k_j+1⋯ b_c-1 k_c  ),5-10A
    
    A_2:=   
    (log d )(b_c-1 k_c -r_c) .5-10B

□

For the full-randomness capacity region, we have the following theorems.
TH8
Assume that c=2 and r_2/k_2 is an integer.
Then, we have

    C_1= C_1,L=  C_2= C_2,L
    =
     C_1,D= C_1,L,D=  C_2,D
    
    =    C_2,L,D
    =
     C_1,AC= C_1,L,AC=  C_2,AC= C_2,L,AC.

□


TH9
Assume that c=3 and r_3/k_3 is an integer.

    C_1= C_1,L
    = C_1,D= C_1,L,D
    = C_1,AC= C_1,L,AC
    
    =    {(R_1, …, R_b) | ∑_i'=1^b R_i'≤ A_3,
    R_i ≤ A_2  for  i=1,…, b }e5-8,

where

    A_3
    
    :=    (log d) 
    min( (k_1 -r_1) b_1,
       min_2 ≤ j ≤ 3
    (b_j-1 k_j -r_j) b_j 
    
    (b_j k_j+1  -r_j+1) ⋯ (b_c-1k_c - r_c) /b_j k_j+1⋯ b_c-1 k_c  
    ) 
    
    =   (log d) 
    min( (k_1 -r_1) b_1,
    (b_1 k_2 -r_2) b_2
    b_2k_3 - r_3 /b_2 k_3  ,
    
       
    (b_2 k_3 -r_3) b_3
    ) .

□




 §.§ Converse part for Theorem <ref>
S4-2
We consider the j-th group as one intermediate node,
and the set of the b terminal nodes as one terminal node,
which yields a relay network.
Then, applying the relation (<ref>) to this relay network, 
we obtain the condition ∑_i'=1^b R_i'≤ A_1.

Next, we consider the j-th group as one intermediate node,
and focus only on the i-th terminal nodes,
which yields another relay network.
Then, applying the relation (<ref>) to this relay network, 
we obtain the other condition R_i≤ A_2.




 §.§ Code construction for Theorem <ref>
S4-3
Here, by induction, we make a linear code to achieve the RHS of (<ref>) when d is a prime power q.
In the general case, we can construct the desired linear code by using the method in Lemma <ref>.
The liner code construction with c=1 is given from the code given in Subsection <ref>.
We construct the desired linear code by induction with respect to the number c.

Assume that n is a multiple of n:=max_1≤ i ≤ cn_b_i-1k_i ,r_i.
Now, we assume that the source node can securely transmit 
∑_i'=1^b N_i' letters to each intermediate node in the c-1-th group
by n use of the channel.
When N_i'≤ n k_c, under this assumption, 
we can transmit N_i' b_c-1 -n r_c letters from the source node to the i'-th terminal node by n use of the channel as follows.

Such a code will be called Code (N_1 ,…, N_b).

For j_2= 1, …, b, j_1= 1, …, k_c,
we denote 
the ∑_i'=1^j_2-1N_i' + j_1-th securely transmitted letter to j-th intermediate node in the c-1-th group
by X_j_2, j_1 + j N_i'.
Then, for a given j_2=1, …, b, the source node
prepares messages 
M_j_2, j_3 for j_3=1, … ,N_j_2 b_c-1 -n r_c
and scramble random numbers
L_j_2, j_3 for j_3=1, … , n r_c.
Then, the source node
makes conversion from
the pair of M⃗_j_2 and L⃗_j_2 to X⃗_j_2
such that 
there is no information leakage for 
M⃗_j_2 even when any nr_c letters of X⃗_j_2 are eavesdropped.
Such a code can be constructed by using the discussion in 
Subsection <ref>.


Now, we employ the assumption of induction.
So, there exist an integer n and a code Φ_n with block-length n
such that the rate tuple is 
(A_4/b_c-1, …, A_4/b_c-1), where

    A_4:=    
    min_1 ≤ j ≤ c-1((b_j-1 k_j -r_j) b_j 
       ·(b_j k_j+1  -r_j+1) ⋯ (b_c-2k_c-1 - r_c-1) /b_j k_j+1⋯ b_c-2 k_c-1) .
    5-10C

Using this fact, we show the desired statement by classifying two cases.

(1) Case of A_4/b_c-1≥  k_c b_c:
In this case, the minimum in (<ref>) is realized with j=c, which implies A_1=b_c A_2.

To attain the RHS of (<ref>),
it is sufficient to give a code with the rate tuple 
( A_2, …, A_2)=
( log d (b_c-1 k_c-r_c), …, log d (b_c-1 k_c-r_c)).
The required secure transmission from the source node to the c-1-th group
is possible as follows.
Combining the assumption of induction and Code 
(n k_c ,…, n k_c).
We obtain a linear code with the rate tuple 
( log d (b_c-1 k_c-r_c), …, log d (b_c-1 k_c-r_c)).


(2) Case of A_4/b_c-1<  k_c b_c:
We have A_1= A_4  b_c-1k_c - r_c/b_c-1 k_c.
To attain the RHS of (<ref>),
it is sufficient to give a code with the rate tuple 
( R_1, …, R_b) satisfying conditions
∑_i'=1^b R_i'≤ A_1 and R_i ≤ A_2.
Due to the assumption of induction,
the source node can securely transmit 
n A_4/b_c-1 letters to each node in the c-1-th group.
Now, we choose n such that n A_4/b_c-1b is an integer,
n is a multiple of n,
and n R_i' is integer for i'=1, …, b.
Therefore, using Code (n R_1, …, n R_b),
we obtain a linear code, in which, 



 the source node can securely transmit to the i'-th terminal 
with rate R_i'.
Since this linear code construction requires only the conditions
∑_i'=1^b R_i'≤ A_1 and R_i ≤ A_2,
the RHS of (<ref>) is attained.

Due to the same discussion as Section <ref>
node operations on node of i-th group has complexity 
O(n k_i^2 logn).




 §.§ Proof of Theorem <ref>
SS7
To show Theorem <ref>, it is sufficient to show the converse part, i.e.,
C_1,D⊂ C_2,D.
The i-th intermediate node can transmit information
of k_2 symbols per single use of channel to the j-th terminal node.
In order that the j-th terminal node recovers the original message M_j,
the j-th terminal node needs to recover 
a part of information M_i,j with respect to the original message that
is determined by the information received by the i-th intermediate node.
That is, collecting the variables M_1,j, …, M_b_1,j,
the j-th terminal node recovers M_j.
We choose an injective function s from {1, …, r_2/k_2} to
{1, …, b_2}.
Now, we consider the case that Eve wiretaps all the channels 
from the s(i)-th intermediate node to the j-th terminal node
for i=1,…, r_2/k_2.
When the s(i)-th terminal node introduces scramble random variables L_s(i),j in the channel to the j-th terminal node,
the j-th terminal node needs to recover M_s(i),j.
In this case, Eve also recovers M_s(i),j.
Then, there is no merit to introduce the scramble random variables L_s(i),j in this channel.
When the i'-th terminal node introduces scramble random variables L_i',j in the channel to the j-th terminal node
for i' ∈{1, …, b_2}∖{s(1), …, s(r_2/k_2)},
the j-th terminal node needs to recover M_i',j.
In this case, Eve has no access to this channel.
Hence, there is no need to introduce the scramble random variables L_i',j in this channel.
Therefore, considering this special case, there is no advantage to introduce 
scramble random variables in the intermediate nodes.
That is, any code can be reduced to a code with the no-randomness condition (C2).



 §.§ Proof of Theorem <ref>

Due to the discussion in Subsection <ref>,
the scramble random number introduced in intermediate nodes in the 2nd group does not work.
Hence, we obtain the converse part, i.e., 
C_D
⊂{(R_1, …, R_b) | ∑_i'=1^b R_i'≤ A_3,
R_i ≤ A_2  for  i=1,…, b }.


Next, we construct a code to achieve the capacity region.
Each intermediate node in the first group can securely transmit 
to each terminal node
with the following capacity region:

    {(R_1, …, R_b) | ∑_i'=1^b R_i'≤A_5/b_1,
    R_i ≤A_2/b_1 for  i=1,…, b }e5-6

with

    A_5
    
    :=    (log d) 
    min( 
    (b_1 k_2 -r_2) b_2
    b_2k_3 - r_3 /b_2 k_3  ,
    
     (b_2 k_3 -r_3) b_3
    ) .


Now, the source node can securely transmit information to each intermediate node in the first group with the rate
(log d) (k_1 -r_1).
Combining these discussions, 
the source node can securely transmit information to each terminal node
via a specific intermediate node in the first group
with the following capacity region:

    {(R_1, …, R_b) | ∑_i'=1^b R_i'≤A_3/b_1,
    R_i ≤A_2/b_1 for  i=1,…, b }

because A_3= min ( (log d) (k_1 -r_1) b_1,A_5).
Summing up the above region with respect to intermediate nodes in the first group,
we find 
the relation C_D,L⊃{(R_1, …, R_b) | ∑_i'=1^b R_i'≤ A_3,
R_i ≤ A_2  for  i=1,…, b }, which is the direct part.




§ HOMOGENEOUS MULTIPLE MULTICAST RELAY NETWORK
 S9


 §.§ Formulation and capacity regions
SS2-1
Next, as a special case of Example <ref>, 
we consider the homogeneous multiple multicast relay network (Fig. 5) defined as follows.
This network has a source nodes and b terminal nodes.
It has c-1 groups of intermediate nodes.
The i-th group has b_i intermediate nodes, and
the set of b terminal nodes is regarded as the c-th group,
and the source node is regarded as the 0-th group.
So, the numbers b_0 and b_c are defined to be a and b.
Each node of the i-the group is expressed as n(i,1), …, n(i,b_i).

Each source code is connected to each intermediate node in the first group with k_1 edges.
For i ≥ 2,
each node of the i-1-th group is connected to every node of the i-th group with k_i edges.
That is, there are b_i-1b_i k_i edges from the i-1-th group to the i-th group.
For each node of the i-th group,
Eve is assumed to wiretap r_1 edges among k_1 edges 
between each source node and each intermediate node in the first group.
Totally, Eve wiretaps ab_1 r_1 edges among ab_1 k_1 edges between the 0-th group and the first group.
For i ≥ 2, Eve is assumed to wiretap r_i edges among b_i-1 k_i edges connected to the node of the i-th group from nodes of the i-1-th group.
That is, Eve wiretaps r_i b_i edges among b_i-1b_i k_i edges
between the i-1-th group and the i-th group.






Then, we have the following theorem for the no-randomness capacity region.
TH11

    C_2= 
     C_2,L= 
     C_2,D= 
     C_2,L,D= 
     C_2,AC= 
     C_2,L,AC
    
    =   {(R_i,j)_1≤ i ≤ a, 1≤ j ≤ b| 
    [     ∑_i',j' R_i',j'≤ B_1,;         ∑_j' R_i,j'≤ B_2,;           ∑_i'R_i',j≤ B_3; for  i=1,…, a ,  j=1,…, b ].}, e5-7T

where

    B_1
    
    
    :=   (log d) 
    min(
     a (k_1 -r_1) b_1
    (b_1 k_2-r_2) ⋯ (b_c-1k_c - r_c) /b_1 k_2⋯ b_c-1 k_c   ,
    
       min_2 ≤ j ≤ c
    (b_j-1 k_j -r_j) b_j
    (b_j k_j+1-r_j+1) ⋯ (b_c-1k_c - r_c) /b_j k_j+1⋯ b_c-1 k_c  ),
    5-10X
       B_2
    
    :=   (log d) 
    min(
     (k_1 -r_1) b_1
    (b_1 k_2  -r_2) ⋯ (b_c-1k_c - r_c) /b_1 k_2⋯ b_c-1 k_c   ,
    
       min_2 ≤ j ≤ c
    (b_j-1 k_j -r_j) b_j
    (b_j k_j+1 -r_j+1) ⋯ (b_c-1k_c - r_c) /b_j k_j+1⋯ b_c-1 k_c  )
    5-11X,

and

    B_3
    :=
    (log d )(b_c-1 k_c -r_c) .5-10T

□

For the full-randomness capacity region, we have the following theorems.
TH18
Assume that c=2 and r_2/k_2 is an integer.
Then, we have

    C_1=  C_1,L=
     C_2=  C_2,L
    = C_1,D=  C_1,L,D=
     C_2,D
    
    =    C_2,L,D
    = C_1,AC=  C_1,L,AC=
     C_2,AC=  C_2,L,AC.

□


TH19
Assume that c=3 and r_3/k_3 is an integer.

    C_1=  C_1,L= 
     C_1,D=  C_1,L,D
    =
     C_1,AC=  C_1,L,AC
    
    =   {(R_i,j)_1≤ i ≤ a, 1≤ j ≤ b| 
    [     ∑_i',j' R_i',j'≤ B_4,;         ∑_j' R_i,j'≤ B_5,;          ∑_i' R_i',j≤ B_3; for  i=1,…, a ,  j=1,…, b ]. }e5-8X,

where

    B_4 
    
    :=    (log d) 
    min( a( k_1 -r_1) b_1,
    
       min_2 ≤ j ≤ 3
    (b_j-1 k_j -r_j) b_j
    (b_j k_j+1  -r_j+1) ⋯ (b_c-1k_c - r_c) /b_j k_j+1⋯ b_c-1 k_c  ) 
    
    =    (log d) 
    min( a( k_1 -r_1) b_1,
    
       (b_1 k_2 -r_2) b_2
    b_2k_3 - r_3 /b_2 k_3  ,
    (b_2 k_3 -r_3) b_3
    ), 
       B_5 
    
    :=    (log d) 
    min( (k_1 -r_1) b_1,
    
       min_2 ≤ j ≤ 3
    (b_j-1 k_j -r_j) b_j
    (b_j k_j+1  -r_j+1) ⋯ (b_c-1k_c - r_c) /b_j k_j+1⋯ b_c-1 k_c  ) 
    
    =    (log d) 
    min( (k_1 -r_1) b_1,
        (b_1 k_2 -r_2) b_2
    b_2k_3 - r_3 /b_2 k_3  ,
    (b_2 k_3 -r_3) b_3
    ) .

□




 §.§ Converse part for Theorem <ref>
SS2-2
We consider the j-th group as one intermediate node,
and the set of the b terminal nodes and
the set of the a source nodes as one terminal node and 
one source node, respectively,
which yields a relay network.
Then, applying the relation (<ref>) to this relay network, 
we obtain the condition ∑_i',j'^b R_i',j'≤ B_1.

Applying the discussion in Subsection <ref> to the network
from the i-th source node to the j-th group,
we obtain the condition ∑_j'^b R_i,j'≤ B_2.
Similarly, applying the discussion in Subsection <ref> to the network
from the first group to the j-th terminal node,
we obtain the condition ∑_i'R_i',j≤ B_3.






 §.§ Code construction for Theorem <ref>
SS2-3
Here, by induction, we make a code to achieve the RHS of (<ref>) when d is a prime power q.
In the general case, we can construct the desired code by using the method in Lemma <ref>.
The code construction with c=1 is given from the code given in Subsection <ref>.
We construct the desired code by induction with respect to the number c.

Assume that n is a multiple of n:=max_1≤ i ≤ cn_b_i-1k_i ,r_i.
We choose a rate tuple ( R_i,j)_i,j satisfying the condition in the RHS of (<ref>).
As mentioned in the proof of Theorem <ref>,
when we can securely transmit an unlimited number of messages from the source node to
all of intermediate nodes in the c-1-th group,
using the code with block-length n constructed in Subsection <ref>,
we can transmit n(b_c-1 k_c- r_c) letters 
from the source node to each terminal node, in which,
the source node securely transmits n k_c letters to each intermediate node in the c-1-th group.
Therefore, the rate tuple ( R_i,j)_i,j can be realized by secure transmission with the rate 
R_i,j':=  b_c-1 k_c /b_c-1 k_c -r_c ∑_j R_i,j 
from the i-th source node to 
the j-th intermediate node in the c-1-th group.



The assumption of induction guarantees that the rate tuple ( R_i,j')_i,j is attainable in the network from the first group to the c-1-th group
because the rate tuple ( R_i,j')_i,j satisfies the conditions
∑_i',j' R_i',j'' ≤ B_1',
∑_j' R_i,j'' ≤ B_2',
∑_i'R_i',j' ≤ B_3' for i=1,…, a ,  j=1,…, b_c-1,
where

    B_1':=   (log d) min_1 ≤ j ≤ c-1(
    (b_j-1 k_j -r_j) b_j
       ·(b_j k_j+1  -r_j+1) ⋯ (b_c-2k_c-1 - r_c-1) /b_j k_j+1⋯ b_c-2 k_c-1),
    
    B_2':=   (log d) 
       ·min(
     (k_1 -r_1) b_1
    (b_1 k_2  -r_2) ⋯ (b_c-2k_c-1 - r_c-1) /b_1 k_2⋯ b_c-2 k_c-1 ,
    
       min_2 ≤ j ≤ c-1(
    (b_j-1 k_j -r_j) b_j 
       ·(b_j k_j+1  -r_j+1) ⋯ (b_c-2k_c-1 - r_c-1) /b_j k_j+1⋯ b_c-2 k_c-1)
    ),
    
    
    B_3':=    
    (log d )(b_c-2 k_c-1 -r_c-1) .

Therefore, the rate tuple ( R_i,j)_i,j is achievable.
Due to the same discussion as Section <ref>
node operations on node of i-th group has complexity 
O(n k_i^2 logn).




 §.§ Proof of Theorem <ref>
SS17
To show Theorem <ref>, it is sufficient to show the converse part
C_1⊂ C_2.
As shown in the proof of Theorem <ref>,
any code can be reduced to a code with the no-randomness condition (C2).
Hence, we obtain C_1⊂ C_2.




 §.§ Proof of Theorem <ref>

Similar to the proof of Theorem <ref>,
the scramble random number introduced in intermediate nodes in the 2nd group do not work.
Hence, we obtain the converse part.

Next, we construct a code to achieve the capacity region.
Each source node can securely transmit information to each intermediate node in the first group with the rate
(log d) (k_1 -r_1).
Combining this code and the codes given in (<ref>) from each intermediate node in the first group to 
 each terminal node,
the set of source nodes can securely transmit information to each terminal node
via a specific intermediate node in the first group
with the following capacity region:

    {(R_i,j)_1≤ i ≤ a, 1≤ j ≤ b| 
    [  ∑_i',j' R_i',j'≤B_4/b_1,;      ∑_j' R_i,j'≤B_5/b_1,;       ∑_i' R_i',j≤B_3/b_1; for  i=1,…, a ,  j=1,…, b ].}

because B_3=A_3,
B_4= min ( (log d) a (k_1 -r_1) b_1,A_5)
and B_5= min ( (log d) (k_1 -r_1) b_1,A_5).
Summing up the above region with respect to intermediate nodes in the first group,
we find that the rate region defined in the RHS of (<ref>).

0


§ AN EXTENSION
 sec:ex
By investigation of the proofs, one can easily find that the assumption that “a wiretapper may choose an arbitrary subsets W_j ∈[k_j]  r_j..." is not essential, and [k_j]  r_j can be replaced by any collection of subsets in [k_j] satisfying the condition of Lemma <ref>. Namely instead of assumption 

∙ “ a wiretapper may choose an arbitrary subsets W_j ∈[k_j]  r_j and wiretaps the outputs of channels e_j(i) ∈ W_j, for j=0,1,2,…, l, simultaneously."

we assume that 

∙  “a wiretapper may choose an arbitrary subsets W_j ∈ W_j and wiretaps the outputs of channels e_j(i) ∈ W_j, for j=0,1,2,…, k, simultaneously for all collection of subsets of [k_j] such that such that each member of [k_j] 

-exactly contained in h_j members of W_j (which will addressed as '=-extension' below) or

-contained in at least h_j members of W_j (which will addressed as `≥ extension' below)."


Denote by | W|:=𝔴_j, then we have

For =-extension and ≥-extension, we have that

    eq-ext
    I_W ≥ R- min_j ∏_v=0^j-1𝔴_v-h_v/𝔴_vmin_W_j ∈ W_j∑_i ∈ W_j^cs_j(i).


By replacing [k_j]  r_j by W_j, one may prove the =-extension in the same way as before. One may reduce ≥-extension to =-extension by deleting “superfluous points" from members of W_j properly, which only makes the communication “safer". Thus ≥-extension  follows.
(Shifting wiretapping)
For 𝔟_i < 𝔴_i, by replacing [k_i] by {0,1, …,k_i-1},  we assume that W_i:={{a⊕ b: b=0,1, …𝔟_i}:a=0,1,…, k_i}, where ⊕ is sum (mod 𝔟_i). Then we have an alternative model.
□




§ CONCLUSION

We have studied active and adaptive attacks,
and have investigated whether an adaptive attack improves Eve's ability.
As our result, we have shown that 
an adaptive attack improves Eve's ability when our code is a linear code.
However, when our code is not a linear code,
we have found an example where an adaptive attack improves Eve's ability
in Section <ref>.
Any linear code cannot realize the performance of the non-linear code given there under the setting of Section <ref>
when Eve is allowed to a deterministic attack.
Hence, the improvement by the adaptive attack is essential in this setting.

Next, we consider several types of network, in which there is restriction for randomness in the intermediate nodes.
This kind of restriction is crucial in the secure network because
randomness is required to realize the secrecy.
In the latter part of this paper, we have addressed various types of relay networks 
in the asymptotic setting, where we employ liner codes, i.e., these codes are given as vector spaces over a finite field.
In Section <ref>, we have considered a typical type of unicast relay network 
and have derived the capacity under various restrictions for randomness in the intermediate nodes.
To show the converse part, we have shown a notable lemma in Section <ref>.
Our proof of the direct part follows from a lemma related to wiretap channel II.
Also, in Subsection <ref>, 
we have shown that the code does not work when it is given as a scalar of a finite field.
Further, we have proceeded to more complicated networks, e.g., 
 a typical type of multicast relay network and  a typical type of multiple multicast relay network.
 Since their asymptotic performances are characterized as their capacity regions,
in Sections <ref> and <ref>,
we have derived them under the condition that the intermediate nodes have no scramble random number by generalizing the method used in Section <ref>.  


While our asymptotic results are limited to special networks,
the minimum cut theorem does not work in these networks.
Hence, our codes suggest a general theory for networks whose capacity cannot be shown by the minimum cut theorem.
It is an interesting future study to establish such a theory.
As explained in Section <ref>,
when the spaces of the intermediate nodes and/or the budget are limited,
it might be better to avoid to equip scramble random variables in the intermediate nodes. 
The study with this constraint is much desired for the practical viewpoint.






§ ACKNOWLEDGMENTS

The authors are very grateful to Dr. Wangmei Guo
for her helpful discussions and her hospitality during the authors' stay in Xidian University.
They also are grateful to Mr. Seunghoan Song for helpful comments for Appendix and Lemma 4.
The authors thank a reviewer of the previous version of this paper for 
explaining the network code given in Fig. <ref>.
They are also grateful to the referees of this paper to their helpful comments.





§ PROOF OF LEMMA <REF>
A1
When k=r, it is trivial. When k=r+1, we do not need to make any algebraic extension
because it is sufficient to choose r vectors v_1, …, v_r ∈_q^k 
such that v_i,j with j=1, …, r is δ_i,j
and v_i,r+1 is 1.

Now, we consider the case when k> r+1.

When q>p, we choose element e_1, …, e_t such that
_q is given as _p[e_1, …, e_t].
When t < k-2, we make further algebraic extension 
_p[e_1, …, e_k-2] by adding elements e_t+1, …, e_k-2.
Now, we denote 1 by e_0.
Then, we choose r vectors v_1, …, v_r ∈_p[e_1, …, e_k-2]^k by

    v_i,j:=
    {[          δ_i,j    when  j ≤ r;              1  when  j = r+1;      e_i+j-r-2 when  j > r+1. ].

 
We can show that the r vectors v_1, …, v_r 
satisfy the required condition as follows.
Choose the function s such that s(1)< …< s(r).
It is sufficient to show that the vector 
(v_1,s(r), …, v_r,s(r))
cannot be written as a linear combination of 
(v_1,s(1), …, v_r,s(1)), …,
(v_1,s(r-1), …, v_r,s(r-1)).
When s(r)=r or r+1, it is trivial.
So, we show the case when s(r)>r+1.
Since all entries of v_i,s(j) belong to _p[e_1, …, e_s(r)-2],
we choose coefficients α_1, …, α_r∈_p[e_1, …, e_s(r)-2]
such that ∑_i=1^r α_i v_j,s(i)=0 for j=1,…, r.
We show the desired statement by assuming α_r=1.

For i=1, …, r-1, we divide the coefficient α_i into r parts, i.e., 
we choose α_i,j∈_p[e_1, …, e_s(r)+j-r-2]∖_p[e_1, …, e_s(r)+j-r-3] as 
α_i=∑_j=1^r α_i,j.
Since we have ∑_i=1^r-1α_i v_j,s(i)  = -  e_s(r)+j-r-2∈_p[e_1, …, e_s(r)+j-r-2] for j=1,…, r,
we have
∑_i=1^r-1α_i,j' v_j,s(i)  =0
for j' >j because α_i,j'∉_p[e_1, …, e_s(r)+j-r-2]
and v_j,s(i) ∈_p[e_1, …, e_s(r)+j-r-2].

That is, the vectors 
α(j'):= (α_1,j', …, α_r-1,j')^T for j'=1, …, r
and
β(j):= (v_j, s(1) , …, v_j,s(r-1) )^T for j=1, …, r-1
satisfy the conditions:

    (α(j'),β(j))    =0  for  j'>j 
    ∑_j'=1^j (α(j'),β(j))    =-e_s(r)+j-r-2.

Since ∑_j'=1^j-1 (α(j'),β(j)) ∈_p[e_1, …, e_s(r)+j-r-3],
and -e_s(r)+j-r-2 (≠ 0) ∉_p[e_1, …, e_s(r)+j-r-3],
we have (α(j),β(j))≠ 0  for j=1,…, r-1. 
These properties are summarized as 

    (α(i),β(j))
    {[          = 0  when  i > j;         =≠ 0 when  i =j . ].

The property of triangle matrix implies that 
β(1), …, β(r-1) 
are linearly independent.
Since (α(r),β(j))=0 for j=1, …, r-1,
and α(r) is a r-1-dimensional vector,
we have α(r)=0, which implies 
 e_s(r)-2=0. So, we obtain contradiction.





1
Cai2002
N. Cai and R. Yeung, “Secure network coding,” 
Proc. 2002 IEEE Int. Symp. Information Theory (ISIT 2002), Lausanne, Swiss, July 2002, p. 323.

CY
N. Cai and R. W. Yeung,
“Secure Network Coding on a Wiretap Network,”
IEEE Trans. Inform. Theory, 
vol. 57, no. 1, 424 – 435 (2011).

YN
R. W. Yeung and N. Cai, 
“On the optimality of a construction of secure network codes,” 
Proc. 2008 IEEE Int. Symp. Information Theory (ISIT 2008), 
Toronto, ON, Canada, Jul. 6 – 11, 2008, pp. 166 – 170.


CG
T. Chan and A. Grant, 
“Capacity bounds for secure network coding,” 
Proc. Australian Commun. Theory Workshop, 
Christchurch, NZ, Jan. 30 – Feb. 1, 2008, pp. 95 – 100.


RSS
S. El Rouayheb, E. Soljanin, and A. Sprintson, 
“Secure network coding for wiretap, networks of type II,” 
IEEE Trans. Inform. Theory, 
vol. 58, no. 3, pp. 1361 – 1371 (2012).                      


FMSS
J. Feldman, T. Malkin, C. Stein, and R. A. Servedio, 
“On the capacity of secure network coding,” 
Proc. 42nd Annu. Allerton Conf. Commun. Control Comput., Monticello, IL, Sep. 29 – Oct. 1, 2004.


NYZ
C.-K. Ngai, R. W. Yeung, and Z. Zhang, 
“Network generalized hamming weight,” 
Proc. Workshop Network Coding Theory Appl., 
Lausanne, Switzerland, 2009, pp. 48 – 53.  


HY
K. Harada and H. Yamamoto, 
“Strongly secure linear network coding,” 
IEICE Trans. Fund., 
vol. E91-A, no. 10, pp. 2720 – 2728 (2008).


Cai
N. Cai, “Valuable messages and random outputs of channels in linear
network coding,” 
Proc. 2009 IEEE Int. Symp. Information Theory (ISIT 2009), 
Seoul, Korea, Jun. 28 – Jul. 3, 2009, pp. 413 – 417. 

CC
N. Cai and T. Chan,
“Theory of Secure Network Coding,”
Proceedings of the IEEE, vol. 99, no. 3, 421 – 437 (2011).

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



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

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

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., vol. 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).

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, pp. 1978 – 1987 (2014).

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;

arXiv:1703.00723 (2017).

Channel
M. Hayashi, 
“Discrimination of two channels by adaptive methods and its application to quantum system,” 
IEEE Trans. Inform. Theory, 
vol.55, no. 8, pp. 3807 – 3820 (2009).

HG
M. Herrero-Collantes and J. C. Garcia-Escartin
“Quantum Random Number Generators,”
Rev. Mod. Phys., vol. 89, 015004 (2017).

HZ
M. Hayashi and H. Zhu
“Secure uniform random number extraction via incoherent strategies,”
Phys. Rev. A, 97, 012302 (2018).

CY-07
N. Cai and R. W. Yeung,
“A Security Condition for Multi-Source Linear Network Coding,”
Proc. 2007 IEEE Int. Symp. Information Theory (ISIT 2007),  
Nice, France, June 2007, p. 561 – 565.

CHK-10
T. Cui, T. Ho, and J. Kliewer,
“Achievable strategies for general secure network coding”,
Information Theory and Applications Workshop (ITA), 2010.

CHK-13
T. Cui, T. Ho, and J. Kliewer,
“On Secure Network Coding With Nonuniform or Restricted Wiretap Sets”,
IEEE Trans. Inform. Theory, 
vol. 59, pp. 166 – 176, (2013).

Dougherty
R. Dougherty, C. Freiling, and K. Zeger,
“Insufficiency of Linear Coding in Network Information Flow,”
IEEE Trans. Inform. Theory, 
vol. 51, no. 8, 2745 – 2759 (2005).

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

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

Ozarow
L. H. Ozarow and A. D. Wyner,
“Wire-tap channel II,” 
AT& T Bell Labs. Tech. J., vol. 63, pp. 2135 – 2157, 1984.

Han
T. S. Han, 
“Nonnegative entropy measures of multivariate symmetric
correlations,” 
Inform. Contr., vol. 36, no. 2, pp. 133 – 156, 1978.

ACLY
R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung,
“Network Information Flow,”
IEEE Trans. Inform. Theory, 
vol. 46, no. 4, 1204 – 1216, (2000).

LYC
S.-Y. R. Li, R. W. Yeung, and N. Cai, 
“Linear network coding,” 
IEEE Trans. Inform. Theory, 
vol. 49, pp. 371 – 381, 2003.

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

Bara
Z. Baranyai, “On the factorization of the complete uniform hypergraph,” 
Colloquia Mathematica Societatis, János Bolyai 10. Infinite and finite sets, Keszthely,
Hungary, 91–108, (eds.: A. Hajnal, R. Rado, V.T. Sós), 1973.

SHIOJI
E. Shioji, R. Matsumoto, and T. Uyematsu, 
“Vulnerability of MRD-Code-based Universal Secure Network Coding against Stronger Eavesdroppers,” 
IEICE Trans. Fundamentals, vol.E93-A, no.11, pp. 2026 – 2033 (2010).

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 Int. Symp. Information Theory (ISIT 2015), 
Hong Kong, China, Jun. 14 – 19, 2015, pp. 2530 – 2534.

 Bhattad
K. Bhattad, and  K. R. Narayanan,  “Weakly secure network coding,”
1st Workshop on Network Coding, Theory, and App., April 2005;
DOI: 10.1109/ITWNIT.2009.5158587.
CCMG
A. Cohen, A. Cohen, M. Médard,  and O. Gurewitz, 
“Individually-secure multi-source multicast,” 
Proc. 2017 IEEE Int. Symp. Information Theory (ISIT 2017), 
Aachen, Germany, Jun. 25 – 30, 2017, pp. 3105 – 3109;
arXiv:1702.03012

H-tight
M. Hayashi, 
“Tight exponential analysis of universally composable privacy amplification and its applications,”
IEEE Trans. Inform. Theory, 
vol.  59, no. 11, pp. 7728 – 7746 (2013).

Carter
L. Carter and M. Wegman,
“Universal classes of hash functions,”

J. Comput. System Sci., vol. 18, no. 2, 143 – 154 (1979).

WC81
M. N. Wegman and J. L. Carter,
“New Hash Functions and Their Use in Authentication and Set Inequality,"
J. Comput. System Sci., vol. 22, 265 – 279 (1981).

AVF16-1
G. K. Agarwal, M. Cardone, and C. Fragouli, 
“Coding across unicast sessions can increase the secure message capacity,” 
Proc. 2016 IEEE Int. Symp. Information Theory (ISIT 2016), 
Barcelona, Spain, 10 – 15 July, 2016, pp. 2134 – 2138.

AVF16-2
G. K. Agarwal, M. Cardone, and C. Fragouli, 
“On secure network coding for two unicast sessions: studying butterflies,”
Proc. 2016 IEEE Globecom Workshops (GC Wkshps), 
Washington, DC, USA, 4 – 8 Dec., 2016, pp. 1 – 6.


AVF17
G. K. Agarwal, M. Cardone, and C. Fragouli, 
“Secure Network Coding for Multiple Unicast: On the Case of Single Source,”
In International Conference on Information Theoretic Security (pp. 188-207). 
Springer, Cham. 2017, November. 

YC2 R. W. Yeung and N. Cai, 
“Network error correction, Part I: basic concepts and upper bounds,” 
Communications in Information and Systems, vol. 6, no. 1, pp. 19 – 36 (2006).

CY2 N. Cai and R. W. Yeung, 
“Network error correction, Part II: lower bounds,” 
Communications in Information and Systems,
vol. 6, no. 1, pp.37 – 54 (2006).

NY C. K. Ngai and S. Yang, 
“Deterministic Secure Error-Correcting (SEC) Network Codes,” 
Information Theory Workshop, Lake Tahoe, USA, 2007.

DFZ R. Dougherty, C.  Freiling, and K. Zeger, 
“Insufficiency of Linear Coding in Network Information Flow,” 
IEEE Trans. Inform. Theory, 
vol. 51, no. 8, 2745 – 2759 (2005).



