Exercises

The server (honest-but-curious) plus up to $T$ colluding users. They follow the protocol but pool all observed messages and inputs.

Server: all uploads + protocol-spec messages. Colluders: their own gradients, random coins, and received messages.

Anything about $\{\mathbf{g}_k : k \notin \mathcal{U}\}$ beyond what is implied by the aggregate $\mathbf{G} = \sum_k \mathbf{g}_k$. Information-theoretic equality: $I(\{\mathbf{g}_k\}_{k \notin \mathcal{U}}; \text{view}) = I(\{\mathbf{g}_k\}; \mathbf{G})$.

Convention: $\mathbf{r}_{ji} = -\mathbf{r}_{ij}$. For each pair $(i, j)$, user $i$ adds $+\mathbf{r}_{ij}$ and user $j$ adds $-\mathbf{r}_{ij}$. The pair's contribution is zero.

Summing over all users: $\sum_k \tilde{\mathbf{g}}_k = \sum_k \mathbf{g}_k + \sum_k \sum_{j \neq k} \mathbf{r}_{kj} = \sum_k \mathbf{g}_k + \sum_{i<j} (\mathbf{r}_{ij} + \mathbf{r}_{ji}) = \mathbf{G}$. All pairs cancel. ✓

$\binom{n}{2} = \binom{50}{2} = 1225$ pairs. Each requires one DH exchange.

$d \cdot 32 = 3.2 \cdot 10^8$ bits $= 40$ MB per user.

Aggregate uplink: $50 \cdot 40$ MB = 2 GB. Plus 1225 DH messages of $\sim 100$ bits each: negligible compared to the gradient uplink.

$T + \delta n \leq n - 1$, equivalently $T + 1 + \delta n \leq n$. The Shamir threshold $t$ must satisfy $T + 1 \leq t \leq n - \delta n$.

Strict colluder threshold ($T$) plus tolerated dropouts ($\delta n$) cannot together exceed the user pool minus one. This is a structural feasibility limit, not adjustable by clever engineering.

$\tilde{\mathbf{g}}_k = \mathbf{g}_k + \sum_{j \neq k} \pm \mathbf{r}_{kj}$. The server has no access to any $\mathbf{r}_{kj}$ (those are shared between $k$ and $j$ only). The sum of $n - 1$ independent uniform random vectors over $\mathbb{F}_q^d$ is itself uniform.

Adding $\mathbf{g}_k$ to a uniform random vector gives a uniform random vector. Hence $\tilde{\mathbf{g}}_k$ looks uniform to the server, revealing nothing about $\mathbf{g}_k$ in the marginal distribution.

The joint distribution of all uploads is constrained by $\sum_k \tilde{\mathbf{g}}_k = \mathbf{G}$ — the aggregate is the only piece of information that leaks.

If a user $k$ does not drop and the server reconstructs all of $k$'s pairwise seeds (to cancel masks of dropped users), the server can compute $\sum_{j \in \mathcal{D}} \mathbf{r}_{kj}$ — the sum of $k$'s mask contributions to dropped users. Subtracting this from the server's aggregated sum reveals additional information about $\mathbf{g}_k$.

Each user adds an extra self-mask $\mathbf{m}_k$ (Shamir-shared like the pairwise seeds). Even if all of $k$'s pairwise seeds are reconstructed, $\mathbf{m}_k$ remains private (under the threshold). Hence $\mathbf{g}_k$ stays masked.

The self-mask is reconstructed by the server only if user $k$ also drops out (other surviving users provide their shares of $b_k$). For non-dropped $k$, $\mathbf{m}_k$ remains private and protects $\mathbf{g}_k$.

Lower: $T + 1 = 31$. Upper: $n - \delta n = 200 - 50 = 150$.

Any $t \in [31, 150]$ is valid. Production choice: $t = \lceil 2n/3 \rceil = 134$ — safe margin against further dropouts and collusion beyond design assumptions.

For any secure-aggregation scheme with uncoded groupwise keys, tolerating $T$ colluders and $\delta n$ dropouts, the per-round communication is $\geq nd + \binom{n - \delta n}{2} / (n - \delta n - T)$. For $\delta = 0$ and $T = O(1)$: $R \geq nd + \Omega(n^2)$.

Uncoded groupwise keys: each user's upload is a linear combination of subsetwise random keys (no coding of gradients). Pairwise masking (Bonawitz) is the canonical instance.

Bonawitz's pairwise-masking protocol achieves the bound. Within the uncoded class, $O(n^2)$ is tight.

CCESA's mask structure is a sparse random graph (Erdős–Rényi), not a complete pairwise graph. The masking still works because the pairwise cancellations sum out probabilistically, but the construction is coded: the masks are chosen to cancel under specific subset conditions.

The Caire et al. theorem is restricted to protocols where keys are unmodified (uncoded). CCESA's mask structure is coded via the random graph topology, putting it outside the class.

