Pith. sign in

REVIEW 3 major objections 3 minor 19 references

On the Optimal Source Key Size of Secure Gradient Coding

T0 review · 3 major / 3 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper pins the minimum source key size for secure gradient coding with m at least 1 to a recursive formula that matches a new lower bound in several regimes.

desk verdict The achievable schemes are fresh and interesting, but the converse bound rests on an undefined 'symmetric transmission' assumption, so the claimed optimality is not established. read the letter →

arxiv 2504.20662 v1 pith:S4RZJCEO submitted 2025-04-29 cs.IT math.IT

Yang Zhou , Wenbo Huang , Kai Wan , Robert Caiming Qiu This is my paper · ORCID
classification cs.ITmath.IT MSC 94A1594A6268M14
keywords securegradientcodingsourcekeysizedataassignmentcommunicationcostlinearencodinginformation-theoreticlowerboundtransmitterinterferencealignmentstragglerresilience
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

In secure gradient coding, a user must recover the sum of $K$ gradients from any $N_r$ responsive servers while learning nothing else about the data, even if all servers transmit. Earlier work showed that this security constraint does not raise the optimal communication cost, which stays at $N_r/m$ under linear encoding, provided enough random source keys are shared among servers. This paper asks how large those keys must be when $m \ge 1$, i.e., when each dataset is stored with more than minimal redundancy, and proposes an answer: a new information-theoretic lower bound on the source key size together with a recursive data-assignment scheme whose key requirement matches the bound in several regimes and beats the standard cyclic assignment. If correct, the exact minimum key size is $\eta^\star = N/M - 1$ whenever $M = N - N_r + m$ divides $N$.

What carries the argument

The central object is the source key size $\eta = H(Q_1,\ldots,Q_N)/L$, the total randomness shared among servers normalized by the gradient length, paired on the achievability side with the recursive function $h(N,M)$ defined by four cases: $N > 2M$; $1.5M \le N < 2M$ with $M$ even or odd; and $M < N < 1.5M$. The lower bound runs through ordered server sets: if an ordered list $s_1,\ldots,s_{|s|}$ has each server holding a dataset that appeared at most $m-1$ times among earlier servers, the proof argues that those $|s|$ transmissions must carry at least $|s|L/m$ fresh entropy, forcing $\eta \ge |s|/m - 1$. The upper bound is carried by data assignments based on fractional repetition and transmitter interference alignment, a linear-coding technique that places coefficient vectors in left null spaces of sub-matrices so that servers missing certain datasets still transmit combinations that fit the decoding demand matrix.

What would settle it

Take a small case such as $K=N=5$, $m=2$, $M=3$, choose an assignment with three servers satisfying condition (8), and write the coefficient matrix of their transmissions in terms of the $L/2$-length gradient pieces. If the rank of that matrix is strictly below $3L/2$, the entropy step $H(X_{s_1},X_{s_2},X_{s_3}) \ge 3L/2$ behind Theorem 2 fails, and the claimed lower bound would have to be lowered. A direct search over assignments and random linear encoders for small $N,M$ looking for $\eta < \lceil mN/M\rceil/m - 1$ would settle whether the claimed minimum is real.

Watch

Extended reading notes

Core claim

The central claim is that for the $(K,N,N_r,m)$ secure gradient coding problem under linear encoding and optimal communication cost $N_r/m$, the minimum source key size satisfies $\eta^\star \ge \lceil mN/(N-N_r+m)\rceil/m - 1$, and a newly designed recursive scheme achieves $\eta = h(N,M)/m - 1$ for a recursively defined $h(N,M)$, matching the converse in several parameter regimes and giving the exact value $\eta^\star = N/M - 1$ when $M = N - N_r + m$ divides $N$. The achievability scheme partitions servers and datasets into blocks, uses fractional repetition within blocks, and coordinates groups with transmitter interference alignment so that any $N_r$ servers recover the full gradient sum while the number of transmitted linearly independent combinations is kept equal to $h(N,M)$. The paper also shows numerically that this scheme needs fewer source keys than the optimal cyclic-assignment scheme.

Load-bearing premise

The converse relies on the assumption that each server's transmission contains an independent $1/m$ slice of some gradient that earlier servers cannot compute; in a general linear scheme the transmitted symbols are combinations shared across all datasets assigned to that server, so this per-dataset independence is assumed rather than proved.

