FlagThis

Abstract

Secure aggregation is a fundamental component of federated learning that enables a central server to aggregate local model updates from multiple users while preserving the privacy of each individual update without compromising model accuracy. A major bottleneck in scaling federated learning to a large number of users is the communication overhead incurred by secure aggregation, which has motivated the information theory community to study its fundamental limits. To provide privacy guarantees, existing information-theoretic secure aggregation problems typically assume that correlated random keys among users are either provided by a trusted third party (TTP) or generated according to a prescribed symmetric groupwise structure, while the communication cost required to establish such correlated randomness is often ignored. Consequently, the fundamental limits of secure aggregation under general key-distribution mechanisms remain largely unknown. In this paper, we study the T-colluding information-theoretic secure aggregation problem with N users and a single server under a general two-phase framework consisting of a key distribution phase and an update aggregation phase. Unlike prior works, we explicitly model the key distribution phase through user-to-user communication and allow arbitrary key distribution mechanisms established through user cooperation, thereby eliminating the need for a TTP or any prescribed groupwise key-distribution structure. This formulation enables a unified treatment of both phases and allows us to jointly characterize three fundamental resources in secure aggregation: the amount of randomness required for security, the communication required for key distribution, and the communication required for update aggregation. We completely characterize the capacity region among these three resources. Specifically, the optimal key rate and key-distribution communication rate are both N/(N-T), while the optimal aggregation communication rate is N. These optimal rates are simultaneously achieved by 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 a pairwise key-distribution structure, enabling practical realization through standard cryptographic key-establishment mechanisms such as 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.