Exercises

Follows the protocol; passively analyzes messages to extract information. Example: Google's server in Gboard FL, running the protocol faithfully but inferring user typing patterns from aggregated gradients.

Actively deviates from the protocol — sends corrupted messages, refuses to participate, or colludes adaptively. Example: A compromised device in a cross-silo FL deployment uploading adversarial gradients to bias the trained model.

Different protocols needed. Bonawitz (Ch. 10) handles the first; ByzSecAgg (this chapter) adds protection against the second.

Byzantine user $k$ uploads $\tilde{\mathbf{g}}_k = \mathbf{g}_k^{\text{adv}} + \text{masks}$ with $\mathbf{g}_k^{\text{adv}}$ arbitrary. Masks cancel in the aggregate; the Byzantine contribution remains.

Server's aggregate = honest sum + $\sum_{k \in \mathcal{B}} \mathbf{g}_k^{\text{adv}}$. Byzantine users can arbitrarily shift the aggregate. No mechanism in Bonawitz detects or filters this.

ByzSecAgg adds coded distance computation + outlier filtering + vector commitments to handle Byzantine users.

Chapter 3 §3.4. Gives $g$-fold smaller shares than Shamir + Byzantine error-correction structure. Sets privacy threshold $T$ and Byzantine tolerance $B$.

Chapter 8 §8.3. Computes $\|\mathbf{g}_i - \mathbf{g}_j\|^2$ on ramp shares via Lagrange Coded Computing, enabling outlier detection without learning individual gradients.

Cryptographic primitive. Each user commits to its gradient before sharing, preventing Byzantine users from modifying shares after the protocol has begun.

Privacy (ramp) + detection (coded) + integrity (commitments) = ByzSecAgg.

$g = 2B + 1 = 2 \cdot 15 + 1 = 31$.

$B \leq (n - T - 1)/3 = (100 - 20 - 1)/3 = 79/3 \approx 26.3$. Since $B = 15 < 26.3$, the protocol is feasible.

Each user's upload is $d / g = d / 31$ of the full gradient size — a $31\times$ savings over Shamir sharing.

Each user commits to its gradient $\mathbf{g}_k$ before sharing. The commitment $\mathcal{C}_k$ is a hash/cryptographic digest that binds the user to a specific $\mathbf{g}_k$ without revealing it.

A Byzantine user could send two inconsistent shares: a "mild" share to the distance- computation phase (looks honest), then a "malicious" share to the reconstruction phase. The server would reconstruct a corrupted aggregate without the filter catching it.

Shares must be openings of $\mathcal{C}_k$. Any deviation between distance and reconstruction shares is detectable via commitment verification. Byzantine users cannot change their gradient between phases.

$d_{ij}$ is quadratic in the gradients ($d_f = 2$). LCC recovery threshold: $K_{\text{rec}} = d_f(n-1) + 1 = 2(n-1) + 1 = 2n - 1$ responses.

User $\ell$ holds ramp shares $s_{i, \ell}$ and $s_{j, \ell}$. Locally computes $\hat d^{(\ell)} = \|s_{i, \ell} - s_{j, \ell}\|^2$. This is one evaluation of a polynomial of degree $2$ in the inputs, interpolating to $d_{ij}$ at $x = 0$.

Server collects $\hat d^{(\ell)}$ from (at least) $2n - 1$ users. Lagrange interpolation on these values gives $d_{ij}$ at $x = 0$, which is the desired pairwise distance.

The server sees only the scalar $d_{ij}$ for each pair — no individual $\mathbf{g}_k$ is revealed. Distance matrix is enough for Krum filtering but gives no additional information.

$n = 6, B = 1, n - B - 1 = 4$. Each user's Krum score is the sum of 4 smallest distances to other users.

Users 1–5: 4 nearest are all honest → each distance $\sim 2$. Score: $\sim 4 \cdot 2 = 8$.

User 6: 4 nearest are users 1–5 (all honest). Distances $\sim 100$ each. Score: $\sim 4 \cdot 100 = 400$.

