Ferkans — Interactive Telecom Tutor

The Sparse Random-Graph Idea

The core insight of CCESA is simple to state but subtle to analyze: use a sparse random graph of masks instead of the complete graph. If the Bonawitz protocol mask pair-graph is replaced by an Erdős–Rényi random graph $G(n, p)$ with $p = O(\sqrt{\log n / n})$ , the resulting protocol still provides the privacy guarantees of Bonawitz (with high probability), and its communication overhead drops from $O(n^2)$ to $O(n\sqrt{n/\log n})$ .

The point is that the complete-graph mask structure of Bonawitz is overkill. The graph just needs to be "connected enough" to cancel masks in the aggregate, and an Erdős–Rényi graph is connected with high probability at edge densities much lower than the complete graph.

Section 12.2 develops the CCESA construction and identifies it as the fourth CommIT contribution of Part III. Section 12.3 proves the privacy and reliability guarantees; §12.4 places CCESA in the broader design space.

🎓CommIT Contribution(2022)

CCESA: Communication-Efficient Secure Aggregation via Sparse Random Graphs

B. Choi, J.-y. Sohn, D.-J. Han, J. Moon, G. Caire — IEEE Journal on Selected Areas in Communications

CCESA is the CommIT-group contribution by Byeong-Geun Choi, Jy-yong Sohn, Dong-Jun Han, Jaekyun Moon, and Giuseppe Caire. It reduces the Bonawitz protocol's per-round communication overhead from $O(n^2)$ to $O(n\sqrt{n/\log n})$ by using a sparse Erdős–Rényi random graph of pairwise masks instead of the complete graph.

Key technical contributions:

Sparse random-graph mask structure. Each pair of users $(i, j)$ shares a pairwise mask with probability $p = c \sqrt{\log n / n}$ for a constant $c > 1$ , independently per pair. The expected number of mask pairs per user is $O(\sqrt{n \log n})$ instead of $O(n)$ .
Privacy + reliability guarantees via random- graph theory. The privacy guarantee holds with probability $\geq 1 - n^{-\Theta(1)}$ (uniform over the graph draw). Reliability (server can always reconstruct) holds with the same probability.
Communication complexity $O(n\sqrt{n/\log n})$ . Matches the information-theoretic lower bound for sparse-graph schemes up to logarithmic factors.
Compatibility with dropouts and threshold cryptography. CCESA is drop-in compatible with Chapter 10's dropout-handling via Shamir-shared seeds; the sparse-graph structure does not break this integration.

Why it matters: CCESA unlocks secure aggregation at large $n$ — essential for modern cross-device FL (millions of users) and cross-silo federations (hundreds of institutions). The sparse-graph idea transfers to many secure-aggregation variants and is now standard in production thinking.

The result is the fourth CommIT Part III contribution (after Chapter 3 foundations, Chapter 10 optimality, and Chapter 11 ByzSecAgg), closing the CommIT-group privacy-preserving FL research programme at the information-theoretic frontier.

ccesacommit-contributionsparse-graphView Paper →

Definition:
CCESA Protocol

The CCESA protocol for $n$ users, collusion threshold $T$ , and edge probability $p = c\sqrt{\log n / n}$ (for some constant $c > 1$ ) operates as follows:

Phase 0: Graph Sampling. A publicly-known pseudorandom generator samples an Erdős–Rényi graph $G = G(n, p)$ : for each pair $(i, j)$ , independently include the edge $\{i, j\} \in \mathcal{E}(G)$ with probability $p$ . The graph is derived deterministically from a round-specific public seed, so all users and the server agree on $G$ .

Phase 1: Pairwise Key Exchange (sparse). For each edge $\{i, j\} \in \mathcal{E}(G)$ , users $i$ and $j$ perform a Diffie–Hellman exchange and derive a pairwise seed $s_{ij}$ via a PRG. Users do not exchange keys with non-neighbors.

Phase 2: Masked Upload. User $k$ uploads $\tilde{\mathbf{g}}_k \;=\; \mathbf{g}_k + \sum_{j \in \mathcal{N}(k)} \text{sign}(k, j) \mathbf{r}_{kj} \;+\; \mathbf{m}_k,$ where $\mathcal{N}(k)$ is $k$ 's graph neighborhood and $\mathbf{m}_k$ is a self-mask (as in Bonawitz §10.3). Note: far fewer masks per user than in Bonawitz.

Phase 3: Aggregation. Server computes $\mathbf{G} = \sum_k \tilde{\mathbf{g}}_k$ . Masks cancel because edges in the graph contribute symmetric $\pm \mathbf{r}_{ij}$ pairs.

Phase 4: Dropout Handling (optional). Shamir shares of the pairwise seeds are exchanged as in Bonawitz — but only over the sparse graph, reducing overhead.

