On the Capacity of Secure Network Coding.
J. Feldman and T. Malkin and R. Servedio and C. Stein.
42nd Annual Allerton Conference on Communication, Control, and Computing, 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.

Postscript or pdf .

Back to main papers page