Editorial extensions

If this is right

  • When $M$ divides $N$, the minimum source key size is exactly $\eta^\star = N/M - 1$, so the key overhead is pinned by the storage redundancy alone.
  • Because the achievable scheme keeps the communication cost at $N_r/m$, security against a user who receives all transmissions costs no extra communication, only a key of size roughly $h(N,M)/m - 1$.
  • For parameters covered by the four recursive cases, the new assignment requires fewer source keys than the optimal cyclic assignment, so data assignment is a first-order factor in key efficiency.
  • Corollary 2 gives a universal benchmark: every secure linear scheme, regardless of assignment, must use at least $\lceil mN/(N-N_r+m)\rceil/m - 1$ source-key symbols.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One testable next step is to compute the gap between Corollary 2 and Theorem 3 for all small $(N,M)$; if the gap is always zero, the exact key-size formula likely has a closed form as a Euclidean-type recursion.
  • If the symmetric-transmission assumption can be removed from the converse proof, the min-max problem in Corollary 1 would become the exact characterization for arbitrary linear schemes, not only symmetric ones.
  • The interference-alignment design may transfer to heterogeneous gradient coding, where datasets have different replication counts, yielding key-size bounds for non-uniform assignments.
  • Because the key size grows roughly as $N/M - 1$, a natural tradeoff question is how much communication cost must be given up to reduce the key size below this level.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies the (K, N, N_r, m) secure gradient coding problem, in which a user must recover the sum of K gradient vectors from the responses of any N_r of N servers, each dataset is stored at M = N - N_r + m servers, and the full set of N responses must reveal nothing beyond the sum. The authors aim to characterize the minimum source-key size η needed to achieve the optimal communication cost N_r/m under linear encoding. Theorem 2 states a lower bound η ≥ |s|/m - 1 for any ordered set of servers satisfying condition (8); Corollary 2 converts this into the universal bound η* ≥ ⌈mN/(N - N_r + m)⌉/m - 1. Theorem 3 proposes a recursive achievable scheme with key size h(N, M)/m - 1, and Remark 1 claims exact optimality η* = N/M - 1 when M divides N. The paper also compares the proposed scheme with the cyclic-assignment scheme in a numerical example.

Significance. If established, the paper would extend the known m = 1 characterization of the minimum source-key size to all m ≥ 1 and would show that non-cyclic assignments can strictly reduce the required key size while preserving the optimal communication cost. The recursive assignment constructions and the worked example in Section IV-C are useful, and the numerical comparison illustrates the claimed gains over cyclic assignment. However, the information-theoretic converse is the load-bearing part of the optimality claim, and it rests on an undefined 'symmetric transmission' assumption and an unproved combinatorial assertion. As it stands, the manuscript provides an achievability study for structured assignments but does not establish the optimality of the proposed key size for the model defined in Section II.

major comments (3)
  1. [Appendix A, Eq. (23d)] The key step (23d) is not justified. The inequality H(X_{s_1},...,X_{s_|s|}) ≥ |s|L/m is supported only by the sentence 'Under the symmetric transmission and linear coding, each server should contain 1/m independent part of W_{s_i}', but 'symmetric transmission' is never defined in Section II and is not a consequence of the model. In a general linear scheme, X_n is an F_q-linear function of all gradients assigned to server n and of the key Q_n; it need not decompose into independent per-dataset shares, and the claim that 'the length of each message should be larger than L/m' does not follow from R = N_r/m, which bounds the sum of T_n over any N_r servers rather than each individual T_n. Theorem 2, and hence the lower bound built on it, is not established for the model as stated.
  2. [Appendix B (proof of Corollary 2)] The proof asserts without proof that 'for any possible assignment, we can find ⌈mK/M⌉ servers' satisfying condition (8), and the displayed equality ⌈mK/M⌉ = ⌈mN/(N - N_r + m)⌉ silently replaces K by N; no such replacement is stated in the model. The sentence 'we assign K/N (N - N_r + m) datasets to each server' also presumes that every server has the same number of assigned datasets, which is not required by the data assignment phase. Consequently the universal converse bound (11) is unsupported even if the argument in Appendix A were repaired.
  3. [Appendix C and Theorem 3] The achievability proof is incomplete as a proof of Theorem 3 for the stated problem. Section IV explicitly restricts attention to K = N and transfers only when N divides K, so the general-K case is left open. Within the recursive schemes, several rank assertions are made without proof; for example, in Scheme 3 the decoding argument states that 'any m + N - (3M - 1)/2 servers in either of the groups compute linearly independent combinations,' and Appendix D justifies the need for interference alignment only by comparing the number of equations with the dimension of a null space. The dependence on [19] as a black box, together with the unspecified finite-field size in statements such as 'linearly independent with high probability' in Scheme 4, means the matching achievability claim is not fully verified.
