Colloquium Speaker

Cliff Stein, Columbia University
Secure Network Coding via Filtered Secret Sharing
Date: Thursday, February 3, 2005
Time: 11:00AM
Place: Gould-Simpson, Room 701
Refreshments will be served in the 7th floor lobby of Gould-Simpson at 10:45 AM


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 distanceproperties.