  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.
