REVIEW 1 major objections 5 minor 1 cited by
Capacity of Hierarchical Secure Coded Gradient Aggregation with Straggling Communication Links
T0 review · 1 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read The paper proves that the optimal rate region for hierarchical secure coded gradient aggregation is the set of pairs $(R_X,R_Y)$ satisfying $R_X \geq 1/(N_r-T)$ and $R_Y \geq 1/(N_r-T)$ when $N_r>T$, and is empty otherwise.
desk verdict Solid information-theoretic capacity result for a new hierarchical secure aggregation model; the paper earns a serious referee. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The encoding is carried by two structured matrices. Each user multiplies its $L/(N_r-T)$ gradient parts and $T$ randomness parts by a globally known $N \times N_r$ Vandermonde matrix $V$, producing one message per helper. Each helper $n$ forms a decoding matrix $S_n = V G_n^{-1}$, where $G_n$ is an $N_r \times N_r$ Vandermonde matrix built from helper-specific and extra evaluation points; the rows of $S_n$ let a helper reconstruct a missing user message from linear combinations sent by other helpers. Helper-side randomness $Z_n$, generated by a trusted third party, is inserted through an extended Vandermonde matrix with a zero first row, so that the randomness masks inter-helper traffic without changing the aggregate the master decodes. The rate follows because every user and every helper sends exactly $l = L/(N_r-T)$ symbols.
What would settle it
Find any valid scheme for $N_r \leq T$ satisfying both the correctness constraint and the two security constraints, or for $N_r > T$ a scheme with either $R_X < 1/(N_r-T)$ or $R_Y < 1/(N_r-T)$; either would contradict Theorem 1. A simpler check is to simulate the proposed scheme for small parameters and test whether a coalition of $T$ helpers can recover any gradient information, which would expose a flaw in the masking argument.
Extended reading notes
Core claim
The central discovery is a complete capacity characterization of the hierarchical secure coded gradient aggregation problem with $K$ users, $N$ helpers, resiliency threshold $N_r$, and at most $T$ colluding helpers. Theorem 1 states that the optimal rate region is empty when $N_r \leq T$, and is exactly $\{(R_X,R_Y): R_X \geq 1/(N_r-T), R_Y \geq 1/(N_r-T)\}$ when $N_r > T$. Security is information-theoretic: any set of at most $T$ colluding helpers learns nothing about the gradients beyond what colluding users already know, and the master learns nothing beyond the desired sum and the colluding users' knowledge. The proposed scheme achieves these rates exactly, and the matching converse proves that no lower rates are possible.
Load-bearing premise
The achievability scheme requires a trusted third party to generate and distribute the helper-side randomness $Z_n$; if no such trusted setup exists, the proposed scheme cannot be executed and the claimed optimal rates are not realized.
Editorial extensions
If this is right
- If the paper is right, the per-link privacy overhead in a two-layer secure aggregation network is pinned down: each user must send at least $1/(N_r-T)$ of the gradient size to each helper, and each helper must send the same fraction to the master.
- Secure aggregation becomes impossible whenever the adversary can collude with as many helpers as the resilience threshold; no amount of coding or randomness can restore feasibility in this model.
- The optimal rates do not grow with the number of users $K$, so the scheme scales gracefully as more users join the hierarchy.
- Because the achievability proof does not rely on the uniformity or independence of the gradients, the same rates are achieved for arbitrary gradient distributions, including non-uniform real-world models.
Reading between the lines
- The same $1/(N_r-T)$ law suggests a general design principle for multi-layer secure aggregation: each layer must spend one symbol per unit of information for every surplus non-colluding path it needs, a pattern that might extend to deeper hierarchies.
- The reliance on a trusted third party for helper-side randomness is the main obstacle to direct deployment; investigating whether pairwise masks or public-key setups can replace it while preserving the same rates is a natural next step.
- A concrete way to stress-test the result is to simulate the scheme for small parameters and verify empirically that the mutual information between gradients and the view of any $T$ colluding helpers is zero, and that the converse bound is tight.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper formulates a hierarchical secure coded gradient aggregation problem in which K users communicate with a master through N helpers, with at least N_r non-straggling links per user and at least N_r surviving helpers to the master, and with up to T colluding helpers and any number of colluding users. The main result, Theorem 1, states that the optimal rate region is empty when N_r <= T, and is given by R_X >= 1/(N_r-T) and R_Y >= 1/(N_r-T) when N_r > T. The achievability proof constructs explicit Vandermonde-based user encodings and helper-side randomness, and derives matching converse bounds from the correctness and security constraints. The paper also proves the infeasibility of the N_r <= T case and presents a worked example with K=2, N=4, N_r=3, T=1.
Significance. If the result holds, it provides a sharp, parameter-free characterization of the optimal communication rates for a natural hierarchical variant of secure coded gradient aggregation. The paper's strengths are the explicit construction, the matching converse, and the infeasibility result, all of which are presented without fitted parameters and with a concrete toy example that verifies the algebra. The main limitations are the explicit assumption of a trusted third party that distributes helper-side randomness and the deferral of the small-field-size case to [7]; both are standard in this literature and are stated in the model, so they restrict applicability rather than invalidate the claimed rate region for the stated model.
major comments (1)
- [Section IV-D, Eq. (40c)] The proof of Lemma 2 applies Lemma 1 to the set N_k union T \ {t} in order to evaluate H(Z_{N_k union T \ {t}, t}) - H(Z_{T \ {t}, t}) as (N_r - |T|)l. Since |N_k| >= N_r, this set can have cardinality larger than N_r-1, and Lemma 1 does not apply in that regime; for example, with N_r=3, T={4}, and N_k={1,2,3}, the set has size 3, which exceeds N_r-1=2. The displayed equality is therefore not justified by Lemma 1 as written. This step is load-bearing because Lemma 2 is used directly in the proof of security against helpers. The underlying claim appears repairable: for a fixed receiver t, the variables Z_{n,t} are linear functions of a common Q_t through the matrix S_t \tilde G, which has rank N_r-1, so the entropy difference should be computed by a rank argument rather than by Lemma 1. Please supply this argument explicitly.
minor comments (5)
- [Section III, Remarks 1 and 2] Remark 1 says the infeasibility threshold is 'the number of potentially colluding users', but T denotes the number of colluding helpers; Remark 2 states 'When N_r < T' where the subsequent discussion only makes sense for N_r > T. Both should be corrected.
- [Section IV-B, field-size discussion] The proof assumes q >= N + N_r and defers the small-field case to [7]. The statement of Theorem 1 should either include this condition explicitly or state that the result holds for a sufficiently large finite field; otherwise the theorem as stated is stronger than what is proved in the manuscript.
- [Equation (22)] The displayed equation writes the helper-side variables as Z_{1,n}, ..., Z_{N,n}, while Eq. (25) defines M_{n,i} = X_{k,n} + Z_{n,i}. The first and second indices of Z should be aligned consistently, and the matrix concatenation [G_n, \tilde G] should be defined explicitly as horizontal concatenation.
- [Section II and VI] The model requires a trusted third party that generates and distributes the helper-side randomness Z_n. This is an explicit assumption, but the paper should state in the conclusions that the achievability result depends on this trusted setup and that the rates are not realized without it.
- [Headings, Section IV-A] The headings 'Security Againist Helpers' and 'Security Againist the Master' contain typos; they should read 'Security Against Helpers' and 'Security Against the Master'.
Circularity Check
No significant circularity: the achievability and converse are explicit, and cited prior work is not load-bearing.
full rationale
The derivation chain is self-contained. Theorem 1 is established by an explicit achievability construction in Section IV and a matching converse in Section V. The achievable scheme fixes user uploads as linear combinations of the gradient and user randomness through a Vandermonde matrix, defines helper-side randomness through an extended Vandermonde matrix with a rank property proved in Remark 4, and verifies correctness and both security constraints by direct entropy and invertibility arguments; no parameter is fitted to the target rate and no quantity called a prediction is defined in terms of the result. The converse lower bounds bound I(W_k; X_{k,[Nr]}) and I(W; Y^nu_[Nr]) using only the correctness constraint (5) and the security constraints (6)-(7), plus the stated uniformity assumption on W_k, with no imported uniqueness claim and no hidden reliance on the achievability rates. The trusted-third-party generation of the helper-side randomness Z_n is an explicit model assumption in Section II, not a hidden reuse of the conclusion; it limits applicability but does not make the derivation circular. Cited prior work such as [7] and [26]-[29] supplies system-model context and a standard finite-field-extension technique, but none of those citations carries the paper's capacity result, and no load-bearing step reduces to a self-citation by the present authors. No circular step is present.
Assumptions & free parameters
assumptions (4)
- domain assumption The finite field F_q is large enough (q at least N + N_r) so that distinct evaluation points exist for the Vandermonde matrices.
- domain assumption A trusted third party generates and distributes the helper-side randomness Z_n (Section II, before eq. (3)).
- domain assumption The local gradients W_k are i.i.d. uniform over F_q^L (eq. (1)).
- standard math Any N_r rows of an N x N_r Vandermonde matrix with distinct evaluation points form an invertible matrix.
Cite this review
Pith. "Pith review of Capacity of Hierarchical Secure Coded Gradient Aggregation with Straggling Communication Links." pith.science (2026). https://pith.science/paper/LVOTFG6L
@misc{pith2026241211496,
author = {Pith},
title = {Pith review of: Capacity of Hierarchical Secure Coded Gradient Aggregation with Straggling Communication Links},
year = {2026},
howpublished = {\url{https://pith.science/paper/LVOTFG6L}},
note = {Machine review of arXiv:2412.11496}
}
abstract
The growing privacy concerns in distributed learning have led to the widespread adoption of secure aggregation techniques in distributed machine learning systems, such as federated learning. Motivated by a coded gradient aggregation problem in a user-helper-master hierarchical network setting with straggling communication links, we formulate a new secure hierarchical coded gradient aggregation problem. In our setting, \( K \) users communicate with the master through an intermediate layer of \( N \) helpers, who can communicate with each other. With a resiliency threshold of \( N_r \) for straggling communication links, and at most \( T \) colluding helpers and any number of colluding users, the master aims to recover the sum of all users' gradients while remaining unaware of any individual gradient that exceeds the expected sum. In addition, helpers cannot infer more about users' gradients than what is already known by the colluding users. We propose an achievable scheme where users' upload messages are based on a globally known Vandermonde matrix, and helper communication is facilitated using an extended Vandermonde matrix with special structural properties. A matching converse bound is also derived, establishing the optimal result for this hierarchical coded gradient aggregation problem.
Figures
Forward citations
Cited by 1 Pith paper
-
Linear network codes for vector-linear network function computation over three-layer networks
For three-layer networks with fixed MDS target function and cyclic source access, the vector-linear computing capacity equals the cut-set bound whenever that bound is an integer, and at least its floor otherwise.
Reference graph
Works this paper leans on
-
[7]
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
2022
-
[1]
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,” in Proceedings of the 20th International Conference on Artifi- cial Intelligence and Statistics , ser. Proceedings of Machine Learning Research, vol. 54. PMLR, April 20–22 2017, pp. 1273–1282
work page 2017
-
[2]
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
2020
-
[3]
L. Zhu, Z. Liu, and S. Han, “Deep leakage from gradients,” in Pro- ceedings of the 33rd International Conference on Neural Information Processing Systems (NeurIPS) , vol. 32, 2019, pp. 1–11
work page 2019
-
[4]
Practical secure aggregation for privacy-preserving machine learning,
K. Bonawitz, V . Ivanov, B. Kreuter, A. Marcedone, and K. Seth, “Practical secure aggregation for privacy-preserving machine learning,” in the 2017 ACM SIGSAC Conference , 2017
work page 2017
-
[5]
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
-
[6]
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
2021
-
[8]
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,” in 2022 IEEE International Symposium on Information Theory (ISIT) , 2022, pp. 103– 108
work page 2022
Show all 33 references
-
[9]
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
-
[10]
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, vol. 70, no. 2, pp. 1376–1387, 2024
2024
-
[11]
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 Trans- actions on Information Theory , vol. 70, no. 9, pp. 6596–6619, 2024
2024
-
[12]
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 , vol. 70, no. 10, pp. 6932– 6949, 2024
2024
-
[13]
Securing secure aggregation: Mitigating multi-round privacy leakage in federated learn- ing,
J. So, R. E. Ali, B. G ¨uler, J. Jiao, and A. S. Avestimehr, “Securing secure aggregation: Mitigating multi-round privacy leakage in federated learn- ing,” in Proceedings of the AAAI Conference on Artificial Intelligence , vol. 37, no. 8, 2023, pp. 9864–9873
2023
-
[14]
Secure Aggre- gation for Buffered Asynchronous Federated Learning,
J. So, R. E. Ali, B. G ¨uler, and A. Salman Avestimehr, “Secure Aggre- gation for Buffered Asynchronous Federated Learning,” arXiv e-prints, p. arXiv:2110.02177, Oct. 2021
2021 arXiv
-
[15]
Federated learning with buffered asynchronous aggregation,
J. Nguyen, K. Malik, H. Zhan, A. Yousefpour, M. Rabbat, M. Malek, and D. Huba, “Federated learning with buffered asynchronous aggregation,” in Proceedings of The 25th International Conference on Artificial Intelligence and Statistics , ser. Proceedings of Machine Learning Rese...
2022
-
[16]
Fastsecagg: Scalable secure aggregation for privacy-preserving federated learning,
K. Swanand, R. Nived, K. Onur, Ozan, and R. Kannan, “Fastsecagg: Scalable secure aggregation for privacy-preserving federated learning,” CoRR, vol. abs/2009.11248, 2020. [Online]. Available: https://arxiv.org/ abs/2009.11248
2009 arXiv
-
[17]
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,” 2021. [Online]. Available: https://arxiv.org/abs/2012.05433 11
2021 arXiv
-
[18]
Heterosag: Secure aggregation with heterogeneous quantization in federated learning,
A. R. Elkordy and A. S. Avestimehr, “Heterosag: Secure aggregation with heterogeneous quantization in federated learning,” IEEE Transac- tions on Communications , vol. 70, no. 4, pp. 2372–2386, 2022
2022
-
[19]
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,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security , ser. CCS ’20. New York, NY , USA: Association for...
2020
-
[20]
Secure gradient aggregation with sparsifi- cation for resource-limited federated learning,
H. Us Sami and B. G ¨uler, “Secure gradient aggregation with sparsifi- cation for resource-limited federated learning,” IEEE Transactions on Communications, vol. 72, no. 11, pp. 6883–6899, 2024
2024
-
[21]
Client-edge-cloud hierarchical federated learning,
L. Liu, J. Zhang, S. Song, and K. B. Letaief, “Client-edge-cloud hierarchical federated learning,” in ICC 2020 - 2020 IEEE International Conference on Communications (ICC) , 2020, pp. 1–6
2020
-
[22]
Communication-efficient federated learning with adaptive aggregation for heterogeneous client-edge-cloud network,
L. Luo, C. Zhang, H. Yu, G. Sun, S. Luo, and S. Dustdar, “Communication-efficient federated learning with adaptive aggregation for heterogeneous client-edge-cloud network,” IEEE Transactions on Services Computing, pp. 1–14, 2024
2024
-
[23]
Demystifying why local aggregation helps: Convergence analysis of hierarchical sgd,
J. Wang, S. Wang, R.-R. Chen, and M. Ji, “Demystifying why local aggregation helps: Convergence analysis of hierarchical sgd,” in Pro- ceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 8, 2022, pp. 8548–8556
2022
-
[24]
Federated learning over multi- hop wireless networks with in-network aggregation,
X. Chen, G. Zhu, Y . Deng, and Y . Fang, “Federated learning over multi- hop wireless networks with in-network aggregation,” IEEE Transactions on Wireless Communications, vol. 21, no. 6, pp. 4622–4634, 2022
2022
-
[25]
Design and optimization of hierarchical gradient coding for distributed learning at edge devices,
W. Tang, J. Li, L. Chen, and X. Chen, “Design and optimization of hierarchical gradient coding for distributed learning at edge devices,” IEEE Transactions on Communications , pp. 1–1, 2024
2024
-
[26]
Hier- archical coded gradient aggregation for learning at the edge,
S. Prakash, A. Reisizadeh, R. Pedarsani, and A. S. Avestimehr, “Hier- archical coded gradient aggregation for learning at the edge,” in 2020 IEEE International Symposium on Information Theory (ISIT) , 2020, pp. 2616–2621
2020
-
[27]
Two-layer coded gradient aggregation with straggling communication links,
K. Liang and Y . Wu, “Two-layer coded gradient aggregation with straggling communication links,” in 2020 IEEE Information Theory Workshop (ITW), 2021, pp. 1–5
2020
-
[28]
Coded gradient aggregation: A tradeoff between communication costs at edge nodes and at helper nodes,
B. Sasidharan and A. Thomas, “Coded gradient aggregation: A tradeoff between communication costs at edge nodes and at helper nodes,” in 2021 IEEE International Symposium on Information Theory (ISIT) , 2021, pp. 2286–2291
2021
-
[29]
Hierarchical coded gradient aggregation based on layered mds codes,
M. N. Krishnan, A. Thomas, and B. Sasidharan, “Hierarchical coded gradient aggregation based on layered mds codes,” in 2023 IEEE International Symposium on Information Theory (ISIT), 2023, pp. 2547– 2552
2023
-
[30]
Private aggregation in wireless federated learning with heterogeneous clusters,
M. Egger, C. Hofmeister, A. Wachter-Zeh, and R. Bitar, “Private aggregation in wireless federated learning with heterogeneous clusters,” in 2023 IEEE International Symposium on Information Theory (ISIT) , 2023, pp. 54–59
2023
-
[31]
Private aggregation in hierarchical wireless federated learning with partial and full collusion,
——, “Private aggregation in hierarchical wireless federated learning with partial and full collusion,” 2024. [Online]. Available: https: //arxiv.org/abs/2306.14088
2024 arXiv
-
[32]
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,” 2024. [Online]. Available: https://arxiv.org/abs/2410.14035
2024
-
[33]
Shfl: Secure hierarchical federated learning framework for edge networks,
O. Tavallaie, K. Thilakarathna, S. Seneviratne, A. Seneviratne, and A. Y . Zomaya, “Shfl: Secure hierarchical federated learning framework for edge networks,” 2024. [Online]. Available: https: //arxiv.org/abs/2409.15067
2024 arXiv
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.