pith. sign in

arxiv: 2605.22261 · v1 · pith:FXDHFRVEnew · submitted 2026-05-21 · 💻 cs.IT · math.IT

Information-Theoretic Decentralized Secure Aggregation with User Dropouts

Zhou Li , Xiang Zhang , Yizhou Zhao , Han Yu , Giuseppe Caire This is my paper

Pith reviewed 2026-05-22 04:09 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords decentralized secure aggregationinformation-theoretic securityuser dropoutscommunication rate regionMDS matricesbroadcast channelscollusion resistance
0
0 comments X

The pith

Decentralized secure aggregation is impossible if surviving users are at most colluders plus one, and otherwise requires rates R1 at least 1 and R2 at least 1 over (U minus T minus 1).

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

This paper determines the lowest communication rates needed for users in a network without any trusted server to securely compute the sum of their private inputs even when some users drop out. It proves that secure aggregation cannot be done at all if the guaranteed number of surviving users U is no more than the maximum number of colluders T plus one. When more users survive, the minimal rates in a two-round broadcast protocol are one unit per input in the first round and one over the effective redundancy level in the second round. The result matters because it supplies exact efficiency limits for privacy-preserving computation in distributed systems where dropouts are common and no central authority can be trusted. The construction uses matrices to generate correlated secret keys that handle both the dropouts and the security requirement at once.

Core claim

In a fully decentralized network of K users communicating over broadcast channels, each user holds a private input and the goal is for each surviving user to recover the sum of inputs from at least U surviving users while revealing no extra information about individual inputs even if that user colludes with up to T others. The authors prove that decentralized secure aggregation is infeasible when U is at most T plus one. Otherwise the optimal communication rate region is given by R1 greater than or equal to 1 and R2 greater than or equal to 1 divided by (U minus T minus 1), where R1 and R2 are the first-round and second-round rates. This region is achieved by a scheme that builds correlated,

What carries the argument

Correlated secret keys constructed from (T+1)-private maximum distance separable (MDS) matrices that simultaneously enable reconstruction of the aggregate sum and protect individual inputs against collusion.

If this is right

  • The optimal second-round rate depends only on the redundancy level U minus T minus 1 and is independent of the total number of users K.
  • Decentralized secure aggregation cannot be performed with finite communication rates when the number of guaranteed surviving users is at most T plus one.
  • The MDS-matrix construction simultaneously provides robustness to dropouts and information-theoretic security against up to T colluders.
  • Matching converse bounds establish that the stated rates are the best possible under the two-round broadcast model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Networks that can guarantee a larger surplus of surviving users beyond T plus 1 can reduce per-user communication cost as that surplus increases.
  • The broadcast-channel assumption may be approximated in partially connected settings to obtain practical rate estimates.
  • Protocols allowed more than two rounds could potentially achieve lower rates, but would need separate analysis.

Load-bearing premise

The characterization assumes a fully connected broadcast channel, exactly two rounds of communication, that at least U users always survive, and that security must hold information-theoretically against any set of at most T colluding users including the receiver.

What would settle it

A concrete falsifier would be a two-round protocol that achieves a second-round rate strictly below 1 divided by (U minus T minus 1) while still guaranteeing correct sum recovery for every dropout pattern with at least U survivors and information-theoretic security against T colluders.

Figures

Figures reproduced from arXiv: 2605.22261 by Giuseppe Caire, Han Yu, Xiang Zhang, Yizhou Zhao, Zhou Li.

Figure 1
Figure 1. Figure 1: DSA with K = 4, U = 3, and T = 0. In the first round, each user k broadcasts Xk to all other users. In this example, User 3 drops out over first round, and hence the set of surviving user is U1 = {1, 2, 4}. In the second round, each surviving user k ∈ U1 broadcasts Y U1 k . From the received messages and its own input and secret key, each surviving user must recover W1 + W2 + W4 while learn nothing more. T… view at source ↗
read the original abstract

This paper investigates the fundamental limits of information-theoretic decentralized secure aggregation (DSA) with user dropouts. We consider a fully decentralized network where $K$ users communicate over broadcast channels without a trusted aggregation server. Each user holds a private input and aims to recover the sum of the surviving users' inputs (users may drop) while ensuring that no additional information about individual inputs is revealed to that user, even if it can collude with other users. A two-round communication protocol is considered, where we assume at least $U$ users survive and each user can collude with at most $T$ other users. For this setting, the optimal communication rate region is fully characterized: we show that DSA is infeasible if $U\le T+1$; otherwise, the optimal rate region is given by $R_1\geq 1$ and $R_2\geq \frac{1}{U-T-1}$, where $R_1$ and $R_2$ denote the first- and second-round communication rates, respectively. The proposed aggregation scheme is based on correlated secret keys constructed from $(T+1)$-private maximum distance separable (MDS) matrices, which simultaneously provide robustness against user dropouts and security against collusion. We also derive tight converse bounds that establish the optimality of the proposed scheme. Our result shows that the optimal second-round communication rate depends only on the effective redundancy level $U-T-1$ regardless the total number of users.

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.

