  Anonymous messaging platforms, such as Secret and Whisper, have emerged as
important social media for sharing one's thoughts without the fear of being
judged by friends, family, or the public. Further, such anonymous platforms are
crucial in nations with authoritarian governments; the right to free expression
and sometimes the personal safety of the author of the message depend on
anonymity. Whether for fear of judgment or personal endangerment, it is crucial
to keep anonymous the identity of the user who initially posted a sensitive
message. In this paper, we consider an adversary who observes a snapshot of the
spread of a message at a certain time. Recent advances in rumor source
detection shows that the existing messaging protocols are vulnerable against
such an adversary. We introduce a novel messaging protocol, which we call
adaptive diffusion, and show that it spreads the messages fast and achieves a
perfect obfuscation of the source when the underlying contact network is an
infinite regular tree: all users with the message are nearly equally likely to
have been the origin of the message. Experiments on a sampled Facebook network
show that it effectively hides the location of the source even when the graph
is finite, irregular and has cycles. We further consider a stronger adversarial
model where a subset of colluding users track the reception of messages. We
show that the adaptive diffusion provides a strong protection of the anonymity
of the source even under this scenario.
