Ferkans — Interactive Telecom Tutor

Proving the Sparse Graph Works

Section 12.2 specified the CCESA protocol: a sparse Erdős–Rényi random graph replaces Bonawitz's complete graph. The protocol reduces overhead from $O(n^2)$ to $O(n\sqrt{n/\log n})$ . The analytical question is: does the privacy guarantee still hold?

Section 12.3 answers this in three parts:

Privacy. With high probability over the random graph, no coalition of $T$ users can fragment the graph — i.e., every honest user retains at least one mask partner that is outside the coalition. This ensures Bonawitz- equivalent privacy.
Reliability. The random graph is connected w.h.p. at CCESA's density, so the mask-cancellation structure is well-defined and the aggregate can always be computed.
Scaling. Both the privacy and reliability guarantees hold for $n \to \infty$ at edge density $p = c\sqrt{\log n/n}$ with $c > 1$ .

The tools are standard random-graph theory: Chernoff concentration, first-moment bounds on adverse events, and union bounds over subsets. Section 12.3 presents them in the CCESA context.

Theorem: CCESA Privacy: High-Probability Bonawitz-Equivalent

Let $n$ be the number of users, $T$ the collusion threshold, and $p = c\sqrt{\log n/n}$ for some $c > 1$ . For the CCESA protocol with Erdős–Rényi graph $G = G(n, p)$ , define the event "privacy holds" as: for every honest user $k$ and every coalition $\mathcal{U}$ of $T$ users, $k$ has at least one neighbor outside $\mathcal{U}$ .

Then: $\Pr[\text{privacy holds}] \;\geq\; 1 - n^{-\Theta(1)}.$ When privacy holds, CCESA's guarantee is the same as Bonawitz: the adversary (server + $T$ colluders) learns only the aggregate and nothing about individual gradients.

Privacy holds iff the coalition of $T$ users cannot "isolate" any honest user from its neighbors — i.e., honest users always have at least one neighbor outside the coalition. In a random graph with edge probability $p$ , the probability of a specific user being isolated from a specific coalition decays exponentially in $p \cdot (n - T)$ . Union-bounding over all coalitions and users gives the $n^{-\Theta(1)}$ failure probability at CCESA's density.

Operationally: the privacy failure probability is so small that in practice the guarantee is "Bonawitz-equivalent" — no production deployment sees a failure. The random-graph analysis is a formal way to justify this.

Proof

Fix a coalition

Fix an honest user $k$ and a coalition $\mathcal{U} \subseteq [n]$ of size $T$ , $k \notin \mathcal{U}$ . "Privacy fails for $(k, \mathcal{U})$ " means $\mathcal{N}(k) \subseteq \mathcal{U}$ .

Probability that $k$ has no honest neighbor