Referee Report

0 major / 2 minor

Summary. The manuscript characterizes the fundamental limits of two-round information-theoretic decentralized secure aggregation (DSA) with user dropouts over broadcast channels without a trusted server. For K users where at least U survive and security must hold against any T colluders (including the receiver), it proves DSA is infeasible when U ≤ T+1; otherwise the optimal rates satisfy R1 ≥ 1 and R2 ≥ 1/(U-T-1). Achievability is obtained via correlated secret keys generated from (T+1)-private MDS matrices that simultaneously ensure dropout robustness and information-theoretic security, while the converse follows from standard entropy inequalities on the broadcast messages that isolate the effective redundancy U-T-1.

Significance. If the result holds, the work delivers a tight, self-contained characterization of the DSA rate region that isolates the second-round rate dependence on the single parameter U-T-1 independent of total users K. The explicit (T+1)-private MDS construction for correlated keys that jointly achieves dropout tolerance and collusion security, together with matching converse bounds obtained via entropy arguments, constitutes a clear advance for information-theoretic secure aggregation and decentralized secure computation.

minor comments (2)
  1. [Abstract] Abstract: the statement that the second-round rate depends only on U-T-1 'regardless the total number of users' is correct but would be clearer if it explicitly noted that K appears only in the feasibility threshold U > T+1.
  2. [Theorem 1] The main theorem statement would benefit from an explicit equation label for the rate region (R1, R2) to facilitate cross-references in the converse proof.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and the recommendation to accept the manuscript. The referee's summary accurately captures the main contributions, including the infeasibility result when U ≤ T+1 and the tight rate bounds R1 ≥ 1 and R2 ≥ 1/(U-T-1) otherwise, along with the MDS-based construction and converse arguments.

Circularity Check

0 steps flagged

No significant circularity: self-contained characterization via explicit construction and standard converse

full rationale

The paper derives the rate region directly from the model constraints. Achievability is shown by an explicit scheme using (T+1)-private MDS matrices to generate correlated keys that simultaneously handle dropouts (requiring at least U survivors) and T-collusion security; this construction is parameter-free and does not rely on fitting or prior self-citations for the target rates R1=1 and R2=1/(U-T-1). The converse applies standard entropy inequalities to the two-round broadcast messages, isolating the redundancy U-T-1 from the security and dropout conditions without reducing to fitted inputs or self-referential definitions. The infeasibility for U ≤ T+1 follows immediately from the same entropy arguments. No load-bearing step collapses to a self-citation chain, ansatz smuggling, or renaming of a known result; the derivation is independent of external benchmarks beyond basic information-theoretic tools.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard information-theoretic axioms (entropy chain rules, mutual information non-negativity) and coding-theoretic properties of MDS codes; no free parameters are fitted to data and no new entities are postulated.

axioms (2)
  • standard math Standard properties of Shannon entropy and mutual information hold for the discrete random variables modeling user inputs and messages.
    Invoked throughout the converse proof to bound information leakage and communication rates.
  • domain assumption Existence of (T+1)-private MDS matrices of appropriate dimensions over sufficiently large finite fields.
    Used to construct the correlated secret keys that simultaneously achieve security and dropout robustness.

