{"id":"88f6f06f-6416-4b5a-9b2c-4aedb18e63e4","arxiv_id":"2504.20662","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"For secure gradient coding with each dataset stored on M=N−Nr+m servers, the minimum source key size is claimed to be at least ceil(mN/M)/m−1, with a recursive scheme achieving this bound for several parameter regimes.","lead":"This paper studies how much secret randomness servers must share to securely compute a sum of gradients while tolerating stragglers. It proposes new lower bounds and data assignment schemes for the general m≥1 case, claiming to need fewer keys than the standard cyclic assignment.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The converse bound rests on an undefined 'symmetric transmission' assumption (App. A, step (23d)) that treats each server's L/m output symbols as an independent per-gradient share; general linear encoding does not have this structure, so Theorem 2 and Corollary 2 are not established.","rationale":"The reader's weakest assumption correctly identifies the hinge of the paper: the converse lower bound on source key size, which is needed for the claimed optimality result, depends on the entropic step (23d). The paper invokes an undefined 'symmetric transmission' condition to conclude that each server contributes an independent L/m share of a particular gradient. Nothing in the system model (Section II) or in the definition of linear encoding implies this decomposition. A server's transmitted symbols are linear combinations of all gradients assigned to it, and the same set of symbols can encode multiple datasets simultaneously. Therefore the lower bound on H(X_{s_1},...,X_{s_|s|}) does not follow. Corollary 2 inherits this gap, and its Appendix B proof is only a two-line counting assertion without a derivation. The achievable scheme may be valuable, but the paper's headline claim of characterizing the minimum source key size is not established. The reader's REJECT verdict is appropriate; my stress-test does not change it.","tokens_in":17226,"tokens_out":11966,"duration_ms":120841,"concrete_test":"Fix the smallest instance where the bound is nontrivial and the paper's own cyclic scheme is claimed optimal, e.g. (K,N,Nr,m)=(6,6,5,2), so M=3 and the claimed cyclic key size is η=Nr/m−1=1.5. Write out the cyclic assignment and the actual linear transmissions of the scheme that achieves communication cost Nr/m. For the ordered set s=(1,...,6), condition (8) is satisfied (e.g., server 6 can choose D_6, which appears once in the preceding set). Then compute H(X_1,...,X_6) for the proposed linear scheme. If H(X_1,...,X_6) < 6·L/2 = 3L, step (23d) is false. If H(X_1,...,X_6) ≥ 3L, then inequality (22f) forces η ≥ 2, contradicting the claimed η=1.5. Either outcome shows that the proof of Theorem 2, or the claimed cyclic bound, cannot stand as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Central claim: η* ≥ ceil(mN/(N−Nr+m))/m − 1 and matching achievability. The achievability is plausible, but the converse is the load-bearing part. Theorem 2's proof in Appendix A derives H(X_{s_1},...,X_{s_|s|}) ≥ |s|L/m at step (23d). The justification is that each server s_i contains a gradient W_{s_i} whose previous multiplicity is at most m−1; then 'under the symmetric transmission and linear coding, each server should contain 1/m independent part of W_{s_i}', hence that server's transmission has L/m fresh entropy independent of earlier transmissions. This is not a consequence of the model in Section II. In a general linear scheme, the L/m transmitted symbols are F_q-linear combinations of all gradients assigned to that server; they cannot generally be decomposed into a per-dataset 'independent part' of one particular gradient, and no definition of 'symmetric transmission' is given anywhere in the paper. The phrase appears only in the proof. The same unsupported assumption is carried into Corollary 2 via Appendix B, whose counting step ('we can find ceil(mN/M) servers...') is also asserted, not proved. Consequently the claimed optimality of the source key size is not supported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17431,"tokens_out":10518,"duration_ms":107802,"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":[{"comment":"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.","section":"Appendix A, Eq. (23d)"},{"comment":"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.","section":"Appendix B (proof of Corollary 2)"},{"comment":"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.","section":"Appendix C and Theorem 3"}],"minor_comments":[{"comment":"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.","section":"Section IV-C, Example 1"},{"comment":"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.","section":"Figure 2"},{"comment":"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.","section":"Section II and Corollary 2"}],"recommendation":"reject","confidential_remarks":"The main reason for rejection is technical: the converse proof contains a load-bearing gap that is not a local presentation issue. The paper's proposed schemes may be of interest as an achievability construction, but the claimed optimality of the source-key size is not supported by the submitted proofs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Have you seen this secure gradient coding paper? Let me give you my read.\n\nThe genuinely new part is the achievable side. The authors extend the m=1 key-size problem to m≥1 and design a recursive assignment strategy that beats the cyclic assignment in their numerical examples. The use of transmitter interference alignment from [19] is a real idea, and the examples in Section IV are worked out in enough detail to be plausible. If the converse were solid, this would settle the question.\n\nThe problem is the converse. Theorem 2's proof in Appendix A rests on a step that I don't think follows from the model. At (23d) they need H(X_{s_1},...,X_{s_|s|}) ≥ |s|L/m. The justification is that each server s_i holds some gradient W_{s_i} that at most m−1 of the previous servers can compute, and 'under the symmetric transmission and linear coding' each server contains an independent 1/m share of that gradient. But 'symmetric transmission' is never defined, and it is not a consequence of linear encoding. A server's L/m output symbols are linear combinations of all gradients assigned to it; nothing forces those symbols to decompose into a per-gradient independent share. In fact, you can cook up linear schemes where a server's output is a linear combination that overlaps with previous servers' outputs, and the entropy increment is less than L/m. The security and decodability constraints don't rule that out as far as I can tell. Corollary 2 then inherits this gap, and its counting step (existence of ceil(mN/M) servers with the required property) is asserted, not proved.\n\nSo the paper's central claim—that it characterizes the minimum source key size—is not supported. The lower bound may be true, and the achievable schemes are interesting enough to make me think a rigorous proof might exist. But as written, the load-bearing part of the paper is not established.\n\nI'd tell the editor: send it to review in the sense that it deserves a serious referee—the problem is relevant and the construction is fresh—but the current version should be rejected, with an invitation to revise and either prove the converse properly or state explicitly what 'symmetric transmission' means and argue it is without loss of generality for optimal schemes. I wouldn't cite it as a definitive result until the lower bound is fixed.\n\nFor your reading group: maybe. It's a decent example of a paper with a promising scheme and a shaky converse, and the gap is worth discussing.","headline":"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.","tokens_in":18011,"tokens_out":9141,"would_cite":false,"duration_ms":91597,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A62","68M14"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["secure gradient coding","source key size","data assignment","communication cost","linear encoding","information-theoretic lower bound","transmitter interference alignment","straggler resilience"],"falsifier":"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.","tokens_in":16975,"feed_emoji":"🔒","tokens_out":11721,"duration_ms":113703,"temperature":0.7,"pith_summary":"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$.","feed_headline":"Minimum key size for secure gradient coding found for m>1","feed_subtitle":"A recursive assignment scheme cuts key overhead versus cyclic assignment and matches the new lower bound.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It introduces the gradient coding model and the straggler-resilience decoding condition that the secure problem extends.","marker":"[8]"},{"why":"It establishes that the optimal communication cost under linear encoding is $N_r/m$, the target every scheme in this paper must meet.","marker":"[9]"},{"why":"It supplies the transfer theorem that turns a non-secure scheme into a secure one at no extra communication cost and settles the $m=1$ key-size case this paper extends.","marker":"[11]"},{"why":"It provides transmitter interference alignment, the coding tool used to design the coefficient matrices in the recursive schemes.","marker":"[17]"},{"why":"It supplies the interference-alignment result underlying the coefficient designs for servers with missing datasets.","marker":"[18]"},{"why":"It characterizes the optimal cyclic-assignment scheme against which the new assignments are compared in the numerical evaluations.","marker":"[19]"}],"fun_headline_variants":["New lower bound and matching scheme for secure gradient key size","Recursive assignment cuts key overhead and hits bound","Secure gradient coding needs fewer keys than cyclic scheme","Exact minimum key size for any m in secure gradient coding"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["New lower bound and matching scheme for secure gradient key size","Recursive assignment cuts key overhead and hits bound","Secure gradient coding needs fewer keys than cyclic scheme","Exact minimum key size for any m in secure gradient coding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000238,"raw_usage":{"total_tokens":1533,"prompt_tokens":989,"completion_tokens":544,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":605,"completion_tokens_details":{"reasoning_tokens":480}},"tokens_in":605,"tokens_out":544,"duration_ms":5332,"temperature":1.0,"reasoning_tokens":480,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:24:30.725706+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Gradient coding: Avoiding stragglers in distributed learning,","cited_arxiv_id":null,"evidence_quote":"It introduces the gradient coding model and the straggler-resilience decoding condition that the secure problem extends."},{"cited_title":"On secure distributed linearly separable computation,","cited_arxiv_id":null,"evidence_quote":"It supplies the transfer theorem that turns a non-secure scheme into a secure one at no extra communication cost and settles the $m=1$ key-size case this paper extends."},{"cited_title":"Degrees of freedom for the mimo interference channel,","cited_arxiv_id":null,"evidence_quote":"It supplies the interference-alignment result underlying the coefficient designs for servers with missing datasets."},{"cited_title":"Fundamental limits of distributed linearly separable computation under cyclic assign- ment,","cited_arxiv_id":null,"evidence_quote":"It characterizes the optimal cyclic-assignment scheme against which the new assignments are compared in the numerical evaluations."}],"review_version":1}