{"id":"554758f4-4de6-42d1-8e63-56f4c59a093f","arxiv_id":"2502.09817","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The optimal total key rate for vector linear secure aggregation is rank([F;G]) - rank(F).","lead":"This paper analyzes privacy-preserving aggregation where K users send data to a server so that it can compute arbitrary linear combinations while learning nothing about other protected linear combinations. It proves the minimum total randomness needed is exactly the dimension of the protected linear space that lies outside the computed space, generalizing the classic secure summation result.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's verdict is ACCEPT with high confidence, and my stress-test agrees with that outcome. The reader's weakest_assumption names the i.i.d.-uniform input model and the unproved WLOG row-reduction at (29). The input model is part of the problem statement, so it is not a weakness of the theorem relative to its stated assumptions. The WLOG row/column reduction is a presentation gap rather than a correctness gap: invertible row operations and user relabelings preserve the sigma-algebras of the computed and protected functions, so the conditional secrecy constraint (8) is invariant. I therefore do not treat these as load-bearing. I also checked the less explicit technical steps: the unnamed Han/Shearer inequality in (66) is applied in the correct direction, and the existence of V in (30) is guaranteed by the dimension argument because F contains an identity submatrix after the WLOG reduction. The achievability security proof's key substitution at (41) is justified by injectivity of the linear map from W to (FW, GW, V W_last). The converse is equally clean: Lemma 1 correctly bounds I(X; W), Lemma 2 correctly captures the communication lower bound using the no-zero-column assumption, and the entropy chain (60)-(67) yields exactly rank([F;G]) - rank(F). No internal inconsistency, unproven numerical assertion, or circular dependence on prior work was found. The honest output is a non-finding: the central claim holds up under scrutiny.","tokens_in":9485,"tokens_out":29366,"duration_ms":308709,"concrete_test":"As an independent verification worth running, implement the achievability construction for random small instances (e.g., K=5, q=7, random full-row-rank F with no zero columns and random full-row-rank G), explicitly form V and V_perp as in Section 4.3, and check symbolically that (i) the block matrix in (30) has full column rank K, (ii) V V_perp = 0, and (iii) the protocol satisfies H(F | X) = 0 and I(G; X | F) = 0 by exact enumeration over the finite-field input and key distributions. A second check is to re-derive the converse chain (60)-(67) using an entropy inequality solver for K=3 to confirm that no term in the Han/Shearer step (66) was misordered.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the achievability construction and the converse proof line by line, I find no load-bearing flaw in the central claim. The formula R*_ZSigma = rank([F;G]) - rank(F) is supported by a valid information-theoretic proof. The two points flagged by the reader as minor gaps do not threaten correctness. First, the WLOG reduction at (29) is legitimate: an invertible row operation on F preserves the sigma-algebra generated by FW, hence the conditioning in (8); a column permutation is just a relabeling of users, and both F W and G W are preserved as random variables up to the same relabeling. Second, the Han/Shearer step at (66) is valid: H(X_u | (W_k,Z_k)_{k≠u}) <= H(X_u | X_{≠u}) because X_{≠u} is a function of the conditioning variables, and summing the latter over u is bounded by H(X_1,...,X_K) via Han's inequality. The nontrivial step in achievability, the existence of V in (30), is also sound: because F = [I_M, tilde F], the row space of [F;G] projects onto the first M coordinates, so its intersection with the last K-M coordinate subspace has dimension rank([F;G]) - M, which is exactly the dimension needed for the bottom rows. The substitution H(X | V W_last, G, F) = H(X | W) in (41) follows from the injectivity of the linear map W -> (FW, GW, V W_last). No hidden circularity, parameter fitting, or unsupported numerical claim appears. The open individual-key-rate problem is explicitly scoped and does not affect the total-key-rate theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines a vector linear generalization of secure aggregation. K users hold independent uniform inputs W_k over F_q (length L), as well as keys Z_k derived from a shared key Z_Sigma; user k sends a message X_k that is a function of W_k and Z_k. The server must decode F W for a full-row-rank matrix F, and the security requirement is I(G; X_1,...,X_K | F W) = 0 for a full-row-rank matrix G. The main result, Theorem 1, states that the optimal total key rate is R*_{Z_Sigma} = rank([F;G]) - rank(F). The achievability proof gives explicit linear schemes: after a WLOG reduction F = [I_M, \\tilde F], the authors choose a matrix V completing [F;G] to a K x K invertible matrix, generate K-M noise symbols as V_perp S with V V_perp = 0, and verify correctness and security through the entropy chain in equations (35)-(46). The converse combines a bound on I(X;W) (Lemma 1), a per-user lower bound H(X_u | W_{-u}, Z_{-u}) >= L (Lemma 2), and an entropy inequality to lower-bound LZ_Sigma. The paper also identifies the individual-key-rate region as an open problem.","tokens_in":9761,"tokens_out":19035,"duration_ms":197636,"significance":"The result is a clean and natural generalization of the secure summation capacity result of Zhao and Sun, with an intuitive formula: the optimal total key rate equals the dimension of the part of the protected function G that is not already revealed by the computed function F. The achievability construction is explicit and the proof is self-contained, recovering the secure summation special case as rank([1; I_K]) - rank(1) = K - 1. I checked the entropy chain and the converse line by line; I found no load-bearing error, and the two gaps flagged in the stress-test note (the WLOG reduction at (29) and the entropy step at (66)) are both valid with standard arguments. The contribution is modest but solid and appropriate for the journal.","major_comments":[],"minor_comments":[{"comment":"The reduction to F = [I_M, \\tilde F] is asserted without proof; please add a sentence explaining that an invertible row operation preserves the sigma-algebra generated by F W and that a column permutation is just a relabeling of users, so both the correctness and the security constraint are invariant under these transformations.","section":"Section 4.3, Eq. (29)"},{"comment":"The inequality H(X) >= sum_u H(X_u | (W_k,Z_k)_{k != u}) is used without justification; it follows from Han's inequality applied to X, together with the fact that X_{-u} is a function of (W_k,Z_k)_{k != u}. Please include a citation or a one-line derivation.","section":"Section 5, Eq. (66)"},{"comment":"The achievability construction is written for L = 1; for general block length L the same scheme is applied symbol-by-symbol with independent keys, and this should be stated explicitly so that the rate claim LZ_Sigma/L = rank([F;G]) - rank(F) is fully justified.","section":"Section 4.3"},{"comment":"The definition of the total key rate RZ_Sigma uses LZ_Sigma, the length of the source key Z_Sigma, but the individual key lengths LZ are not directly related to LZ_Sigma; a short remark clarifying that the converse lower-bounds LZ_Sigma (not the sum of individual key lengths) would help the reader.","section":"Section 2, Eq. (9)"},{"comment":"In the sentence describing the special case, 'F is the all 1 row vector' should read 'F is the all-one row vector' for clarity.","section":"Section 1"}],"recommendation":"minor_revision","confidential_remarks":"The central claim is correct and the paper is well within scope. The requested changes are local: mainly adding short justifications for the WLOG reduction in (29) and the entropy inequality in (66). I recommend minor revision rather than outright acceptance because these two steps are used in load-bearing positions, even though both are easily fixed with standard arguments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — the short version: Theorem 1 is correct and the paper earns its keep. The result is that for K users with inputs W_k and a server computing F W while leaking nothing about G W beyond F W, the minimum total key entropy is rank([F;G]) - rank(F). That is a genuine generalization of Zhao–Sun's secure summation, which is the case G=I and F the all-ones row, and it recovers the K-1 total randomness. I verified the achievability construction in Section 4.3 line by line; the trick of precoding correlated noise through V-perp so that V kills it is sound, and the entropy chain (35)–(46) checks out. The converse via Lemmas 1 and 2 is also valid: Lemma 1 bounds the message–input mutual information by K - rank(G|F) using the security constraint, and Lemma 2 shows each user's message has at least L bits of entropy conditional on the other users' inputs and keys, using only the no-zero-column assumption on F. The formula is new in the stated generality; the earlier secure summation result does not state it.\n\nThe soft spots are minor. The WLOG reduction to F = [I_M, tilde F] at (29) is asserted without proof, but it is legitimate: invertible row operations preserve the sigma-algebra of F W, and column permutation is just relabeling users. The step at (66) uses an unnamed Han/Shearer inequality, which is fine because X_{≠u} is a function of the conditioning random variables. Both are presentation gaps, not correctness issues. The model assumes i.i.d. uniform inputs and fresh keys; change that and the formula is not established, but that is the same model as [4], and the paper does not oversell. The citation pattern is fine; earlier results are context, not load-bearing inputs.\n\nThe open individual-key-rate problem is scoped honestly, and the discussion is clear. This paper is for people who care about information-theoretic secure aggregation and private computation; it is not a federated-learning protocol paper, but the motivation is there.\n\nI would send this to peer review without hesitation. A serious referee will find it checkable and correct, and the main result is worth stating cleanly in the literature.","headline":"A clean, self-contained capacity result for a natural vector-linear generalization of secure summation; the optimal total key rate formula is right and the proofs hold up.","tokens_in":10303,"tokens_out":2767,"would_cite":true,"duration_ms":25392,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"For vector linear secure aggregation, the minimum total key rate equals the conditional rank of the protected function given the computed function: the dimension of the protected row space that lies outside the computed row space.","keywords":["secure aggregation","secure summation","linear function computation","information-theoretic security","randomness cost","conditional rank","finite fields","federated learning"],"falsifier":"For $K=3$ over $\\mathbb{F}_5$ with $F=[1\\;1\\;1]$ and $G=[1\\;2\\;3]$, the formula gives $\\mathrm{rank}([F;G])-\\mathrm{rank}(F)=1$; a correct and perfectly secure scheme whose shared key has entropy below one symbol per input would refute Theorem 1, and for this small case all deterministic message functions can in principle be enumerated.","tokens_in":9255,"feed_emoji":"🔑","tokens_out":11759,"duration_ms":110091,"temperature":0.7,"pith_summary":"This paper generalizes secure summation to the case where the server must compute an arbitrary linear function $F$ of the $K$ users' inputs while leaking nothing about another arbitrary linear function $G$ beyond what $F$ already reveals. It establishes that the minimum total key rate, the number of random key symbols needed per input symbol, is exactly $\\operatorname{rank}([F;G])-\\operatorname{rank}(F)$, the dimension of $G$'s row space that is not contained in $F$'s row space. The result covers ordinary secure summation as the special case where $G$ is the identity and $F$ is the all-ones sum, recovering the known bound of $K-1$ key symbols. Because secure aggregation is a building block for privacy-preserving distributed learning, an exact randomness cost tells designers precisely how much shared randomness a given computation and privacy requirement demand.","feed_headline":"Secure aggregation needs keys only for the part it doesn't compute","feed_subtitle":"Minimum shared randomness equals the protected dimensions left out of the computed function.","key_machinery":"The central object is the conditional rank $\\operatorname{rank}(G\\mid F)=\\operatorname{rank}([F;G])-\\operatorname{rank}(F)$, counting the dimensions of the protected function's row space that are not already determined by the computed function. The load-bearing mechanism is the pair of matrices $(V,V_\\perp)$: $V$ completes $[F;G]$ to full rank, and the key noise is precoded as $N=V_\\perp S$ with $VV_\\perp=0$, so the noise lives in the null space of $V$ and drops out when the server forms the required linear combinations. This arrangement maximizes the part of the messages that depends only on inputs and is independent of $G$ given $F$, which is exactly the term that makes the mutual information in the security constraint vanish.","core_discovery":"The paper's central claim, Theorem 1, is that for every full-row-rank $F$ and $G$ with $F$ having no zero columns, the optimal total key rate is $R^\\ast_{\\Sigma}=\\operatorname{rank}([F;G])-\\operatorname{rank}(F)=\\operatorname{rank}(G\\mid F)$. On the achievability side, after putting $F$ in the form $[I_M,\\tilde{F}]$, the scheme chooses a matrix $V$ so that $[F;G;0\\;\\;V]$ has full rank $K$, generates noise $N=V_\\perp S$ from uniform key symbols $S$ with $VV_\\perp=0$, and assigns messages $X_k=W_k-\\tilde{F}N$ on the first $M$ users and $X_k=W_k+N$ on the rest, so the noise cancels exactly in the desired output. An entropy chain then shows the security constraint $I(G;X_1,\\dots,X_K\\mid F)=0$ is forced to zero. The converse uses Lemma 1, bounding how much information the messages can reveal about the inputs, and Lemma 2, showing each user's message must carry at least one symbol of its input; together they force the total key entropy to be at least $\\operatorname{rank}(G\\mid F)L$, matching achievability.","pith_inferences":["Because the formula depends only on ranks, it would be natural to test whether the same conditional-rank expression governs randomness cost when correctness and secrecy are relaxed to allow small error or small leakage; the paper does not consider approximate-secrecy variants.","The construction assumes all users follow the protocol and all keys come from a shared source; adapting the noise beamforming to user dropouts or colluding servers, as is done for ordinary secure aggregation, is a plausible next step that the paper does not carry out.","The open individual-key-rate problem might be attackable by symmetrizing the scalar scheme across repetitions, the same technique used to reach $R_Z=2/3$, but a matching per-user converse would need a new argument rather than the total-key converse."],"forward_implications":["Ordinary secure summation is the special case $G=I_K$, $F=[1\\;\\cdots\\;1]$, and the formula gives the known optimal total key rate $K-1$.","The optimal communication rate is one symbol per input per user: each user must send its whole input, and the construction meets this exactly.","The total key rate depends only on the row-space relation of $F$ and $G$, not on the field size or on the specific coefficients chosen to represent the two functions.","The per-user key rate is not settled by this formula; the paper leaves as open the gap $1/2 \\le R_Z \\le 2/3$ in a three-user example."],"supporting_citations":[{"why":"Supplies the secure summation capacity region and the entropy-converse technique that the lower bound adapts to the vector linear setting.","marker":"[4]"},{"why":"Introduces source-security for computing linear functions over networks, the relaxation this paper extends from sums to arbitrary linear functions.","marker":"[5]"},{"why":"Formulates function-security for network computation, the conceptual model of protecting a linear function rather than all inputs.","marker":"[6]"}],"fun_headline_variants":["Randomness cost equals protected dimensions not in computed span","Secure vector sums need keys only for protected linear combos","Minimum randomness is the gap between protected and computed spans","Vector linear secure aggregation: key cost equals protected span gap"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes every input symbol is uniformly random, inputs are independent of one another and of the keys, and the keys are fresh uniform randomness; if any of these fail, the mutual-information cancellations in the achievability proof and the entropy inequalities in the converse no longer hold.","fun_headline_variants_meta":{"raw":{"variants":["Randomness cost equals protected dimensions not in computed span","Secure vector sums need keys only for protected linear combos","Minimum randomness is the gap between protected and computed spans","Vector linear secure aggregation: key cost equals protected span gap"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000974,"raw_usage":{"total_tokens":4154,"prompt_tokens":971,"completion_tokens":3183,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":587,"completion_tokens_details":{"reasoning_tokens":3118}},"tokens_in":587,"tokens_out":3183,"duration_ms":22197,"temperature":1.0,"reasoning_tokens":3118,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T20:22:59.038092+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $K=3$ over $\\mathbb{F}_5$ with $F=[1\\;1\\;1]$ and $G=[1\\;2\\;3]$, the formula gives $\\mathrm{rank}([F;G])-\\mathrm{rank}(F)=1$; a correct and perfectly secure scheme whose shared key has entropy below one symbol per input would refute Theorem 1, and for this small case all deterministic message functions can in principle be enumerated.","supporting_citations":[{"cited_title":"Secure Summation: Capacity Region, G roupwise Key, and Feasibility,","cited_arxiv_id":null,"evidence_quote":"Supplies the secure summation capacity region and the entropy-converse technique that the lower bound adapts to the vector linear setting."},{"cited_title":"Secure Network Functio n Computation for Linear Functions—Part I: Source Security,","cited_arxiv_id":null,"evidence_quote":"Introduces source-security for computing linear functions over networks, the relaxation this paper extends from sums to arbitrary linear functions."},{"cited_title":"Secure Network Functio n Computation: Function- Security,","cited_arxiv_id":null,"evidence_quote":"Formulates function-security for network computation, the conceptual model of protecting a linear function rather than all inputs."}],"review_version":1}