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
Speaker Biography
Paul Bunn is a fifth-year graduate student in the math department at the University of California, Los Angeles, working with Prof. Rafail Ostrovsky. Paul’s research focuses on problems in number theory and theoretical computer science, including cryptography, networks and distributed algorithms. He was awarded NSF VIGRE research fellowships in 2006 and 2007, is an active member of the Cryptography research group and Number Theory group at UCLA, and is a Sigma Xi member since 2001. Paul was one of six graduate students recognized by the math department for excellence in teaching in 2006. Paul graduated with distincition from Duke University in 2001 with a double-major in physics and computer science.