arxiv: 2604.26391 · v1 · submitted 2026-04-29 · 💻 cs.IT · math.IT

Recognition: unknown

Multi-Server Secure Aggregation with Arbitrary Collusion and Heterogeneous Security Constraints

Giuseppe Caire, Jiguang He, Xiang Zhang, Zhou Li

Authors on Pith no claims yet

Pith reviewed 2026-05-07 12:45 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords secure aggregationmulti-serverheterogeneous securityinformation theoretic securitytwo-hop networkarbitrary collusioncommunication ratekey rate

0 comments

The pith

Multi-server secure aggregation rates and key requirements are fully characterized for heterogeneous security constraints in two-hop networks.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the exact communication rates needed for multiple servers to compute the sum of user inputs while protecting different prescribed subsets of those inputs from arbitrary user-server collusions. It provides matching lower bounds and achievable schemes for most parameter settings and a bounded-gap result for the rest. This matters because real-world distributed systems often have uneven privacy needs across data subsets rather than uniform protection levels. A reader would care as the results quantify precisely how network topology and varying security demands set the minimum communication and randomness costs.

Core claim

We characterize the communication rates for all parameter regimes, and determine the minimum key rate required for secure aggregation in most regimes. In particular, we establish tight information-theoretic lower bounds and matching achievable schemes in a broad class of regimes. For the remaining regime, we derive a general lower bound together with an achievable scheme that attains it within a bounded gap.

What carries the argument

The two-hop network with servers each linked to disjoint user subsets, together with heterogeneous security constraints that specify which input subsets must stay hidden from colluding servers and users.

Load-bearing premise

The model assumes information-theoretic security must hold against any user collusion with the servers while the heterogeneous constraints are given as fixed subsets of inputs that cannot leak beyond the aggregate.

What would settle it

A concrete small instance with two servers, four users, and one specific heterogeneous security pattern where either the observed communication rate falls below the derived lower bound or the key rate exceeds the claimed minimum by more than the bounded gap.

Figures

Figures reproduced from arXiv: 2604.26391 by Giuseppe Caire, Jiguang He, Xiang Zhang, Zhou Li.

**Figure 1.** Figure 1: Multi-server secure aggregation with U = 3 servers and V1 = 3, V2 = V3 = 2 users per server. Each server computes the sum of all users’ inputs W1,1 +W1,2 +W1,3 +W2,1 +W2,2 +W3,1 +W3,2 without revealing the inputs in the security sets S, even if users in the colluding sets T cooperate. The security sets are S = (∅, {(1, 1)}, {(2, 1)}, {(1, 1),(2, 1)}), and the possible colluding sets T include all combinati… view at source ↗

read the original abstract

We study the fundamental limits of multi-server secure aggregation over a two-hop network where multiple servers, each connected to a disjoint subset of users, jointly compute the sum of all users' inputs. The goal is to ensure that no server can infer any information about prescribed subsets of inputs beyond the desired aggregate, even when colluding with an arbitrary subset of users. Existing works largely focus on homogeneous security requirements, where all inputs are protected against colluding sets up to a given size. Such formulations are insufficient to capture more general scenarios in which different subsets of inputs may require protection against different collusion patterns. In this paper, we consider a general model with heterogeneous security requirements and arbitrary user collusion. We characterize the communication rates for all parameter regimes, and determine the minimum key rate required for secure aggregation in most regimes. In particular, we establish tight information-theoretic lower bounds and matching achievable schemes in a broad class of regimes. For the remaining regime, we derive a general lower bound together with an achievable scheme that attains it within a bounded gap. Our results reveal how the interplay between network topology and heterogeneous security constraints fundamentally determines the communication and key generation requirements, and generalize existing results on secure aggregation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper delivers a full rate characterization for multi-server secure aggregation under heterogeneous security constraints and arbitrary collusion, with tight matches in most regimes.

read the letter

The paper gives a complete picture of the communication and key rates needed for multi-server secure aggregation when different subsets of inputs have different security requirements against arbitrary user collusion. It extends the homogeneous case by allowing arbitrary collusion patterns and heterogeneous hiding sets in the two-hop network with disjoint server connections. The main contribution is tight information-theoretic lower bounds matched by achievable schemes in a broad class of regimes, plus a bounded-gap result for the remaining cases. This reveals the interplay between the network topology and the security constraints, generalizing earlier work. The derivations use standard techniques: outer bounds from mutual information that incorporate the topology and security model, and inner bounds via coding that respects the partitions. Nothing indicates circularity or post-hoc choices. The regime split appears clean. A minor limitation is the bounded gap in one regime, which might be closable with more work, but the paper is transparent about it. Overall the argument holds up. This is for people studying privacy in federated or distributed computation from an information theory angle. A reader interested in exact rate regions for secure protocols would get value here. It deserves serious peer review because the results are sharp enough to matter in the subfield.