minor comments (3)
  1. [Section IV-C, Example 1] The notation is inconsistent: the text introduces F_1,...,F_6, the matrix in (18) is written with rows f_1,...,f_6, and the design of 'f_5 and f_6' is promised but never explicitly given; the reader has to infer the relation between F and f.
  2. [Figure 2] The caption is garbled ('e for TheCombined Schem', 'or CorollaConverse bound f', 'gnityclic asscith thewScheme'); it should be rewritten to identify the three curves clearly.
  3. [Section II and Corollary 2] The notation switches between K and N without comment: Corollary 2 and Theorem 3 are stated for the (K, N, N_r, m) problem, but the bound (11) and the function h(N, M) depend only on N and M; the role of K should be clarified throughout.

Circularity Check

1 steps flagged · score 6.0 of 10

The converse bound in Theorem 2 is obtained by assuming the exact entropy increment it needs: the undefined 'symmetric transmission' condition is used to assert that each server contributes L/m fresh independent symbols, which is precisely (23d).

  1. self definitional [Appendix A, proof of Theorem 2, step (23d); Theorem 2 statement (Section III)]
    "Under the symmetric transmission and linear coding, each server should contain 1/m independent part of W_{s_i}. Thus, we have the message of server s_i is independent to messages from {s_1,...,s_{i-1}}, because of the independent part of W_{s_i}. Since the length of each message should be larger than L/m, we can obtain (23d) under the symmetric transmission and linear coding."

    Equation (23d) is H(X_{s_1},...,X_{s_|s|}) ≥ |s|L/m, which is exactly the lower bound needed to conclude η ≥ |s|/m − 1. The proof establishes it by asserting that each server s_i's transmission contains a 1/m independent part of W_{s_i} and is therefore independent of earlier transmissions, giving the per-server entropy increment L/m. That per-server independence/entropy claim is not derived from the Section II model (linear ψ_n, security constraint, assignment rule); 'symmetric transmission' is never defined. The operative content of the phrase is precisely the conclusion: each server contributes L/m fresh entropy. Thus Theorem 2's converse is assumed in the proof step rather than derived; Corollary 2 inherits this reduction.

full rationale

The paper's main new converse bound (Theorem 2/Corollary 2) is not self-contained: Appendix A's key step (23d) is supported only by an undefined 'symmetric transmission and linear coding' assertion that each server has a fresh 1/m share of some gradient. No equation in the model implies this decomposition for general linear coding, where a server's L/m transmitted symbols are linear combinations shared across all its datasets; hence the claimed lower bound is effectively built into the proof's assumption. This is a circular reduction, though not a fitted-parameter or self-citation chain. The self-citations to [11] and [19] (both involve author Wan, and [19] also Huang/Qiu) are load-bearing as external tools but are separate published results used as black boxes; they do not restate the target η* bound, so they do not add circularity. The achievability schemes in Section IV and Appendix C are constructive and independent of the converse; they neither assume nor fit the target key size. Because the converse is a central claimed contribution and reduces to an assumed per-server entropy increment, the score is 6 rather than a minor-citation score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper does not fit any free parameters to data; its claims rest on standard information-theoretic assumptions and on prior published results ([9], [11], [19]), including two papers from the same research group. The main unstated modeling assumption is 'symmetric transmission', which is never defined. No new physical or mathematical entities are introduced.

