Secure Network Coding via Filtered Secret Sharing
Cliff Stein, Columbia University
December 2nd, 2005

Abstract

We study 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. We establish a close connection between secure linear network coding and a new variant of the secret sharing problem, which we call "filtered secret sharing." Using this connection, we establish new trade-offs between security, capacity, and bandwidth of secure linear network coding schemes.

Our positive results show that by giving up a small amount of capacity, it is possible to dramatically reduce the bandwidth
requirements of secure linear network coding. Our negative results show that within the framework we consider, unless capacity is relaxed, the bandwidth requirements can be prohibitively high. These results are obtained by showing that the problem of making a linear network code secure is equivalent to the problem of finding a linear error-correcting code with certain generalized distance properties.

Joint work with Jon Feldman, Tal Malkin and Rocco Servedio