Biblio

Anonymous microblogging platforms, such as Whisper, Yik Yak, and Secret have emerged as important tools for sharing one’s thoughts without fear of judgment by friends, the public, or authorities. These platforms provide anonymity by allowing users to share content (e.g., short messages) with their peers without revealing authorship information to other users. However, recent advances in rumor source detection show that existing messaging protocols, including those used in the mentioned anonymous microblogging applications, leak authorship information when the adversary has global access to metadata. For example, if an adversary can see which users of a messaging service received a particular message, or the timestamps at which a subset of users received a given message, the adversary can infer the message author’s identity with high probability. We introduce a novel anonymous messaging protocol, which we call adaptive diffusion, that is designed to resist such adversaries. We show that adaptive diffusion spreads messages quickly while achieving provably-optimal anonymity guarantees for specific classes of connectivity networks. Simulations on real social network data show that adaptive diffusion effectively hides the location of the source on real-world networks.

Anonymous messaging platforms like Whisper and Yik Yak allow users to spread messages over a network (e.g., a social network) without revealing message authorship to other users. The spread of messages on these platforms can be modeled by a diffusion process over a graph. Recent advances in network analysis have revealed that such diffusion processes are vulnerable to author deanonymization by adversaries with access to metadata, such as timing information. In this work, we ask the fundamental question of how to propagate anonymous messages over a graph to make it difficult for adversaries to infer the source. In particular, we study the performance of a message propagation protocol called adaptive diffusion introduced in (Fanti et al., 2015). We prove that when the adversary has access to metadata at a fraction of corrupted graph nodes, adaptive diffusion achieves asymptotically optimal source-hiding and significantly outperforms standard diffusion. We further demonstrate empirically that adaptive diffusion hides the source effectively on real social networks.
 

Anonymous messaging applications have recently gained popularity as a means for sharing opinions without fear of judgment or repercussion. These messages propagate anonymously over a network, typically de ned by social connections or physical proximity. However, recent advances in rumor source detection show that the source of such an anonymous message can be inferred by certain statistical inference attacks. Adaptive di usion was recently proposed as a solution that achieves optimal source obfuscation over regular trees. However, in real social networks, the degrees difer from node to node, and adaptive di usion can be signicantly sub-optimal. This gap increases as the degrees become more irregular.

In order to quantify this gap, we model the underlying network as coming from standard branching processes with i.i.d. degree distributions. Building upon the analysis techniques from branching processes, we give an analytical characterization of the dependence of the probability of detection achieved by adaptive di usion on the degree distribution. Further, this analysis provides a key insight: passing a rumor to a friend who has many friends makes the source more ambiguous. This leads to a new family of protocols that we call Preferential Attachment Adaptive Di usion (PAAD). When messages are propagated according to PAAD, we give both the MAP estimator for nding the source and also an analysis of the probability of detection achieved by this adversary. The analytical results are not directly comparable, since the adversary's observed information has a di erent distribution under adaptive di usion than under PAAD. Instead, we present results from numerical experiments that suggest that PAAD achieves a lower probability of detection, at the cost of increased communication for coordination.