TY - JOUR
T1 - Hiding the Rumor Source
AU - Fanti, Giulia
AU - Kairouz, Peter
AU - Oh, Sewoong
AU - Ramchandran, Kannan
AU - Viswanath, Pramod
N1 - Funding Information:
Manuscript received August 23, 2016; revised January 25, 2017; accepted April 5, 2017. Date of publication April 24, 2017; date of current version September 13, 2017. This work was supported in part by the NSF CISE under Award CCF-1422278, Award CCF-1553452, and Award CCF-1409135, in part by the SaTC under Award CNS-1527754, in part by ARO under Grant W911NF-14-1-0220, in part by AFOSR under Grant 556016, under Grant NSF CCF-1705007, Grant NSF CCF-1718270, and in part by the Maryland Procurement Office under Contract H98230-14-C-C0141. This work was presented at the 2015 and 2016 ACM Sigmetrics. (Corresponding author: Giulia Fanti.) G. Fanti, P. Kairouz, S. Oh, and P. Viswanath are with the University of Illinois at Urbana–Champaign, Urbana, IL 61801 USA (e-mail: fanti@illinois.edu; kairouz2@illinois.edu; swoh@illinois.edu; pramodv@illinois.edu).
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2017/10
Y1 - 2017/10
N2 - 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 that 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 or 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, is irregular, and has cycles.
AB - 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 that 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 or 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, is irregular, and has cycles.
KW - anonymous social media
KW - diffusion
KW - Privacy
UR - http://www.scopus.com/inward/record.url?scp=85029954788&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85029954788&partnerID=8YFLogxK
U2 - 10.1109/TIT.2017.2696960
DO - 10.1109/TIT.2017.2696960
M3 - Article
AN - SCOPUS:85029954788
SN - 0018-9448
VL - 63
SP - 6679
EP - 6713
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
IS - 10
M1 - 7907223
ER -