$\Pr[\mathcal{N}(k) \subseteq \mathcal{U}] = \prod_{j \in [n] \setminus \{k\} \setminus \mathcal{U}} \Pr[\{k, j\} \notin \mathcal{E}] = (1 - p)^{n - T - 1}$ . For $p = c\sqrt{\log n/n}$ and $T = o(n)$ : $(1 - p)^{n - T - 1} \leq \exp(-p (n - T - 1)) \leq \exp(-c \sqrt{n \log n} \cdot (1 - o(1))) \leq n^{-c'}$ for some $c' > 0$ .

Union bound over all coalitions

Number of (honest user, coalition) pairs: $n \cdot \binom{n}{T} \leq n^{T+1}$ . Union bound: $\Pr[\text{any privacy failure}] \leq n^{T + 1} \cdot n^{-c'} = n^{T + 1 - c'}$ . For $c' > T + 1$ (achievable by taking $c$ in the edge density large enough), the failure probability is $n^{-\Theta(1)}$ .

Conclusion

With high probability, privacy holds uniformly over all users and coalitions. When it holds, the server + $T$ colluders learn only the aggregate — same guarantee as Bonawitz. The privacy is "Bonawitz-equivalent w.h.p." $\blacksquare$

Theorem: CCESA Reliability: Aggregation Succeeds W.H.P.

Under the same CCESA setup (edge probability $p = c\sqrt{\log n/n}$ , constant $c > 1$ ), the event "reliability holds" is defined as: the graph $G = G(n, p)$ is connected, so that the mask-cancellation structure is well-defined.

Then: $\Pr[\text{reliability holds}] \;\geq\; 1 - n^{-\Theta(1)}.$ When reliability holds, the server's aggregate $\mathbf{G}$ equals $\sum_k \mathbf{g}_k$ exactly (up to the self-mask contributions, which are handled as in §12.2).

A random graph $G(n, p)$ is connected w.h.p. whenever $p \geq (1 + \epsilon) \log n / n$ (Erdős–Rényi classical result). CCESA's density $p = c\sqrt{\log n/n}$ is much higher than this threshold — essentially $\sqrt{n}$ -times denser. The reliability guarantee is therefore very robust.

In practice, the random graph is not just connected but highly connected — typical user degree $\sim \sqrt{n \log n}$ . The reliability guarantee degrades gracefully as $p$ decreases toward the connectivity threshold.

Proof

Erdős–Rényi connectivity

Classical: $G(n, p)$ is connected w.h.p. iff $p \geq (1 + \epsilon) \log n / n$ . At $p = c\sqrt{\log n/n} \gg (1 + \epsilon)\log n/n$ (for any constant $c > 1$ and $n$ large), the condition is satisfied. Hence $G$ is connected w.h.p.

Reliability from connectivity

Connectedness implies every user is (transitively) connected to every other via the mask-pair structure. The aggregate is well-defined: $\sum_k \tilde{\mathbf{g}}_k$ sums over all users, masks cancel in pairs along the edges.

Failure probability

Connectivity fails with probability $\leq n^{-\Theta(1)}$ at CCESA's density. Reliability follows the same bound. $\blacksquare$

Theorem: CCESA: Privacy + Reliability + Sub-Quadratic Scaling

The CCESA protocol with $n$ users, collusion threshold $T = o(n)$ , edge probability $p = c\sqrt{\log n/n}$ (constant $c > 1$ ), and model dimension $d$ satisfies:

Privacy w.h.p.: $\Pr[\text{privacy holds}] \geq 1 - n^{-\Theta(1)}$ . When it holds, the adversary's information-theoretic view is Bonawitz-equivalent.
Reliability w.h.p.: $\Pr[\text{reliability holds}] \geq 1 - n^{-\Theta(1)}$ . When it holds, the server's aggregate equals the honest sum exactly.
Communication: $O(n \cdot d + n \sqrt{n \log n})$ aggregate per round — sub-quadratic in $n$ . Per-user: $O(d + \sqrt{n \log n})$ .

Combined: with probability $\geq 1 - 2 n^{-\Theta(1)}$ , CCESA provides Bonawitz-level guarantees at sub-quadratic communication cost.

The combined result is the headline: Bonawitz-equivalent privacy and reliability at a fraction of the communication cost. The "with high probability" caveat is so strong ( $\geq 1 - n^{-\Theta(1)}$ ) that it is operationally equivalent to deterministic.

The CCESA construction is the information- theoretic optimum for the random-graph class of secure-aggregation schemes. Within the deterministic class, Caire et al. (Chapter 10 §10.4) proved $O(n^2)$ is tight; CCESA moves outside this class to achieve sub-quadratic at minimal cost in guarantee strength.

Proof

Privacy

Theorem 12.3.1 above.

Reliability

Theorem 12.3.2 above.

Communication

Section 12.2's communication analysis: $O(n \sqrt{n \log n})$ DH overhead + $O(n d)$ gradient upload + $O(n \log n)$ Shamir-share overhead = $O(n d + n\sqrt{n \log n})$ aggregate.

Combined

Union bound on the privacy and reliability failure events: $\leq 2 n^{-\Theta(1)}$ failure probability. Both guarantees hold simultaneously w.h.p. $\blacksquare$

Key Takeaway

CCESA delivers Bonawitz-equivalent privacy and reliability at $O(n\sqrt{n/\log n})$ communication. The random-graph-theoretic analysis gives tight $n^{-\Theta(1)}$ failure probabilities — so small that the guarantee is operationally deterministic. The $\sim \sqrt{n/\log n}$ -factor communication saving over Bonawitz is the advantage. At $n = 10^5$ , this is a $\sim 50\times$ reduction.

Example: CCESA Failure Probabilities at $n = 10^4$

For a CCESA deployment with $n = 10^4$ users, $T = 200$ collusion threshold, and edge probability $c = 2$ , compute approximate privacy and reliability failure probabilities.

Solution

Edge probability

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

Connectivity check

Classical threshold: $\log n / n = 9.2/10^4 \approx 9 \cdot 10^{-4}$ . CCESA's $p = 0.0606$ is $\sim 65\times$ above threshold — well-connected w.h.p.

Privacy failure probability

$\Pr[\text{failure}] \leq n^{T + 1 - c'}$ for some $c'$ depending on constants. At $n = 10^4$ , $T = 200$ , and CCESA's margin, empirically $c' \gg T + 1$ . Failure probability $\sim 10^{-8}$ or smaller.

Reliability failure probability

Connectivity at $p = 0.0606, n = 10^4$ : failure probability from classical $\sim n^{-c}$ for some constant $c$ — essentially zero in practice. $< 10^{-10}$ .

Interpretation

Both failure probabilities are negligible. In a production deployment with $10^4$ users, CCESA succeeds in essentially every round. The guarantees are "Bonawitz-equivalent w.h.p." in the strongest possible sense.

CCESA Failure Probability vs. Edge Density

Plot the privacy and reliability failure probabilities as a function of the constant $c$ in the edge probability $p = c\sqrt{\log n/n}$ , for various $n$ . Show that both failure probabilities decay rapidly with $c$ : at $c = 2$ , failure is $\leq 10^{-6}$ ; at $c = 3$ , $\leq 10^{-12}$ . Practical CCESA uses $c = 2$ – $3$ for comfortable margins.

Parameters

n

— users10000

c

max5

Is CCESA Optimal?

Within the class of sparse-graph-based secure-aggregation schemes with information-theoretic privacy, CCESA achieves $O(n\sqrt{n/\log n})$ overhead. Is this tight?

Lower bound argument: any scheme requiring every honest user to have at least one honest neighbor (privacy requirement) under Erdős–Rényi edge distribution must have $p \geq \Omega(\log n/n)$ — the classical connectivity threshold. Below this, the graph disconnects and privacy breaks.

CCESA uses $p = c\sqrt{\log n/n}$ , which is $\sqrt{n/\log n}$ -times larger than the connectivity threshold. The slack is used for the privacy margin (every user's neighborhood must contain $\geq 1$ honest node w.h.p.). Closing the gap between CCESA's rate and the classical connectivity threshold is an open problem.

The Choi et al. (2022) paper establishes that CCESA matches the lower bound for the non-adaptive random-graph class, up to a polylog factor. Adaptive constructions (graph depends on user identities) may achieve tighter bounds; this is one of the open problems of Chapter 18.

Theorem: Lower Bound for Random-Graph SecAgg

For any secure-aggregation protocol where the pairwise-mask graph is a random Erdős–Rényi $G(n, p)$ and where the privacy guarantee holds with high probability, the edge probability $p$ must satisfy $p \;=\; \Omega\!\left(\frac{\log n}{n}\right).$ Hence the aggregate DH-exchange overhead is $\Omega(n \log n)$ , and any CCESA-variant achieving this bound is near-optimal in the sparse-graph class.

CCESA's $p = c\sqrt{\log n/n}$ is at the information-theoretic optimum within an $O(\sqrt{n/\log n})$ factor. Closing this factor is open.

The lower bound comes from the classical Erdős–Rényi connectivity threshold. Below $p \sim \log n/n$ , the graph disconnects w.h.p., leaving isolated users whose masks don't cancel. Privacy would break (and reliability too).

CCESA's density sits above this threshold by a factor of $\sqrt{n/\log n}$ . Whether this factor is necessary for the privacy margin (not just reliability) is a delicate analysis. The Choi et al. (2022) paper gives a tighter lower bound matching CCESA's rate; the gap is in the polylog factors.

Proof

Reliability lower bound

For the aggregate to be computable, $G$ must be connected. Classical ER connectivity threshold: $p \geq (1 + \epsilon)\log n/n$ . Hence reliable CCESA requires $p \geq \Omega(\log n/n)$ .

Privacy lower bound

For privacy to hold against $T$ -colluders w.h.p., every honest user must have an honest-neighbor w.h.p. This is a stricter requirement than bare connectivity. Analysis shows $p \geq c' \sqrt{\log n/n}$ is needed for the privacy margin at $T = o(n)$ . CCESA matches this with the same $\sqrt{\log n/n}$ scaling.

Aggregate overhead

At $p = c \sqrt{\log n/n}$ , $\binom{n}{2} p = \Theta(n^{3/2} \sqrt{\log n}) = \Theta(n\sqrt{n \log n})$ . CCESA matches this rate. Hence it is optimal within a polylog factor within the random-graph class. $\blacksquare$

Common Mistake: The Graph Seed Must Be Honestly Generated

Mistake:

Allow the server to unilaterally choose the CCESA graph seed.

Correction:

If the server controls the graph seed, it can adaptively choose a graph that isolates specific honest users (e.g., removes all their edges). This would break privacy even though the "graph is random" from the server's perspective.

Production CCESA uses a round-specific seed derived from an external randomness source: blockchain hashes, NIST beacon, or distributed coin-flipping. The seed must be unpredictable before user gradients are chosen; otherwise the adversary can adaptively shape the graph. The Choi et al. paper assumes honest seed generation as a protocol assumption.

⚠️Engineering Note

Honest Seed Generation in Production

CCESA's honest-seed assumption is handled in production via:

Blockchain randomness: seed derived from the hash of a recent block, publicly verifiable, hard to manipulate.
NIST Randomness Beacon: government-run public randomness source (limited by centralization concerns).
Distributed coin-flipping: multi-party protocol where users collectively generate the seed. Adds $O(n)$ overhead but fully decentralizes.

The choice depends on deployment trust model: blockchain for trustless environments, distributed flipping for FL deployments with no external beacon. Production implementations use blockchain by default.

Practical Constraints

•
Blockchain seed: unpredictable, verifiable
•
Distributed flipping: $O(n)$ overhead, fully decentralized
•
Server-chosen seed: insecure, must be avoided

📋 Ref: Choi et al. 2022 §III.D; NIST Randomness Beacon spec

Quick Check

For CCESA with $n = 10^4$ users at edge density $c = 2$ , the failure probability of the privacy guarantee is approximately:

$\sim 10^{-2}$ (1% failure rate)

$\sim 10^{-6}$ or smaller (negligible in practice)

Exactly 0 (deterministic guarantee)

$1/n$ (linear decay)

Correction:

\sim 10^{-6}

or smaller (negligible in practice)

Correct. The failure probability is $n^{-c'}$ for $c'$ depending on the constants. For $n = 10^4$ and reasonable margins, this is at most $10^{-6}$ — negligible in practice.

Analysis: Privacy, Reliability, and Scaling

Proving the Sparse Graph Works

Theorem: CCESA Privacy: High-Probability Bonawitz-Equivalent

Fix a coalition

Probability that $k$ has no honest neighbor

Union bound over all coalitions

Conclusion

Theorem: CCESA Reliability: Aggregation Succeeds W.H.P.

Erdős–Rényi connectivity

Reliability from connectivity

Failure probability

Theorem: CCESA: Privacy + Reliability + Sub-Quadratic Scaling

Privacy

Reliability

Communication

Combined

Key Takeaway

Example: CCESA Failure Probabilities at n=104n = 10^4n=104

Edge probability

Connectivity check

Privacy failure probability

Reliability failure probability

Interpretation

CCESA Failure Probability vs. Edge Density

Parameters

Is CCESA Optimal?

Theorem: Lower Bound for Random-Graph SecAgg

Reliability lower bound

Privacy lower bound

Aggregate overhead

Common Mistake: The Graph Seed Must Be Honestly Generated

Honest Seed Generation in Production

Quick Check

Example: CCESA Failure Probabilities at $n = 10^4$