Vector Linear Secure Aggregation

Hua Sun; Xihang Yuan

Vector Linear Secure Aggregation

T0 review · 0 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2502.09817 v1 pith:2J2JRJAW submitted 2025-02-13 cs.IT math.IT

Xihang Yuan , Hua Sun This is my paper · ORCID

classification cs.ITmath.IT MSC 94A1594A17

keywords secureaggregationsummationlinearfunctioncomputationinformation-theoreticsecurityrandomnesscostconditionalrankfinitefieldsfederatedlearning

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the 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.

The 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.

The 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.

I 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.

Referee Report

0 major / 5 minor

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.

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.

minor comments (5)

[Section 4.3, Eq. (29)] 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 5, Eq. (66)] 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 4.3] 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 2, Eq. (9)] 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 1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the achievability and converse derive rank([F;G]) - rank(F) from the problem definitions; the prior secure-summation result is recovered as a special case, not assumed.

full rationale

Theorem 1 is not circular. The achievability proof (Section 4.3) starts from the arbitrary matrices F and G, reduces F to [I_M, tilde-F] by row and column operations that preserve the problem, constructs V via (30) and V_perp via (32), and uses exactly rank([F;G]) - M uniform key symbols. Correctness is verified in (35)-(36) and security in (37)-(46) with entropy equalities that rely only on the construction and the definitions in (6)-(8); the final equality (46) is an identity, not a restatement of the theorem. The converse (Section 5) does not invoke the theorem. Lemma 1 follows from the security constraint (8) and standard mutual-information bounds, while Lemma 2 follows from correctness (7), the no-zero-column assumption (5), and the independence assumption (1). Combining these lemmas yields exactly rank(G|F)L through (60)-(67). No parameter is fitted, no prediction is forced by a fitted value, and no load-bearing step is outsourced to the authors' earlier secure-summation result [4]; that result is mentioned as background and recovered as a special case. The WLOG reduction at (29) and the Han/Shearer-type step at (66) are proof details rather than circular reductions. Overall, the derivation is self-contained and exhibits no significant circularity.

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

No fitted or hand-chosen numeric parameters appear in the paper; the theorem's quantity is a rank difference determined by F and G. The matrices V and V-perp are constructive linear-algebra objects derived from F and G, not new postulated entities with independent physical content. All non-trivial mathematical facts used are standard linear algebra or entropy inequalities, plus the problem's stated modeling assumptions.

assumptions (7)

domain assumption Inputs (W_k) are i.i.d. uniform over F_q and independent of keys (Eqs. (1)-(2)).
The entropy bounds and the independence argument in the achievability proof (41)-(46) rely on full per-symbol entropy and on inputs being independent of keys.
standard math F and G have full row rank.
Stated without loss of generality; the rank terms in the theorem are only well-defined with full row rank.
domain assumption F has no zero columns (Eq. (5)).
The paper justifies this as eliminating users whose inputs do not affect the desired function; the converse Lemma 2 uses F(:,u) nonzero.
domain assumption Keys (Z_k) are deterministic functions of a common source key Z_Sigma (Eq. (3)).
This defines the total key rate and is part of the problem model.
standard math There exists a matrix V over F_q such that [F;G;0 V] has full rank K.
Used in (30) and justified in footnote 1 by extending the row basis of [F;G]; holds by linear algebra over finite fields.
domain assumption Security is perfect conditional secrecy: I(G; messages | F) = 0 (Eq. (8)).
This is the problem's security definition and the target of both the achievability and converse proofs.
standard math Han/Shearer inequality: H(X) >= sum_u H(X_u | X_[K]\{u}).
Used implicitly in the converse at line (66) to lower bound H(X|W) by a sum of conditional entropies minus I(X;W).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Vector Linear Secure Aggregation." pith.science (2026). https://pith.science/paper/2J2JRJAW

@misc{pith2026250209817,
  author       = {Pith},
  title        = {Pith review of: Vector Linear Secure Aggregation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2J2JRJAW}},
  note         = {Machine review of arXiv:2502.09817}
}

abstract

The secure summation problem, where $K$ users wish to compute the sum of their inputs at a server while revealing nothing about all $K$ inputs beyond the desired sum, is generalized in two aspects - first, the desired function is an arbitrary linear function (multiple linear combinations) of the $K$ inputs instead of just the sum; second, rather than protecting all $K$ inputs, we wish to guarantee that no information is leaked about an arbitrary linear function of the $K$ inputs. For this vector linear generalization of the secure summation problem, we characterize the optimal randomness cost, i.e., to compute one instance of the desired vector linear function, the minimum number of the random key variables held by the users is equal to the dimension of the vector space that is in the span of the vectors formed by the coefficients of the linear function to protect but not in the span of the vectors formed by the coefficients of the linear function to compute.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 18 canonical work pages

[4]

Secure Summation: Capacity Region, G roupwise Key, and Feasibility,

Y. Zhao and H. Sun, “Secure Summation: Capacity Region, G roupwise Key, and Feasibility,” IEEE Transactions on Information Theory , vol. 70, no. 2, pp. 1376–1387, 2024

work page 2024
[1]

Practical Secure Aggregation for Pri vacy-Preserving Machine Learn- ing,

K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. Mc Mahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical Secure Aggregation for Pri vacy-Preserving Machine Learn- ing,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Comm unications Security, 2017, pp. 1175–1191

work page 2017
[2]

Information Theoretic Secure Aggreg ation With User Dropouts,

Y. Zhao and H. Sun, “Information Theoretic Secure Aggreg ation With User Dropouts,” IEEE Transactions on Information Theory , vol. 68, no. 11, pp. 7471–7484, 2022

work page 2022
[3]

Light- SecAgg: a Lightweight and Versatile Design for Secure Aggre gation in Federated Learning,

J. So, C. J. Nolet, C.-S. Yang, S. Li, Q. Yu, R. E Ali, B. Gule r, and S. Avestimehr, “Light- SecAgg: a Lightweight and Versatile Design for Secure Aggre gation in Federated Learning,” Proceedings of Machine Learning and Systems , vol. 4, pp. 694–720, 2022

work page 2022
[5]

Secure Network Functio n Computation for Linear Functions—Part I: Source Security,

X. Guang, Y. Bai, and R. W. Yeung, “Secure Network Functio n Computation for Linear Functions—Part I: Source Security,” IEEE Transactions on Information Theory , vol. 70, no. 1, pp. 676–697, 2024

work page 2024
[6]

Secure Network Functio n Computation: Function- Security,

Y. Bai, X. Guang, and R. W. Yeung, “Secure Network Functio n Computation: Function- Security,” in 2024 IEEE International Symposium on Information Theory (ISIT) , 2024, pp. 1514–1519

work page 2024
[7]

Cache-A ided General Linear Function Retrieval,

K. Wan, H. Sun, M. Ji, D. Tuninetti, and G. Caire, “Cache-A ided General Linear Function Retrieval,” Entropy, vol. 23, no. 1, p. 25, 2020

work page 2020
[8]

On Multi-Message Private Computation,

A. Gholami, K. Wan, T. Jahani-Nezhad, H. Sun, M. Ji, and G. Caire, “On Multi-Message Private Computation,” in 2024 IEEE International Symposium on Information Theory (ISIT) , 2024, pp. 945–950

work page 2024

Show all 19 references

[9]

Private Multiple Line ar Computation: A Flexible Communication-Computation Tradeoﬀ,

J. Zhu, L. Li, X. Tang, and P. Deng, “Private Multiple Line ar Computation: A Flexible Communication-Computation Tradeoﬀ,” in 2024 IEEE International Symposium on Informa- tion Theory (ISIT) , 2024, pp. 939–944

2024
[10]

Distributed Linearl y Separable Computation,

K. Wan, H. Sun, M. Ji, and G. Caire, “Distributed Linearl y Separable Computation,” IEEE Transactions on Information Theory , vol. 68, no. 2, pp. 1259–1278, 2022

2022
[11]

Multi-Server Multi-Function Dis- tributed Computation,

D. Malak, M. R. Deylam Salehi, B. Serbetci, and P. Elia, “ Multi-Server Multi-Function Dis- tributed Computation,” Entropy, vol. 26, no. 6, p. 448, 2024

2024
[12]

On the Capacity of Computation Br oadcast,

H. Sun and S. A. Jafar, “On the Capacity of Computation Br oadcast,” IEEE Transactions on Information Theory, vol. 66, no. 6, pp. 3417–3434, 2020. 10

2020
[13]

On the Generic Capacity of K-user Symmetric Linear Computation Broadcast,

Y. Yao and S. A. Jafar, “On the Generic Capacity of K-user Symmetric Linear Computation Broadcast,” IEEE Transactions on Information Theory , vol. 70, no. 5, pp. 3693–3717, 2024

2024
[14]

Private Sum Comput ation: Trade-Oﬀ Between Shared Randomness and Privacy,

R. A. Chou, J. Kliewer, and A. Yener, “Private Sum Comput ation: Trade-Oﬀ Between Shared Randomness and Privacy,” in 2024 IEEE International Symposium on Information Theory (ISIT), 2024, pp. 927–932

2024
[15]

Weakly Secure Summation with Colluding Users,

Z. Li, Y. Zhao, and H. Sun, “Weakly Secure Summation with Colluding Users,” in 2023 IEEE International Symposium on Information Theory (ISIT) , 2023, pp. 2398–2403

2023
[16]

Network Function Computation w ith Diﬀerent Secure Conditions,

M. Xu, G. Ge, and M. Liu, “Network Function Computation w ith Diﬀerent Secure Conditions,” arXiv preprint arXiv:2206.05468 , 2022

2022 arXiv
[17]

The Capacity Re gion of Information Theo- retic Secure Aggregation with Uncoded Groupwise Keys,

K. Wan, H. Sun, M. Ji, T. Mi, and G. Caire, “The Capacity Re gion of Information Theo- retic Secure Aggregation with Uncoded Groupwise Keys,” IEEE Transactions on Information Theory, vol. 70, no. 10, pp. 6932–6949, 2024

2024
[18]

Secure Aggregation with an Oblivious Server,

H. Sun, “Secure Aggregation with an Oblivious Server,” arXiv preprint arXiv:2307.13474 , 2023

2023 arXiv
[19]

Opt imal Rate Region for Key Eﬃcient Hierarchical Secure Aggregation with User Collusi on,

X. Zhang, K. Wan, H. Sun, S. Wang, M. Ji, and G. Caire, “Opt imal Rate Region for Key Eﬃcient Hierarchical Secure Aggregation with User Collusi on,” IEEE Information Theory Workshop (ITW) , pp. 573–578, 2024. 11

2024

Pith tools

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

[1] [4]

Secure Summation: Capacity Region, G roupwise Key, and Feasibility,

Y. Zhao and H. Sun, “Secure Summation: Capacity Region, G roupwise Key, and Feasibility,” IEEE Transactions on Information Theory , vol. 70, no. 2, pp. 1376–1387, 2024

work page 2024

[2] [1]

Practical Secure Aggregation for Pri vacy-Preserving Machine Learn- ing,

K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. Mc Mahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical Secure Aggregation for Pri vacy-Preserving Machine Learn- ing,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Comm unications Security, 2017, pp. 1175–1191

work page 2017

[3] [2]

Information Theoretic Secure Aggreg ation With User Dropouts,

Y. Zhao and H. Sun, “Information Theoretic Secure Aggreg ation With User Dropouts,” IEEE Transactions on Information Theory , vol. 68, no. 11, pp. 7471–7484, 2022

work page 2022

[4] [3]

Light- SecAgg: a Lightweight and Versatile Design for Secure Aggre gation in Federated Learning,

J. So, C. J. Nolet, C.-S. Yang, S. Li, Q. Yu, R. E Ali, B. Gule r, and S. Avestimehr, “Light- SecAgg: a Lightweight and Versatile Design for Secure Aggre gation in Federated Learning,” Proceedings of Machine Learning and Systems , vol. 4, pp. 694–720, 2022

work page 2022

[5] [5]

Secure Network Functio n Computation for Linear Functions—Part I: Source Security,

X. Guang, Y. Bai, and R. W. Yeung, “Secure Network Functio n Computation for Linear Functions—Part I: Source Security,” IEEE Transactions on Information Theory , vol. 70, no. 1, pp. 676–697, 2024

work page 2024

[6] [6]

Secure Network Functio n Computation: Function- Security,

Y. Bai, X. Guang, and R. W. Yeung, “Secure Network Functio n Computation: Function- Security,” in 2024 IEEE International Symposium on Information Theory (ISIT) , 2024, pp. 1514–1519

work page 2024

[7] [7]

Cache-A ided General Linear Function Retrieval,

K. Wan, H. Sun, M. Ji, D. Tuninetti, and G. Caire, “Cache-A ided General Linear Function Retrieval,” Entropy, vol. 23, no. 1, p. 25, 2020

work page 2020

[8] [8]

On Multi-Message Private Computation,

A. Gholami, K. Wan, T. Jahani-Nezhad, H. Sun, M. Ji, and G. Caire, “On Multi-Message Private Computation,” in 2024 IEEE International Symposium on Information Theory (ISIT) , 2024, pp. 945–950

work page 2024