This paper presents secure routing techniques for structured peer-to-peer (p2p) overlay networks. Structured p2p overlays, such as CAN, Chord, Pastry, and Tapestry, provide a self-organizing substrate for large-scale, decentralized applications. These overlays are highly resilient, but current overlays are not secure; even a small fraction of malicious nodes can prevent correct message delivery. This paper studies attacks aimed at preventing correct message delivery in structured p2p overlays and presents defenses to these attacks. We describe and evaluate techniques that allow nodes to join the overlay, maintain routing state, and forward messages securely in the presence of malicious nodes. Secure routing requires (1) a secure assignment of node identifiers, (2) secure routing table maintenance, and (3) secure message forwarding. We present techniques for each of these problems and show how using these techniques, secure routing can be maintained efficiently despite up to 25% of malicious participating nodes. Moreover, we show that the overhead of secure routing is acceptable and proportional to the fraction of malicious nodes. The paper discusses attacks on structured p2p overlays, including attacks on node identifier assignment, routing table maintenance, and message forwarding. It presents solutions to these problems, including certified node identifiers, constrained routing tables, and secure message forwarding. Certified node identifiers are assigned by a trusted authority and include a public key and IP address. Constrained routing tables ensure that routing table entries point to nodes that are close to a specific point in the id space. Secure message forwarding ensures that messages are delivered to all correct replica roots for a key. The paper also discusses the use of self-certifying data to minimize the overhead of secure routing. It concludes that secure routing is a key building block that can be combined with existing, application-specific security techniques to construct secure, decentralized applications upon structured overlays. The paper evaluates the performance of secure routing in the context of Pastry and shows that the overhead of secure routing is acceptable and proportional to the fraction of malicious nodes.This paper presents secure routing techniques for structured peer-to-peer (p2p) overlay networks. Structured p2p overlays, such as CAN, Chord, Pastry, and Tapestry, provide a self-organizing substrate for large-scale, decentralized applications. These overlays are highly resilient, but current overlays are not secure; even a small fraction of malicious nodes can prevent correct message delivery. This paper studies attacks aimed at preventing correct message delivery in structured p2p overlays and presents defenses to these attacks. We describe and evaluate techniques that allow nodes to join the overlay, maintain routing state, and forward messages securely in the presence of malicious nodes. Secure routing requires (1) a secure assignment of node identifiers, (2) secure routing table maintenance, and (3) secure message forwarding. We present techniques for each of these problems and show how using these techniques, secure routing can be maintained efficiently despite up to 25% of malicious participating nodes. Moreover, we show that the overhead of secure routing is acceptable and proportional to the fraction of malicious nodes. The paper discusses attacks on structured p2p overlays, including attacks on node identifier assignment, routing table maintenance, and message forwarding. It presents solutions to these problems, including certified node identifiers, constrained routing tables, and secure message forwarding. Certified node identifiers are assigned by a trusted authority and include a public key and IP address. Constrained routing tables ensure that routing table entries point to nodes that are close to a specific point in the id space. Secure message forwarding ensures that messages are delivered to all correct replica roots for a key. The paper also discusses the use of self-certifying data to minimize the overhead of secure routing. It concludes that secure routing is a key building block that can be combined with existing, application-specific security techniques to construct secure, decentralized applications upon structured overlays. The paper evaluates the performance of secure routing in the context of Pastry and shows that the overhead of secure routing is acceptable and proportional to the fraction of malicious nodes.