Fighting Byzantine Adversaries in Networks: Network Error-Correcting Codes
Speaker: Sidharth Jaggi , MIT LIDS
Date: November 6 2006
Time: 4:00PM to 5:15PM
Location: 32-G575
Host: Madhu Sudan, MIT CSAIL
Contact: Joanne Hanley, 617.253.6054, joanne@csail.mit.edu
Relevant URL: http://theory.csail.mit.edu/~madhu/algcomp/sid-abs.html
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.
See other events that are part of Algorithms and Complexity Series 2006/2007
See other events happening in November 2006
