On the Capacity of Secure Network Coding
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein · 2004
We consider the problem of using a multicast network code to transmit information securely in the presence of a "wire-tap " adversary who can eavesdrop on a bounded number of network edges. Cai & Yeung (ISIT, 2002) gave a method to alter any given linear network code into a new code that is secure. However, their construction is in general inefficient, and requires a very large field size; in many cases this is much greater than the field size required by standard network code construction algorithms to achieve the min-cut capacity (without a security guarantee). In this paper we generalize and simplify the method of Cai & Yeung, and show that the problem of making a linear network code secure is equivalent to the problem of finding a linear code with certain generalized distance properties. We show that if we give up a small amount of overall capacity, then a random code achieves these properties using a much smaller field size-- in some cases a field of constant size suffices-- than the construction of Cai & Yeung. We add further support to this approach by showing that if we are not willing to give up any capacity, then a large field size may sometimes be required to achieve security.