Anonymous Messaging - July 2016

Public Audience
Purpose: To highlight project progress. Information is generally at a higher level which is accessible to the interested public. All information contained in the report (regions 1-3) is a Government Deliverable/CDRL.

PI(s): Pramod Viswanath

Researcher: Giulia Fanti and Jiaqi Mu

HARD PROBLEM(S) ADDRESSED
This refers to Hard Problems, released November 2012.

Hard problem: Scalability and Composability

Anonymity is a basic right and a core aspect of Internet. Recently, there has been tremendous interest in anonymity and privacy in social networks, motivated by the natural desire to share one's opinions without the fear of judgment or personal reprisal (by parents, authorities, and the public). We propose to study the fundamental questions associated with building such a semi-distributed, anonymous messaging platform, which aims to keep anonymous the identity of the source who initially posted a message as well as the identity of the relays who approved and propagated the message.

PUBLICATIONS
Papers published in this quarter as a result of this research. Include title, author(s), venue published/presented, and a short description or abstract. Identify which hard problem(s) the publication addressed. Papers that have not yet been published should be reported in region 2 below.

[1] G. Fanti, P. Kairouz, S. Oh, K. Ramchandran and P. Viswanath, "Metadata-conscious Anonymous Messaging", International Conference on Machine Learning, (ICML 2016), New York, NY, June 19-24, 2016.

Abstract: Anonymous messaging platforms like Whisper and Yik Yak allow users to spread messages over a network (e.g., a social network) without revealing message authorship to other users. The spread of messages on these platforms can be modeled by a diffusion process over a graph. Recent advances in network analysis have revealed that such diffusion processes are vulnerable to author deanonymization by adversaries with access to metadata, such as timing information. In this work, we ask the fundamental question of how to propagate anonymous messages over a graph to make it difficult for adversaries to infer the source. In particular, we study the performance of a message propagation protocol called adaptive diffusion introduced in (Fanti et al., 2015). We prove that when the adversary has access to metadata at a fraction of corrupted graph nodes, adaptive diffusion achieves asymptotically optimal source-hiding and significantly outperforms standard diffusion. We further demonstrate empirically that adaptive diffusion hides the source effectively on real social networks.

[2] G. Fanti, P. Kairouz, S. Oh, K. Ramchandran and P. Viswanath, "Rumor Source Obfuscation on Irregular Trees", ACM Sigmetrics, 2016Antibes Juan-les-Pins, June 14-18, 2016.

Abstract: Anonymous messaging applications have recently gained popularity as a means for sharing opinions without fear of judgment or repercussion. These messages propagate anonymously over a network, typically defined by social connections or physical proximity. However, recent advances in rumor source detection show that the source of such an anonymous message can be inferred by certain statistical inference attacks. Adaptive diffusion was recently proposed as a solution that achieves optimal source obfuscation over regular trees. However, in real social networks, the degrees differ from node to node, and adaptive diffusion can be significantly sub-optimal. This gap increases as the degrees become more irregular. In order to quantify this gap, we model the underlying network as coming from standard branching processes with i.i.d. degree distributions. Building upon the analysis techniques from branching processes, we give an analytical characterization of the dependence of the probability of detection achieved by adaptive diffusion on the degree distribution. Further, this analysis provides a key insight: passing a rumor to a friend who has many friends makes the source more ambiguous. This leads to a new family of protocols that we call Preferential Attachment Adaptive Diffusion (PAAD). When messages are propagated according to PAAD, we give both the MAP estimator for finding the source and also an analysis of the probability of detection achieved by this adversary. The analytical results are not directly comparable, since the adversary's observed information has a different distribution under adaptive diffusion than under PAAD. Instead, we present results from numerical experiments that suggest that PAAD achieves a lower probability of detection, at the cost of increased communication for coordination.

ACCOMPLISHMENT HIGHLIGHTS

• Fundamental limits to spreading and hiding of messages with and without timestamp meta-data information.