Interactive communication limits for secure multi party sum calculation
The Capacity of Interactive Secure Summation
Information Theory
Summary
Sometimes many people want to securely add their secret numbers together without anyone else finding out their individual numbers. Usually, everyone just sends one message directly to a special person who adds them up. This paper studies what happens when everyone can talk many times to each other using secret messages and only their own random choices. The authors figured out the best possible communication and randomness needed so that the sum can be computed securely, even if some people try to cheat or collaborate secretly. Their results show exactly how much talking and random secret information each person must use in this interactive setting.
What this means in practice
- •For network protocol designers: Design communication protocols for secure sum calculation that minimize total data exchange and randomness among multiple interacting parties.
- •For distributed system engineers: Build multi party computation systems that securely compute sums with optimal resource usage when parties can interact repeatedly.
A theory result. No direct application yet.
Authors
Hua Sun
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\le T\le 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,\ldots,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.