# The communication cost of security and privacy in federated frequency estimation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2022.

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

- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Private Federated Frequency Estimation: Adapting to the Hardness of the Instance](https://mlsanity.com/paper/2306.09396/) (2023)

## Abstract (arXiv)

We consider the federated frequency estimation problem, where each user holds a private item Xi from a size-d domain and a server aims to estimate the empirical frequency (i.e., histogram) of n items with n ll d. Without any security and privacy considerations, each user can communicate its item to the server by using log d bits. A naive application of secure aggregation protocols would, however, require dlog n bits per user. Can we reduce the communication needed for secure aggregation, and does security come with a fundamental cost in communication? In this paper, we develop an information-theoretic model for secure aggregation that allows us to characterize the fundamental cost of security and privacy in terms of communication. We show that with security (and without privacy) Omegaleft( n log d right) bits per user are necessary and sufficient to allow the server to compute the frequency distribution. This is significantly smaller than the dlog n bits per user needed by the naive scheme, but significantly higher than the log d bits per user needed without security. To achieve differential privacy, we construct a linear scheme based on a noisy sketch which locally perturbs the data and does not require a trusted server (a.k.a. distributed differential privacy). We analyze this scheme under ℓ2 and ℓ_∞ loss. By using our information-theoretic framework, we show that the scheme achieves the optimal accuracy-privacy trade-off with optimal communication cost, while matching the performance in the centralized case where data is stored in the central server.