Prerequisites & Notation
Before You Begin
Chapter 11 carries the third CommIT-group contribution of Part III: the ByzSecAgg protocol that simultaneously handles privacy, dropouts, and Byzantine adversaries. The chapter composes machinery from multiple earlier chapters: Shamir/ramp sharing (Ch 3), polynomial codes (Ch 5), gradient coding (Ch 6), and Bonawitz secure aggregation (Ch 10). Readers comfortable with all four will find the construction modular and natural.
- Shamir + ramp secret sharing (Chapter 3)(Review ch03)
Self-check: State the share-size advantage of ramp sharing (-fold smaller) and the leakage tradeoff.
- Polynomial codes for matrix multiplication (Chapter 5)(Review ch05)
Self-check: Why does the polynomial code achieve recovery threshold ?
- Gradient coding (Chapter 6)(Review ch06)
Self-check: Recall how gradient coding tolerates stragglers at per-worker storage .
- Bonawitz secure aggregation (Chapter 10)(Review ch10)
Self-check: Restate the threat model and Bonawitz's cost.
- Cryptographic vector commitments (Merkle trees, Pedersen)
Self-check: Can you sketch a Merkle tree for committing to a vector and prove a single-element opening in ?
Notation for This Chapter
Byzantine-resilient secure aggregation extends Chapter 10's notation with the Byzantine threshold (number of malicious users), the ramp-sharing parameters , and a vector-commitment scheme. The ramp width controls the share-size savings.
| Symbol | Meaning | Introduced |
|---|---|---|
| Number of users | s01 | |
| Maximum number of Byzantine (malicious) users | s01 | |
| Privacy threshold (colluding honest-but-curious users) | s01 | |
| User 's gradient (honest) or arbitrary vector (Byzantine) | s01 | |
| Ramp width = (Chapter 3) | s02 | |
| Vector commitment to user 's gradient | s02 | |
| Opening / proof of | s02 | |
| Coded distance score between users and (used for outlier detection) | s03 | |
| Model dimensionality | s01 |