In Part I of this two-part paper, we put forward the problem of secure network function computation.We investigated securely computing linear target functions with a wiretapper who can eavesdrop any edge subset up to a certain sizer, referred to as the security level, where the security function is the identity function, i.e., we need to prevent the source messages from being leaked to the wiretapper. The notion of this security is called source security. In the current Part II of the two-part paper, we consider another interesting model which is the same as the above one except that the security function is identical to the target function, i.e., we need to prevent the target function from being leaked to the wiretapper. The notion of this security is calledtarget-function security. We first prove a non-trivial upper bound on the secure computing capacity defined as the maximum average number of times that the target function can be securely computed with zero error at the sink node for one use of the network. The upper bound obtained is applicable to arbitrary network topologies and arbitrary security levels. In particular, when the security levelris equal to 0, the upper bound reduces to the computing capacity without security consideration. This upper bound is always not less than the upper bound obtained in Part I for source security, which accords with the relation between the secure computing capacities for target-function security and source security. We further obtain a bound on the gap between the two upper bounds, and show that the gap between the two upper bounds can be unbounded. Furthermore, we present an algebraic framework for linear (function-computing) secure codes for the target-function-security model by proving two equivalent conditions for computability and target-function security, respectively. With this framework, we develop a construction of linear secure codes for the target-function-security model and thus obtain a lower bound on the secure computing capacity. In the same spirit, we also prove an equivalent algebraic condition for source security, and so obtain an algebraic framework for linear secure codes for the source-security model. With this, we not only generalize the code construction developed in Part I for the source-security model but also can present it in a more succinct and understandable way. In addition, motivated by the fact that a source-secure code is target-function-secure but not vice versa, we compare our code construction for the target-function-security model and the generalized code construction for the source-security model, and show that the codes constructed by the generalized code construction for source security are only a very special subclass of the codes constructed by the code construction for target-function security. Further, a considerably smaller field size can be used for our code construction for target-function security compared with the generalized code construction for source security.

In this paper, we consider code construction for the model of secure network function computation, where in a directed acyclic network, a sink node is required to correctly compute a linear function, regarded as the target function, of source messages generated at multiple source nodes; while a wiretapper, who can access any one edge subset up to a certain size$r$, referred to as the security level, is not allowed to obtain any information about a security function of the source messages. Here, we focus on an interesting and important case that the security function is identical to the target function, namely that we need to protect any information of the target function from being leaked to the wiretapper, which is called the target-function security. We prove an equivalent condition for targetfunction security for the existence of linear function-computing secure network codes from an algebraic point of view. With this, we develop a construction of linear function-computing secure network codes and thus obtain a lower bound on the secure computing capacity, defined as the maximum average number of times that the target function can be securely computed with zero error at the sink node for one use of the network under the target-function-security constraint.

The problem of network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a target function, of which the inputs are generated at multiple source nodes. Existing research on network function computation explores two types of problems regarding block-length network codes and variable-length network codes. In this paper, we concentrate on an important class of variable-length network codes, namely uniquely-decodable network codes, whose computing rate is the maximum average expected number of bits transmitted on all edges in the network for computing the target function once with zero error. In the existing papers, lower bounds on the computing capacity of uniquely-decodable network codes have been proposed under certain constraints on either the network topology or the target function. By developing a novel graph coloring approach based on a cut-set strong partition, we obtain a general lower bound on the computing capacity of uniquely-decodable network codes, which is applicable to arbitrary network topologies, arbitrary information sources and arbitrary target functions. Furthermore, we show that this lower bound is a strict improvement over the previous results by applying this lower bound to the problem of computing an arithmetic sum over a diamond network.