Sort scores: 5 honest at $\sim 8$, 1 user (user 6) at $\sim 400$. Largest $B = 1$: user 6. Correctly identified as Byzantine.

Surviving set $\mathcal{H} = \{1, ..., 5\}$. Server reconstructs $\mathbf{G}^* = \sum_{k \in \mathcal{H}} \mathbf{g}_k$.

Ramp width $g = 2B+1 = 41$. Per-user upload: $d/g = 2.4 \cdot 10^6$ scalars × 32 bits = $7.8 \cdot 10^7$ bits = 10 MB. Aggregate: $n \cdot 10 + Bd/8 \approx 2000 + 2.5 \cdot 10^7$ MB. Total $\sim 2.5$ GB per round.

Per-user: $d \cdot 32 = 3.2 \cdot 10^9$ bits = 400 MB. Aggregate: $n \cdot 400 = 80$ GB. No Byzantine defense.

Each gradient replicated $B + 1 = 21$ times for Byzantine voting, multiplying the 400 MB by 21 to 8.4 GB per user. Aggregate: 1.7 TB. Loses privacy because Krum requires plaintext.

ByzSecAgg is $\sim 680\times$ smaller than naive composition AND preserves privacy. Compared to Bonawitz alone: ByzSecAgg costs $\sim 30\times$ less aggregate traffic because ramp shares are $41\times$ smaller per user. At $n = 200$, ByzSecAgg is a clear winner.

The ramp scheme has $t_2 = T + 2B + 1$ (allows reconstruction with up to $B$ errors). The surviving honest-user count must exceed $t_2$: $n - B \geq t_2$, i.e., $n - B \geq T + 2B + 1$.

$n \geq T + 3B + 1$, or $B \leq (n - T - 1)/3$.

Each Byzantine user "costs" 3 units of the feasibility budget: one for their direct contribution, two for Reed-Solomon error correction. The factor of 3 is structural, not arbitrary.

Non-private Byzantine schemes (Krum without privacy) tolerate up to $B < n/2$ — much higher. The combination of privacy and Byzantine tolerance is strictly harder, reflected in the 3-factor.

Shamir $(t, n)$-sharing has per-share size = gradient size. Ramp $(t_1, t_2, n)$-sharing has per-share size = gradient size / $g$ where $g = t_2 - t_1$. For ByzSecAgg with $g = 2B+1$, this is a $\sim 2B$-fold savings.

The ramp gap $g = 2B + 1$ matches the Reed- Solomon minimum-distance requirement for correcting $B$ errors. The width serves both purposes: share-size savings AND error- correction structure.

Ramp still guarantees perfect secrecy against $T = t_1$ colluders. The relaxation vs. Shamir (which has $g = 1$) is that coalitions of size between $t_1$ and $t_2$ learn a partial aggregate — but this is already the desired output, so no extra privacy loss.

Ramp is a strictly better primitive for ByzSecAgg than Shamir. Chapter 3 §3.4 develops the ramp construction in detail.

Ramp $(T, T + 2B + 1, n-1)$-sharing (Chapter 3 §3.4) guarantees that any $T$ shares of a gradient are uniform (perfect secrecy). Hence any $T$ colluders see uniform shares — no information about individual gradients.

The server sees pairwise distances $d_{ij}$. These are symmetric functions — they reveal no information about which specific gradient is which. Formally: $d_{ij}$ depends on the two gradients only through their squared Euclidean distance, not on their individual values.

After Krum filtering, the honest set $\mathcal{H}$ contributes to the aggregate. Byzantine gradients are filtered out. The server learns $\mathbf{G}^* = \sum_{k \in \mathcal{H}} \mathbf{g}_k$ and (for each honest $k$) nothing beyond what's implied by $\mathbf{G}^*$.

Colluders learn: their own gradients (trivial), ramp shares of others (uniform over ramp structure), and pairwise distances (symmetric functions). By composition, their total information about non-colluding honest gradients is bounded by what's implied by $\mathbf{G}^*$ — the target privacy guarantee. $\blacksquare$

