On Distributed Differential Privacy and Counting Distinct Elements

By Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi. 2020

35 citations recorded by the source corpus.

We study the setup where each of $n$ users holds an element from a discrete set, and the goal is to count the number of distinct elements across all users, under the constraint of $(\epsilon, \delta)$-differentially privacy: - In the non-interactive local setting, we prove that the additive error of any protocol is $\Omega(n)$ for any constant $\epsilon$ and for any $\delta$ inverse polynomial in $n$. - In the single-message shuffle setting, we prove a lower bound of $\Omega(n)$ on the error for any constant $\epsilon$ and for some $\delta$ inverse quasi-polynomial in $n$. We do so by building on the moment-matching method from the literature on distribution estimation. - In the multi-message shuffle setting, we give a protocol with at most one message per user in expectation and with an error of $\tilde{O}(\sqrt(n))$ for any constant $\epsilon$ and for any $\delta$ inverse polynomial in $n$. Our protocol is also robustly shuffle private, and our error of $\sqrt(n)$ matches a known lower bound for such protocols. Our proof technique relies on a new notion, that we call dominated protocols, and which can also be used to obtain the first non-trivial lower bounds against multi-message shuffle protocols for the well-studied problems of selection and learning parity. Our first lower bound for estimating the number of distinct elements provides the first $\omega(\sqrt(n))$ separation between global sensitivity and error in local differential privacy, thus answering an open question of Vadhan (2017). We also provide a simple construction that gives $\tilde{\Omega}(n)$ separation between global sensitivity and error in two-party differential privacy, thereby answering an open question of McGregor et al. (2011).

Subfields: Artificial Intelligence, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Privacy & Security

Citations in the corpus

Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “Several works have also extended the study of shuffled model beyond simple aggregation tasks; for example, (Balcer et al., 2021; Chen et al., 2021) considers the count distinct problem whereas (Chang et al.”
The limits of pan privacy and shuffle privacy for learning and estimation (2020, background): “Comparison to the Concurrent Works of [15] and [7].”
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, background): “…histograms and heavy hitters (Ghazi et al., 2021a; Balcer & Cheu, 2020; Ghazi et al., 2020a;b; Cheu & Zhilyaev, 2021), counting distinct elements (Balcer et al., 2021; Chen et al., 2021) and private mean estimation (Girgis et al., 2021), as well as k -means clustering (Chang et al., 2021).”
On the Round Complexity of the Shuffle Model (2020, background): “[14] presented strong impossibility results for 1-round shuffle model protocols.”
On the Power of Multiple Anonymous Messages (2019, unknown): “In subsequent work Chen et al. [28] have extended Theorem 3 to the setting when each user only sends few messages; in particular, they show that if each user sends at most m messages in the shuﬄe model, then the number of users should be Ω p B { m q .”