(June 27) Hiding the Source of a Rumor in Anonymous Messaging

Anonymous messaging platforms, such as Secret, Whisper and Yik Yak, 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, where the right to free expression and sometimes the personal safety of the message author depends on anonymity. Whether for fear of judgment or personal endangerment, it is crucial to keep anonymous the identity of the users who initially posted sensitive messages in these platforms. In this talk, we consider two types of adversaries, one who has a snapshot of the spread of the messages at a certain time and another with collaborating spies among the users tracking all the messages that they receive. We pose the problem of designing a messaging protocol that spreads the message fast while keeping the identity of the source hidden from the adversary. We present an anonymous messaging protocol, which we call adaptive diffusion, and show that it spreads fast and achieves (near) optimal performance in obfuscating the source. In the process, we discover interesting properties of the Polya’s urn processes for enhancing privacy, and prove a new concentration result of Galton-Watson processes to analyze the performance of the proposed protocol.   Joint work with: Giulia Fanti (UIUC), Peter Kairouz (UIUC), Kannan Ramchandran (Berkeley), Pramod Viswanath (UIUC)