The protocol's correctness and privacy depend on the graph being "well-connected" with high probability, which Erdős–Rényi at $p = c\sqrt{\log n / n}$ achieves.

The key contrast with Bonawitz: each user has degree $\Theta(\sqrt{n \log n})$ in CCESA vs. degree $n - 1$ in Bonawitz. Per-user DH exchanges drop from $O(n)$ to $O(\sqrt{n \log n})$ , and aggregate DH overhead from $O(n^2)$ to $O(n \sqrt{n \log n})$ . Reliability and privacy are preserved with high probability over the random graph.

CCESA

Communication-Efficient Secure Aggregation via sparse Erdős–Rényi random graphs. Reduces Bonawitz's $O(n^2)$ overhead to $O(n\sqrt{n/\log n})$ while preserving information-theoretic privacy (with high probability). The fourth CommIT-group Part III contribution.

Erdős–Rényi Random Graph

The random graph $G(n, p)$ where each of the $\binom{n}{2}$ edges is included independently with probability $p$ . Classical connectivity threshold: $G(n, p)$ is connected w.h.p. iff $p \geq (1 + \epsilon)\log n / n$ for any $\epsilon > 0$ . CCESA uses edge density $p = c\sqrt{\log n / n}$ , well above the connectivity threshold, for privacy + reliability guarantees.

CCESA Protocol

Complexity: Per-user:

O(\sqrt{n \log n})

DH exchanges,

d

-scalar upload. Aggregate:

O(n \sqrt{n \log n})

DH + Shamir-share overhead.

Input: Number of users

n

, collusion

threshold

T

, edge probability

p

, round seed.

Setup. All parties compute

G = G(n, p)

deterministically from the round seed (so no

communication needed for graph agreement).

Phase 1 — User $k$ :

1. Identify neighbors

\mathcal{N}(k) = \{j : \{k, j\} \in \mathcal{E}(G)\}

.

2. For each

j \in \mathcal{N}(k)

, execute

Diffie–Hellman key exchange. Derive pairwise

seed

s_{kj}

.

3. Derive pairwise masks

\mathbf{r}_{kj}

via PRG

on

s_{kj}

.

4. Draw self-mask seed

b_k

uniformly.

Phase 2 — User $k$ :

5. Compute

\mathbf{m}_k

from

b_k

via PRG.

6. Upload

\tilde{\mathbf{g}}_k = \mathbf{g}_k + \sum_{j \in \mathcal{N}(k)} \text{sign}(k, j) \mathbf{r}_{kj} + \mathbf{m}_k

to the server.

Phase 3 — Server:

7. Receive all

\tilde{\mathbf{g}}_k

. Sum over

k

.

8. Mask terms cancel per edge:

\sum_k \sum_{j \in \mathcal{N}(k)} \text{sign}(k, j) \mathbf{r}_{kj} = \sum_{\{i,j\} \in \mathcal{E}} (\mathbf{r}_{ij} - \mathbf{r}_{ij}) = \mathbf{0}

.

9. Self-masks: need to reconstruct all

\mathbf{m}_k

(from Shamir shares) and subtract. Output:

\mathbf{G} = \sum_k \mathbf{g}_k

.

Phase 4 — Dropout handling (as in §10.3):

10. For any dropped user

j

: surviving neighbors'

Shamir shares of

s_{jk}

are collected. Seeds

reconstructed, leftover masks cancelled.

The protocol is structurally identical to Bonawitz — only the graph density differs. All the same cryptographic primitives (DH, PRG, Shamir sharing) apply. Implementation overhead is low; performance benefit is dramatic.

Theorem: CCESA Communication Complexity

The CCESA protocol with $n$ users, edge probability $p = c \sqrt{\log n / n}$ (for some constant $c > 1$ ), and model dimension $d$ has:

Per-user uplink: $d$ scalars (gradient) + $O(\sqrt{n \log n})$ DH exchanges.
Aggregate per-round communication: $O(n \cdot d + n \sqrt{n \log n})$ .
Per-user DH cost: $\Theta(\sqrt{n \log n})$ — a $\sqrt{n/\log n}$ reduction over Bonawitz.

Simplified for the typical $d = \Theta(n)$ regime: $O(n d + n^{3/2} \sqrt{\log n}) = O(n \sqrt{n/\log n})$ — sub-quadratic, substantial improvement over Bonawitz's $O(n^2)$ .

Each user's degree in $G(n, p)$ is $\text{Bin}(n-1, p)$ with expectation $(n-1)p \approx c \sqrt{n \log n}$ . Chernoff: with high probability, every user has degree $\Theta(\sqrt{n \log n})$ . Hence each user does $\Theta(\sqrt{n \log n})$ DH exchanges, not $O(n)$ as in Bonawitz. Aggregate overhead: $n \cdot \Theta(\sqrt{n \log n}) = \Theta(n \sqrt{n \log n})$ — sub-quadratic.

