Metadata-conscious anonymous messaging

Giulia Fanti, Peter Kairouz, Sewoong Oh, Kannan Ramchandran, Pramod Viswanath
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:108-116, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-fanti16, title = {Metadata-conscious anonymous messaging}, author = {Fanti, Giulia and Kairouz, Peter and Oh, Sewoong and Ramchandran, Kannan and Viswanath, Pramod}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {108--116}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/fanti16.pdf}, url = {https://proceedings.mlr.press/v48/fanti16.html}, 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.} }
Endnote
%0 Conference Paper %T Metadata-conscious anonymous messaging %A Giulia Fanti %A Peter Kairouz %A Sewoong Oh %A Kannan Ramchandran %A Pramod Viswanath %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-fanti16 %I PMLR %P 108--116 %U https://proceedings.mlr.press/v48/fanti16.html %V 48 %X 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.
RIS
TY - CPAPER TI - Metadata-conscious anonymous messaging AU - Giulia Fanti AU - Peter Kairouz AU - Sewoong Oh AU - Kannan Ramchandran AU - Pramod Viswanath BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-fanti16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 108 EP - 116 L1 - http://proceedings.mlr.press/v48/fanti16.pdf UR - https://proceedings.mlr.press/v48/fanti16.html AB - 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. ER -
APA
Fanti, G., Kairouz, P., Oh, S., Ramchandran, K. & Viswanath, P.. (2016). Metadata-conscious anonymous messaging. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:108-116 Available from https://proceedings.mlr.press/v48/fanti16.html.

Related Material