In this paper, we first explore the underlying mathematical structure of edge subsets on a finite directed acyclic graph in using a lattice-theoretic approach. We prove that a collection of edge subsets, depending on different conditions it satisfies, together with the corresponding “cut-separating” partial order, can form a meet-semilattice, a join-semilattice or a lattice. The bottom and top thus derived generalize the concept of the primary minimum cut introduced by Guang and Yeung (2018) and hence we provide a new way from the lattice-theoretic point of view to understand the primary minimum cut and its existence and uniqueness. The introduced concepts and obtained results regarded as a bridge connect graph theory and lattice theory, which appear to be of fundamental interest in graph theory, lattice theory, and even beyond. In addition, we consider linear network error correction (LNEC) coding when errors may occur on edges of a communication network of which the topology is known. In LNEC coding, the minimum required field size for the existence of LNEC codes, in particular LNEC maximum distance separable (MDS) codes which are regarded as a most important type of optimal codes, is an open problem not only of theoretical interest but also of practical importance. By applying the approach of the above edge-subset (semi-)lattice, we obtain an improved upper bound on the minimum required field size for the existence of LNEC (MDS) codes. We quantify the improvement over the existing results by both theoretical analysis and numerical simulations and thus show that the improvement is in general significant. The improved upper bound, which is graph-theoretic, depends only on the network topology and requirement of the error correction capability but not on a specific code construction. We also develop an efficient algorithm that can compute the bound in a linear time of the number of edges.

In this paper, we put forward the problem of secure network function computation under the function-security constraint. In this model, a target function, of which the inputs are generated at multiple source nodes as source messages, is required to be computed with zero error at a sink node over a network, while a wiretapper, who can access any one but not more than one wiretap set in a given collection of wiretap sets, is not allowed to obtain any information about a target function of the source messages. The secure computing rate of a secure function-computing network code is the average number of times the target function can be securely computed per use of the network. However, characterizing this secure capacity with this general setup is overwhelmingly difficult. In this paper, we consider this secure model in which the target function and the security function are identical to be a linear function; and the wiretapper can eavesdrop any one edge subset up to a size$r$, referred to as the security level. We obtain a non-trivial upper bound on the secure computing capacity, which is applicable to arbitrary network topologies and arbitrary security levels. When$r=0$, the upper bound reduces to the computing capacity without security consideration. By applying the upper bound, we obtain an upper bound on the maximum security level such that the function can be securely computed with a positive rate, and fully characterize the secure computing capacity for a class of secure models. Finally, we prove that our upper bound is always larger than or equal to the upper bound previously obtained by Guang et al. on the secure computing capacity for source-security. This is consistent with the relation between the secure computing capacities for source-security and function-security.

In this paper, we consider the problem of zero-error network function computation. In a directed acyclic network, a single sink node requires to compute with zero error a function of source messages generated by multiple source nodes. We are interested in the information-theoretic computing capacity, which is defined as the average number of times that the function can be computed with zero error for one use of the network. The explicit characterization of the computing capacity in general is extremely challenging. The best known upper bound, applicable to arbitrary network topologies and arbitrary target functions, is the one proved by Guang et al. using the cut-set strong partition approach. This bound is tight for all previously considered network function computation problems whose computing capacities are known. In this paper, we focus on the model of computing the binary arithmetic sum over an asymmetric diamond network, which is of great importance to illustrate the combinatorial nature of network function computation problem. We first prove an upper bound of 1 on the computing capacity by using a linear programming approach, which rectifies an invalid upper bound previously proposed in the literature. However, this upper bound does not surpass the best known upper bound for this model, which is also equal to 1. Further, by developing a different graph coloring approach, we obtain an improved upper bound 3–1 0.822). We thus show that the best known upper bound by Guang et al. is not tight for this model. On the other hand, we present an explicit code construction, which implies a lower bound 6 0.815) on the computing capacity. Comparing the improved upper and lower bounds thus obtained, there exists a rough 0.007 gap between them.

In this paper, we consider stegotext reconstruction problem in information embedding. By adding the requirement of restoring the stegotext under certain fidelity criterion, we generalize the concept of reversible/irreversible information embedding. We focus on the stegotext reconstruction in a discrete memoryless host dependent attack channel, which can be regarded as a generalized Gel’fand-Pinsker problem with an input reconstruction constraint. For this problem, we prove an upper bound and a lower bound on its embedding capacity-distortion function, which is defined to describe the tradeoff between embedding information rate, host composition loss, and stegotext reconstruction distortion. In particular, our upper and lower bounds thus obtained match each other for the binary XOR attack channel with Hamming distortion and Costa’s additive Gaussian attack channel with quadratic loss. We further consider a variant of this problem, where host signal is available at the encoder in a causal way. For this case, we completely characterize its capacity-distortion function.

