Information-Theoretic Secure Aggregation With Heterogeneous Client Quantization

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.

Federated learning enables collaborative model training across distributed clients, yet vanilla FL exposes client updates to the central server. Secure-aggregation schemes protect privacy against an honest-but-curious server, but existing approaches often suffer from many communication rounds, heavy public-key operations, or difficulty handling client dropouts. Recent methods like One-Shot Private Aggregation (OPA) cut rounds to a single server interaction per FL iteration, yet they impose substantial cryptographic and computational overhead on both server and clients. We propose a new protocol called DisAgg that leverages a small committee of clients called Aggregators to perform the aggregation itself: each client secret-shares its update vector to Aggregators, which locally compute partial sums and return only aggregated shares for server-side reconstruction. This design eliminates local masking and expensive homomorphic encryption, reducing endpoint computation while preserving privacy against a curious server and a limited fraction of colluding clients. By leveraging optimal trade-offs between communication and computation costs, DisAgg processes 100k-dimensional update vectors from 100k 5G clients with a 4.6x speedup compared to OPA, the previous best protocol.

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.