The communication cost of security and privacy in federated frequency estimation

Wei-Ning Chen, Ayfer Ozgur, Graham Cormode, Akash Bharadwaj
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:4247-4274, 2023.

Abstract

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 nd. Without any security and privacy considerations, each user can communicate its item to the server by using logd bits. A naive application of secure aggregation protocols would, however, require dlogn 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) Ω(nlogd) bits per user are necessary and sufficient to allow the server to compute the frequency distribution. This is significantly smaller than the dlogn bits per user needed by the naive scheme but significantly higher than the logd bits per user needed without security. To achieve differential privacy, we construct a linear scheme based on a noisy sketch that 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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v206-chen23e, title = {The communication cost of security and privacy in federated frequency estimation}, author = {Chen, Wei-Ning and Ozgur, Ayfer and Cormode, Graham and Bharadwaj, Akash}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {4247--4274}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/chen23e/chen23e.pdf}, url = {https://proceedings.mlr.press/v206/chen23e.html}, abstract = {We consider the federated frequency estimation problem, where each user holds a private item $X_i$ 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 $d\log 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) $\Omega\left( 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 $d\log 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 that locally perturbs the data and does not require a trusted server (a.k.a. distributed differential privacy). We analyze this scheme under $\ell_2$ and $\ell_\infty$ 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.} }
Endnote
%0 Conference Paper %T The communication cost of security and privacy in federated frequency estimation %A Wei-Ning Chen %A Ayfer Ozgur %A Graham Cormode %A Akash Bharadwaj %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-chen23e %I PMLR %P 4247--4274 %U https://proceedings.mlr.press/v206/chen23e.html %V 206 %X We consider the federated frequency estimation problem, where each user holds a private item $X_i$ 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 $d\log 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) $\Omega\left( 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 $d\log 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 that locally perturbs the data and does not require a trusted server (a.k.a. distributed differential privacy). We analyze this scheme under $\ell_2$ and $\ell_\infty$ 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.
APA
Chen, W., Ozgur, A., Cormode, G. & Bharadwaj, A.. (2023). The communication cost of security and privacy in federated frequency estimation. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:4247-4274 Available from https://proceedings.mlr.press/v206/chen23e.html.

Related Material