PaperlayerView exact revision on arXiv

Source-linked AI summary

The Capacity of Interactive Secure Summation

Hua Sun

arXiv:2610.29954v1cs.ITmath.IT

TL;DR

Interactive secure summation replaces one-hop communication with multi-round secure links and independent local randomness, making communication and per-party randomness part of the capacity question. The paper characterizes those rates, gives linear schemes and a converse, and establishes optimal rates plus extensions to two related models.

  • Problem

    Interactive secure summation asks which communication and per-party randomness rates are achievable when parties use secure links and independent local randomness rather than one-hop messages with advance correlated randomness.

    Source: §1 · p. 1

  • Method

    The paper proves a converse for all interactive protocols and constructs linear schemes that attain the optimal communication rate with every extreme randomness allocation.

    Source: §7 · p. 21

  • Results

    For 0≤T≤K−2, optimal communication is K(K−1)/(K−T), and the per-party randomness rates form a polyhedron with one extreme point up to relabeling.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The capacity characterization extends to all-reduce and inputless-server summation, with specified changes to communication and no server randomness required.

    Source: §1 · p. 4, §7 · p. 21

    The model assumes parties follow the protocol without deviations such as dropping out.

    Source: §2 · p. 6

Abstract

from arXiv · show

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.

1 Introduction

The paper characterizes communication and per-party randomness rates for interactive secure summation with independent local randomness. It gives optimal rates, linear constructions, a converse for interactive protocols, and extensions to all-reduce and server-based summation.

1 Introduction

  • The model replaces one-hop messages and advance correlated randomness with secure links between every pair, independent local randomness, and messages that can depend on earlier rounds.Source: §1 · p. 1
  • For 0≤T≤K−2, optimal communication is K(K−1)/(K−T), and the randomness-rate polyhedron has one extreme point up to party relabeling, with total rate T(K−1)/(K−T).The T nonzero party rates are (K+T−2t)/(K−T), for t=1,…,T; linear schemes achieve every extreme point together with optimal communication.Source: §1 · p. 3
  • The construction first shares zero-sum noise, then routes noisy inputs along trees; noise cancels in each sum, while full-rank noise makes coalition observations reveal nothing beyond the sum.The example uses 8 randomness symbols for three sums, supplied by parties 1 and 2 at rates 5/3 and 1.Source: §1 · p. 3
  • The converse applies to nonlinear interactive protocols: security requires honest-party messages to carry input uncertainty, and averaging over honest sets bounds communication and randomness.Source: §1 · p. 3
  • For all-reduce, optimal communication increases by K−1 while the randomness polyhedron is unchanged; with an inputless server, user rates are unchanged, server communication is 1, and server randomness is zero.Source: §1 · p. 4

1.1 Related Work

  • Prior one-hop studies use correlated randomness, sometimes generated through input-independent communication [13] [14], whereas this work models independent local randomness at every party; earlier bounds leave long-input capacity open for 2 ≤ T ≤ K − 3.Source: §1 · p. 2, §1.1 · p. 4

2 Problem Statement

The problem statement specifies independent inputs and local randomness, secure links, and a multi-round protocol for recovering the sum while protecting inputs from colluding parties. It defines the achievable rate region and assumes protocol-following parties, while noting that weak security and vanishing recovery error leave capacity unchanged.

2 Problem Statement

  • Each of K parties holds L independent uniform input symbols over Fq and generates independent local randomness; no randomness is initially shared, and party K is the destination.Source: §2 · p. 5
  • Every pair has a secure noiseless link, and messages in each of N rounds may depend on the sender’s input, randomness, and messages received in earlier rounds.Source: §2 · p. 5
  • A valid protocol lets the destination recover the sum and ensures that at most T colluding parties learn nothing about inputs beyond their existing knowledge and, if included, the sum.Source: §2 · p. 5
  • The capacity region is the closure of achievable tuples for total communication and each party’s randomness, measured per symbol of the sum.Source: §2 · p. 6
  • Parties are assumed to follow the protocol without deviations such as dropping out; allowing vanishing recovery error and normalized leakage does not change capacity.Source: §2 · p. 6

3 Main Result

The theorem characterizes the communication and randomness rates for interactive secure summation when 0 ≤ T ≤ K − 2. Linear schemes achieve every extreme randomness allocation together with optimal communication.

3 Main Result

  • Up to relabeling, each extreme allocation gives T parties rates (K + T − 2t)/(K − T), t = 1,…,T, and zero to the others; total randomness is T(K − 1)/(K − T).The randomness region consists of vectors at least a convex combination of the extreme points.Source: §3 · pp. 7–8
  • For (K, T) = (5, 2), the 20 extreme points assign rates 5/3 and 1 to two parties, totaling 8/3.The points are grouped by the destination’s role.Source: Table 1 · p. 7, §3 · p. 7
  • RX ≥ K(K − 1)/(K − T) is the optimal communication rate for 0 ≤ T ≤ K − 2.Every extreme randomness allocation is achievable together with this rate.Source: §3 · pp. 7–8
  • For T ≥ 1, the destination’s randomness rate can range up to (K + T − 2)/(K − T), but cannot exceed that bound when total randomness is optimal.Intermediate amounts are achieved by time sharing with an extreme point where the destination has no randomness.Source: §3 · p. 8
  • With no collusion, communication rate K − 1 is achievable without randomness; requiring every party to recover the sum adds exactly K − 1 communication rate without changing randomness constraints.The no-collusion scheme sends every input to the destination.Source: §3 · p. 8
  • The converse bounds communication by averaging the load across honest sets, then bounds randomness using the entropy of messages and the sum.Each set of K − T parties is treated as an honest set; the resulting average load per link is at least 2L/(K − T) symbols.Source: §3 · p. 8
  • For any set A of M ≤ T parties, the parties outside A require randomness rate (T − M)(K − M − 1)/(K − T).This rate is achieved with optimal communication by extreme points whose M largest randomness rates are assigned to A.Source: §3 · pp. 7–8

