Social media platforms for anonymous messaging allow users to express their thoughts without judgment from others. Such is particularly important in authoritarian environments where free expression requires anonymity. This paper looks at an adversary in the current context of rumor detection and the vulnerability of current messaging protocols. A new messaging protocol, adaptive diffusion, is shown to propagate messages quickly with perfect source obfuscation when the contact network is infinite and a regular tree. All users are likely to have originated the message. Facebook experiments show effective source hiding even for graphs that are finite, irregular, or with cycles.

A very significant introductory section lays the foundation for the subject at hand, and then the second section provides two illustrative examples to cover key background ideas and analysis. The authors’ adaptive diffusion messaging protocol is presented along with some theoretical results in the third section; more general contact networks are addressed next as the protocol is extended to real-world networks. The paper closes with a brief discussion of the protocol’s significance. Appropriate references are included, and a multipage appendix provides proofs for material in the body of the paper.

This carefully presented paper is important for researchers and practitioners in the world of anonymous messaging. Numerous figures as well as pseudocode and mathematical details strengthen the presentation and provide key insights.