Consider the following problem setting: A network $G$ comprises of $n$ nodes where each node is aware of only its neighbors but not the entire graph $G$. Each node has a unique identity and cannot fake its identity to its neighbors. Assume that $k$ among the $n$ nodes act in an adverserial manner and the remaining $n-k$ nodes are good nodes. Under what constraints, can the good nodes securely route packets to each other in the presence of adverserial nodes attempting to disrupt the routing process?

In this talk, we will describe certain decentralized security mechanisms (that are devoid of a public key infrastructure) that address the above mentioned secure routing problem given certain constraints on the connectivity properties of the graph. We will also briefly describe how these mechanisms can be extended to exisiting Internet routing protocols (BGP and OSPF).

This is joint work with Randy Katz, Volker Roth, Ion Stoica and Scott Shenker.