pith-pipeline@v0.9.0 · 5798 in / 1439 out tokens · 33847 ms · 2026-05-22T04:09:22.749635+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · 3 internal anchors

  1. [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. 12

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  2. [2]

    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,” inProceedings of the 20th International Conference on Artificial Intelligence and Statistics, ser. Proceedings of Machine Learning Research, A. Singh and J. Zhu, Eds., vol. 54. PMLR, 20–22 Apr 2017, pp. 1273–1282. [...

    work page 2017

  3. [3]

    Advances and open problems in federated learning,

    P. Kairouz and H. B. McMahan, “Advances and open problems in federated learning,”Foundations and Trends in Machine Learning, vol. 14, no. 1-2, pp. 1–210, 06 2021. [Online]. Available: https: //doi.org/10.1561/2200000083

    work page doi:10.1561/2200000083 2021

  4. [4]

    Federated learning: Challenges, methods, and future directions,

    T. Li, A. K. Sahu, A. Talwalkar, and V . Smith, “Federated learning: Challenges, methods, and future directions,”IEEE Signal Processing Magazine, vol. 37, no. 3, pp. 50–60, 2020

    work page 2020

  5. [5]

    Applied Federated Learning: Improving Google Keyboard Query Suggestions

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

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  6. [7]

    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

    work page 2017

  7. [8]

    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

    work page 2023

  8. [9]

    Efficient dropout-resilient ag- gregation for privacy-preserving machine learning,

    Z. Liu, J. Guo, K.-Y . Lam, and J. Zhao, “Efficient dropout-resilient ag- gregation for privacy-preserving machine learning,”IEEE Transactions on Information Forensics and Security, vol. 18, pp. 1839–1854, 2022

    work page 2022

  9. [10]

    Mds variable generation and secure summation with user selection,

    Y . Zhao and H. Sun, “Mds variable generation and secure summation with user selection,”IEEE Transactions on Information Theory, vol. 71, no. 4, pp. 3129–3141, 2025

    work page 2025

  10. [11]

    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

    work page 2025

  11. [12]

    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

  12. [13]

    Fundamental limits of hierarchical secure aggregation with cyclic user association,

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

    work page

  13. [14]

    Available: https://tinyurl.com/mtj4zhvt

    [Online]. Available: https://tinyurl.com/mtj4zhvt

    work page

  14. [15]

    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

    work page 2026

  15. [16]

    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,” 2026. [Online]. Available: https://arxiv.org/abs/2601.06836

    work page arXiv 2026

  16. [17]

    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

  17. [18]

    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

  18. [19]

    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

  19. [20]

    Information theoretic secure aggregation with user dropouts,

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

    work page 2022

  20. [21]

    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

    work page 2022

  21. [22]

    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

    work page 2022

  22. [23]

    On the fundamental limits of hierarchical secure aggregation with dropout and collusion resilience,

    Z. Li, Y . Zhao, X. Zhang, and G. Caire, “On the fundamental limits of hierarchical secure aggregation with dropout and collusion resilience,”

    work page

  23. [24]

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

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

    work page arXiv

  24. [25]

    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

    work page 2025

  25. [26]

    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

  26. [27]

    Communication Theory of Secrecy Systems,

    C. E. Shannon, “Communication Theory of Secrecy Systems,”Bell System Technical Journal, vol. 28, no. 4, pp. 656–715, 1949

    work page 1949

  27. [28]

    The Capacity of Symmetric Private Information Retrieval,

    H. Sun and S. A. Jafar, “The Capacity of Symmetric Private Information Retrieval,”IEEE Transactions on Information Theory, vol. 65, no. 1, pp. 322–329, 2019

    work page 2019

  28. [29]

    Cross Subspace Alignment and the Asymptotic Capacity of X–Secure T–Private Information Retrieval,

    Z. Jia, H. Sun, and S. A. Jafar, “Cross Subspace Alignment and the Asymptotic Capacity of X–Secure T–Private Information Retrieval,” IEEE Transactions on Information Theory, vol. 65, no. 9, pp. 5783– 5798, 2019

    work page 2019

  29. [30]

    Practical Secure Aggregation for Federated Learning on User-Held Data

    K. Bonawitz, V . Ivanov, B. Kreuter, A. Marcedone, H. B. McMa- han, 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 internal anchor Pith review Pith/arXiv arXiv 2016

  30. [31]

    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

    work page 2017

  31. [32]

    Secure Single-Server Aggregation with (Poly) Logarithmic Overhead,

    J. H. Bell, K. A. Bonawitz, A. Gasc ´on, T. Lepoint, and M. Raykova, “Secure Single-Server Aggregation with (Poly) Logarithmic Overhead,” inProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, 2020, pp. 1253–1269

    work page 2020

  32. [33]

    Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning,

    J. So, B. G ¨uler, and A. S. Avestimehr, “Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning,”IEEE Journal on Selected Areas in Information Theory, vol. 2, no. 1, pp. 479–489, 2021

    work page 2021

  33. [34]

    Fast- SecAgg: Scalable Secure Aggregation for Privacy-Preserving Federated Learning,

    S. Kadhe, N. Rajaraman, O. O. Koyluoglu, and K. Ramchandran, “Fast- SecAgg: Scalable Secure Aggregation for Privacy-Preserving Federated Learning,”arXiv preprint arXiv:2009.11248, 2020

    work page arXiv 2009

  34. [35]

    Federated learning with autotuned communication-efficient secure ag- gregation,

    K. Bonawitz, F. Salehi, J. Kone ˇcn`y, B. McMahan, and M. Gruteser, “Federated learning with autotuned communication-efficient secure ag- gregation,” in2019 53rd Asilomar Conference on Signals, Systems, and Computers. IEEE, 2019, pp. 1222–1226

    work page 2019

  35. [36]

    Communication- Computation Efficient Secure Aggregation for Federated Learning,

    B. Choi, J. yong Sohn, D.-J. Han, and J. Moon, “Communication- Computation Efficient Secure Aggregation for Federated Learning,” arXiv preprint arXiv:2012.05433, 2020

    work page arXiv 2012