Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming

Abstract

We study the fundamental problem of frequency estimation under both privacy and communication constraints, where the data is distributed among $k$ parties. We consider two application scenarios: (1) one-shot, where the data is static and the aggregator conducts a one-time computation; and (2) streaming, where each party receives a stream of items over time and the aggregator continuously monitors the frequencies. We adopt the model of multiparty differential privacy (MDP), which is more general than local differential privacy (LDP) and (centralized) differential privacy. Our protocols achieve optimality (up to logarithmic factors) permissible by the more stringent of the two constraints. In particular, when specialized to the $\epsilon$-LDP model, our protocol achieves an error of $\sqrt{k}/(e^{\Theta (\epsilon )}-1)$ using $O(k\max \{\epsilon ,\frac{1}{\epsilon }\})$ bits of communication and $O(k\log u)$ bits of public randomness, where $u$ is the size of the domain.

References in corpus (4)

• Local Differential Privacy and Its Applications: A Comprehensive Survey
• Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters
• Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead
• Lossless Compression of Efficient Private Local Randomizers