In this paper, we put forward secure network function computation over a directed acyclic network. In such a network, a sink node is required to compute with zero error a target function of which the inputs are generated as source messages at multiple source nodes, while a wiretapper, who can access any one but not more than one wiretap set in a given collection of wiretap sets, is not allowed to obtain any information about a security function of the source messages. The secure computing capacity for the above model is defined as the maximum average number of times that the target function can be securely computed with zero error at the sink node with the given collection of wiretap sets and security function for one use of the network. The characterization of this capacity is in general overwhelmingly difficult. In the current paper, we consider securely computing linear functions with a wiretapper who can eavesdrop any subset of edges up to a certain size$r$, referred to as the security level, with the security function being the identity function. We first prove an upper bound on the secure computing capacity, which is applicable to arbitrary network topologies and arbitrary security levels. This upper bound depends on the network topology and security level. Furthermore, we obtain an upper bound and a lower bound on this bound, which are both in closed form. In particular, when the security level$r$is equal to 0, our upper bound reduces to the computing capacity without security consideration. Also, we discover the surprising fact that for some models, there is no penalty on the secure computing capacity compared with the computing capacity without security consideration. Furthermore, we obtain an equivalent expression of the upper bound by using a graph-theoretic approach, and accordingly we develop an efficient approach for computing this bound. On the other hand, we present a construction of linear function-computing secure network codes and obtain a lower bound on the secure computing capacity. By our code construction, for the linear function which is over a given finite field, we can always construct a (vector-) linear function-computing secure network code over the same field. We also give some sufficient conditions for the tightness of the lower bound in terms of the network topology. With this lower bound and the upper bound we have obtained, the secure computing capacity for some classes of secure models can be fully characterized. Another interesting case is that the security function is the same as the target function, which will be investigated in Part II of this paper.

In this paper, we put forward a model of zero-error distributed function compression system of two binary memoryless sources$X$and$Y$. In this model, there are two encoders$\mathbf {En1}$and$\mathbf {En2}$and one decoder$\mathbf {De}$, connected by two channels$(\mathbf {En1}, \mathbf {De})$and$(\mathbf {En2}, \mathbf {De})$with the capacity constraints$C_{1}$and$C_{2}$, respectively. The encoder$\mathbf {En1}$can observe$X$or$(X,Y)$and the encoder$\mathbf {En2}$can observe$Y$or$(X,Y)$according to the two switches${\mathbf {s}}_{1}$and${\mathbf {s}}_{2}$open or closed (corresponding to taking values 0 or 1). The decoder$\mathbf {De}$is required to compress the binary arithmetic sum$f(X,Y)=X+Y$with zero error by using the system multiple times. We use$({\mathbf {s}}_{1}{\mathbf {s}}_{2};C_{1}, C_{2}; f)$to denote the model in which it is assumed that$C_{1}\geq C_{2}$by symmetry. The compression capacity for the model is defined as the maximum average number of times that the function$f$can be compressed with zero error for one use of the system, which measures the efficiency of using the system. We fully characterize the compression capacities for all the four cases of the model$({\mathbf {s}}_{1}{\mathbf {s}}_{2};C_{1}, C_{2}; f)$for${\mathbf {s}}_{1}{\mathbf {s}}_{2}=00,01,10,11$. Here, the characterization of the compression capacity for the case$(01;C_{1},C_{2};f)$with$C_{1}>C_{2}$is highly nontrivial, where a novel graph coloring approach is developed. Furthermore, we apply the compression capacity for$(01;C_{1},C_{2};f)$to an open problem in network function computation that whether the best known upper bound of Guang et al. on computing capacity is in general tight. Up to now, we are not aware of any example for which this upper bound is not tight. By considering a network function computation model transformed from$(01;C_{1},C_{2};f)$with$C_{1}>C_{2}$, we give the answer that in general the upper bound of Guang et al. is not tight.

