  Friend-to-friend (F2F) overlays, which restrict direct communication to
mutually trusted parties, are a promising substrate for privacy-preserving
communication due to their inherent membership-concealment and
Sybil-resistance. Yet, existing F2F overlays suffer from a low performance, are
vulnerable to denial-of-service attacks, or fail to provide anonymity. In
particular, greedy embeddings allow highly efficient communication in arbitrary
connectivity-restricted overlays but require communicating parties to reveal
their identity. In this paper, we present a privacy-preserving routing scheme
for greedy embeddings based on anonymous return addresses rather than
identifying node coordinates. We prove that the presented algorithm are highly
scalalbe, with regard to the complexity of both the routing and the
stabilization protocols. Furthermore, we show that the return addresses provide
plausible deniability for both sender and receiver. We further enhance the
routing's resilience by using multiple embeddings and propose a method for
efficient content addressing. Our simulation study on real-world data indicates
that our approach is highly efficient and effectively mitigates failures as
well as powerful denial-of-service attacks.
