Hiding the Source of a Rumor in Anonymous Messaging

Tuesday, November 17, 2015 - 4:00pm to Wednesday, November 18, 2015 - 3:55pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Sewoong Oh

Affiliation

University of Illinois

Building and Room Number

32-141

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. 

Sewoong Oh is an Assistant Professor of Industrial and Enterprise Systems Engineering at UIUC. He received his PhD from the department of Electrical Engineering at Stanford University in 2011. Following his PhD, he worked as a postdoctoral researcher at Laboratory for Information and Decision Systems (LIDS) at MIT. He was co-awarded the Kenneth C. Sevcik outstanding student paper award at the Sigmetrics 2010 and the best paper award at the SIGMETRICS 2015.