4 Converse

The converse establishes lower bounds for interactive protocols by combining recoverability from each party’s link messages with the uncertainty security preserves among honest parties. A covering argument yields communication and randomness bounds, illustrated for (K,T)=(5,2) and generalized to all admissible K,T.

4 Converse

  • Recoverability follows because each party’s link messages together with the sum determine its input.The proof uses input independence and the fact that information about a party’s input can leave only through its links.Source: §4 · p. 9

4.1 Example: The Converse for (K, T) = (5, 2)

  • For each honest set in the (5,2) example, security requires its inputs beyond their sum to remain uncertain to the coalition, so messages among honest parties must carry that uncertainty.Covering the honest sets yields the average per-link communication lower bound.Source: §4.1 · pp. 10–11
  • For (K,T)=(5,2), the communication rate is at least 20/3 and the total randomness rate is at least 8/3.The example also establishes an average load of at least 2L/3 symbols per link.Source: §4.1 · p. 11

4.2 Proof of the Converse of Theorem 1

  • Communication rate is at least K(K−1)/(K−T), and total randomness rate is at least T(K−1)/(K−T).These are converse bounds for the general case.Source: §4.2 · p. 12
  • For any set A of M parties, with 1≤M≤T, the proof bounds randomness outside A using coalition bounds for honest sets disjoint from A.The case A=∅ gives the bound on total randomness.Source: §4.2 · p. 12

5 Achievability

The section characterizes the randomness polyhedron’s extreme points, works through a (5,2) example, and gives a scheme at every extreme point with optimal communication.

5.1 Extreme Points

  • The randomness polyhedron’s extreme points are permutations of d, whose entries are zero through K-T and then increase as d(m)=(2m-2-K+T)/(K-T).The chain argument shows there are no other extreme points.Source: §5.1 · p. 13

5.2 Example: An Extreme Point for (K, T) = (5, 2)

  • The (5,2) example first prepares zero-sum noise from two suppliers, then routes three noisy sums through collectors; unseen supplier shares provide the masking.Security holds because the relevant noise matrix is invertible for the coalition considered, and the general coalition argument retains full row rank.Source: §5.2 · pp. 14, 16
  • 20 symbols for L=3 give RX=20/3 and randomness rates (5/3,1,0,0,0) in the (5,2) example.The destination, party 5, has randomness rate 5/3 in this example.Source: §5.2 · p. 16

5.3 A Scheme at Every Extreme Point

  • In the general scheme, suppliers share zero-sum randomness, Γ converts each party’s shares into noise, and three rounds distribute shares, route noisy inputs, and forward partial sums.When q<K, the construction runs over an extension field and the rates remain unchanged.Source: §5.3 · pp. 16–17
  • For every coalition, Γ(J,U) has full row rank, so observed noise contributes its full symbol count and the mutual information in (11) is zero.This establishes security for every coalition in the scheme.Source: §5.3 · p. 17
  • RX = K(K-1)/(K-T), with randomness rates (K+T-2t)/(K-T) for supplier t after dividing its K+T-2t random symbols by K-T.The general scheme attains the extreme-point rates.Source: §5.3 · p. 17

6 Generalizations

The paper extends its interactive secure-summation capacity results to all-party recovery and to a server without input.

6.1 Output to Every Party

  • All-party recovery raises optimal communication by exactly K −1 while leaving the randomness constraints unchanged.This is secure all-reduce, in which every party recovers the sum.Source: §6.1 · p. 18
  • It is optimal to compute the sum securely at one party and send it onward; interaction cannot reduce communication.The converse uses the correlation among the parties’ final views.Source: §6.1 · p. 18

6.2 Server

  • In the server model, user-to-user communication and user randomness match Theorem 1; server communication is 1 and server randomness is unconstrained.The optimal total randomness and server communication rates are each K −1 lower than in the one-hop model [14].Source: §6.2 · p. 20

7 Conclusion

The conclusion reports exact capacity results for interactive secure summation and states that linear schemes attain the optimal rates.

7 Conclusion

  • The capacity region is characterized for all K and 0 ≤T ≤K −2, including communication and each party’s randomness.Table 4 collects the capacity regions for this range.Source: §7 · p. 21, Table 4 · p. 21
  • The converse holds for all interactive protocols.Source: §7 · p. 21
  • Linear schemes achieve the optimal rates simultaneously.Source: §7 · p. 21

A Relation to Results in Theoretical Computer Science

The paper distinguishes its per-symbol capacity results from scalar private-computation results, then compares communication and randomness costs in related regimes.

A Relation to Results in Theoretical Computer Science

  • The scalar costs in prior private-computation work are not directly comparable with rates per sum symbol as input length grows.Those works count messages and random bits for one computation, often with one bit or group element per party.Source: A Relation to Results in Theoretical… · p. 21
  • K(K−1) bits per K−T binary additions are achieved by the scheme over a binary base field.Franklin and Yung give O(K^2 log K) bits for K−T parallel additions when K > 2T + 1 and T is proportional to K.Source: A Relation to Results in Theoretical… · p. 22
  • T(K−1)/(K−T) is the optimal total randomness rate for every K and T, asymptotic to T as T/K →0.The cited batch construction has a batch size limited by the number of parties and retains overhead before reaching its amortized order.Source: A Relation to Results in Theoretical… · p. 22
Loading 2610.29954v1…