Referee Report

0 major / 2 minor

Summary. The paper studies multi-server secure aggregation over a two-hop network in which servers connect to disjoint user subsets and jointly compute the sum of all user inputs. It incorporates heterogeneous security constraints (prescribed subsets of inputs that must remain hidden) and arbitrary user collusion with servers. The central claims are a complete characterization of the communication rates across all parameter regimes, tight information-theoretic lower bounds matched by achievable schemes (via linear coding or secret sharing) for the minimum key rate in most regimes, and a general lower bound plus a bounded-gap scheme in the residual regime. The results generalize prior homogeneous-security work by showing the interplay between topology and heterogeneous constraints.

Significance. If the derivations hold, the work makes a solid contribution by moving beyond homogeneous collusion thresholds to a general heterogeneous model while delivering exact rate characterizations in broad regimes. The pairing of standard mutual-information outer bounds (incorporating the two-hop disjoint partitions and hiding sets) with explicit inner-bound constructions is a strength, as is the regime-partitioning approach that isolates the bounded-gap case. This advances the information-theoretic understanding of secure aggregation and provides concrete guidance on how network structure and security prescriptions jointly determine communication and key-generation costs.

minor comments (2)

[Main theorem / Section on residual regime] The abstract states that the scheme attains the lower bound 'within a bounded gap' in the residual regime; the main theorem statement should explicitly identify the gap factor (e.g., a constant multiplier on the key rate) rather than leaving it implicit.
[Model section] Notation for the heterogeneous hiding sets and the arbitrary-collusion model should be introduced with a small illustrative example early in the model section to aid readability before the general rate expressions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, the accurate summary of our contributions on multi-server secure aggregation with heterogeneous security constraints and arbitrary collusion, and the recommendation for minor revision. We are pleased that the generalization beyond homogeneous models, the regime-partitioning approach, and the pairing of mutual-information outer bounds with explicit constructions are recognized as strengths.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives its communication rate characterizations and key-rate bounds directly from standard information-theoretic outer bounds (mutual-information inequalities incorporating the two-hop topology, disjoint server-user partitions, and prescribed heterogeneous hiding sets) paired with explicit inner-bound constructions via linear coding and secret sharing. These steps are self-contained within the model assumptions stated in the abstract and do not reduce to fitted parameters, self-definitions, or load-bearing self-citations; the regime partitioning and gap analysis follow from the same first-principles inequalities without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard information-theoretic security definitions and the stated network topology; no new free parameters, invented entities, or ad-hoc axioms appear in the abstract.

axioms (2)

standard math Information-theoretic security defined via mutual information (no information leakage beyond the aggregate)
Invoked to formalize that servers learn nothing about prescribed input subsets.
domain assumption Two-hop network with servers connected to disjoint user subsets
Defines the communication topology used for all rate calculations.

pith-pipeline@v0.9.0 · 5512 in / 1318 out tokens · 26334 ms · 2026-05-07T12:45:01.700472+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

39 extracted references · 17 canonical work pages · 1 internal anchor

[1]

Federated Learning: Strategies for Improving Communication Efficiency

