Fighting Byzantine Adversaries in Networks: Network Error-Correcting Codes

Sidharth Jaggi (MIT LIDS)

It was shown by Ahlswede et al. that in general network coding is required to attain the multicast capacity. But since network coding involves mixing of information inside the network, a single corrupted packet generated by a malicious node can end up contaminating all the information reaching a destination, preventing decoding.

This talk introduces the first distributed polynomial-time rate-optimal network error-correcting codes that work in the presence of Byzantine nodes. We present algorithms that target adversaries with different attacking capabilities. When the adversary can eavesdrop on all links and jam z links, our first algorithm achieves a rate of C − 2z, where C is the network capacity. In contrast, when the adversary has limited snooping capabilities, we provide algorithms that achieve the higher rate of C − z. Our algorithms attain the optimal rate given the strength of the adversary. They are information-theoretically secure. They can be designed and operated in a distributed manner, assume no knowledge of the topology, and can be designed and implemented in polynomial-time. Furthermore, only the source and destination need to be modified; non-malicious nodes inside the network are oblivious to the presence of adversaries and implement a classical distributed network code. Finally, our algorithms work over wired and wireless networks.

This is joint work done with Michael Langberg, Sachin Katti, Tracey Ho, Dina Katabi, and Muriel Médard.

Host: Madhu Sudan

(The Algorithms and Complexity Seminar series talks are usually held Mondays from 4-5:15pm in 32-G575.)