Network coding for security and error correction

Network coding is one of the most important breakthroughs in information theory in recent years. The theory gives rise to a new concept regarding the role of nodes in a communication network. Unlike in existing networks where the nodes act as switches, in the paradigm of network coding, every node in the network can act as an encoder for the incoming information. With this new infrastructure, it is possible to utilize the full capacity of the network where it is impossible to do so without network coding. In the seminar paper by Ahlswede et al. [1] where network coding was introduced, the achievability of the maxflow bound for every single source multicast network by using network coding was also proved. By further exploring the possibility of linear network coding, Cai and Yeung introduced the idea of error-correcting network coding and secure network coding in [7] and [8] respectively. These papers launched another two important research areas in the field of network coding.;In this work, we consider the possibility and the effectiveness of implementing secure network coding and error-correcting network coding at the same time. Upon achieving this goal, information can be multicast securely to the sink nodes through a noisy network. Toward this end, we propose constructions of such codes and prove their optimality. After that, we extend the idea of generalized Hamming Weight [54] for the classical point-to-point communication channel to linear network coding. We also extend the idea of generalized Singleton bound to linear network coding. We further show that the generalized Hamming weight can completely characterize the security performance of linear code at the source node on a given linear network code. We then introduce the idea of Network Maximum Distance Separable code (NMDS code), which can be shown to play an important role in minimizing the information that an eavesdropper can obtain from the network. The problem of obtaining the optimal security performance is in fact equivalent to the problem of obtaining a Network Maximum Distance Separable code.