On Distributed Differential Privacy and Counting Distinct Elements

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 local setting, we prove that the additive error of any protocol is Omega(n) for any constant epsilon and any delta inverse polynomial in n. This provides the first separation between global sensitivity and error that is omega(sqrt{n}) in local differential privacy, thus answering a question of Vadhan (2017). - In the single-message shuffle setting, we prove a lower bound of tilde{Omega}(n) on the error for any constant epsilon and for some delta inverse quasi-polynomial in n. We do so using the moment-matching method from the literature on distribution estimation. - In the multi-message shuffle setting, we give a protocol with <= 1 message per user in expectation and with an error of tilde{O}(sqrt{n}) for any constant epsilon and delta inverse polynomial in n. Our proof technique relies on a new notion, that we call dominated protocols, and which can be used to obtain the first non-trivial lower bounds against multi-message shuffle protocols for the well-studied problems of Selection and Parity Learning.

• Algorithms and Theory

• Security, Privacy and Abuse Prevention