Fundamental Limits of Information-Theoretic Secure Aggregation with User Dropouts in Federated Learning
Authors: Jinbao Zhu, Kai Wan, Giuseppe Caire
Organizations: Information Coding and Transmission (ICT) Key Laboratory of Sichuan Province, Southwest Jiaotong University, Chengdu 611756, China · School of Electronic Information and Communications, Huazhong University of Science and Technology, Wuhan 430074, China · Electrical Engineering and Computer Science Department, Technische Universität Berlin, 10587 Berlin, Germany
Secure aggregation enables a server to compute the sum of users' gradients or model updates without revealing individual values. With user dropouts, correlated random keys protect local gradients while allowing recovery of the desired gradient sum. We consider three phases: key distribution, masked-gradient upload, and mask elimination. Users establish correlated keys, upload masked gradients, and provide additional messages to eliminate residual aggregate masks. Existing information-theoretic schemes typically design mask-elimination communication for a prescribed dropout threshold and evaluate its cost under worst-case dropouts across the masked-gradient upload and mask-elimination phases. Such designs cannot adjust communication to actual dropout scenarios. Moreover, the randomness and communication costs of establishing correlated keys remain largely unexplored. To address these limitations, we formulate an adaptive secure aggregation framework under the T-colluding security constraint and construct a single scheme that supports all feasible dropout scenarios by adapting its communication to the actual number of dropouts. We establish converse bounds on four resources: key randomness, key-distribution communication, masked-gradient communication, and mask-elimination communication. The latter two bounds are characterized for each realized dropout set in the masked-gradient upload phase. The proposed scheme achieves the optimal masked-gradient communication rate for every feasible dropout scenario and the optimal mask-elimination communication rate in almost all feasible regimes. Its key rate and key-distribution communication rate are each optimal or within a factor of two of their respective information-theoretic optima. These results characterize the fundamental randomness and communication costs of secure aggregation with user dropouts.
Figures & tables
Fig. 1: Achievable and converse regions for the key rate RZ and the key-distribution communication rate RK under two representative parameter settings: (N,T)=(6,3) and (N,T)=(10,3) . The blue region is achievable, whereas the green region is ruled out by the converse bounds. The remaining red region represents a gap of at most a factor of two.
TABLE I: Performance comparison between our proposed scheme and the secure aggregation schemes in [ 17 , 18 , 22 ] .
Secure aggregation allows a server to aggregate users' local updates while preserving update privacy. Existing information-theoretic problems typically assume that correlated random keys are provided by a trusted third party (TTP) or generated via prescribed groupwise structures, while the communication cost for establishing such correlated keys is often ignored. Consequently, the fundamental limits under general key-distribution mechanisms remain unknown. In this paper, we study the T-colluding information-theoretic secure aggregation problem with N users under a general two-phase framework consisting of a key distribution phase and an update aggregation phase. Unlike prior work, we model key distribution through user-to-user communication and allow arbitrary user-generated key-distribution mechanisms, eliminating TTP or prescribed structures. This enables a joint characterization of three resources: randomness for security, key-distribution communication, and aggregation communication. We completely characterize the capacity region among these three resources by constructing a novel secure aggregation scheme together with a matching information-theoretic converse. In particular, we develop an explicit deterministic capacity-achieving construction over any finite field of size at least N, whereas most existing schemes either rely on TTP or employ randomized or existential constructions over sufficiently large finite fields. We further show that the optimal performance can be achieved using only pairwise shared keys, enabling implementation via Diffie--Hellman key exchange. Compared with Google's seminal secure aggregation scheme, the proposed scheme requires fewer random masking keys while preserving the same aggregation communication overhead.
Lanxin Yi, Jinbao Zhu, Kai Wan +1
Information Coding and Transmission (ICT) Key Laboratory of Sichuan Province, Southwest Jiaotong University, Chengdu 611756, China · School of Electronic Information and Communications, Huazhong University of Science and Technology, Wuhan 430074, China
Secure aggregation is a vital component for mitigating gradient leakage in federated learning, but its communication cost conventionally scales with the gradient dimension. This becomes prohibitive for large models and even more pronounced in decentralized federated learning with limited bandwidth and unreliable nodes. Top-K gradient sparsification is an effective approach to reduce communication by transmitting only a few entries of the full gradient, while maintaining competitive model accuracy. Nevertheless, the top-K entries selected by each user are unpredictable and vary across users, which poses a challenge for efficient sparse secure aggregation. This paper studies information-theoretic secure aggregation with top-K sparsification in decentralized federated learning under user dropouts and user collusion. We propose a communication-efficient sparse secure aggregation scheme that offloads dimension-dependent overhead to an offline phase and protects private gradients using random masks and permutations. Experimental results demonstrate that our scheme preserves accuracy comparable to full-gradient aggregation even with only 1% gradient sparsification, while substantially reducing the communication cost.
In federated learning (FL), secure aggregation enables a server to compute the sum of local model updates of N clients, without revealing any information on the individual model updates to the server, beyond their sum. Different clients may be subject to heterogeneous bandwidth constraints, and consequently may choose different numbers of quantization levels to represent the information they send. Most secure aggregation works require the clients to project the values of their update parameters to a common finite group (or field), which does not directly accommodate heterogeneous precision constraints on their transmitted masked updates. Existing approaches of secure aggregation with heterogeneous quantization levels reveal partial aggregates of model-updates, and can reveal segments of individual model updates, under certain dropout and client-server collusion patterns. To prevent this privacy breach, we propose an information-theoretic secure aggregation scheme that tolerates client drop-outs, and up to T semi-honest clients that collude with each other and with the server, under heterogeneous quantization at clients. Our protocol utilizes the (T+1,N) threshold black-box secret sharing construction, where secret shares of the client updates, despite belonging to distinct algebraic groups owing to different quantization, are generated from identical linear integer systems.
Shreya Meel, Sennur Ulukus, Itzhak Tamo
Department of Electrical and Computer Engineering, University of Maryland, College Park, MD, USA · Department of Electrical Engineering, Tel Aviv University, Tel Aviv, Israel