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.


Abstract:

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