In this paper, we put forward the model of zero-error distributed function compression system of two binary memoryless sources X and Y as depicted in Fig. 1. In the model, there are two encoders En1 and En2 and one decoder De, connected by two channels with capacity constraints C1and C2, respectively. The encoder En1 can observe X or (X, Y), and the encoder En2 can observe Y or (X, Y). Here, we use two switches s1and s2open or closed (taking values 0 or 1) to represent whether En1 can observe Y and En2 can observe X, respectively. The decoder De is required to compress the binary arithmetic sum f(X, Y) = X + Y with zero error by using the system multiple times. We use (s1s2; C1, C2; f) to denote the model. The compression capacity is defined as the maximum average number of times that the function f can be compressed with zero error for one use of the system, which measures the efficiency for using the system. In the paper, the compression capacities for all the four models are fully characterized. Amongst them, the characterization of the compression capacity for (01; C1, C2; f) is very difficult. Toward this end, we develop a novel graph coloring approach in the converse part and the proof is highly nontrivial. Furthermore, we apply the compression capacity for (01; C1, C2; f) to the open problem in network function computation that whether the best known upper bound by Guang et al. on computing capacity is in general tight. This upper bound is always tight for all previously considered network function computation problems whose computing capacities are known. By considering equivalent network function computation models of (01; C1, C2; f), we give the answer that in general the upper bound of Guang et al. is not tight.

The problem of secure network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a target function f, of which the inputs are generated at multiple source nodes, while a wiretapper, who can access any one but not more than one wiretap set in a given collection of wiretap sets, obtains no information about the source inputs. The secure computing rate of a secure function-computing network code is the average number of times the target function can be securely computed for one use of the network. In the paper, we are interested in securely computing linear functions with the wiretapper who can eavesdrop any subset of edges up to a certain size r, referred to as the security level. We obtain an improved upper bound on the secure computing capacity, which is applicable to arbitrary network topologies and arbitrary security levels. When the security level r is equal to 0, our improved upper bound reduces to the computing capacity without security consideration. Furthermore, by applying the improved upper bound, we obtain a non-trivial upper bound on the maximum security level such that the function can be securely computed with a positive rate. We also present a lower bound on the secure computing capacity and give some sufficient conditions in terms of the network topology on the tightness of the lower bound. Together with the improved upper bound, the secure computing capacity for a class of security models can be fully characterized.

In this paper, we put forward the model of secure network function computation. In this model, a target function, of which the inputs are generated at multiple source nodes, is required to be computed with zero error at a sink node over a network while being protected from a wiretapper who can access any one but not more than one wiretap set in a given collection of wiretap sets. The secure computing rate of a secure network code is the average number of times the target function can be securely computed with zero error for one use of the network. However, characterizing this secure capacity with this general setup is overwhelmingly difficult. In the paper, we only consider this secure model for linear functions with the wiretapper being able to eavesdrop any subset of edges in the network up to a certain size, referred to as the security level. We prove a non-trivial upper bound on the secure computing capacity. Also, we discover the surprising fact that for some models, there is no penalty on the secure computing capacity compared with the computing capacity without security consideration. We further present a lower bound by designing a secure network coding scheme. Both the upper and lower bounds are tight for some cases but not tight in general. Finally, by comparing the upper and lower bounds thus obtained, we can exactly characterize the secure computing capacity when network topology satisfies a certain condition.

In this paper, we investigate a two-way lossy source coding problem, where both users have access to a common message from a helper encoder. When the correlated sources are a product of two reversely degraded components, we characterize the rate-distortion region. The converse part for this mismatched case is proved by suitably applying the enhancement argument. We combine the Heegard-Berger scheme and the Wyner-Ziv encoding to obtain the achievability part.

In this paper, we introduce an n-channel multilevel imperfect secret sharing problem, which can be regarded as a generalization of secret sharing and a variation of multilevel diversity coding. In this model, a discrete memoryless source (DMS) is encoded into n encoded messages. To measure the secrecy of the system, we introduce a security level for each subset of encoded messages. In the paper, we focus on the n-channel symmetric multilevel imperfect secret sharing (SMISS) problem, i.e., the security levels of all the subsets with the same cardinality are identical. First, we explicitly characterize the coding rate regions for 2-channel and 3-channel SMISS problems. However, it is difficult to characterize the explicit rate region for a general n, since the complexity of designing optimal coding schemes can grow with n exponentially. Nevertheless, we put forward an inner bound and an outer bound on the rate region of the general n-channel SMISS problem. Moreover, we consider two special cases, i.e., the Two-SMISS problem and the linear SMISS problem, and prove that the inner and outer bounds are tight for these two problems, respectively.

