Exercises

Bonawitz requires $\binom{n}{2} \approx n^2/2$ pairwise DH exchanges. At $n = 10^5$ users, this is $5 \cdot 10^9$ exchanges per round.

At $\sim 100\mu$s per DH exchange (mobile production), $5 \cdot 10^9 \cdot 10^{-4}\text{s} = 5 \cdot 10^5$ seconds = 6 days per round.

Per-round latency far exceeds reasonable bounds (seconds-minutes). Bonawitz cannot be deployed at this $n$.

$p = c \sqrt{\log n / n}$ for some constant $c > 1$. Typical $c = 2$–$3$.

Aggregate per round: $O(n d + n \sqrt{n \log n})$. Sub-quadratic in $n$.

Bonawitz: $O(n^2 + nd)$. CCESA improvement over Bonawitz: $\Theta(\sqrt{n/\log n})$ factor on the structural overhead. At $n = 10^5$: $\sim 50\times$ faster.

The Caire et al. theorem applies to the uncoded groupwise-key class: schemes where each user's mask is a deterministic linear combination of subsetwise keys.

CCESA's mask structure is randomized (the Erdős–Rényi graph is random). The mask configuration is no longer a deterministic groupwise key; it's a randomized object with probabilistic properties.

The Caire et al. lower bound does not bind randomized schemes. CCESA's $O(n\sqrt{n/\log n})$ is below the Bonawitz $O(n^2)$ bound — but only because it operates in a different scheme class with weaker (probabilistic) guarantees.

$p = 2 \sqrt{\log n / n} = 2\sqrt{9.2 / 10^4} \approx 2 \cdot 0.0303 = 0.0606$.

$(n-1)p \approx 10^4 \cdot 0.0606 = 606$ — far less than Bonawitz's $n - 1 \approx 10^4$. Each user has $\sim 600$ mask partners instead of all $\sim 10^4$ others.

By Chernoff, every user has degree within $\pm \epsilon \cdot 606$ of the expected value with high probability. Production deployments use the maximum-expected-degree as a worst-case bound.

For each edge $\{i, j\} \in \mathcal{E}(G)$, users $i$ and $j$ contribute $+\mathbf{r}_{ij}$ and $-\mathbf{r}_{ij}$ respectively to their uploads. Summed: zero.

$\sum_k \tilde{\mathbf{g}}_k = \sum_k \mathbf{g}_k + \sum_{\{i, j\} \in \mathcal{E}} (\mathbf{r}_{ij} - \mathbf{r}_{ij}) = \sum_k \mathbf{g}_k = \mathbf{G}$. All edges contribute zero; aggregate is correct.

Self-masks $\mathbf{m}_k$ are reconstructed from Shamir shares (as in Bonawitz §10.3) and subtracted by the server. Final output: $\mathbf{G}$.

If $G$ disconnects, some pairs of users cannot share masks, leading to leftover masks in the sum. Reliability depends on connectivity.

Erdős–Rényi (1959): $G(n, p)$ is connected with probability $\to 1$ as $n \to \infty$ if $p \geq (1 + \epsilon) \log n / n$ for any $\epsilon > 0$.

$p_{\text{CCESA}} = c\sqrt{\log n/n}$. Compare to threshold $\log n/n$: $p_{\text{CCESA}} / (\log n/n) = c\sqrt{n/\log n}$ — much larger than 1 for $n$ large.

CCESA's edge density is $\sqrt{n/\log n}$- times higher than the connectivity threshold. Connectivity holds with probability $\geq 1 - n^{-\Theta(1)}$ — in fact much smaller failure than the classical threshold result (since CCESA is far above the boundary).

$p = 2\sqrt{\log 10^5 / 10^5} = 2\sqrt{11.5/ 10^5} \approx 2 \cdot 0.0107 = 0.0214$.

$\binom{10^5}{2} \cdot 0.0214 \approx 5 \cdot 10^9 \cdot 0.0214 \approx 1.07 \cdot 10^8$ DH exchanges per round.

$\binom{10^5}{2} = 5 \cdot 10^9$ DH exchanges per round.

$5 \cdot 10^9 / 1.07 \cdot 10^8 \approx 47$. CCESA needs $\sim 47\times$ fewer DH exchanges than Bonawitz at this scale.

At 100$\mu$s per DH: Bonawitz $\sim 6$ days; CCESA $\sim 3$ hours. Production-deployable for CCESA, infeasible for Bonawitz.

Below $\log n/n$, the graph disconnects, making the aggregate uncomputable. So $p > \log n/n$ is needed for correctness.

For privacy: every honest user must have an honest neighbor (not in the colluder set). At $p$ near the connectivity threshold, some honest users have very few neighbors; a colluder set covering one of them removes their honest connection.

CCESA uses $c\sqrt{\log n/n}$ — a $\sqrt{n/\log n}$ margin over connectivity. The margin ensures every user has multiple honest neighbors w.h.p., so privacy holds uniformly.

Section 12.3 Theorem 12.3.5 establishes $\Omega(\log n/n)$ as the lower bound. Closing the polylog gap to CCESA's $\sqrt{\log n/n}$ is open.

Pairwise seeds Shamir-shared with threshold $t$. Surviving users provide shares to reconstruct dropped seeds.

Same Shamir mechanism, but only over the sparse graph. Only $O(\sqrt{n \log n})$ Shamir shares per user (matching the graph degree). Reconstruction overhead drops proportionally.

Shamir threshold must satisfy the same constraints as Bonawitz: $T + 1 \leq t \leq n - \delta n$. Within this region, CCESA works with the sparse-graph adaptation.

