Hiding the Rumor Source

Giulia Fanti, Peter Kairouz, Sewoong Oh, Kannan Ramchandran, Pramod Viswanath

Research output: Contribution to journalArticle

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 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.

Original languageEnglish (US)
Article number7907223
Pages (from-to)6679-6713
Number of pages35
JournalIEEE Transactions on Information Theory
Volume63
Issue number10
DOIs
StatePublished - Oct 2017

Fingerprint

rumor
contact
anxiety
anonymity
facebook
Metadata
social media
Maximum likelihood
experiment
Experiments

Keywords

  • Privacy
  • anonymous social media
  • diffusion

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this

Fanti, G., Kairouz, P., Oh, S., Ramchandran, K., & Viswanath, P. (2017). Hiding the Rumor Source. IEEE Transactions on Information Theory, 63(10), 6679-6713. [7907223]. https://doi.org/10.1109/TIT.2017.2696960

Hiding the Rumor Source. / Fanti, Giulia; Kairouz, Peter; Oh, Sewoong; Ramchandran, Kannan; Viswanath, Pramod.

In: IEEE Transactions on Information Theory, Vol. 63, No. 10, 7907223, 10.2017, p. 6679-6713.

Research output: Contribution to journalArticle

Fanti, G, Kairouz, P, Oh, S, Ramchandran, K & Viswanath, P 2017, 'Hiding the Rumor Source', IEEE Transactions on Information Theory, vol. 63, no. 10, 7907223, pp. 6679-6713. https://doi.org/10.1109/TIT.2017.2696960
Fanti G, Kairouz P, Oh S, Ramchandran K, Viswanath P. Hiding the Rumor Source. IEEE Transactions on Information Theory. 2017 Oct;63(10):6679-6713. 7907223. https://doi.org/10.1109/TIT.2017.2696960
Fanti, Giulia ; Kairouz, Peter ; Oh, Sewoong ; Ramchandran, Kannan ; Viswanath, Pramod. / Hiding the Rumor Source. In: IEEE Transactions on Information Theory. 2017 ; Vol. 63, No. 10. pp. 6679-6713.
@article{63c910f7d382435886b516157174a7f7,
title = "Hiding the Rumor Source",
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 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.",
keywords = "Privacy, anonymous social media, diffusion",
author = "Giulia Fanti and Peter Kairouz and Sewoong Oh and Kannan Ramchandran and Pramod Viswanath",
year = "2017",
month = "10",
doi = "10.1109/TIT.2017.2696960",
language = "English (US)",
volume = "63",
pages = "6679--6713",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "10",

}

TY - JOUR

T1 - Hiding the Rumor Source

AU - Fanti, Giulia

AU - Kairouz, Peter

AU - Oh, Sewoong

AU - Ramchandran, Kannan

AU - Viswanath, Pramod

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 - Privacy

KW - anonymous social media

KW - diffusion

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

VL - 63

SP - 6679

EP - 6713

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 10

M1 - 7907223

ER -