We investigate the problem of the successive refinement for Wyner-Ziv coding with degraded side information and obtain a complete characterization of the rate region for the quadratic vector Gaussian case. The achievability part is based on the evaluation of the Tian-Diggavi inner bound that involves Gaussian auxiliary random vectors. For the converse part, a matching outer bound is obtained with the aid of a new extremal inequality. Herein, the proof of this extremal inequality depends on the integration of the monotone path argument and the doubling trick as well as information-estimation relations.

We consider linear network error correction (LNEC) coding when errors may occur on the edges of a communication network of which the topology is known. In this paper, we first revisit and explore the framework of LNEC coding, and then unify two well-known LNEC coding approaches. In LNEC coding, LNEC maximum distance separable (MDS) codes are a type of most important optimal codes. However, the minimum required field size for the existence of LNEC MDS codes is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we obtain an improved lower bound on the required field size by developing a graph-theoretic approach. The improvement over the existing results is in general significant. Furthermore, by applying the graph-theoretic approach to the framework of LNEC coding, we obtain a significantly enhanced characterization of the capability of an LNEC code in terms of its minimum distance.

Information-theoretic security is considered in the paradigm of network coding in the presence of wiretappers, who can access one arbitrary edge subset up to a certain size, also referred to as the security level. Secure network coding is applied to prevent the leakage of the source information to the wiretappers. In this paper, we consider the problem of secure network coding when the information rate and the security level can change over time. To efficiently solve this problem, we put forward local-encoding-preserving secure network coding, where a family of secure linear network codes (SLNCs) is called local-encoding-preserving if all the SLNCs in this family share a common local encoding kernel at each intermediate node in the network. We first consider the design of a family of local-encoding-preserving SLNCs for a fixed security level and a flexible rate. A simple approach is presented for efficiently constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same security level and the rate reduced by one. By applying this approach repeatedly, we can obtain a family of local-encoding-preserving SLNCs with a fixed security level and multiple rates. We further consider the design of a family of local-encoding-preserving SLNCs for a fixed rate and a flexible security level. We present a novel and efficient approach for constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same rate and the security level increased by one. Next, we consider the design of a family of local-encoding-preserving SLNCs for a fixed dimension (equal to the sum of rate and security level) and a flexible pair of rate and security level. We propose another novel approach for designing an SLNC such that the same SLNC can be applied for all the rate and security-level pairs with the fixed dimension. Also, two polynomial-time algorithms are developed for efficient implementations of the later two proposed approaches, respectively. Furthermore, we prove that all our three approaches do not incur any penalty on the required field size for the existence of SLNCs in terms of the best known lower bound by Guang and Yeung. Finally, we consider the ultimate problem of designing a family of local-encoding-preserving SLNCs that can be applied to all possible pairs of rate and security level. By combining the constructions of the three families of local-encoding-preserving SLNCs in the paper in suitable ways, we can obtain a family of local-encoding-preserving SLNCs that can be applied for all possible pairs of rate and security level. Three possible such constructions are presented.

In the paradigm of network coding, information-theoretic security is considered in the presence of wiretappers, who can access one arbitrary edge subset up to a certain size, referred to as the security level. Secure network coding is applied to prevent the leakage of the source information to the wiretappers. In this paper, we consider the problem of secure network coding for flexible pairs of information rate and security level with any fixed dimension (equal to the sum of rate and security level). We present a novel approach for designing a secure linear network code (SLNC) such that the same SLNC can be applied for all the rate and security-level pairs with the fixed dimension. We further develop a polynomial-time algorithm for efficient implementation and prove that there is no penalty on the required field size for the existence of SLNCs in terms of the best known lower bound by Guang and Yeung. Finally, by applying our approach as a crucial building block, we can construct a family of SLNCs that not only can be applied to all possible pairs of rate and security level but also share a common local encoding kernel at each intermediate node in the network.

