The Capacity of Interactive Secure Summation
Abstract
In secure summation, K parties each hold an input, and the sum of the inputs is computed at one party, securely against at most T colluding parties. Communication typically takes one hop: each party sends one message directly to the party that computes the sum, using correlated randomness that is independent of the inputs and held in advance. We consider interactive secure summation, where every pair of parties is connected by a secure link, so that each party can send messages to every other party, each party has only independent local randomness, and the messages may depend on the inputs and on earlier messages over multiple rounds. We characterize the capacity region, the set of achievable rates of communication, counting all messages exchanged among the parties over all rounds, and of the randomness of every party, counted in symbols per symbol of the sum. For 0≤ T≤ K−2, the optimal communication rate is $K(K-1)/(K-T)$, and the randomness rates form a polyhedron with, up to a relabeling of the parties, a single extreme point: T parties have the randomness rates (K+T−2t)/(K−T), t=1,…,T, and the others none. In particular, the optimal total randomness rate is $T(K-1)/(K-T)$. Linear schemes achieve every extreme point together with the optimal communication rate. The same techniques give the capacity region when every party recovers the sum and when the sum is computed at a server without input.
Related
- A Classification of Fourier Summation Formulas and Crystalline Measures
- Generalized Glaisher-Kinkelin constants and Ramanujan summation of series
- A unification of Euler-Maclaurin and Euler-Boole summation formulas
- A generating function identity for finite and symmetric multiple zeta values via Dougall's bilateral 2H2 summation
- Two parametric q-supercongruences from a summation formula for q-series
BibTeX
@misc{sun2026capacity,
title = {{The Capacity of Interactive Secure Summation}},
author = {Hua Sun},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29954},
eprint = {2610.29954},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29954},
}
RIS
TY - UNPB
TI - The Capacity of Interactive Secure Summation
AU - Hua Sun
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29954
UR - https://arxiv.org/abs/2610.29954
AB - In secure summation, K parties each hold an input, and the sum of the inputs is computed at one party, securely against at most T colluding parties. Communication typically takes one hop: each party sends one message directly to the party that computes the sum, using correlated randomness that is independent of the inputs and held in advance. We consider interactive secure summation, where every pair of parties is connected by a secure link, so that each party can send messages to every other party, each party has only independent local randomness, and the messages may depend on the inputs and on earlier messages over multiple rounds. We characterize the capacity region, the set of achievable rates of communication, counting all messages exchanged among the parties over all rounds, and of the randomness of every party, counted in symbols per symbol of the sum. For 0≤ T≤ K−2, the optimal communication rate is $K(K-1)/(K-T)$, and the randomness rates form a polyhedron with, up to a relabeling of the parties, a single extreme point: T parties have the randomness rates (K+T−2t)/(K−T), t=1,…,T, and the others none. In particular, the optimal total randomness rate is $T(K-1)/(K-T)$. Linear schemes achieve every extreme point together with the optimal communication rate. The same techniques give the capacity region when every party recovers the sum and when the sum is computed at a server without input.
ER -