Robust Overlays for Privacy-Preserving Data Dissemination over a Social Graph

A number of recently proposed systems provide secure and privacy-preserving data dissemination by leveraging pre-existing social trust relations and effectively mapping them into communication links. However, as we show in this paper, the underlying trust graph may not be optimal as a communication overlay. It has relatively long path lengths and it can be easily partitioned in scenarios where users are unavailable for a fraction of time. Following this observation, we present a method for improving the robustness of trust-based overlays. Essentially, we start with an overlay derived from the trust graph and evolve it in a privacy-preserving fashion into one that lends itself to data dissemination. The experimental evaluation shows that our approach leads to overlays that are significantly more robust under churn, and exhibit lower path lengths than the underlying trust graph.