In this paper, we consider Successive refinement for the Wyner-Ziv source coding problem, in which sources are vector Gaussian distributed and side information follows a degraded order assumption. We fully characterize its ratedistortion region with covariance mean square error distortions. We use jointly Gaussian auxiliary random variables to evaluate the existing single-letter description of the rate region by Tian and Diggavi, which gives the achievability. The converse relies on the information-estimation relationship, with which the tight outer bound is obtained.

The problem of network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a target function, of which the inputs are generated at multiple source nodes. The edges in the network are assumed to be error-free and have limited capacity. The nodes in the network are assumed to have unbounded computing capability and be able to perform network coding. The computing rate of a network code that can compute the target function over the network is the average number of times that the target function is computed with zero error for one use of the network. In this paper, we obtain an improved upper bound on the computing capacity, which is applicable to arbitrary target functions and arbitrary network topologies. This improved upper bound not only is an enhancement of the previous upper bounds but also is the first tight upper bound on the computing capacity for computing an arithmetic sum over a certain non-tree network, which has been widely studied in the literature. We also introduce a multi-dimensional array approach that facilitates evaluation of the improved upper bound. Furthermore, we apply this bound to the problem of computing a vector-linear function over a network. With this bound, we are not only able to enhance a previous result on computing a vector-linear function over a network but also simplify the proof significantly. Finally, we prove that for computing the binary maximum function over the reverse butterfly network, our improved upper bound is not achievable. This result establishes that in general our improved upper bound is non-achievable, but whether it is asymptotically achievable or not remains open.

The problem of network function computation over a directed acyclic network is investigated in this paper. In such a network, a sink node desires to compute with zero error a target function, of which the inputs are generated at multiple source nodes. The computing rate of a network code that can compute the target function over the network is the average number of times that the target function is computed with zero error for one use of the network. In this paper, we obtain an improved upper bound on the computing capacity, which is applicable to arbitrary target functions and arbitrary network topologies. By applying this bound to the problem of computing a vector-linear function over a network, we are able to not only enhance a previous result on computing a vector-linear function over a network but also simplify the proof significantly. Finally, we prove that for computing the binary maximum function over the reverse butterfly network, our improved upper bound is not achievable. This result establishes that in general our improved upper bound is non achievable, but whether it is asymptotically achievable or not remains open.

We generalize secret sharing to a symmetric multilevel imperfect secret sharing (SMISS) problem. To measure the secrecy of the system, we introduce a security level for each set of encoded messages, which is measured by the equivocation of the source message given the encoded messages in this set. The security levels of all the subsets with the same cardinality are assumed to be identical. This problem in its general case is complicated. In this paper, we explicitly characterize the rate regions of the general two-level and three-level SMISS problems.

In the future communication applications, users may obtain their messages that have different importance levels distributively from several available sources, such as distributed storage or even devices belonging to other users. This scenario is the best modeled by the multilevel diversity coding systems (MDCS). To achieve perfect (information-theoretic) secrecy against wiretap channels, this paper investigates the fundamental limits on the secure rate region of the asymmetric MDCS (AMDCS), which include the symmetric case as a special case. Threshold perfect secrecy is added to the AMDCS model. The eavesdropper may have access to any one but not more than one subset of the channels but know nothing about the sources, as long as the size of the subset is not above the security level. The question of whether superposition (source separation) coding is optimal for such an AMDCS with threshold perfect secrecy is answered. A class of secure AMDCS (S-AMDCS) with an arbitrary number of encoders is solved, and it is shown that linear codes are optimal for this class of instances. However, in contrast with the secure symmetric MDCS, superposition is shown to be not optimal for S-AMDCS in general. In addition, necessary conditions on the existence of a secrecy key are determined as a design guideline.