Same privacy guarantee, lower communication — CCESA's sparse graph reduces both regular protocol and dropout-handling overhead in tandem.

If the server picks the seed, it can adaptively choose a graph that isolates specific honest users — making them have no honest neighbors. Their masks don't cancel against any honest user, exposing their gradient to the server.

With adversarial graph control, the effective coalition is potentially the entire user set (the server controls who each user shares with). Privacy guarantees vanish.

Use a randomness source the server cannot manipulate: blockchain hash, NIST beacon, distributed coin-flipping. The seed is unpredictable and verifiable, making adaptive attacks impossible.

Fix honest user $k$ and coalition $\mathcal{U}$ of size $T < n$, $k \notin \mathcal{U}$. Privacy fails for $(k, \mathcal{U})$ iff $\mathcal{N}(k) \subseteq \mathcal{U}$.

$\Pr[\mathcal{N}(k) \subseteq \mathcal{U}] = \Pr[\text{no edge from } k \text{ to } [n] \setminus \{k\} \setminus \mathcal{U}] = (1 - p)^{n - T - 1}$. For $p = c\sqrt{\log n/n}$ and $T = O(n^{1-\epsilon})$: $(1 - p)^{n-T-1} \leq \exp(-p(n-T-1)) \leq \exp(-c\sqrt{n\log n}) \leq n^{-c'}$ for some $c' = c'(c) > 0$.

Number of (honest user, coalition) pairs: $n \cdot \binom{n}{T} \leq n^{T+1}$. $\Pr[\text{any failure}] \leq n^{T + 1 - c'}$. For sufficiently large $c$ in the edge density, $c' > T + 1$, giving failure probability $\leq n^{-\Theta(1)}$.

With probability $\geq 1 - n^{-\Theta(1)}$, privacy holds uniformly over all users and coalitions. When it holds, CCESA's guarantee is Bonawitz-equivalent. $\blacksquare$

$c' = p(n - T - 1) / \log n \approx c\sqrt{\log n \cdot (n-T-1)/n}$. For $T \ll n$: $c' \approx c \sqrt{\log n}$.

At $n = 10^4$, $\log n \approx 9.2$, $c = 2$: $c' \approx 2 \sqrt{9.2} \approx 6.07$.

$n^{-c'} = 10^{-6.07 \cdot 4} \approx 10^{-24}$. Essentially zero. Even with $T = 100$ colluders, the union-bound factor $n^{T+1}$ is $10^{405}$ — still bounded by $10^{-c'\cdot 4} = 10^{-24}$ if $c' > T+1$, which requires $c$ slightly larger. In practice, choosing $c = 3$ gives more comfortable margin.

At reasonable $T$ values, CCESA's privacy failure is so improbable that "Bonawitz- equivalent w.h.p." is operationally equivalent to "always".

ByzSecAgg's coded distance computation requires every pair of users' shares to compute pairwise distances. With CCESA's sparse graph, only edges exist for some pairs — distance computation is undefined for non-edges.

One approach: compute distances only along graph edges; aggregate distance scores require additional graph-theoretic reasoning. Krum-style filtering on edge-only distances is approximate but feasible.

Whether CCESA-Byzantine composition achieves the same privacy and efficiency as ByzSecAgg-Bonawitz composition is open. The combination of sparse graph + Byzantine resilience is an active research direction (Chapter 18).

For $n \leq 200$ and Byzantine threats, use ByzSecAgg + dense graph (Chapter 11). For large-$n$ passive threats, use CCESA

• dense graph (Chapter 12). For large-$n$ Byzantine: open research.

Partition $n$ users into $k$ cohorts of size $m = n/k$ each. Run CCESA within each cohort to produce a per-cohort masked aggregate. Aggregate the $k$ cohort outputs at the server.

Within each cohort: $O(m \sqrt{m \log m})$ DH + $m d$ gradient. Total across $k$ cohorts: $k \cdot O(m\sqrt{m\log m} + m d) = O(n \sqrt{m \log m} + n d)$.

Server aggregates $k$ values. Negligible cost.

Total = $O(n \sqrt{m \log m} + n d)$ — minimized when $m$ small. But too small $m$ loses some privacy (cohort-internal privacy threshold $T$ must be at most $m - O(1)$).

$m \approx \sqrt{n}$ gives $O(n^{5/4} (\log n)^{1/2}) + O(n d)$. Slightly worse than plain CCESA's $O(n^{3/2} \sqrt{\log n})$ by a polylog factor — but conceptually cleaner. Hierarchical CCESA is a useful production tool when implementations need cohort-based parallelism.

CCESA: $O(n\sqrt{n \log n})$ aggregate. Lower bound (connectivity-based): $\Omega(n \log n)$. Gap: factor of $\sqrt{n/\log n}$.

CCESA's edge density $\sqrt{\log n/n}$ is higher than the connectivity threshold $\log n/n$ to ensure every honest user has an honest neighbor (privacy condition), not just connectivity.

• Expander graphs: random graphs with better-than-Erdős–Rényi vertex-isoperimetry. Privacy may hold at lower density.
• Bipartite constructions: separate the masking graph from the user-pair graph, giving more flexibility.
• Combinatorial designs (Steiner systems): explicit, deterministic structures with similar density to random graphs.

Several candidates exist (FastSecAgg uses regular expanders; Kadhe et al. 2020). None currently achieves $\tilde O(n \log n)$ with full Bonawitz-equivalent privacy. Closing the gap is a current research direction.