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 d. Without any security and privacy considerations, each user can communicate their 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) Ω( n logd ) 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 L2 and Linfinty 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.
[ bib | Alternate Version | .pdf ] Back
This file was generated by bibtex2html 1.92.