License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.24
URN: urn:nbn:de:0030-drops-191504
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19150/
Guerraoui, Rachid ;
Kermarrec, Anne-Marie ;
Kucherenko, Anastasiia ;
Pinot, Rafael ;
Voitovych, Sasha
On the Inherent Anonymity of Gossiping
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.
BibTeX - Entry
@InProceedings{guerraoui_et_al:LIPIcs.DISC.2023.24,
author = {Guerraoui, Rachid and Kermarrec, Anne-Marie and Kucherenko, Anastasiia and Pinot, Rafael and Voitovych, Sasha},
title = {{On the Inherent Anonymity of Gossiping}},
booktitle = {37th International Symposium on Distributed Computing (DISC 2023)},
pages = {24:1--24:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-301-0},
ISSN = {1868-8969},
year = {2023},
volume = {281},
editor = {Oshman, Rotem},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19150},
URN = {urn:nbn:de:0030-drops-191504},
doi = {10.4230/LIPIcs.DISC.2023.24},
annote = {Keywords: Gossip protocol, Source anonymity, Differential privacy}
}
|
Keywords: |
|
Gossip protocol, Source anonymity, Differential privacy |
|
Collection: |
|
37th International Symposium on Distributed Computing (DISC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.10.2023 |
