1 Search Results for "Hendrikx, Hadrien"


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

Authors: Aurélien Bellet, Rachid Guerraoui, and Hadrien Hendrikx

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)


Abstract
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.

Cite as

Aurélien Bellet, Rachid Guerraoui, and Hadrien Hendrikx. Who Started This Rumor? Quantifying the Natural Differential Privacy of Gossip Protocols. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bellet_et_al:LIPIcs.DISC.2020.8,
  author =	{Bellet, Aur\'{e}lien and Guerraoui, Rachid and Hendrikx, Hadrien},
  title =	{{Who Started This Rumor? Quantifying the Natural Differential Privacy of Gossip Protocols}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.8},
  URN =		{urn:nbn:de:0030-drops-130868},
  doi =		{10.4230/LIPIcs.DISC.2020.8},
  annote =	{Keywords: Gossip Protocol, Rumor Spreading, Differential Privacy}
}
  • Refine by Author
  • 1 Bellet, Aurélien
  • 1 Guerraoui, Rachid
  • 1 Hendrikx, Hadrien

  • Refine by Classification
  • 1 Security and privacy → Privacy-preserving protocols

  • Refine by Keyword
  • 1 Differential Privacy
  • 1 Gossip Protocol
  • 1 Rumor Spreading

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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