2022/11/18 by Weining Chen, Ayfer Özgür, Chen, Wei-Ning +5 · 1 citation
Computer Science · Engineering · #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT) #Privacy-Preserving Technologies in Data #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.2211.10041
openalex publication_date 2022/11/18 · openalex created_date 2022/11/28 · openalex updated_date 2026/07/28
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 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) Ω( n log d ) 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.