Document Open Access Logo

On the Inherent Anonymity of Gossiping

Authors Rachid Guerraoui , Anne-Marie Kermarrec , Anastasiia Kucherenko, Rafael Pinot , Sasha Voitovych

PDF
Thumbnail PDF

File

LIPIcs.DISC.2023.24.pdf
  • Filesize: 0.82 MB
  • 19 pages

Document Identifiers

Author Details

Rachid Guerraoui
  • Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Anne-Marie Kermarrec
  • Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Anastasiia Kucherenko
  • Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Rafael Pinot
  • Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Sasha Voitovych
  • University of Toronto, Canada

Acknowledgements

The authors are thankful to Nirupam Gupta and Pierre-Louis Roman for fruitful discussions on the early version of the paper, and to the anonymous reviewers of DISC 2023 for their constructive comments.

Cite As Get BibTex

Rachid Guerraoui, Anne-Marie Kermarrec, Anastasiia Kucherenko, Rafael Pinot, and Sasha Voitovych. On the Inherent Anonymity of Gossiping. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.DISC.2023.24

Abstract

Detecting the source of a gossip is a critical issue, related to identifying patient zero in an epidemic, or the origin of a rumor in a social network. Although it is widely acknowledged that random and local gossip communications make source identification difficult, there exists no general quantification of the level of anonymity provided to the source. This paper presents a principled method based on ε-differential privacy to analyze the inherent source anonymity of gossiping for a large class of graphs. First, we quantify the fundamental limit of source anonymity any gossip protocol can guarantee in an arbitrary communication graph. In particular, our result indicates that when the graph has poor connectivity, no gossip protocol can guarantee any meaningful level of differential privacy. This prompted us to further analyze graphs with controlled connectivity. We prove on these graphs that a large class of gossip protocols, namely cobra walks, offers tangible differential privacy guarantees to the source. In doing so, we introduce an original proof technique based on the reduction of a gossip protocol to what we call a random walk with probabilistic die out. This proof technique is of independent interest to the gossip community and readily extends to other protocols inherited from the security community, such as the Dandelion protocol. Interestingly, our tight analysis precisely captures the trade-off between dissemination time of a gossip protocol and its source anonymity.

Subject Classification

ACM Subject Classification
  • Security and privacy → Privacy-preserving protocols