• Ramp share of gradient: $d / g = d / (2B+1)$ scalars.
• Vector commitment: $O(\log d)$ bits (Merkle tree root hash).
• Distance computation contribution per pair: 1 scalar ($\hat d^{(k)}$ for one pair). For all $\binom{n}{2}$ pairs, this is $O(n^2)$ scalars total across the protocol, or $O(n)$ per user.

$n$ users × $(d/(2B+1) + \log d + n)$ = $O(nd/(2B+1) + n \log d + n^2)$. For $B = O(n)$: $O(d + n \log d + n^2)$ = $O(n^2 + n \log d)$. For $B = o(n)$: $O(nd/B + n^2)$.

Dominant terms: $O(n \log n + Bd)$ for the regime where $B$ is proportional to $n$. Specifically, per-round bits $\sim n \log n + Bd$ — the theorem statement.

Information-theoretic lower bound: $\Omega(nd + Bd)$. ByzSecAgg's $O(n\log n + Bd)$ matches up to a $\log n$ factor.

Byzantine users coordinate to send gradients that are close to the honest cluster's centroid but shifted in a coordinated direction. Their pairwise distances to each other are small; distances to honest users are comparable to honest-honest distances. Krum scores are similar to honest users'.

Krum's decision rests on Byzantine users being outliers. If they cluster near honest gradients, they are not outliers — Krum picks one of them (or mixes their contribution into the aggregate) without filtering.

Bulyan (El Mhamdi et al. 2018) applies trimmed-mean post-processing. Even if Krum picks a Byzantine user, the trimmed-mean step removes extremes per-coordinate, limiting the Byzantine influence. Within ByzSecAgg, Bulyan can replace Krum as the filtering step without breaking the framework.

• Segmented filtering: FedSeg (Sun et al. 2021) partitions the gradient into segments and filters per-segment.
• Reputation tracking: Byzantine users flagged across rounds via reputation accumulation.
• DP noise: Add post-aggregate DP noise to bound any surviving Byzantine contribution.

None is a universal fix — adaptive Byzantine robustness remains an open problem.

Each user adds Gaussian noise $\mathcal{N}(0, \sigma^2)$ to its gradient before ramp-sharing. Noise flows through ByzSecAgg's pipeline and appears in the final aggregate.

• Information-theoretic (from ByzSecAgg): server learns only $\mathbf{G}^* + \text{noise}$, nothing about individual gradients.
• Differential (from DP noise): noisy aggregate satisfies $\epsilon$-DP with respect to any single honest user's contribution.
• Byzantine resilience: still $B$ Byzantine tolerance, though DP noise may degrade the Krum filter's effectiveness.

DP noise requires larger $\sigma$ for strong guarantees (small $\epsilon$). Larger noise slows SGD convergence. The tradeoff: stronger DP → slower convergence → more rounds → more total communication. Balance depends on privacy requirements.

Sound and useful in practice. Chapter 18 lists full characterization of the three-way tradeoff (IT privacy × DP privacy × Byzantine × convergence) as an open problem.

The $\log n$ comes from the Lagrange interpolation used to reconstruct pairwise distances from coded contributions. Each pairwise reconstruction involves Lagrange coefficients, each costing $O(\log n)$ bits of precision in the ramp-share coding.

1. Specialized interpolation: for the quadratic distance function specifically, a reconstruction that doesn't use general Lagrange may avoid the $\log n$ factor.
2. Batched reconstruction: amortizing across many pairs could reduce per-pair cost.
3. Different aggregator: replacing Krum with a filter that doesn't need pairwise distances (e.g., per-coordinate trimmed mean) may avoid the $\log n$.

Open. The $\log n$ factor is not believed to be essential but no known construction removes it. Interested researchers can explore in the direction of specialized LCC-for-quadratic-functions or aggregator-agnostic reductions. Part of the open problems in Chapter 18.