Random linear network coding (RLNC) is a promising network coding solution when the network topology information is not fully available to all the nodes. However, in practice, nodes have partial knowledge of the network topology information. Motivated by this, we investigate the performance of RLNC and obtain different upper bounds on the failure probability of RLNC for the network constrained by different partial network topology information. These upper bounds not only improve the existing ones in the literature, but also show that the partial network topology information can bring benefits to the performance analysis of RLNC. On the other hand, it is observed that if more network topology information can be utilized, tighter upper bounds can be obtained, as expected. The upper bounds on two classical networks are compared for demonstration. To obtain a deeper understanding about the performance of RLNC, the asymptotic behavior of RLNC as the field size goes to infinity is also investigated.

We consider a communication network where there exist wiretappers who can access a subset of channels, called a wiretap set, which is chosen from a given collection of wiretap sets. The collection of wiretap sets can be arbitrary. Secure network coding is applied to prevent the source information from being leaked to the wiretappers. In secure network coding, the required alphabet size is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we develop a systematic graph-theoretic approach for improving Cai and Yeung's lower bound on the required alphabet size for the existence of secure network codes. The new lower bound thus obtained, which depends only on the network topology and the collection of wiretap sets, can be significantly smaller than Cai and Yeung's lower bound. A polynomial-time algorithm is devised for efficient computation of the new lower bound.

A function computation problem over a directed acyclic network has been considered in the literature, where a sink node is required to compute a target function correctly with the inputs arbitrarily generated at multiple source nodes. The network links are error free but capacity limited, and the intermediate nodes perform network coding. The computing rate of a network code is the average number of times that the target function is computed for one use of the network, i.e., each link in the network is used at most once. In the existing papers, two cut-set bounds were proposed on the computing rate. However, we in this paper show that these bounds are not valid for general network function computation problems. We analyze the reason of the invalidity and propose a general cut-set bound by using a new equivalence relation associated with the inputs of the target function. Moreover, some results in the existing papers were proved by applying the invalid upper bound. We also justify the validity of these results.

Batched sparse (BATS) code is a promising technology for reliable end-to-end transmission in multi-hop wireless networks. One main research topic for BATS code is how to design an optimal inner code that is typically random linear network code. In this paper, this issue is focus on the number of transmissions from an end-to-end perspective. The problem is formulated as a mixed integer nonlinear programming (MINLP) problem with the objective of minimizing the total number of transmissions from source to destination. Subsequently, the inherent properties of inner codes are exploited to relax the integer restrictions by the means of the regularized incomplete beta function. As a result, a new nonlinear programming (NLP) problem is constructed. Solving the NLP problem provides a valid lower bound on the optimal solution, and, hence, is used as the performance measure for our heuristic. Furthermore, a centralized approximation approach is developed to solve our MINLP problem efficiently. The numerical results demonstrate that all solutions developed in the paper are near-optimal with a guaranteed performance bound.

Whether superposition (source separation) Is optimal for the asymmetric multilevel diversity coding systems (AMDCS) with perfect secrecy is answered in this paper by studying a non-trivial example. Threshold perfect secrecy is added to the AMDCS model. The eavesdropper may have access to any one but not more than one subset of the channels but can get nothing about the sources, as long as the size of the subset is not above the security level. The secure AMDCS (S-AMDCS) with five sources, four encoders and security level two is solved and it is shown that linear codes are optimal for this instance. However, in contrast with the secure symmetric multilevel diversity coding systems (S-SMDCS), superposition is shown to be not optimal for S-AMDCS in general from this counterexample.

We consider a communication network where there exist wiretappers who can access a subset of channels, called a wiretap set, which is chosen from a given collection of wiretap sets. The collection of wiretap sets can be arbitrary. Secure network coding is applied to prevent the source information from being leaked to the wiretappers. In secure network coding, the minimum required alphabet size is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of such coding schemes in terms of computational complexity and storage requirement. In this paper, we develop a systematic graph-theoretic approach for improving Cai and Yeung's lower bound on the required alphabet size for the existence of secure network codes. The new lower bound thus obtained, which depends only on the network topology and the collection of wiretap sets, can be significantly smaller than Cai and Yeung's lower bound. A polynomial-time algorithm is devised for efficient computation of the new lower bound. The graph-theoretic concepts introduced and the results obtained appear to be of fundamental interest in graph theory.