CCESA achieves $O(n\sqrt{n/\log n})$ — strictly below the Caire et al. lower bound for the uncoded class. The CCESA paper (Chapter 12) provides the matching converse for the sparse-graph class.

Each user quantizes its gradient to $b$ bits per scalar before applying pairwise masks. The masks are over the same field, so the quantization is compatible with the protocol.

Per-user upload: $b \cdot d$ bits (gradient) + $O(n)$ bits (DH messages). Aggregate: $n \cdot b \cdot d + O(n^2)$ bits.

At $b = 8$ vs. $b = 32$: $4\times$ savings on gradient component. The $O(n^2)$ key overhead is unchanged. For $n = 100, d = 10^7, b = 8$: $8 \cdot 10^9 + 10^4 = 8 \cdot 10^9$ — gradient dominates. Quantization helps when $nd >> n^2$.

Server sees $\{\tilde{\mathbf{g}}_k\}_{k=1}^n$ with $\tilde{\mathbf{g}}_k = \mathbf{g}_k + \sum_j \pm \mathbf{r}_{kj}$. Pairwise seeds $\{\mathbf{r}_{ij}\}$ are uniform random over $\mathbb{F}_q^d$, independent.

Given the aggregate constraint $\sum_k \tilde{\mathbf{g}}_k = \mathbf{G}$, the joint distribution of $(\tilde{\mathbf{g}}_1, \ldots, \tilde{\mathbf{g}}_n)$ is uniform over $\{(\mathbf{x}_1, \ldots, \mathbf{x}_n) : \sum_k \mathbf{x}_k = \mathbf{G}\}$.

Conditional on $\mathbf{G}$, the server's view is uniform — independent of which specific $(\mathbf{g}_1, \ldots, \mathbf{g}_n)$ summed to $\mathbf{G}$. By the chain rule, $I(\mathbf{g}_k; \text{view}) = I(\mathbf{g}_k; \mathbf{G})$. The view adds nothing beyond the aggregate. $\blacksquare$

Consider the cut between any single user and the rest of the system. The user's upload must contribute its gradient to the aggregate, but the aggregate must reveal nothing else.

The server's view consists of $n$ uploads. For privacy, each user's upload must be masked by sufficient unique keys (in the uncoded class, this means subsetwise keys). Counting the constraints gives at least $\binom{n}{2}$ distinct keys for $T = 0, \delta = 0$.

$\binom{n}{2} = O(n^2)$ keys — each contributing at least $O(1)$ bits to the protocol's communication. Total: $O(n^2)$ key-related cost, plus $O(nd)$ gradient cost, giving the bound $R \geq nd + \Omega(n^2)$. Bonawitz matches this with equality. $\blacksquare$

Both protocols use subset-indexed keys: in coded caching, each subset of users has a common cached chunk; in secure aggregation, each pair (or subset) shares a common mask. Both use the cancellation / constraint structure of the keys to achieve the protocol's goal (deliver content / aggregate gradient).

Coded caching delivers requests across subsets (one broadcast satisfies many users); secure aggregation conceals individual contributions (sum across subsets cancels masks). The algebraic mechanics are dual: caching uses XOR-aligned broadcasts; SecAgg uses subset-cancelled masks.

Both fields use similar cut-set / IA arguments. The Caire et al. optimality proof (§10.4) reuses the Maddah-Ali / Niesen cut-set machinery. This algebraic kinship is one of the unifying themes of Part II.

Each user adds Gaussian noise $\mathcal{N}(0, \sigma^2)$ to its gradient before applying Bonawitz masks. The server receives masked noisy gradients; aggregating gives $\mathbf{G} + \mathcal{N}(0, n \sigma^2)$ — noisy aggregate.

• Information-theoretic (from Bonawitz): server learns only the (noisy) aggregate, not individual gradients.
• Differential (from DP noise): the noisy aggregate satisfies $\epsilon$-DP for some $\epsilon$ depending on $\sigma$ and the $L_2$ sensitivity of gradients.

Stronger than either alone: even if the information-theoretic guarantee were broken (e.g., by a powerful adversary), the DP noise bounds the aggregate-level leakage. Production FL deployments commonly use this composition.

The CCESA construction (random sparse graph) gives the privacy guarantee with high probability — not deterministically. The natural question is whether deterministic sparse constructions can match this.

Steiner systems, expander graphs, and other combinatorial structures have the right "any subset of $T$ users misses some key" property. Constructing such graphs with appropriate density would give a deterministic CCESA-like protocol.

No known explicit construction matches CCESA's $O(n\sqrt{n/\log n})$ bound deterministically. Some partial results exist (Kadhe et al. 2020 FastSecAgg) but with weaker scaling. The full characterization is open. Research-grade problem at the intersection of combinatorics and cryptography.