Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Who started this rumor? Quantifying the natural differential privacy
  guarantees of gossip protocols   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.

13
The categories of this paper are: quant-ph
5
The categories of this paper are: gr-qc
29
The categories of this paper are: funct-an
0
The categories of this paper are: hep-ph
31
The categories of this paper are: ao-sci
7
The categories of this paper are: hep-th
9
The categories of this paper are: nlin
18
The categories of this paper are: econ
24
The categories of this paper are: dg-ga
27
The categories of this paper are: comp-gas
26
The categories of this paper are: bayes-an
32
The categories of this paper are: atom-ph
15
The categories of this paper are: nucl-ex
34
The categories of this paper are: chem-ph
11
The categories of this paper are: hep-lat
17
The categories of this paper are: q-fin