Keywords
  • Gossip protocol
  • Source anonymity
  • Differential privacy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Huseyin Acan, Andrea Collevecchio, Abbas Mehrabian, and Nick Wormald. On the push&pull protocol for rumor spreading. SIAM Journal on Discrete Mathematics, 31(2):647-668, 2017. URL: https://doi.org/10.1145/2767386.2767416.
  2. David J. Aldous. Lower bounds for covering times for reversible markov chains and random walks on graphs. Journal of Theoretical Probability, 2:91-100, 1989. Google Scholar
  3. Yeganeh Alimohammadi, Christian Borgs, and Amin Saberi. Algorithms using local graph features to predict epidemics. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), 2022. URL: https://doi.org/10.1137/1.9781611977073.136.
  4. Amos Beimel and Shlomi Dolev. Buses for anonymous message delivery. Journal of Cryptology, 16(1), 2003. URL: https://doi.org/10.1007/s00145-002-0128-6.
  5. Aurélien Bellet, Rachid Guerraoui, and Hadrien Hendrikx. Who started this rumor? Quantifying the natural differential privacy of gossip protocols. In International Symposium on Distributed Computing (DISC 2020), 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.8.
  6. Petra Berenbrin, George Giakkoupis, and Peter Kling. Tight bounds for coalescing-branching random walks on regular graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 2018. Google Scholar
  7. Shaileshh Bojja Venkatakrishnan, Giulia Fanti, and Pramod Viswanath. Dandelion: Redesigning the bitcoin network for anonymity. In Proceedings of the ACM on Measurement and Analysis of Computing Systems (SIGMETRICS 2017), 2017. URL: https://doi.org/10.1145/3078505.3078528.
  8. Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6):2508-2530, 2006. URL: https://doi.org/10.1109/TIT.2006.874516.
  9. Yun Chai, Youguo Wang, and Liang Zhu. Information sources estimation in time-varying networks. IEEE Transactions on Information Forensics and Security, 16:2621-2636, 2021. URL: https://doi.org/10.1109/TIFS.2021.3050604.
  10. Nicholas A. Cook, Larry Goldstein, and Tobias Johnson. Size biased couplings and the spectral gap for random regular graphs. Annals of Probability, 46:72-125, 2018. URL: https://doi.org/10.1214/17-AOP1180.
  11. Colin Cooper, Tomasz Radzik, and Nicolas Rivera. The coalescing-branching random walk on expanders and the dual epidemic process. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC 2016), 2016. URL: https://doi.org/10.1145/2933057.2933119.
  12. Colin Cooper, Tomasz Radzik, and Nicolás Rivera. Improved cover time bounds for the coalescing-branching random walk on graphs. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2017), 2017. URL: https://doi.org/10.1145/3087556.3087564.
  13. Edwige Cyffers and Aurélien Bellet. Privacy amplification by decentralization. In International Conference on Artificial Intelligence and Statistics (AIStat 2020), 2020. Google Scholar
  14. Debajyoti Das, Sebastian Meiser, Esfandiar Mohammadi, and Aniket Kate. Anonymity trilemma: Strong anonymity, low bandwidth overhead, low latency-choose two. In IEEE Symposium on Security and Privacy (SP), pages 108-126, 2018. URL: https://doi.org/10.1109/SP.2018.00011.
  15. Damien Desfontaines and Balazs Pejo. Sok: Differential privacies. In Proceedings on Privacy Enhancing Technologies Symposium (PETS 2020), 2020. Google Scholar
  16. Claudia Díaz, Stefaan Seys, Joris Claessens, and Bart Preneel. Towards measuring anonymity. In Privacy Enhancing Technologies, pages 54-68, 2003. Google Scholar
  17. Benjamin Doerr, Mahmoud Fouz, and Tobias Friedrich. Social networks spread rumors in sublogarithmic time. In Proceedings of the forty-third annual ACM symposium on Theory of computing (STOC 2011), 2011. Google Scholar
  18. Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, and Scott Roche. Coalescing-branching random walks on graphs. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2013), 2013. URL: https://doi.org/10.1145/2817830.
  19. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288-323, 1988. URL: https://doi.org/10.1145/42282.42283.
  20. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284, 2006. Google Scholar
  21. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407, 2013. URL: https://doi.org/10.1561/0400000042.
  22. Giulia Fanti, Peter Kairouz, Sewoong Oh, Kannan Ramchandran, and Pramod Viswanath. Rumor source obfuscation on irregular trees. In International Conference on Measurement and Modeling of Computer Systems, (SIGMETRICS 2016), 2016. URL: https://doi.org/10.1145/2896377.2901471.
  23. Giulia Fanti, Peter Kairouz, Sewoong Oh, Kannan Ramchandran, and Pramod Viswanath. Hiding the rumor source. IEEE Transactions on Information Theory, 63(10):6679-6713, 2017. URL: https://doi.org/10.1109/TIT.2017.2696960.
  24. Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz R Kowalski. Asynchronous gossip. Journal of the ACM, 60(2):1-42, 2013. URL: https://doi.org/10.1145/2450142.2450147.
  25. Chryssis Georgiou, Seth Gilbert, and Dariusz R. Kowalski. Confidential gossip. In International Conference on Distributed Computing Systems (DISC 2011), 2011. URL: https://doi.org/10.1109/ICDCS.2011.71.
  26. George Giakkoupis, Rachid Guerraoui, Arnaud Jégou, Anne-Marie Kermarrec, and Nupur Mittal. Privacy-conscious information diffusion in social networks. In International Symposium on Distributed Computing (DISC 2015), 2015. Google Scholar
  27. Karol Gotfryd, Marek Klonowski, and Dominik Pająk. On location hiding in distributed systems. In Structural Information and Communication Complexity, pages 174-192, 2017. Google Scholar
  28. Rachid Guerraoui, Anne-Marie Kermarrec, Anastasiia Kucherenko, Rafael Pinot, and Sasha Voitovych. On the Inherent Anonymity of Gossiping (Full Version), 2023. URL: https://arxiv.org/abs/2308.02477.
  29. Zeyu Guo and He Sun. Gossip vs. markov chains, and randomness-efficient rumor spreading. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 2014. Google Scholar
  30. Herbert W Hethcote. The mathematics of infectious diseases. SIAM review, 42(4):599-653, 2000. URL: https://doi.org/10.1137/S0036144500371907.
  31. Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C Pierce, and Aaron Roth. Differential privacy: An economic method for choosing epsilon. In IEEE 27th Computer Security Foundations Symposium, pages 398-410, 2014. Google Scholar
  32. Yufan Huang, Richeng Jin, and Huaiyu Dai. Differential privacy and prediction uncertainty of gossip protocols in general networks. In IEEE Global Communications Conference (GLOBECOM 2020), 2020. URL: https://doi.org/10.1109/GLOBECOM42002.2020.9322558.
  33. Jiaojiao Jiang, Sheng Wen, Shui Yu, Yang Xiang, and Wanlei Zhou. Identifying propagation sources in networks: State-of-the-art and comparative studies. IEEE Communications Surveys & Tutorials, 19(1):465-481, 2017. URL: https://doi.org/10.1109/COMST.2016.2615098.
  34. Richard Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vocking. Randomized rumor spreading. In 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), 2000. URL: https://doi.org/10.1109/SFCS.2000.892324.
  35. John G Kemeny and J Laurie Snell. Finite markov chains. Springer New York, NY, 1960. Google Scholar
  36. Daniel Kifer and Ashwin Machanavajjhala. Pufferfish: A framework for mathematical privacy definitions. ACM Transactions on Database Systems (TODS), 39(1):1-36, 2014. URL: https://doi.org/10.1145/2514689.
  37. István Z Kiss, Joel C Miller, Péter L Simon, et al. Mathematics of epidemics on networks. Cham: Springer, 598:31, 2017. Google Scholar
  38. Dariusz R Kowalski and Christopher Thraves Caro. Estimating time complexity of rumor spreading in ad-hoc networks. In International Conference on Ad-Hoc Networks and Wireless (ADHOC-NOW 2013), 2013. Google Scholar
  39. Jaewoo Lee and Chris Clifton. How much is enough? Choosing ε for differential privacy. In Information Security: 14th International Conference, pages 325-340, 2011. Google Scholar
  40. Friedrich Liese and Igor Vajda. On divergences and informations in statistics and information theory. IEEE Transactions on Information Theory, 52(10):4394-4412, 2006. URL: https://doi.org/10.1109/TIT.2006.881731.
  41. Xuecheng Liu, Luoyi Fu, Bo Jiang, Xiaojun Lin, and Xinbing Wang. Information source detection with limited time knowledge. In Proceedings of the Twentieth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2019), pages 389-390, 2019. URL: https://doi.org/10.1145/3323679.3326626.
  42. Yang Liu, Junfeng Wu, Ian R. Manchester, and Guodong Shi. Gossip algorithms that preserve privacy for distributed computation part I: The algorithms and convergence conditions. In IEEE Conference on Decision and Control (CDC 2018), 2018. URL: https://doi.org/10.1109/CDC.2018.8619783.
  43. Guy Melancon. Just how dense are dense graphs in the real world? A methodological note. In Proceedings of the AVI Workshop on BEyond Time and Errors: Novel Evaluation Methods for Information Visualization (BELIV 2006), 2006. URL: https://doi.org/10.1145/1168149.1168167.
  44. Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEE, 2017. URL: https://doi.org/10.1109/CSF.2017.11.
  45. Michael Mitzenmacher, Rajmohan Rajaraman, and Scott Roche. Better bounds for coalescing-branching random walks. ACM Transactions on Parallel Computing, 5(1):1-23, 2018. URL: https://doi.org/10.1145/3209688.
  46. Pedro C. Pinto, Patrick Thiran, and Martin Vetterli. Locating the source of diffusion in large-scale networks. Physical Review Letters, 109(6), 2012. URL: https://doi.org/10.1103/PhysRevLett.109.068702.
  47. Boris Pittel. On spreading a rumor. SIAM Journal on Applied Mathematics, 47(1):213-223, 1987. URL: https://doi.org/10.1137/0147013.
  48. Michael K Reiter and Aviel D Rubin. Crowds: Anonymity for web transactions. ACM transactions on information and system security (TISSEC), 1(1):66-92, 1998. URL: https://doi.org/10.1145/290163.290168.
  49. D. Shah and T. Zaman. Rumors in a network: Who’s the culprit? IEEE Transactions on Information Theory, 57(8):5163-5181, 2011. URL: https://doi.org/10.1109/TIT.2011.2158885.
  50. Devavrat Shah and Tauhid Zaman. Detecting sources of computer viruses in networks: Theory and experiment. In Proceedings of ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2010), 2010. Google Scholar
  51. Robin Snader and Nikita Borisov. A tune-up for tor: Improving security and performance in the tor network. In Network and Distributed System Security Symposium (NDSS 2008), 2008. Google Scholar
  52. Konstantin E. Tikhomirov and Pierre Youssef. The spectral gap of dense random regular graphs. The Annals of Probability, 2019. Google Scholar
  53. Parv Venkitasubramaniam and Venkat Anantharam. Anonymity under light traffic conditions using a network of mixes. In 46th Annual Allerton Conference on Communication, Control, and Computing (ALLERTON 2008), 2008. URL: https://doi.org/10.1109/ALLERTON.2008.4797721.
  54. Matthew K. Wright, Micah Adler, Brian Neil Levine, and Clay Shields. An analysis of the degradation of anonymous protocols. In Network and Distributed System Security Symposium (NDSS 2002), 2002. Google Scholar
  55. Yi Yu, Tengyao Wang, and Richard J. Samworth. A useful variant of the Davis-Kahan theorem for statisticians. Biometrika, 102:315-323, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact