Skip to Main content Skip to Navigation
Conference papers

Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols

Aurélien Bellet 1 Rachid Guerraoui 2 Hadrien Hendrikx 3, 4, 5, 6, 7
1 MAGNET - Machine Learning in Information Networks
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
6 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
7 DYOGENE - Dynamics of Geometric Networks
Inria de Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, DI-ENS - Département d'informatique de l'École normale supérieure
Abstract : Gossip protocols are widely used to disseminate information in massive peer-to-peer networks. These protocols are often claimed to guarantee privacy because of the uncertainty they introduce on the node that started the dissemination. But is that claim really true? Can the source of a gossip safely hide in the crowd? This paper examines, for the first time, gossip protocols through a rigorous mathematical framework based on differential privacy to determine the extent to which the source of a gossip can be traceable. Considering the case of a complete graph in which a subset of the nodes are curious, we study a family of gossip protocols parameterized by a ``muting'' parameter s: nodes stop emitting after each communication with a fixed probability 1-s. We first prove that the standard push protocol, corresponding to the case s=1, does not satisfy differential privacy for large graphs. In contrast, the protocol with s=0 achieves optimal privacy guarantees but at the cost of a drastic increase in the spreading time compared to standard push, revealing an interesting tension between privacy and spreading time. Yet, surprisingly, we show that some choices of the muting parameter s lead to protocols that achieve an optimal order of magnitude in both privacy and speed. We also confirm empirically that, with appropriate choices of s, we indeed obtain protocols that are very robust against concrete source location attacks while spreading the information almost as fast as the standard (and non-private) push protocol.
Complete list of metadatas
Contributor : Aurélien Bellet <>
Submitted on : Wednesday, January 6, 2021 - 2:50:04 PM
Last modification on : Thursday, January 7, 2021 - 3:41:18 AM


1902.07138 (1).pdf
Files produced by the author(s)


  • HAL Id : hal-02166432, version 2


Aurélien Bellet, Rachid Guerraoui, Hadrien Hendrikx. Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols. DISC 2020 - 34th International Symposium on Distributed Computing, Oct 2020, Freiburg / Virtual, Germany. ⟨hal-02166432v2⟩



Record views


Files downloads