Prerequisites & Notation

Before You Begin

Chapter 12 carries the fourth and final CommIT-group contribution of Part III: CCESA (Communication- Efficient Secure Aggregation). The chapter builds directly on Chapter 10's Bonawitz protocol and Chapter 3's Shamir sharing, applying a clever sparse-graph construction to reduce the $O(n^2)$ communication overhead. Prerequisites are Chapter 10 (essential) and basic random-graph theory.

Bonawitz secure aggregation (Chapter 10)(Review ch10)
Self-check: State Bonawitz's per-round communication cost and the Caire et al. optimality (Ch. 10 §10.4).
Shamir secret sharing (Chapter 3 §3.2)(Review ch03)
Self-check: State the threshold guarantee of Shamir's scheme.
Basic random graph theory: Erdős–Rényi model
Self-check: For the $G(n, p)$ Erdős–Rényi model, what is the expected number of edges? When is $G(n, p)$ connected with high probability?
Federated learning (Chapter 9)(Review ch09)
Self-check: Why does FL benefit from sub-quadratic communication at large $n$ ?
Chernoff bounds / concentration of measure
Self-check: For a binomial random variable $X \sim \mathrm{Bin}(n, p)$ , what is the Chernoff tail bound?

Notation for This Chapter

CCESA-specific notation extends Chapter 10's Bonawitz conventions. We use $p$ for the Erdős–Rényi edge probability (avoid confusion with the polynomial-code partition count from Part II — context will disambiguate).

Symbol	Meaning	Introduced
$n$	Number of users	s01
$G = G(n, p)$	Erdős–Rényi random graph with $n$ nodes and edge probability $p$	s02
$p \in (0, 1)$	Edge probability in the Erdős–Rényi graph (CCESA parameter)	s02
$T$	Collusion threshold (Chapter 10 convention)	s02
$\mathcal{E}(G)$	Edge set of graph $G$	s02
$\deg(k)$	Degree of node $k$ in $G$ = number of masking partners	s02
$\mathbf{r}_{kj}$	Pairwise mask between users $k$ and $j$ (only if $\{k, j\} \in \mathcal{E}$ )	s02
$d$	Model dimensionality (Chapter 9 convention)	s01
$\delta$	Reliability failure probability	s03

← Ch 11 The

O(n^2)

Bottleneck of Bonawitz