Hiding the Rumor Source

DOI10.1109/TIT.2017.2696960zbMATH Open1391.94830arXiv1509.02849OpenAlexW2963236534MaRDI QIDQ4566520FDOQ4566520

Authors: Giulia Fanti, Peter Kairouz, Sewoong Oh, Kannan Ramchandran, P. Viswanath 

Publication date: 27 June 2018

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Anonymous social media platforms like Secret, Yik Yak, and Whisper have emerged as important tools for sharing ideas without the fear of judgment. Such anonymous platforms are also important in nations under authoritarian rule, where freedom of expression and the personal safety of message authors may depend on anonymity. Whether for fear of judgment or retribution, it is sometimes crucial to hide the identities of users who post sensitive messages. In this paper, we consider a global adversary who wishes to identify the author of a message; it observes either a snapshot of the spread of a message at a certain time, sampled timestamp metadata, or both. Recent advances in rumor source detection show that existing messaging protocols are vulnerable against such an adversary. We introduce a novel messaging protocol, which we call adaptive diffusion, and show that under the snapshot adversarial model, adaptive diffusion spreads content fast and achieves perfect obfuscation of the source when the underlying contact network is an infinite regular tree. That is, all users with the message are nearly equally likely to have been the origin of the message. When the contact network is an irregular tree, we characterize the probability of maximum likelihood detection by proving a concentration result over Galton-Watson trees. Experiments on a sampled Facebook network demonstrate that adaptive diffusion effectively hides the location of the source even when the graph is finite, irregular and has cycles.

Full work available at URL: https://arxiv.org/abs/1509.02849

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Social networks; opinion dynamics (91D30) Authentication, digital signatures and secret sharing (94A62)

Cited In (7)

• Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
• The String of Diamonds Is Tight for Rumor Spreading
• False modesty: when disclosing good news looks bad
• Correlated randomly growing graphs
• On the robustness of the metric dimension of grid graphs to adding a single edge
• How to discreetly spread a rumor in a crowd
• Who started this rumor? Quantifying the natural differential privacy of gossip protocols

This page was built for publication: Hiding the Rumor Source

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566520)