assumptions (5)
  • domain assumption The optimal communication cost under linear encoding is Nr/m (Theorem 1, citing [9] and [11]).
    Used as the fixed cost constraint that the key size minimization is subject to; not re-proved.
  • domain assumption Any non-secure scheme can be made secure without changing communication cost, with key size λ/m−1 where λ is the number of linearly independent messages ([11, Theorem 1]).
    This transfer theorem underpins the achievable schemes in Section IV.
  • domain assumption The general problem can be reduced to K=N when N divides K ([11, Remark 1]).
    Invoked to justify focusing on K=N in the scheme designs.
  • domain assumption The transmitter interference alignment construction from [19] can provide the required row vectors s_n.
    General Scheme 3 (Appendix C) uses [19] as a black box; this is a self-citation by two of the present authors.
  • domain assumption Gradients are independent and uniformly distributed over F_q^L.
    Standard model assumption in Section II, needed for entropy computations in Appendix A.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Optimal Source Key Size of Secure Gradient Coding." pith.science (2026). https://pith.science/paper/S4RZJCEO

@misc{pith2026250420662,
  author       = {Pith},
  title        = {Pith review of: On the Optimal Source Key Size of Secure Gradient Coding},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S4RZJCEO}},
  note         = {Machine review of arXiv:2504.20662}
}
abstract

With gradient coding, a user node can efficiently aggregate gradients from server nodes processing local datasets, achieving low communication costs and maintaining resilience against straggling servers. This paper considers a secure gradient coding problem, where a user aims to compute the sum of the gradients from $K$ datasets with the assistance of $N$ distributed servers. The user should recover the sum of gradients by receiving transmissions from any $N_r$ servers, and each dataset is assigned to $N - N_r + m$ servers. The security constraint guarantees that even if the user receives transmissions from all servers, it cannot obtain any additional information about the datasets beyond the sum of gradients. It has been shown in the literature that this security constraint does not increase the optimal communication cost of the gradient coding problem, provided enough source keys are shared among the servers. However, the minimum required source key size that ensures security while maintaining this optimal communication cost has only been studied for the special case $m = 1$. In this paper, we focus on the more general case $m \geq 1$ and aim to determine the minimum required source key size for this purpose. We propose a new information-theoretic converse bound on the source key size, as well as a new achievable scheme with carefully designed data assignments. Our scheme outperforms the existing optimal scheme based on the widely used cyclic data assignment and coincides with the converse bound under certain system parameters.

Figures

Figures reproduced from arXiv: 2504.20662 by the authors.

Figure 1
Figure 1. Flow diagram of the combined scheme in Theorem 3. 1 2 3 4 5 6 7 8 9 10 m 0 2 4 6 8 10 12 14 Combined Scheme for The Converse bound for Corolla Scheme with the cyclic assignment ry 2 orem 3 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Numerical evaluations for the secure gradient coding with K = N = 24, M = 10. We first consider the data assignment for the servers in [M], whose structure is as follows. server 1 · · · M 2 M 2 + 1 · · · M D1 · · · D1 D1 · · · D1 · · · · · · · · · · · · · · · · · · dataset Dy · · · Dy Dy · · · Dy Dy+1 · · · Dy+1 DM+1 · · · DM+1 · · · · · · · · · · · · · · · · · · DM · · · DM DN · · · DN In this setup, we assign D1 t… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 10 canonical work pages

  1. [19]

    Fundamental limits of distributed linearly separable computation under cyclic assign- ment,

    W. Huang, K. Wan, H. Sun, M. Ji, R. C. Qiu, and G. Caire, “Fundamental limits of distributed linearly separable computation under cyclic assign- ment,” in 2023 IEEE International Symposium on Information Theory (ISIT), 2023, pp. 2296–2301. APPENDIX A PROOF OF THEOREM 2 By the security constraint in (7), the user can only obtain W1 +··· +WK without accessi...

    work page 2023

  2. [1]

    Practical secure aggregation for privacy-preserving machine learning,

    K. Bonawitz, V . Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for privacy-preserving machine learning,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’17. New York, NY , USA: Association for Computing Machinery, 2017, p. 1175–...

    arXiv 2017

  3. [2]

    Privacy-preserving deep learning,

    R. Shokri and V . Shmatikov, “Privacy-preserving deep learning,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security , ser. CCS ’15. New York, NY , USA: Association for Computing Machinery, 2015, p. 1310–1321. [Online]. Available: https://doi.org/10.1145/2810103.2813687

    arXiv 2015

  4. [3]

    How to share a secret,

    A. Shamir, “How to share a secret,” Commun. ACM , vol. 22, no. 11, p. 612–613, Nov. 1979. [Online]. Available: https://doi.org/10.1145/ 359168.359176

    arXiv 1979

  5. [4]

    Non-interactive and information-theoretic secure ver- ifiable secret sharing,

    T. P. Pedersen, “Non-interactive and information-theoretic secure ver- ifiable secret sharing,” in Annual international cryptology conference . Springer, 1991, pp. 129–140

    1991

  6. [5]

    On the complexity of verifiable secret sharing and multiparty computation,

    R. Cramer, I. Damgård, and S. Dziembowski, “On the complexity of verifiable secret sharing and multiparty computation,” in Proceedings of the thirty-second annual ACM symposium on Theory of computing , 2000, pp. 325–334

    work page 2000

  7. [6]

    Multiparty unconditionally secure protocols,

    D. Chaum, C. Crépeau, and I. Damgard, “Multiparty unconditionally secure protocols,” in Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing , ser. STOC ’88. New York, NY , USA: Association for Computing Machinery, 1988, p. 11–19. [Online]. Available: https://doi.org/10.1145/62212.62214

    work page arXiv 1988

  8. [7]

    Healthcare data gateways: found healthcare intelligence on blockchain with novel privacy risk control,

    X. Yue, H. Wang, D. Jin, M. Li, and W. Jiang, “Healthcare data gateways: found healthcare intelligence on blockchain with novel privacy risk control,” Journal of medical systems , vol. 40, pp. 1–8, 2016

    work page 2016

