Chapter 12: CCESA — Communication-Efficient Secure Aggregation

Learning Objectives

• Identify the $O(n^2)$ communication bottleneck of the Bonawitz complete-graph protocol (Chapter 10)
• Construct the CCESA protocol using a sparse Erdős–Rényi random graph of pairwise masks
• Prove the CCESA privacy + reliability guarantees using random-graph connectivity arguments
• Quantify the $O(n\sqrt{n/\log n})$ communication complexity and the matching lower bound for the sparse-graph class
• Recognize how CCESA goes outside the Caire et al. (2022) uncoded-groupwise-key class to achieve sub-quadratic cost
• Compare CCESA with alternative scalable secure-aggregation approaches (FastSecAgg, differential-privacy-based)