March 13, 2008 - Paul Bunn

Title: Optimal-Rate Routing in Adversarial Networks

Abstract:
This talk presents an optimal-rate routing protocol in the public-key setting for synchronous networks in the presence of a malicious poly-time adversary.  Namely, even if the majority of the nodes are controlled by a malicious adversary and the topology of the network is changing at each round, then as long as there is some path of non-corrupted nodes connecting a sender and a receiver at each round (though this path may change every round), we construct a routing protocol with bounded memory per processor that achieves optimal packet transfer rate.

The routing protocol assumes no knowledge of which nodes are corrupted nor which path is reliable at any round. Our result, which can be interpreted as the first interactive coding theorem for malicious networks, states that the protocol cannot be affected in a meaningful way by any polynomial-time malicious adversary whose goal is to disrupt the communication as much as possible, including (but not limited to) deletion, insertion, and replacement of any content, not responding or responding incorrectly to information requests, or any other arbitrary deviation from prescribed protocol rules. The talk will be self-contained and accessible to the general audience.

Joint work with Yair Amir and Rafail Ostrovsky