Show all 19 references
  1. [8]

    Gradient coding: Avoiding stragglers in distributed learning,

    R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient coding: Avoiding stragglers in distributed learning,” in Proceedings of the 34th International Conference on Machine Learning , ser. Proceedings of Machine Learning Research, D. Precup and Y . W. Teh, Eds., vol...

    2017

  2. [9]

    Communication-computation efficient gradient coding,

    M. Ye and E. Abbe, “Communication-computation efficient gradient coding,” in International Conference on Machine Learning . PMLR, 2018, pp. 5610–5619

    2018

  3. [10]

    Optimal communication- computation trade-off in heterogeneous gradient coding,

    T. Jahani-Nezhad and M. A. Maddah-Ali, “Optimal communication- computation trade-off in heterogeneous gradient coding,” IEEE Journal on Selected Areas in Information Theory , vol. 2, no. 3, pp. 1002–1011, 2021

    2021

  4. [11]

    On secure distributed linearly separable computation,

    K. Wan, H. Sun, M. Ji, and G. Caire, “On secure distributed linearly separable computation,” IEEE Journal on Selected Areas in Communi- cations, vol. 40, no. 3, pp. 912–926, 2022

    2022

  5. [12]

    Safelearn: Secure aggregation for private federated learning,

    H. Fereidooni, S. Marchal, M. Miettinen, A. Mirhoseini, H. Möllering, T. D. Nguyen, P. Rieger, A.-R. Sadeghi, T. Schneider, H. Yalame, and S. Zeitouni, “Safelearn: Secure aggregation for private federated learning,” in 2021 IEEE Security and Privacy Workshops (SPW) , 2021, pp. 56–62

    2021

  6. [13]

    Communication- computation efficient secure aggregation for federated learning,

    B. Choi, J.-y. Sohn, D.-J. Han, and J. Moon, “Communication- computation efficient secure aggregation for federated learning,” arXiv preprint arXiv:2012.05433, 2020

    2012 arXiv

  7. [14]

    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,” in Proceedings of Machine Learning and Systems , D. Marculescu, Y . Chi, and C. Wu, Eds., vol. 4, 202...

    2022

  8. [15]

    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,” in 2022 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2022, pp. 103–108

    2022

  9. [16]

    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

  10. [17]

    Interference alignment and degrees of freedom of the k-user interference channel,

    V . R. Cadambe and S. A. Jafar, “Interference alignment and degrees of freedom of the k-user interference channel,” IEEE Transactions on Information Theory, vol. 54, no. 8, pp. 3425–3441, 2008

    2008

  11. [18]

    Degrees of freedom for the mimo interference channel,

    S. A. Jafar and M. J. Fakhereddin, “Degrees of freedom for the mimo interference channel,” IEEE Transactions on Information Theory , vol. 53, no. 7, pp. 2637–2642, 2007

    2007

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.