In conventional distributed storage exact repair problems, all sources are reconstructed when the decoder has access to a certain number of encoders (disks). So, the underlying reconstruction network is equivalent to a single-source problem. This paper considers a variant of the exact repair problem, where the underlying reconstruction network is the independent distributed source coding problem, a type of multi-source problem. As the first non-trivial case with two sources and three encoders, the storage-repair tradeoff regions are proved for all the 33 instances, and it is shown that binary codes are optimal.

The network function computation in directed acyclic networks is investigated in this paper. In such a network, a sink node desires to correctly compute a target function, of which all inputs are generated at multiple source nodes. The network links are assumed to be error-free and have limited capacity. The intermediate nodes can perform network coding. The computing rate of a network code is measured by the average number of times that the target function can be computed for one use of the network. In the paper, by using a cut-set partition approach to refine the equivalence classes associated with the inputs of the target function, a general upper bound on the network computing capacity is obtained, which is applicable to arbitrary target functions and network topologies. It is shown that this new upper bound is in general strictly better than the best existing one proposed by Huang, Tan and Yang.

In network communication, the source often transmits messages at several different information rates within a session. How to deal with information transmission and network error correction simultaneously under different rates is introduced in this paper as a variable-rate network error correction problem. Apparently, linear network error correction maximum distance separable (MDS) codes are expected to be used for these different rates guaranteeing the maximal error-correcting capability. For this purpose, designing a linear network error correction MDS code based on the existing results for each information rate is an alternative solution, but it is inefficient due to its high complexity. In order to solve the problem more efficiently, we present the concept of variable-rate linear network error correction MDS codes preserving local encoding kernels, that is, these linear network error correction MDS codes of different rates have the same local encoding kernel at each internal node. Thus, each nonsource node always uses the same local kernel for coding, no matter what the rate is. Furthermore, we propose an approach to construct such a family of variable-rate network MDS codes and give an algorithm for efficient implementation. This approach economizes the storage space for each internal node, and saves resources and time for transmissions on networks. Moreover, the performance of our proposed algorithm is analyzed, including the field size, the time complexity, the encoding complexity at the source node, and the decoding methods. Finally, a random method is introduced for constructing such a family of variable-rate network MDS codes, and a lower bound on the success probability of this random method is given, which shows that this probability will approach to one as the base field size goes to infinity.

In the paradigm of network coding, when wiretapping attacks occur, secure network coding is introduced to prevent information leaking adversaries. In practical network communications, the source often multicasts messages at several different rates within a session. How to deal with information transmission and information security simultaneously under variable rates and fixed security-level is introduced in this paper as a variable-rate and fixed-security-level secure network coding problem. In order to solve this problem effectively, we propose the concept of locality-preserving secure linear network codes of different rates and fixed security-level, which have the same local encoding kernel at each internal node. We further present an approach to construct such a family of secure linear network codes and give an algorithm for efficient implementation. This approach saves the storage space for both source node and internal nodes, and resources and time on networks. Finally, the performance of the proposed algorithm is analyzed, including the field size, computational and storage complexities.

Recently, network error correction coding (NEC) has been studied extensively. Several bounds in classical coding theory have been extended to NEC, especially the Singleton bound. In this paper, following the research line using the extended global encoding kernels proposed by Zhang in 2008, the refined Singleton bound of NEC can be proved more explicitly. Moreover, we give a constructive proof of the attainability of this bound and indicate that the required field size for the existence of network maximum distance separable (MDS) codes can become smaller further. By this proof, an algorithm is proposed to construct general linear network error correction codes including the linear network error correction MDS codes. Finally, we study the error correction capability of random linear NEC. Motivated partly by the performance analysis of random linear network coding, we evaluate the different failure probabilities defined in this paper in order to analyze the performance of random linear NEC. Several upper bounds on these probabilities are obtained and they show that these probabilities will approach to zero as the size of the base field goes to infinity. Using these upper bounds, we slightly improve on the probability mass function of the minimum distance of random linear network error correction codes in a paper by Balli and colleagues, as well as the upper bound on the field size required for the existence of linear network error correction codes with degradation at mostd.