# On Distributed Differential Privacy and Counting Distinct Elements

arXiv: https://arxiv.org/abs/2009.09604 · HTML: https://mlsanity.com/paper/2009.09604/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Sep 2020.

## Built on by (most cited first, 8 of 8)

- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Privacy Amplification via Shuffling for Linear Contextual Bandits](https://mlsanity.com/paper/2112.06008/) (2021)
- [Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages](https://mlsanity.com/paper/2404.10201/) (2024)
- [Differentially Private Multi-Site Treatment Effect Estimation](https://mlsanity.com/paper/2310.06237/) (2023)
- [Learning from End User Data with Shuffled Differential Privacy over Kernel Densities](https://mlsanity.com/paper/2502.14087/) (2025)
- [The Sample Complexity of Distribution-Free Parity Learning in the Robust Shuffle Model](https://mlsanity.com/paper/2103.15690/) (2021)
- [Anonymized Histograms in Intermediate Privacy Models](https://mlsanity.com/paper/2210.15178/) (2022)
- [Near-optimal Differentially Private Client Selection in Federated Settings](https://mlsanity.com/paper/2310.09370/) (2023)

## Abstract (arXiv)

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 (ε, δ)-differentially privacy: - In the non-interactive local setting, we prove that the additive error of any protocol is Omega(n) for any constant ε and for any δ inverse polynomial in n. - In the single-message shuffle setting, we prove a lower bound of Omega(n) on the error for any constant ε and for some δ 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 tildeO(√(n)) for any constant ε and for any δ inverse polynomial in n. Our protocol is also robustly shuffle private, and our error of √(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 ω(√(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 tildeOmega(n) separation between global sensitivity and error in two-party differential privacy, thereby answering an open question of McGregor et al. (2011).