Duration: 57:00

31 views

1

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.