J. Konecn `y, H. B. McMahan, F. X. Yu, P. Richt ´arik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,”arXiv preprint arXiv:1610.05492, vol. 8, 2016

work page internal anchor Pith review arXiv 2016
[2]

Advances and open problems in federated learning,

P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings et al., “Advances and open problems in federated learning,”Foundations and trends® in machine learning, vol. 14, no. 1–2, pp. 1–210, 2021

2021
[3]

Communication-efficient learning of deep networks from decentralized data,

B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” inArtificial intelligence and statistics. PMLR, 2017, pp. 1273–1282

2017
[4]

Applied federated learning: Improving google keyboard query suggestions,

T. Yang, G. Andrew, H. Eichner, H. Sun, W. Li, N. Kong, D. Ramage, and F. Beaufays, “Applied federated learning: Improving google keyboard query suggestions,”arXiv preprint arXiv:1812.02903, 2018

work page arXiv 2018
[5]

Deep leakage from gradients,

L. Zhu, Z. Liu, and S. Han, “Deep leakage from gradients,” inAdvances in Neural Information Processing Systems, vol. 33, 2020, pp. 14 774–14 784

2020
[6]

Inverting gradients-how easy is it to break privacy in federated learning?

J. Geiping, H. Bauermeister, H. Dr ¨oge, and M. Moeller, “Inverting gradients-how easy is it to break privacy in federated learning?” Advances in neural information processing systems, vol. 33, pp. 16 937–16 947, 2020

2020
[7]

Practical Secure Aggregation for Federated Learning on User-Held Data

K. Bonawitz, V . Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for federated learning on user-held data,”arXiv preprint arXiv:1611.04482, 2016

work page Pith review arXiv 2016
[8]

Practical secure aggregation for privacy-preserving machine learning,

——, “Practical secure aggregation for privacy-preserving machine learning,” inproceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1175–1191

2017
[9]

Secure summation: Capacity region, groupwise key, and feasibility,

Y . Zhao and H. Sun, “Secure summation: Capacity region, groupwise key, and feasibility,”IEEE Transactions on Information Theory, 2023

2023
[10]

Optimal rate region for multi-server secure aggregation with user collusion,

Z. Li, X. Zhang, K. Wan, H. Sun, M. Ji, and G. Caire, “Optimal rate region for multi-server secure aggregation with user collusion,”
[11]

Available: https://arxiv.org/abs/2601.06836

[Online]. Available: https://arxiv.org/abs/2601.06836

work page arXiv
[12]

Weakly secure summation with colluding users,

Z. Li, Y . Zhao, and H. Sun, “Weakly secure summation with colluding users,”IEEE Transactions on Information Theory, 2025

2025
[13]

Optimal key rates for decentralized secure aggregation with arbitrary collusion and heterogeneous security constraints,

Z. Li, X. Zhang, and G. Caire, “Optimal key rates for decentralized secure aggregation with arbitrary collusion and heterogeneous security constraints,”arXiv preprint arXiv:2512.16112, 2025

work page arXiv 2025
[14]

Hierarchical secure aggregation with heterogeneous security constraints and arbitrary user collusion,

Z. Li, X. Zhang, J. Lv, H. Chen, J. Fan, and G. Caire, “Hierarchical secure aggregation with heterogeneous security constraints and arbitrary user collusion,”arXiv preprint arXiv:2507.14768, 2025

work page arXiv 2025
[15]

The optimal rate of mds variable generation,

Y . Zhao and H. Sun, “The optimal rate of mds variable generation,” in2023 IEEE International Symposium on Information Theory (ISIT). IEEE, 2023, pp. 832–837

2023
[16]

Mds variable generation and secure summation with user selection,

——, “Mds variable generation and secure summation with user selection,”arXiv preprint arXiv:2211.01220, 2022

work page arXiv 2022
[17]

Secure summation with user selection and collusion,

——, “Secure summation with user selection and collusion,” in2024 IEEE Information Theory Workshop (ITW). IEEE, 2024, pp. 175–180. 39

2024
[18]

Information theoretic secure aggregation with user dropouts,

——, “Information theoretic secure aggregation with user dropouts,”IEEE Transactions on Information Theory, vol. 68, no. 11, pp. 7471–7484, 2022

2022
[19]

Lightsecagg: a lightweight and versatile design for secure aggregation in federated learning,

J. So, C. He, C.-S. Yang, S. Li, Q. Yu, R. E Ali, B. Guler, and S. Avestimehr, “Lightsecagg: a lightweight and versatile design for secure aggregation in federated learning,”Proceedings of Machine Learning and Systems, vol. 4, pp. 694–720, 2022

2022
[20]

Swiftagg: Communication-efficient and dropout-resistant secure aggregation for federated learning with worst-case security guarantees,

T. Jahani-Nezhad, M. A. Maddah-Ali, S. Li, and G. Caire, “Swiftagg: Communication-efficient and dropout-resistant secure aggregation for federated learning with worst-case security guarantees,” in2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 2022, pp. 103–108

2022
[21]

Swiftagg+: Achieving asymptotically optimal communication loads in secure aggregation for federated learning,

——, “Swiftagg+: Achieving asymptotically optimal communication loads in secure aggregation for federated learning,”IEEE Journal on Selected Areas in Communications, vol. 41, no. 4, pp. 977–989, 2023

2023
[22]

On secure aggregation with uncoded groupwise keys against user dropouts and user collusion,

Z. Zhang, J. Liu, K. Wan, H. Sun, M. Ji, and G. Caire, “On secure aggregation with uncoded groupwise keys against user dropouts and user collusion,”IEEE Transactions on Information Theory, 2025

2025
[23]

On the information theoretic secure aggregation with uncoded groupwise keys,

K. Wan, X. Yao, H. Sun, M. Ji, and G. Caire, “On the information theoretic secure aggregation with uncoded groupwise keys,”IEEE Transactions on Information Theory, 2024

2024
[24]

The capacity region of information theoretic secure aggregation with uncoded groupwise keys,

K. Wan, H. Sun, M. Ji, T. Mi, and G. Caire, “The capacity region of information theoretic secure aggregation with uncoded groupwise keys,”IEEE Transactions on Information Theory, 2024

2024
[25]

The capacity of collusion-resilient decentralized secure aggregation with groupwise keys,

Z. Li, X. Zhang, Y . Zhao, H. Chen, J. Fan, and G. Caire, “The capacity of collusion-resilient decentralized secure aggregation with groupwise keys,”arXiv preprint arXiv:2511.14444, 2025

work page arXiv 2025
[26]

Secure aggregation with an oblivious server,

H. Sun, “Secure aggregation with an oblivious server,”arXiv preprint arXiv:2307.13474, 2023

work page arXiv 2023
[27]

Secure aggregation against malicious users,

F. Karakoc ¸, M. ¨Onen, and Z. Bilgin, “Secure aggregation against malicious users,” inProceedings of the 26th ACM Symposium on Access Control Models and Technologies, 2021, pp. 115–124

2021
[28]

Vector linear secure aggregation,

X. Yuan and H. Sun, “Vector linear secure aggregation,” 2025. [Online]. Available: https://arxiv.org/abs/2502.09817

work page arXiv 2025
[29]

Network function computation with vector linear target function and security function,

M. Xu, Q. Chen, and G. Ge, “Network function computation with vector linear target function and security function,” 2026. [Online]. Available: https://arxiv.org/abs/2602.07316

work page arXiv 2026
[30]

On the capacity region of individual key rates in vector linear secure aggregation,

L. Hu and S. Ulukus, “On the capacity region of individual key rates in vector linear secure aggregation,” 2026. [Online]. Available: https://arxiv.org/abs/2601.03241

work page arXiv 2026
[31]

Information-theoretic decentralized secure aggregation with collusion resilience,

X. Zhang, Z. Li, S. Li, K. Wan, D. W. K. Ng, and G. Caire, “Information-theoretic decentralized secure aggregation with collusion resilience,”arXiv preprint arXiv:2508.00596, 2025

work page arXiv 2025
[32]

Information-theoretic secure aggregation over regular graphs,

X. Zhang, Z. Li, H. Yu, K. Wan, H. Sun, M. Ji, and G. Caire, “Information-theoretic secure aggregation over regular graphs,” 2026. [Online]. Available: https://arxiv.org/abs/2601.19183

work page arXiv 2026
[33]

On resilient and efficient linear secure aggregation in hierarchical federated learning,

S. Weng, X. Zhang, Y . Zhao, G. Caire, M. Xiao, and M. Skoglund, “On resilient and efficient linear secure aggregation in hierarchical federated learning,”arXiv preprint arXiv:2601.12853, 2026

work page arXiv 2026
[34]

Optimal communication and key rate region for hierarchical secure aggregation with user collusion,

X. Zhang, K. Wan, H. Sun, S. Wang, M. Ji, and G. Caire, “Optimal communication and key rate region for hierarchical secure aggregation with user collusion,”IEEE Transactions on Information Theory, vol. 72, no. 2, pp. 1030–1050, 2026

2026
[35]

2025 , journal =

X. Zhang, Z. Li, K. Wan, H. Sun, M. Ji, and G. Caire, “Fundamental limits of hierarchical secure aggregation with cyclic user association,”arXiv preprint arXiv:2503.04564, 2025

work page arXiv 2025
[36]

On hierarchical secure aggregation against relay and user collusion,

M. Xu, X. Han, K. Wan, and G. Ge, “On hierarchical secure aggregation against relay and user collusion,” 2025. [Online]. Available: https://arxiv.org/abs/2511.20117

work page arXiv 2025
[37]

A Probabilistic Remark on Algebraic Program Testing,

R. A. Demillo and R. J. Lipton, “A Probabilistic Remark on Algebraic Program Testing,”Information Processing Letters, vol. 7, no. 4, pp. 193–195, 1978

1978
[38]

Fast Probabilistic Algorithms for Verification of Polynomial Identities,

J. T. Schwartz, “Fast Probabilistic Algorithms for Verification of Polynomial Identities,”Journal of the ACM (JACM), vol. 27, no. 4, pp. 701–717, 1980

1980
[39]

Probabilistic Algorithms for Sparse Polynomials,

R. Zippel, “Probabilistic Algorithms for Sparse Polynomials,” inInternational symposium on symbolic and algebraic manipulation. Springer, 1979, pp. 216–226

1979