Operationally: at $n = 10^5$ , CCESA's DH phase is $\sim \sqrt{n \log n} \approx 3200$ exchanges per user — tractable in seconds. Bonawitz at the same scale would need $\sim 10^5$ exchanges per user — several minutes, impractical.

Proof

Degree concentration

Each user $k$ 's degree $\deg(k) = |\mathcal{N}(k)|$ is a sum of $n - 1$ independent Bernoulli $(p)$ random variables. By Chernoff: $\Pr[|\deg(k) - (n-1)p| > \epsilon (n-1)p] \leq 2 \exp(-\epsilon^2 (n-1)p / 3)$ . For $p = c\sqrt{\log n / n}$ , this is $\leq 2 \exp( -\Theta(\sqrt{n \log n}))$ — vanishingly small.

Aggregate degree

Sum of degrees = $2 |\mathcal{E}(G)|$ . Total edges: $\Theta(n \sqrt{n \log n} / 2) = \Theta( n^{3/2} \sqrt{\log n})$ w.h.p.

DH exchanges

One DH per edge: $\Theta(n^{3/2} \sqrt{\log n})$ DH exchanges aggregate, vs. Bonawitz's $\Theta(n^2)$ . Ratio: $n^{1/2} / \sqrt{\log n}$ — sub-quadratic savings.

Gradient upload

Unchanged: $n \cdot d$ scalars aggregate. For moderate-to-large $d$ , gradient dominates; for small $d$ , the $n^{3/2}$ overhead dominates. CCESA is best when both terms are comparable. $\blacksquare$

Example: CCESA vs. Bonawitz at $n = 10^5$

For $n = 10^5$ users, model size $d = 10^7$ , compute per-user DH exchanges and aggregate communication for both Bonawitz and CCESA.

Solution

Bonawitz

Per-user DH: $n - 1 \approx 10^5$ . Aggregate DH: $\binom{n}{2} \approx 5 \cdot 10^9$ . Gradient upload: $n d = 10^{12}$ scalars. Total: $\sim 10^{12}$ (gradient dominates for $d = 10^7$ ).

CCESA

Edge probability: $p = c\sqrt{\log n / n} = c\sqrt{11.5/10^5} \approx c \cdot 0.0107$ . At $c = 2$ : $p \approx 0.021$ . Per-user DH: $(n-1)p \approx 2140$ — a $\sim 50\times$ reduction over Bonawitz. Aggregate DH: $\binom{n}{2} p \approx 10^8$ — $50\times$ fewer. Gradient: same $10^{12}$ . Total: $\sim 10^{12}$ (gradient still dominates).

DH-time savings

Bonawitz DH time: $5 \cdot 10^9 \cdot 10^{-4} \text{ s} = 5 \cdot 10^5$ s = 5.8 days. CCESA DH time: $10^8 \cdot 10^{-4} = 10^4$ s = 2.8 hours. Ratio: $\sim 50\times$ faster DH phase.

Conclusion

At $n = 10^5$ , CCESA reduces the Bonawitz overhead from "years per round" to "hours per round" — a deployability transformation. Gradient upload dominates both total communications, but CCESA's $50\times$ reduction in DH time is critical for production viability.

From Complete Graph to Sparse Erdős–Rényi

Animation of the transition from Bonawitz's complete- graph pairwise masking to CCESA's sparse Erdős–Rényi graph. Highlights how edges are removed while the graph remains connected, preserving privacy and reliability with lower overhead.

CCESA Graph Density vs. Communication Savings

Plot the per-user DH-exchange count vs. number of users $n$ for CCESA (at various $c$ values in the edge probability $p = c \sqrt{\log n / n}$ ) and for Bonawitz ( $n - 1$ exchanges per user). Larger $c$ gives denser graphs with better connectivity margins but more overhead; typical $c = 2$ – $3$ .

Parameters

n

max — users10000

c

— constant in

p

2

The Graph Is Pseudorandomly Generated

CCESA's random graph is not drawn fresh by each user independently — that would require all users to agree on the graph, requiring $O(n^2)$ communication to confirm. Instead, the graph is pseudorandomly generated from a public round-specific seed. All users and the server apply a known PRG to the seed and obtain the same graph deterministically.

This is a standard trick in protocol design: use public randomness for structural decisions (which users share keys) that must be agreed upon, reserving fresh randomness for the cryptographic primitives (the DH exchanges themselves, the mask derivation). Production implementations use a round-specific seed derived from a beacon or blockchain hash.

🔧Engineering Note

CCESA in Production

Production CCESA deployments (as of 2024) are research-track:

TU Berlin CommIT group: reference implementation in Python/TensorFlow.
Google research: integration into TensorFlow Federated for large- $n$ deployments.
Academic testbeds: cross-institution federated learning pilots at $n \sim 10^3$ .

Engineering considerations:

Graph seed coordination: a round-specific public seed must be agreed upon without $O(n^2)$ communication. Typically derived from a blockchain hash or NIST beacon.
Graph discovery: users compute their neighborhood locally; no per-neighbor communication needed beyond the DH exchange.
Degree variance: Chernoff bounds guarantee degree concentration, but some users may have slightly-above-average degree. Production implementations pad to the maximum expected degree.

The shift from Bonawitz to CCESA is conceptually simple and implementation-light; adoption is gated primarily by the need to validate the graph-theoretic analysis at production scale.

Practical Constraints

•
Graph seed: from blockchain/beacon, $O(1)$ broadcast
•
Degree concentration: Chernoff w.h.p.
•
Adoption path: research → research production → standard (timeline: 1–3 years)

📋 Ref: Choi et al. 2022 J-SAC; TU Berlin CommIT implementation

Key Takeaway

CCESA achieves $O(n\sqrt{n/\log n})$ communication by using a sparse Erdős–Rényi random graph of pairwise masks. The construction is a minimal modification of Bonawitz (change the graph structure; keep DH, PRG, Shamir) with a sub-quadratic asymptotic advantage. The privacy and reliability guarantees hold with high probability over the random graph — a relaxation so mild that it is operationally equivalent to deterministic. Section 12.3 proves these guarantees rigorously.

Common Mistake: The Graph Must Not Be Too Sparse

Mistake:

Set edge probability $p = O(1/n)$ (much below CCESA's $p = c\sqrt{\log n/n}$ ) to save even more communication.

Correction:

Erdős–Rényi's connectivity threshold is $p \geq (1 + \epsilon)\log n / n$ . Below this, the graph has isolated vertices w.h.p. — users without mask partners. Their masks do not cancel; the server cannot compute the aggregate. CCESA's $p = c\sqrt{\log n/n}$ is well above connectivity but below complete — the sweet spot.

Attempting to push $p$ lower risks: (i) isolated vertices (aggregation fails), (ii) small privacy threshold (any $T$ colluders can fragment the graph). The factor $c > 1$ is the safety margin; production uses $c \geq 2$ with verified Chernoff-margin analysis.

Historical Note: From FastSecAgg to CCESA

2020–2022

Reducing Bonawitz's $O(n^2)$ overhead was a recognized open problem circa 2020. FastSecAgg (Kadhe, Rajaraman, Koyluoglu, Ramchandran 2020) was the first practical proposal: regular-graph mask structure with $O(n \log n)$ overhead, but at weakened privacy (the regular-graph structure creates predictable correlations that can be exploited).

CCESA (Choi, Sohn, Han, Moon, Caire 2022) took the next step: random Erdős–Rényi graphs instead of regular. The random-graph analysis gives tight privacy guarantees (high-probability Bonawitz-equivalent privacy) at $O(n\sqrt{n/\log n})$ overhead. The CommIT-group collaboration between TU Berlin and KAIST produced a clean construction that has since become a standard reference.

Post-CCESA, the field continues to explore sparser constructions (expander graphs, combinatorial designs) but CCESA remains the benchmark for random-graph-based secure aggregation.

,

Quick Check

CCESA uses Erdős–Rényi graph $G(n, p)$ with edge probability:

$p = 1$ (complete graph — same as Bonawitz).

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

$p = 1/n$ (constant-degree).

$p = \\log n / n$ (connectivity threshold).

Correction:

p = c \sqrt{\\log n / n}

for some constant

c > 1

.

Correct. This density is well above the $\log n / n$ connectivity threshold and achieves $O(n\\sqrt{n/\\log n})$ aggregate overhead.

CCESA: The Sparse Random-Graph Construction (CommIT Contribution)

The Sparse Random-Graph Idea

CCESA: Communication-Efficient Secure Aggregation via Sparse Random Graphs

Definition: CCESA Protocol

CCESA

Erdős–Rényi Random Graph

CCESA Protocol

Theorem: CCESA Communication Complexity

Degree concentration

Aggregate degree

DH exchanges

Gradient upload

Example: CCESA vs. Bonawitz at n=105n = 10^5n=105

Bonawitz

CCESA

DH-time savings

Conclusion

From Complete Graph to Sparse Erdős–Rényi

CCESA Graph Density vs. Communication Savings

Parameters

The Graph Is Pseudorandomly Generated

CCESA in Production

Key Takeaway

Common Mistake: The Graph Must Not Be Too Sparse

Historical Note: From FastSecAgg to CCESA

Quick Check

Definition:
CCESA Protocol

Example: CCESA vs. Bonawitz at $n = 10^5$