Two Network Coding Talks for the price of one: Security, Low Complexity

December 6, 2005
Sidharth Jaggi | California Institute of Technology

Network coding is good. Among other advantages, it allows for greater throughput, more robust code design, and decentralization of code design. However, if care is not taken, a single malicious adversary hiding in the network can subvert the entire code design and cause catastrophic decoding errors. We present a tight rate-region for this problem, and what is essentially an error-correction scheme for network codes, and show how these codes can protect against a malicious adversary who not only eavesdrops, but also injects false packets into the network. Our schemes are generalizations of Verifiable Secret Sharing schemes to the case of multicasting over a network.

In the second part of the talk, we present a simple new result hot off the presses. We show that a very restricted and simple set of linear encoding operations (that we call permute-and-add codes) are all that are needed to asymptotically achieve network multicast capacity. These have the advantage that besides being easy to describe, their implementation complexity is quadratically lower than those of currently used network codes.

Speaker Details

Sidharth Jaggi received the B.Tech. degree in 2000 from the Indian Institute of Technology, Bombay (IITB) and the M.S. and Ph.D. degrees in 2001 and 2005 respectively from the California Institute of Technology (Caltech), all in Electrical Engineering. Showing an unhealthy predilection for institutes of technology, he will start a post-doctoral scholarship at the Massachusetts Institute of Technology in 2006.His areas of interest include data compression, network information theory, coding theory and network coding. During the summers of 2002 and 2003 he worked at Microsoft Research, Redmond. He was awarded the Caltech Engineering and Applied Sciences Division Fellowship in 2000 and the Microsoft Research Fellowship in 2001.http://jaggi.name