Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Who Started This Rumor? Quantifying the Natural Differential Privacy of Gossip Protocols
 
conference paper

Who Started This Rumor? Quantifying the Natural Differential Privacy of Gossip Protocols

Bellet, Aurélien
•
Guerraoui, Rachid  
•
Hendrikx, Hadrien
2020
Proceedings of the 34th International Symposium on Distributed Computing (DISC 2020)
34th International Symposium on Distributed Computing (DISC 2020)

Gossip protocols (also called rumor spreading or epidemic 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 (nodes forward only once) 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. Privacy guarantees are obtained by showing that only a small fraction of the possible observations by curious nodes have different probabilities when two different nodes start the gossip, since the source node rapidly stops emitting when s is small. The speed is established by analyzing the mean dynamics of the protocol, and leveraging concentration inequalities to bound the deviations from this mean behavior. We also confirm empirically that, with appropriate choices of s, we indeed obtain protocols that are very robust against concrete source location attacks (such as maximum a posteriori estimates) while spreading the information almost as fast as the standard (and non-private) push protocol. LIPIcs, Vol. 179, 34th International Symposium on Distributed Computing (DISC 2020), pages 8:1-8:18

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.4230/lipics.disc.2020.8
Author(s)
Bellet, Aurélien
Guerraoui, Rachid  
Hendrikx, Hadrien
Date Issued

2020

Publisher

Schloss Dagstuhl, Leibniz-Zentrum

Publisher place

Dagstuhl

Published in
Proceedings of the 34th International Symposium on Distributed Computing (DISC 2020)
ISBN of the book

978-3-959771-68-9

Series title/Series vol.

Leibniz International Proceedings in Informatics (LIPIcs)

Note

Licensed under Creative Commons License CC-BY.

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event nameEvent date
34th International Symposium on Distributed Computing (DISC 2020)

October 15, 2020

Available on Infoscience
October 7, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/172272
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés