pith. sign in

arxiv: 2605.01849 · v2 · submitted 2026-05-03 · 💻 cs.IT · math.IT

Optimal Communication Rate of Secure Aggregation over Ring Networks with Pairwise Keys

Xiang Zhang , Han Yu , Zhou Li , Yizhou Zhao , Giuseppe Caire This is my paper

Pith reviewed 2026-05-09 16:55 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords secure aggregationpairwise keysring networkscommunication rateinformation-theoretic securityentropic boundsdecentralized federated learning
0
0 comments X

The pith

With only pairwise independent keys on a ring, secure aggregation of inputs requires each user to send 1 bit for K=3 or 4 and 2 bits for K at least 5.

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

This paper determines the lowest communication cost for users arranged in a circle to add up their secret values using only shared keys between each pair, without a central authority. For three or four users, one bit per user to its two neighbors suffices, but five or more users demand two bits each due to conflicting key constraints from left and right sides. A straightforward linear method of masking inputs with the keys meets this minimum exactly. Tight lower bounds from entropy arguments confirm no better rate is possible, and show that keys only between every second user are enough for optimality in larger rings. This setup supports secure distributed computing like model averaging in federated learning without single points of failure.

Core claim

In a ring network of K users with independent pairwise secret keys, the minimum per-user communication rate to securely compute the sum of inputs is 1 bit when K equals 3 or 4, and 2 bits when K is 5 or greater. This rate is achieved by a linear pairwise-masking scheme, with optimality proven through entropic converse bounds that leverage the structure of key dependencies. For K at least 4, only the pairwise keys connecting users at distance 2 on the ring are required to reach this optimal performance.

What carries the argument

Linear pairwise-masking scheme using independent pairwise keys to mask inputs, with optimality shown via entropic bounds that exploit key independence and the ring's dependency structure.

If this is right

  • The linear masking scheme meets the minimum rate exactly for every ring size.
  • Only distance-two pairwise keys suffice to achieve optimality for all K at least 4.
  • The approach removes reliance on a trusted key server since pairwise keys can be set up directly between users.
  • Results apply to secure model aggregation in decentralized federated learning on ring-like networks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same entropic bounding technique could apply to secure computation on other fixed topologies with independent local keys.
  • Sparse use of only distance-two keys suggests key management overhead can be reduced substantially in large rings without losing optimality.
  • Extensions might explore whether adaptive or nonlinear masking can lower rates when keys are generated on demand rather than pre-shared.

Load-bearing premise

The pairwise keys are independent and uniformly random, the network is a fixed ring topology, and security is perfect information-theoretic with no leakage beyond the sum.

What would settle it

Exhibiting a scheme for a five-user ring in which each user sends only one bit to neighbors while ensuring no individual input leaks beyond the sum would disprove the two-bit lower bound.

Figures

Figures reproduced from arXiv: 2605.01849 by Giuseppe Caire, Han Yu, Xiang Zhang, Yizhou Zhao, Zhou Li.

Figure 1
Figure 1. Figure 1: Key assignment for 4-user ring. Only two keys S1,3 and S2,4 (indicated by red dashed lines) out of the six pairwise keys are used. bits, and set Si,j = 0 for all other i < j. Hence, the keys of the users are Z1 = Z3 = {S1,3}, Z2 = Z4 = {S2,4}. The messages are X1 = W1 + S1,3, X2 = W2 + S2,4, X3 = W3 + S3,1, X4 = W4 + S4,2. (9) Recovery. From each user’s view, the inputs contained in the two received messag… view at source ↗
Figure 2
Figure 2. Figure 2: Key assignment for 5-user ring. Five pairwise keys S1,3, S2,4, S3,5, S1,4 and S2,5 are used. X3 = (X (4) 3 , X(2) 3 ) = (W3 + S3,5, W3 + S3,1), X4 = (X (5) 4 , X(3) 4 ) = (W4 + S4,1, W4 + S4,2), X5 = (X (1) 5 , X(4) 5 ) = (W5 + S5,2, W5 + S5,3), (10) where X (j) i denotes the message component of Xi intended for aggregation at user j ∈ Ni. Since each message has two bits, the achieved rate is RX = 2. Recov… view at source ↗
Figure 3
Figure 3. Figure 3: X2 supports the recovery of W2 + WK at user 1, and W2 + W4 at user 3. The pairwise keys S2,K and S1,2 are the shared randomness between (X2, XK) and (X2, X4), respectively. In this section, we derive a novel converse showing R∗ X ≥ 2, ∀K ≥ 5. Together with the achievable schemes, we fully characterize R∗ X for all K. Proof outline: For K ≥ 5, we prove that user 2’s message must satisfy H(X2) ≥ 2L to suppor… view at source ↗
read the original abstract

Information-theoretic topological secure aggregation (TSA)\cite{zhang2026information_regular} enables distributed users to compute neighborhood sums over arbitrary networks without revealing individual inputs, while remaining communication-efficient. It has broad applications, including secure model aggregation in decentralized federated learning (FL). Existing TSA formulations rely on arbitrarily correlated keys generated by a trusted key server, which introduces a single point of failure. In this paper, we instead study TSA with \tit{pairwise} secret keys, where each user pair $(i,j)$ shares an independent key $S_{i,j}$. Such keys can be established through inter-user communication, eliminating the need for a key server and improving robustness. Focusing on a ring topology with $K$ users, we characterize the minimum per-user communication rate: \tit{to securely compute one bit of the desired input sum, each user must send at least $1$ bit to its neighbors when $K=3,4$, and at least $2$ bits for all $K\ge 5$}. The higher rate in larger networks arises because each user must simultaneously satisfy two independent key-alignment constraints from its two neighborhoods, which cannot be resolved within a single broadcast symbol under pairwise key independence. We propose a linear pairwise-masking scheme that achieves these rates and prove its optimality via tight entropic converse bounds that exploit the dependency structure of the keys. Notably, for all $K\ge 4$, only a subset of the $\binom{K}{2}$ pairwise keys -- specifically, those between users at ring distance $2$ -- is sufficient to achieve optimality, revealing a nontrivial role of topological sparsity in secure aggregation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript characterizes the optimal per-user communication rate for information-theoretic secure aggregation over a ring network with K users using independent pairwise secret keys. It claims that the minimum rate is 1 bit per user for K=3,4 and 2 bits for K≥5 to securely compute one bit of the input sum. A linear pairwise-masking scheme achieves these rates, and tight entropic converse bounds are provided to prove optimality by exploiting the independence of the pairwise keys. For K≥4, only distance-2 pairwise keys are needed.

Significance. If the results hold, this work provides a precise characterization of communication rates in a robust pairwise-key model for secure aggregation, relevant to decentralized federated learning. The identification of the rate jump at K=5 due to independent key-alignment constraints and the sufficiency of sparse keys are notable contributions. The combination of achievable scheme and matching converse strengthens the result, though independent verification of the entropic bounds is essential given the low-level technical nature.

major comments (2)
  1. The entropic converse establishing H(M_i | keys) ≥ 2 for K≥5 relies on the independence of S_{i,i-1} and S_{i,i+1} preventing a single broadcast symbol from satisfying both left and right key-alignment constraints simultaneously. Please provide the explicit steps showing that no hidden dependence from the ring topology or shared broadcast allows rate-1 satisfaction while maintaining perfect security and correctness.
  2. The linear pairwise-masking scheme uses only distance-2 keys for K≥4; confirm that this suffices for all K and detail how the masking aligns with the two neighborhoods without increasing the rate beyond 2.
minor comments (1)
  1. The abstract mentions 'one bit of the desired input sum'; clarify if inputs are over GF(2) or general fields, and specify the field size assumed.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and indicate where revisions will be made to improve clarity.

read point-by-point responses

  1. Referee: The entropic converse establishing H(M_i | keys) ≥ 2 for K≥5 relies on the independence of S_{i,i-1} and S_{i,i+1} preventing a single broadcast symbol from satisfying both left and right key-alignment constraints simultaneously. Please provide the explicit steps showing that no hidden dependence from the ring topology or shared broadcast allows rate-1 satisfaction while maintaining perfect security and correctness.

    Authors: We appreciate the request for expanded detail on this key step. The converse proceeds from the requirement that, for correctness, the collection of messages must permit recovery of the sum X_1 + ... + X_K, while perfect security requires that each M_i is independent of all inputs given the keys. Because the keys S_{i,i-1} and S_{i,i+1} are independent, any linear (or entropic) alignment that cancels the left-neighbor mask cannot simultaneously cancel the right-neighbor mask inside a single symbol without introducing a statistical dependence between the two keys. The ring topology does not create such a dependence: each pairwise key is generated independently, and the public broadcast messages are deterministic functions of local inputs and local keys only. Consequently, the conditional entropy H(M_i | all keys) is at least 2 when the two alignments must be satisfied separately. We will insert a fully expanded derivation (including the chain-rule expansions and the explicit use of key independence) into the revised manuscript. revision: yes

  2. Referee: The linear pairwise-masking scheme uses only distance-2 keys for K≥4; confirm that this suffices for all K and detail how the masking aligns with the two neighborhoods without increasing the rate beyond 2.

    Authors: We confirm that the linear pairwise-masking scheme achieves the claimed rates for every K ≥ 4 while using only distance-2 keys. Each user i transmits a 2-bit vector consisting of the two linear combinations X_i + S_{i,i-2} and X_i + S_{i,i+2} (over GF(2)). The left neighborhood (users i-1 and i-2) uses its own distance-2 keys to unmask the contributions needed for the left local sum; the right neighborhood performs the symmetric unmasking. Because every distance-2 key appears exactly twice in the global sum (once with positive sign and once with negative sign), all masks cancel, recovering the exact input sum. The two bits are necessary and sufficient precisely because the two neighborhoods impose independent alignment constraints; no additional bits are required. This construction holds for arbitrary K ≥ 4 because the cyclic ring structure ensures that the distance-2 edges form a covering that closes consistently. We will add a short illustrative paragraph with the K = 5 case to make the alignment explicit. revision: partial

Circularity Check

0 steps flagged

No significant circularity: rate bounds derived from independent entropic analysis of key independence and ring topology.

full rationale

The paper's core result is a characterization of minimum per-user rates (1 bit for K=3,4; 2 bits for K≥5) via an explicit linear pairwise-masking achievability scheme plus tight entropic converse bounds. These bounds are constructed from first-principles entropy inequalities that directly use the stated assumptions (independent uniform pairwise keys, perfect IT security, fixed ring topology). No step reduces a claimed prediction to a fitted parameter, self-definition, or unverified self-citation chain. The single citation to prior TSA work merely contextualizes the problem setup and is not invoked to justify the new pairwise-key converses or optimality claims. The derivation therefore stands as self-contained mathematical analysis rather than a renaming or forced equivalence to its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard information-theoretic security definitions and the assumption of independent pairwise keys on a ring; no free parameters, ad-hoc axioms, or new invented entities are introduced beyond the network model.

axioms (2)
  • domain assumption Pairwise secret keys are independent and uniformly random
    Explicitly used to model the key distribution that replaces the trusted server
  • domain assumption Information-theoretic security: no leakage of individual inputs beyond the sum
    Core security requirement stated for the TSA problem

pith-pipeline@v0.9.0 · 5604 in / 1326 out tokens · 58306 ms · 2026-05-09T16:55:34.679600+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    Information-theoretic secure aggregation over regular graphs,

    X. Zhang, Z. Li, H. Yu, K. Wan, H. Sun, M. Ji, and G. Caire, “Information-theoretic secure aggregation over regular graphs,”arXiv preprint arXiv:2601.19183, 2026

    work page arXiv 2026

  2. [2]

    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,” inArtificial intelligence and statistics. PMLR, 2017, pp. 1273–1282

    work page 2017

  3. [3]

    Advances and open problems in federated learning,

    P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummingset al., “Advances and open problems in federated learning,”Foundations and trends®in machine learning, vol. 14, no. 1–2, pp. 1–210, 2021

    work page 2021

  4. [4]

    Decentralized federated learning: Fundamentals, state of the art, frameworks, trends, and challenges,

    E. T. M. Beltr´ an, M. Q. P´ erez, P. M. S. S´ anchez, S. L. Bernal, G. Bovet, M. G. P´ erez, G. M. P´ erez, and A. H. Celdr´ an, “Decentralized federated learning: Fundamentals, state of the art, frameworks, trends, and challenges,”IEEE Communications Surveys & Tutorials, vol. 25, no. 4, pp. 2983–3013, 2023

    work page 2023

  5. [5]

    Vulnerabilities in federated learning,

    N. Bouacida and P. Mohapatra, “Vulnerabilities in federated learning,”IEEE Access, vol. 9, pp. 63 229–63 249, 2021

    work page 2021

  6. [6]

    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,” inproceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Se- curity, 2017, pp. 1175–1191

    work page 2017

  7. [7]

    Federated learning with differential privacy: Algorithms and performance analysis,

    K. Wei, J. Li, M. Ding, C. Ma, H. H. Yang, F. Farokhi, S. Jin, T. Q. Quek, and H. V. Poor, “Federated learning with differential privacy: Algorithms and performance analysis,”IEEE transactions on information forensics and security, vol. 15, pp. 3454–3469, 2020. 12

    work page 2020

  8. [8]

    Personalized federated learning with differential privacy,

    R. Hu, Y. Guo, H. Li, Q. Pei, and Y. Gong, “Personalized federated learning with differential privacy,”IEEE Internet of Things Journal, vol. 7, no. 10, pp. 9530–9539, 2020

    work page 2020

  9. [9]

    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

    work page 2022

  10. [10]

    Secure summation: Capacity region, groupwise key, and feasibility,

    ——, “Secure summation: Capacity region, groupwise key, and feasibility,”IEEE Transac- tions on Information Theory, vol. 70, no. 2, pp. 1376–1387, 2024

    work page 2024

  11. [11]

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

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

    work page 2022

  12. [12]

    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, 2023

    work page 2023

  13. [13]

    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

    work page 2022

  14. [14]

    Weakly secure summation with colluding users,

    Z. Li, Y. Zhao, and H. Sun, “Weakly secure summation with colluding users,” in2023 IEEE International Symposium on Information Theory (ISIT). IEEE, 2023, pp. 2398–2403

    work page 2023

  15. [15]

    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,”IEEE Transactions on Information Theory, vol. 72, no. 2, pp. 1030–1050, 2025

    work page 2025

  16. [16]

    2025 , journal =

    X. Zhang, Z. Li, K. Wan, H. Sun, M. Ji, and G. Caire, “Fundamental limits of hierarchical secure aggregation with cyclic user association,”arXiv preprint arXiv:2503.04564, 2025

    work page arXiv 2025

  17. [17]

    Private sum computation: Trade-offs between com- munication, randomness, and privacy,

    R. A. Chou, J. Kliewer, and A. Yener, “Private sum computation: Trade-offs between com- munication, randomness, and privacy,”IEEE Transactions on Information Theory, 2026

    work page 2026

  18. [18]

    Information-theoretic decentral- ized secure aggregation with passive collusion resilience,

    X. Zhang, Z. Li, S. Li, K. Wan, D. W. K. Ng, and G. Caire, “Information-theoretic decentral- ized secure aggregation with passive collusion resilience,”IEEE Journal on Selected Areas in Communications, vol. 44, pp. 4414–4428, 2026

    work page 2026

  19. [19]

    Swiftagg+: Achieving asymp- totically optimal communication loads in secure aggregation for federated learning,

    T. Jahani-Nezhad, M. A. Maddah-Ali, S. Li, and G. Caire, “Swiftagg+: Achieving asymp- totically optimal communication loads in secure aggregation for federated learning,”IEEE Journal on Selected Areas in Communications, vol. 41, no. 4, pp. 977–989, 2023

    work page 2023

  20. [20]

    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 Transactions on Information Theory, 2024

    work page 2024

  21. [21]

    The capacity of collusion-resilient decentralized secure aggregation with groupwise keys,

    Z. Li, X. Zhang, Y. Zhao, H. Chen, J. Fan, and G. Caire, “The capacity of collusion-resilient decentralized secure aggregation with groupwise keys,”arXiv preprint arXiv:2511.14444, 2025

    work page arXiv 2025

  22. [22]

    Weakly secure summation with colluding users,

    Z. Li, Y. Zhao, and H. Sun, “Weakly secure summation with colluding users,”IEEE Trans- actions on Information Theory, 2025. 13

    work page 2025

  23. [23]

    Secure aggregation with an oblivious server,

    H. Sun, “Secure aggregation with an oblivious server,”arXiv preprint arXiv:2307.13474, 2023

    work page arXiv 2023

  24. [24]

    Vector linear secure aggregation,

    X. Yuan and H. Sun, “Vector linear secure aggregation,” 2025. [Online]. Available: https://arxiv.org/abs/2502.09817

    work page arXiv 2025

  25. [25]

    On the capacity region of individual key rates in vector linear secure aggregation,

    L. Hu and S. Ulukus, “On the capacity region of individual key rates in vector linear secure aggregation,”arXiv preprint arXiv:2601.03241, 2026

    work page arXiv 2026

  26. [26]

    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,”arXiv preprint arXiv:2410.14035, 2024

    work page arXiv 2024

  27. [27]

    Capacity of hierarchical secure coded gradient aggregation with straggling communication links,

    Q. Lu, J. Cheng, W. Kang, and N. Liu, “Capacity of hierarchical secure coded gradient aggregation with straggling communication links,”arXiv preprint arXiv:2412.11496, 2024

    work page arXiv 2024

  28. [28]

    Private aggregation in hierarchical wireless federated learning with partial and full collusion,

    M. Egger, C. Hofmeister, A. Wachter-Zeh, and R. Bitar, “Private aggregation in hierarchical wireless federated learning with partial and full collusion,”IEEE Transactions on Information Theory, 2025

    work page 2025

  29. [29]

    On hierarchical secure aggregation against relay and user collusion,

    M. Xu, X. Han, K. Wan, and G. Ge, “On hierarchical secure aggregation against relay and user collusion,”arXiv preprint arXiv:2511.20117, 2025

    work page arXiv 2025

  30. [30]

    DISPFL: Towards communication- efficient personalized federated learning via decentralized sparse training,

    R. Dai, L. Shen, F. He, X. Tian, and D. Tao, “DISPFL: Towards communication- efficient personalized federated learning via decentralized sparse training,”arXiv preprint arXiv:2206.00187, 2022

    work page arXiv 2022

  31. [31]

    The diffie–hellman protocol,

    U. M. Maurer and S. Wolf, “The diffie–hellman protocol,”Designs, Codes and Cryptography, vol. 19, no. 2, pp. 147–171, 2000

    work page 2000

  32. [32]

    Secure multi-party computation,

    O. Goldreich, “Secure multi-party computation,”Manuscript. Preliminary version, vol. 78, no. 110, pp. 1–108, 1998. 14

    work page 1998