Σ

Practical Secure Aggregation

ACM CCS 2017 Google Research

Bonawitz, Ivanov, Kreuter, Marcedone, McMahan, Patel, Ramage, Segal, Seth

Foundational Paper Masterclass ACM CCS 2017 • Dallas, TX 100% Line-by-Line Pedagogical Breakdown

Practical Secure Aggregation for Privacy-Preserving Machine Learning

Authors: Keith Bonawitz* • Vladimir Ivanov* • Ben Kreuter* • Antonio Marcedone†‡ • H. Brendan McMahan* • Sarvar Patel* • Daniel Ramage* • Aaron Segal* • Karn Seth*
*Google, Mountain View, CA 94043 • {bonawitz, vlivan, benkreuter, mcmahan, sarvar, dramage, asegal, karn}@google.com
‡Cornell Tech, 2 West Loop Rd., New York, NY 10044 • marcedone@cs.cornell.edu

🎯 The Core Challenge in Plain English

Suppose thousands of mobile devices want to collaboratively train a global deep neural network (e.g., Gboard predicting the next word you type). To update the model, a central server only needs the average (sum) of everyone's gradient updates: $$\Theta^{t+1} \leftarrow \Theta^t - \eta \frac{\sum_{u} \mathbf{x}_u}{\sum_u |D_u|}$$ However, an individual user's gradient $\mathbf{x}_u$ directly leaks sensitive text (e.g. typing a rare name triggers specific non-zero weights in word embeddings). If users send their raw gradients $\mathbf{x}_u$, the server can read what they typed. Secure Aggregation solves this: it allows the server to compute the exact vector sum $\sum \mathbf{x}_u$ without the server or any participant ever seeing any single user's raw vector $\mathbf{x}_u$.

📱 The 4 Hard Constraints

  • 1. Huge Vectors: Gradients have millions of numbers ($m \ge 10^6$). Overhead must stay under $2\times$ raw upload.
  • 2. Frequent Dropouts: Phones lose 4G/Wi-Fi or run out of battery mid-protocol (up to 30%+ dropouts).
  • 3. No P2P: Phones cannot communicate directly due to carrier firewalls; everything routes through the server.
  • 4. Active Malice: Server or clients may deliberately cheat, lie about dropouts, or forge messages.
Interactive Didactic Sandbox 1

Live SecAgg Protocol Step-by-Step Simulator

Toy 2D Vectors • Threshold (2, 3)

Experience the entire protocol dynamically! Change private user inputs, simulate Bob disconnecting, and inspect the exact algebraic cancellations that recover the true sum while keeping individual vectors 100% confidential.

Alice (User 1) Input Vector $\mathbf{x}_1$
Bob (User 2) Input Vector $\mathbf{x}_2$
Charlie (User 3) Input Vector $\mathbf{x}_3$
Paper Section 1 • Page 1

1. Introduction

Why privacy-preserving machine learning is an urgent societal need, and how Secure Multi-Party Computation (MPC) transforms the problem.

Exact Paper Text • §1 Paragraphs 1–2
"Machine learning models trained on sensitive real-world data promise improvements to everything from medical screening to disease outbreak discovery. And the widespread use of mobile devices means even richer—and more sensitive—data is becoming available... However, large-scale collection of sensitive data entails risks. A particularly high-profile example of the consequences of mishandling sensitive data occurred in 1988, when the video rental history of a nominee for the US Supreme Court was published without his consent. The law passed in response to that incident remains relevant today, limiting how online video streaming services can use their user data."

💡 In Plain English: The 1988 "Bork Video Scandal" and Why Centralized Data Collection is Toxic

In 1988, during the Supreme Court nomination of Robert Bork, a journalist walked into a Washington D.C. video rental store and obtained a list of 146 movie titles Judge Bork and his family had rented, publishing the titles in the press. While the titles were harmless (mostly Hitchcock films), Congress was horrified that a citizen's private habits could be casually revealed by a clerk. They passed the landmark Video Privacy Protection Act (VPPA) of 1988, which carries hefty statutory damages and governs modern streaming platforms (like Netflix and Hulu) today.

The Lesson for Machine Learning: Whenever a technology company centralizes user logs (such as keystroke logs from smart keyboards or medical searches), that data becomes a liability. A rogue employee, a subpoena, or a hacker can compromise millions of users' personal lives. The holy grail is to learn from user data without ever collecting it.

Exact Paper Text • §1 Paragraphs 3–5
"This work outlines an approach to advancing privacy-preserving machine learning by leveraging secure multiparty computation (MPC) to compute sums of model parameter updates from individual users’ devices in a secure manner. The problem of computing a multiparty sum where no party reveals its update in the clear—even to the aggregator—is referred to as Secure Aggregation... We are particularly focused on the setting of mobile devices, where communication is extremely expensive, and dropouts are common. Given these constraints, we would like our protocol to incur no more than twice as much communication as sending the data vector to be aggregated in the clear, and would also like the protocol to be fully robust to users dropping at any point."

📐 Formal Cryptographic Definition: The Ideal Secure Sum Functionality

Let $\mathcal{U} = \{1, \dots, n\}$ be a cohort of $n$ participating clients. Each client $u \in \mathcal{U}$ holds a private vector $\mathbf{x}_u \in \mathbb{Z}_R^m$, where $m$ is the parameter dimensionality (often millions of entries) and $R$ is an integer modulus chosen large enough to prevent arithmetic overflow.

$$f(\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_n) = \sum_{u \in \mathcal{U}} \mathbf{x}_u \pmod R$$

In an ideal execution with a trusted third party, users hand their $\mathbf{x}_u$ to the trusted party, who computes the modular vector sum and reveals only the final sum to the server (and nothing to the clients). Secure Aggregation implements this functionality cryptographically across an untrusted network.

Why Prior Cryptographic Approaches Failed in Mobile Environments

1. Generic MPC (Garbled Circuits / Shamir)

Requires clients to send secret shares of their entire $m$-dimensional vector to many other clients. Total communication per client scales as $O(n \cdot m)$! For $n=1,000$ and a 50MB model, each phone would have to upload 50 Gigabytes of data over cellular data!

2. Dining Cryptographers Networks (DC-Nets)

DC-nets provide unconditional sender anonymity, but are notoriously fragile: if even a single user drops out or fails to send their packet, the zero-sum masks cannot cancel, ruining the aggregation and forcing the entire protocol to restart from scratch.

3. Threshold Homomorphic Encryption (Paillier)

Computationally crippling for mobile CPUs (modular exponentiations of thousands of 2048-bit numbers), and requires an expensive, trusted dealer to set up and distribute threshold decryption keys beforehand.

4. Additive Masking (Ács & Castelluccia)

Pairs agree on masks and send an unmasking recovery message. However, if a user drops out during the recovery round, the protocol deadlocks or leaks the self-masks of surviving users, completely exposing their raw updates!

1.1 Our Results

§1.2 Organization

The authors construct a protocol that achieves all 4 real-world criteria simultaneously:

O(1)
Constant Rounds (4 or 5 rounds, independent of user count)
< 2×
Communication Expansion Factor for practical vector sizes
1 Server
Single Untrusted Server (no non-colluding server pairs needed)
Robust
Tolerates up to 33% to 50% arbitrary user dropouts at any step

The paper presents two variants: Variant 1 is optimized for honest-but-curious adversaries (4 rounds, plain model, no PKI required). Variant 2 provides provable privacy against active adversaries (5 rounds, random oracle model, utilizes PKI to prevent Sybil attacks).

Paper Section 2 • Page 2

2. Secure Aggregation for Federated Learning

Understanding the real-world machine learning engine behind SecAgg: Federated Averaging on mobile devices.

The Evolution of Mobile Machine Intelligence (Figure 1 Explained)

1. Cloud-Centric (Traditional) Worst Privacy

Raw user interactions (every keystroke, voice snippet, photo) are streamed directly to the tech company's cloud datacenters. Models are trained centrally on massive raw data lakes.

Vulnerability: Company possesses raw personal diaries, passwords, medical texts.
2. Standard Federated Learning Decentralized Data

Raw data never leaves the phone. The model is sent to the phone, which computes a local gradient $\mathbf{x}_u = \nabla L(D_u)$. The phone uploads raw gradients to the cloud aggregator.

Vulnerability: Gradients still leak private text via gradient inversion!
3. FL + Secure Aggregation Gold Standard

Phones use MPC pairwise blinding. The server only receives the cryptographically masked sum $\sum \mathbf{x}_u$. The cloud provider learns only the aggregate update.

Guarantee: Provably zero leakage of individual user data or gradients!

📱 Real-World Case Study: Gboard Mobile Keyboard Next-Word Prediction

When you type a message on your smartphone ("I love eating..."), the neural network predicts the next word ("pizza", "sushi", "tacos"). To improve this model, Google wants to train it on real human text messages. But text messages contain bank account passwords, medical symptoms, romantic confessions, and sensitive names.

Users will never agree to upload their text messages. In Federated Learning, the phone computes how the neural network's weights should adjust based on today's typing. But as we will see below, even an individual weight adjustment can reveal the exact words you typed!

⚠️ The Gradient Leakage Vulnerability: Why Gradients Aren't Private

Consider a standard recurrent neural network (RNN) or Transformer with an input embedding table $\mathbf{E} \in \mathbb{R}^{V \times d}$, where $V$ is the vocabulary size (e.g. 50,000 words) and $d$ is the embedding dimension. Each word $w$ is represented by a one-hot vector $\mathbf{e}_w \in \{0, 1\}^V$.

Input vector: $\mathbf{x} = \mathbf{e}_w = [0, 0, \dots, 1, \dots, 0]^T$ (1 at index $w$, 0 elsewhere)
Loss gradient with respect to embedding weights $\theta_v$:
$$\frac{\partial L}{\partial \theta_v} = \begin{cases} \mathbf{0} & \text{if word } v \text{ was NOT typed by the user} \\ \mathbf{g}_w \ne \mathbf{0} & \text{if word } v = w \text{ WAS typed by the user} \end{cases}$$

The Catastrophe: If an inspecting server receives the raw gradient $\mathbf{x}_u$ of client $u$, it can simply iterate through all 50,000 embedding entries. If row 3,842 has non-zero values, the server knows with 100% mathematical certainty that the user typed the word corresponding to index 3,842!

How Secure Aggregation Neutralizes This: When the server only receives the sum $\sum_{u \in \mathcal{U}} \mathbf{x}_u$, if row 3,842 is non-zero, the server only learns that at least one person among the 1,000 users in this cohort typed that word, completely preserving the plausible deniability of every individual user.

Paper Section 3 • Pages 2–4

3. Cryptographic Primitives

The foundational cryptographic tools required to build resilient, dropout-tolerant secure aggregation.

Exact Paper Text • §3.1 Secret Sharing
"We rely on Shamir’s $t$-out-of-$n$ Secret Sharing, which allows a user to split a secret $s$ into $n$ shares, such that any $t$ shares can be used to reconstruct $s$, but any set of at most $t - 1$ shares gives no information about $s$. The scheme is parameterized over a finite field $\mathbb{F}$ of size at least $l > 2^k$ (where $k$ is the security parameter of the scheme), e.g. $\mathbb{F} = \mathbb{Z}_p$ for some large public prime $p$."

💡 In Plain English: The Magic of Shamir's Polynomial Vault

Imagine you have a secret number $s$ (e.g., your master private key). You want to share it among 5 friends such that any 3 friends can unlock it, but any 2 friends learn absolutely nothing.

Remember high school algebra: Two points define a unique line (degree 1). Three points define a unique parabola (degree 2). To make a $t=3$ threshold scheme, you pick a random parabola: $$q(X) = s + a_1 X + a_2 X^2 \pmod p$$ Your secret $s$ is the vertical intercept $q(0)$. You give Friend 1 the point $(1, q(1))$, Friend 2 the point $(2, q(2))$, and so on. If 2 friends combine their points, infinitely many parabolas can still pass through those 2 points—every possible secret in the field is equally likely! But as soon as a 3rd friend arrives, there is exactly one parabola that passes through all 3 points, instantly revealing the secret $q(0) = s$.

📐 Mathematical Formulation: Lagrange Interpolation

Let $\mathcal{U}$ be a set of $n$ user IDs, and $t$ be the threshold ($1 \le t \le n$). The sharing algorithm $\text{SS.share}(s, t, \mathcal{U}) \to \{(u, s_u)\}_{u \in \mathcal{U}}$ evaluates a degree-$(t-1)$ polynomial with constant term $s$. Given any surviving subset $\mathcal{V} \subseteq \mathcal{U}$ with $|\mathcal{V}| \ge t$, the secret is reconstructed via Lagrange basis polynomials evaluated at $X = 0$:

$$s = \text{SS.recon}(\{(u, s_u)\}_{u \in \mathcal{V}}, t) = \sum_{u \in \mathcal{V}} s_u \cdot \ell_u(0) \pmod p$$ $$\text{where } \ell_u(0) = \prod_{v \in \mathcal{V} \setminus \{u\}} \frac{v}{v - u} \pmod p$$
Information-Theoretic Security Property: For any two secrets $s, s' \in \mathbb{F}$ and any unauthorized subset $|\mathcal{V}| < t$: $$\{\{(u, s_u)\}_{u \in \mathcal{U}} \leftarrow \text{SS.share}(s, t, \mathcal{U}) : \{(u, s_u)\}_{u \in \mathcal{V}}\} \equiv \{\{(u, s_u)\}_{u \in \mathcal{U}} \leftarrow \text{SS.share}(s', t, \mathcal{U}) : \{(u, s_u)\}_{u \in \mathcal{V}}\}$$ The distributions of shares are strictly identical ($\equiv$). Even an adversary with infinite computing power cannot extract a single bit of information about $s$.
Exact Paper Text • §3.2 Key Agreement
"Key Agreement consists of a tuple of algorithms $(\text{KA.param}, \text{KA.gen}, \text{KA.agree})$. KA.gen samples $x \leftarrow \mathbb{Z}_q$ as the secret key $s^{SK}_u$, and $g^x$ as the public key $s^{PK}_u$; and $\text{KA.agree}(x_u, g^{x_v}) \to s_{u,v}$ outputs $s_{u,v} = H((g^{x_v})^{x_u}) = H(g^{x_u x_v})$... In order to prove security against active adversaries, we need a somewhat stronger security guarantee... which we call Two Oracle Diffie-Hellman assumption (2ODH)."
Passive Security: Standard DDH Definition 3.1

Adversary gets two honest public keys $A = g^a$ and $B = g^b$. The Decisional Diffie-Hellman (DDH) assumption states that distinguishing the real shared secret $H(g^{ab})$ from a uniformly random 256-bit string $s \xleftarrow{\$} \{0, 1\}^k$ is computationally intractable for any polynomial-time attacker:

$$\text{Adv}_{\mathcal{G}, M}^{\text{DDH}}(k) = |\Pr[\text{DDH-Exp}^1 = 1] - \Pr[\text{DDH-Exp}^0 = 1]| \le \epsilon(k)$$

In practice, the hash function $H$ (e.g. SHA-256) serves as a randomness extractor, transforming the algebraic group element $g^{ab}$ into an unbiased bitstring.

Active Security: 2ODH Definition 3.2

Against an active attacker (who can craft arbitrary malicious public keys $X$ and see how honest parties react), standard DDH is not enough! The attacker has access to two decryption/agreement oracles:

$\mathcal{O}_a(X) = H(X^a) \quad \text{for any } X \ne B$
$\mathcal{O}_b(X) = H(X^b) \quad \text{for any } X \ne A$

Even with oracle access to test other keys, the adversary still cannot distinguish the target secret $H(g^{ab})$ from random. This models an adversarial server probing honest clients with modified Diffie-Hellman keys.

3.3 Authenticated Encryption (AEAD)

Combines encryption and authentication $(\text{AE.enc}, \text{AE.dec})$ under a symmetric key $c \in \{0, 1\}^k$.

Dual Guarantee:
  • IND-CPA (Confidentiality): Ciphertexts do not leak plaintext contents.
  • IND-CTXT (Integrity): The untrusted server cannot tamper with or forge encrypted secret shares without triggering the error symbol $\bot$.

Instantiated in their prototype via AES-GCM (128-bit).

3.4 Pseudorandom Generator (PRG)

Expands a compact 256-bit seed into an $m$-dimensional vector in $\mathbb{Z}_R^m$:

$$\text{PRG}: \{0, 1\}^k \to [0, R)^m$$

The Performance Keystone: Instead of transmitting $m$ numbers (megabytes) across the network, clients transmit a 32-byte seed. Each client uses AES in counter mode (AES-CTR) to locally expand the seed into millions of mask elements.

3.5 Digital Signatures

Standard UF-CMA secure scheme $(\text{SIG.gen}, \text{SIG.sign}, \text{SIG.ver})$ with secret signing key $d^{SK}_u$ and public verification key $d^{PK}_u$.

Used in the active adversary variant to sign public Diffie-Hellman keys in Round 0 and sign the survival cohort in Round 3 (ConsistencyCheck), ensuring the server cannot forge messages.

3.6 Public Key Infrastructure (PKI)

A public bulletin board where each client registers $(u, d^{PK}_u)$ during setup.

The Sybil Defense: Without a PKI, a malicious server could invent 10,000 virtual fake clients, isolate an honest user Alice, and pretend all other users are real, easily recovering Alice's secret shares! The PKI guarantees Alice that she is only sharing secrets with verified registered devices.
Paper Section 4 • Pages 4–5

4. Technical Intuition: The Mechanics of the Breakthrough

How the authors evolved naive one-time pads into the dropout-resilient Double-Masking paradigm.

Exact Paper Text • §4.0.1 Masking with One-Time Pads
"Assume a total order on users, and suppose each pair of users $(u, v), u < v$ agree on some random vector $s_{u,v}$. If $u$ adds this to $x_u$ and $v$ subtracts it from $x_v$, then the mask will be canceled when their vectors are added, but their actual inputs will not be revealed... In other words, each user $u$ computes: $$y_u = x_u + \sum_{v \in \mathcal{U}: u < v} s_{u,v} - \sum_{v \in \mathcal{U}: u > v} s_{v,u} \pmod R$$ and sends $y_u$ to the server, and the server computes $z = \sum_{u \in \mathcal{U}} y_u = \sum_{u \in \mathcal{U}} x_u \pmod R$."

💡 In Plain English: The Zero-Sum Cancellation Trick

Imagine Alice and Bob want to tell the teacher the sum of their exam scores without the teacher knowing either individual score. Alice scored 80, Bob scored 90. The true sum is 170.

Before handing in their papers, Alice and Bob whisper a secret number between themselves: say, 500. Alice agrees to add 500: she reports $80 + 500 = 580$. Bob agrees to subtract 500: he reports $90 - 500 = -410$. The teacher receives 580 and -410. To the teacher, both numbers look completely random and disconnected from reality. But when the teacher adds them up: $$580 + (-410) = 80 + 500 + 90 - 500 = 80 + 90 = 170$$ The $+500$ and $-500$ annihilate each other! The teacher learns the exact sum 170, with mathematical zero knowledge of 80 or 90!

The Two Fatal Flaws of Naive Zero-Sum Masking

Flaw 1: Quadratic Bandwidth ($O(n \cdot m)$)

If each user must generate and exchange a distinct random vector $s_{u,v}$ of size $m$ with every other user, each user must upload and download $(n-1) \times m$ floats. For 1,000 users and a 100MB model, this would require 100 Gigabytes of cellular data per phone!

Flaw 2: Zero Tolerance for Dropouts

If Bob drops his phone in a puddle before uploading his masked vector $y_{\text{Bob}}$, Alice has still added $s_{\text{Alice, Bob}}$ to her update. The sum at the server is contaminated with $+s_{\text{Alice, Bob}}$ that can never be canceled, permanently corrupting the aggregate sum!

Exact Paper Text • §4.0.2 Efficient Communication & Handling Dropped Users
"We notice that we can reduce the communication by having the parties agree on common seeds for a pseudorandom generator (PRG) rather than on the entire mask $s_{u,v}$... We resolve the dropout problem by using a threshold secret sharing scheme and having each user send shares of their Diffie-Hellman secret to all other users... This approach solves the problem of unbounded recovery rounds, but still has an issue: there is a possibility that a user’s data might accidentally be leaked to the server."

🚨 The "Ghost User / Delayed Packet" Attack: Why Single Masking Leaks Raw Data

Suppose we use Shamir secret sharing to share each user's Diffie-Hellman private key $s^{SK}_u$. If user Alice drops out, surviving users send their shares of $s^{SK}_{\text{Alice}}$ to the server. The server reconstructs $s^{SK}_{\text{Alice}}$, re-computes all of Alice's pairwise masks with surviving users, and subtracts them out.

The Attack Scenario Step-by-Step:
  1. Alice is on a slow 3G cellular network connection; her upload $y_{\text{Alice}}$ is delayed.
  2. The server hits a timeout, marks Alice as "DROPPED", and asks surviving users for their shares of Alice's private key $s^{SK}_{\text{Alice}}$.
  3. Surviving users send shares, and the server reconstructs $s^{SK}_{\text{Alice}}$.
  4. Using $s^{SK}_{\text{Alice}}$, the server calculates all pairwise masks: $s_{\text{Alice}, v} = H((g^{s_v})^{s^{SK}_{\text{Alice}}})$.
  5. The Breach: One second later, Alice's delayed packet $y_{\text{Alice}}$ arrives at the server!
$$\mathbf{x}_{\text{Alice}} = y_{\text{Alice}} - \sum_{v > \text{Alice}} \text{PRG}(s_{\text{Alice}, v}) + \sum_{v < \text{Alice}} \text{PRG}(s_{v, \text{Alice}}) \pmod R$$

The server strips off every single mask from $y_{\text{Alice}}$ and exposes Alice's private model gradient $\mathbf{x}_{\text{Alice}}$ in plain text! Furthermore, a curious or malicious server could deliberately lie about Alice having dropped out to trick other users into handing over Alice's key!

Exact Paper Text • §4.0.3 Double-Masking to Protect Security
"To resolve this new security problem, we introduce a double-masking structure that protects $x_u$ even when the server can reconstruct $u$’s masks. First, each user $u$ samples an additional random seed $b_u$... When generating $y_u$, users also add this secondary mask: $$y_u = x_u + \text{PRG}(b_u) + \sum_{v \in \mathcal{U}: u < v} \text{PRG}(s_{u,v}) - \sum_{v \in \mathcal{U}: u > v} \text{PRG}(s_{v,u}) \pmod R$$ During the recovery round, the server must make an explicit choice with respect to each user $u$: from each surviving member $v$, the server can request either a share of the common secret $s_{u,v}$ associated with $u$ or a share of the $b_u$ for $u$; an honest user $v$ will never reveal both kinds of shares for the same user."

🛡️ The Core Breakthrough: The Mutual Exclusivity Rule

By adding an independent personal self-mask $\text{PRG}(b_u)$, the vector is protected by two orthogonal layers of cryptography. Each user creates Shamir secret shares of BOTH their self-mask seed $b_u$ AND their pairwise private key $s^{SK}_u$.

Case 1: User Survives ($u \in \mathcal{U}_3$)

The server requests shares of $b_u$ (self-mask seed).

Server reconstructs $b_u$ and subtracts $\text{PRG}(b_u)$. The pairwise masks $s_{u,v}$ cancel out naturally when summed with other survivors!

Case 2: User Drops Out ($u \in \mathcal{U}_2 \setminus \mathcal{U}_3$)

The server requests shares of $s^{SK}_u$ (pairwise key).

Server reconstructs $s^{SK}_u$ and subtracts the uncompensated pairwise masks. But $b_u$ is never reconstructed!

The Ironclad Invariant: Honest clients verify that they never release both $b_u$ and $s^{SK}_u$ for any single user. Therefore, even if the server falsely claims Alice dropped out and gets $s^{SK}_{\text{Alice}}$, it can NEVER get $b_{\text{Alice}}$. Even if Alice's packet $y_{\text{Alice}}$ arrives later, it remains permanently blinded by $\text{PRG}(b_{\text{Alice}})$, which is an information-theoretically secure one-time pad!
Figure 3: Cost Summary for the Protocol
Metric Client / User Cost Server Cost
Computation $O(n^2 + mn)$ $O(mn^2)$
Communication $O(n + m)$ $O(n^2 + mn)$
Storage $O(n + m)$ $O(n^2 + m)$

Key Asymptotic Takeaway: Notice that for each individual mobile phone, the communication is $O(n + m)$. Since $m$ (model size $\sim 10^7$) is vastly larger than $n$ (cohort size $\sim 10^3$), the communication is completely dominated by the vector size $m$. The cryptographic overhead scales only with $n$, meaning the overhead per client approaches a negligible constant multiplier!

Paper Section 5 • Pages 6–7

5. The Practical Secure Aggregation Protocol

An exhaustive, round-by-round walk-through of Figure 4: Setup through Output Reconstruction.

Protocol Interaction Architecture (Figure 2 Visualized)

Message exchanges between Mobile Clients ($u \in \mathcal{U}$) and the Central Server ($S$)

Passive Protocol Active Defense (Red)
Round 0: AdvertiseKeys Threshold Gate: $|\mathcal{U}_1| \ge t$
Client Action → Upload:

Generate DH keys $(c^{PK}_u, c^{SK}_u)$ and $(s^{PK}_u, s^{SK}_u)$.

Sign keys: $\sigma_u \leftarrow \text{SIG.sign}(d^{SK}_u, c^{PK}_u \parallel s^{PK}_u)$ (Active)

Send: $(c^{PK}_u \parallel s^{PK}_u \parallel \sigma_u) \to \text{Server}$

Server Action → Broadcast:

Collects $\ge t$ messages from cohort $\mathcal{U}_1$.

Broadcasts directory to all users: $\{(v, c^{PK}_v, s^{PK}_v, \sigma_v)\}_{v \in \mathcal{U}_1}$

Round 1: ShareKeys Threshold Gate: $|\mathcal{U}_2| \ge t$
Client Action → Secret Sharing:

Verify signatures. Sample random self-mask seed $b_u \leftarrow \mathbb{F}$.

Create Shamir shares of $s^{SK}_u$ and $b_u$.

Encrypt shares: $e_{u,v} \leftarrow \text{AE.enc}(\text{KA.agree}(c^{SK}_u, c^{PK}_v), u \parallel v \parallel s^{SK}_{u,v} \parallel b_{u,v})$

Send all ciphertexts $\{e_{u,v}\} \to \text{Server}$

Server Action → Routing:

Collects ciphertexts from $\ge t$ users (set $\mathcal{U}_2 \subseteq \mathcal{U}_1$).

Routes incoming encrypted shares: sends $\{e_{v,u}\}_{v \in \mathcal{U}_2}$ to user $u$.

Round 2: MaskedInputCollection Threshold Gate: $|\mathcal{U}_3| \ge t$
Client Action → Dual Blinding:

Compute pairwise seeds $s_{u,v} \leftarrow \text{KA.agree}(s^{SK}_u, s^{PK}_v)$ and stretch to masks $p_{u,v} = \Delta_{u,v} \text{PRG}(s_{u,v})$.

Compute self-mask $p_u = \text{PRG}(b_u)$.

Blind: $y_u \leftarrow \mathbf{x}_u + p_u + \sum_{v \in \mathcal{U}_2} p_{u,v} \pmod R$

Send $y_u \to \text{Server}$

Server Action → Collection:

Collects $y_u$ from $\ge t$ users (surviving cohort $\mathcal{U}_3 \subseteq \mathcal{U}_2$).

Broadcasts survivor cohort list $\mathcal{U}_3$ to all survivors.

Round 3: ConsistencyCheck [Active Adversary Only] Threshold Gate: $|\mathcal{U}_4| \ge t$
Client Action → Sign Cohort:

Verify $|\mathcal{U}_3| \ge t$.

Sign list: $\sigma'_u \leftarrow \text{SIG.sign}(d^{SK}_u, \mathcal{U}_3)$

Send signature $\sigma'_u \to \text{Server}$

Server Action → Broadcast Bundle:

Collects signatures from $\ge t$ users (set $\mathcal{U}_4 \subseteq \mathcal{U}_3$).

Broadcasts signature bundle $\{v, \sigma'_v\}_{v \in \mathcal{U}_4}$ to all users in $\mathcal{U}_4$.

Round 4: Unmasking & Output Threshold Gate: $|\mathcal{U}_5| \ge t$
Client Action → Mutual Exclusivity Release:

Verify signatures and decrypt stored shares.

• For survivors ($v \in \mathcal{U}_3$): send share $b_{v,u}$

• For dropped users ($v \in \mathcal{U}_2 \setminus \mathcal{U}_3$): send share $s^{SK}_{v,u}$

Send shares $\to \text{Server}$

Server Action → Unmasking & Output:

Collects from $|\mathcal{U}_5| \ge t$ users.

Reconstructs $s^{SK}_u$ for dropped users $\to$ recomputes $p_{v,u}$.

Reconstructs $b_u$ for survivors $\to$ recomputes $p_u = \text{PRG}(b_u)$.

$z = \sum y_u - \sum p_u + \sum p_{v,u} = \sum_{u \in \mathcal{U}_3} \mathbf{x}_u \pmod R$

Phase 0: Setup & Parameter Initialization

All parties agree on security parameter $k$, cohort size $n$, threshold $t$ (e.g. $t = \lfloor 2n/3 \rfloor + 1$), dimension $m$, modulus $R$, and secret sharing finite field $\mathbb{F} = \mathbb{Z}_p$. Public Diffie-Hellman parameters $pp \leftarrow \text{KA.param}(k)$ are sampled. In the active security model, every user $u$ receives a private signing key $d^{SK}_u$ and a public bulletin board with verification keys $d^{PK}_v$ for all other users.

Round 0: AdvertiseKeys (Key Generation & Advertising)

User → Server → User

Each user $u$ generates two separate Diffie-Hellman key pairs:

1. Pairwise Agreement Keypair:
$(s^{PK}_u, s^{SK}_u) \leftarrow \text{KA.gen}(pp)$
Used to create the zero-sum pairwise masks $s_{u,v}$.
2. Share Encryption Keypair:
$(c^{PK}_u, c^{SK}_u) \leftarrow \text{KA.gen}(pp)$
Used to encrypt messages sent between clients.

In the active variant, the client signs both public keys: $\sigma_u \leftarrow \text{SIG.sign}(d^{SK}_u, c^{PK}_u \parallel s^{PK}_u)$ and sends $(c^{PK}_u \parallel s^{PK}_u \parallel \sigma_u)$ to the server. The server waits for at least $t$ messages (this set is $\mathcal{U}_1$). If fewer than $t$ arrive before timeout, the server aborts. The server then broadcasts the list of all received public keys to everyone in $\mathcal{U}_1$.

Round 1: ShareKeys (Secret Sharing & Pairwise Encryption)

Client Double-Mask Secret Sharing

Upon receiving the directory $\mathcal{U}_1$, client $u$ validates that $|\mathcal{U}_1| \ge t$, verifies all signatures $\text{SIG.ver}(d^{PK}_v, c^{PK}_v \parallel s^{PK}_v, \sigma_v) = 1$, and samples a private random seed $b_u \xleftarrow{\$} \mathbb{F}$. Now client $u$ performs two Shamir secret shares:

Share pairwise private key: $\{(v, s^{SK}_{u,v})\}_{v \in \mathcal{U}_1} \leftarrow \text{SS.share}(s^{SK}_u, t, \mathcal{U}_1)$
Share personal self-mask seed: $\{(v, b_{u,v})\}_{v \in \mathcal{U}_1} \leftarrow \text{SS.share}(b_u, t, \mathcal{U}_1)$

For every other user $v \in \mathcal{U}_1 \setminus \{u\}$, client $u$ computes the shared encryption key via Diffie-Hellman agreement on their $c$-keys: $\text{KA.agree}(c^{SK}_u, c^{PK}_v)$, and encrypts the two shares: $$e_{u,v} \leftarrow \text{AE.enc}(\text{KA.agree}(c^{SK}_u, c^{PK}_v), u \parallel v \parallel s^{SK}_{u,v} \parallel b_{u,v})$$ Client $u$ sends all ciphertexts $\{e_{u,v}\}$ to the server. The server collects ciphertexts from at least $t$ users (set $\mathcal{U}_2 \subseteq \mathcal{U}_1$). The server acts as a post office: for each client $u \in \mathcal{U}_2$, it delivers all ciphertexts addressed to $u$: $\{e_{v,u}\}_{v \in \mathcal{U}_2}$.

Round 2: MaskedInputCollection (Mask Application & Upload)

The Blinding Operation

User $u$ receives the incoming ciphertexts from surviving users $\mathcal{U}_2$ (asserting $|\mathcal{U}_2| \ge t$). For each surviving peer $v \in \mathcal{U}_2 \setminus \{u\}$, $u$ computes the shared secret $s_{u,v} \leftarrow \text{KA.agree}(s^{SK}_u, s^{PK}_v)$ and stretches it into a pseudorandom vector mask: $$p_{u,v} = \Delta_{u,v} \cdot \text{PRG}(s_{u,v}) \quad \text{where } \Delta_{u,v} = \begin{cases} +1 & \text{if } u > v \\ -1 & \text{if } u < v \end{cases}$$ Crucially, note that $p_{u,v} + p_{v,u} = \mathbf{0}$. User $u$ also computes their own self-mask: $p_u = \text{PRG}(b_u)$. Then user $u$ masks their private training update $\mathbf{x}_u$:

$$y_u \leftarrow \mathbf{x}_u + p_u + \sum_{v \in \mathcal{U}_2} p_{u,v} \pmod R$$

User $u$ uploads $y_u$ to the server. The server waits for at least $t$ users to submit (set $\mathcal{U}_3 \subseteq \mathcal{U}_2$). The server sends the survivor list $\mathcal{U}_3$ back to all users in $\mathcal{U}_3$.

Round 3: ConsistencyCheck [Active Adversary Model Only]

Anti-Partitioning Defense

In the honest-but-curious model, this round is completely omitted (and we set $\mathcal{U}_4 := \mathcal{U}_3$). In the active adversary model, a malicious server could attempt an equivocation / partitioning attack: tell Alice that Bob dropped out, while telling Charlie that Bob survived! This could trick different users into releasing conflicting shares in Round 4.

The Fix: User $u$ receives list $\mathcal{U}_3$, checks $|\mathcal{U}_3| \ge t$, and signs it: $\sigma'_u \leftarrow \text{SIG.sign}(d^{SK}_u, \mathcal{U}_3)$. The server must collect at least $t$ valid signatures on $\mathcal{U}_3$ (set $\mathcal{U}_4 \subseteq \mathcal{U}_3$) and broadcast the signature set $\{v, \sigma'_v\}_{v \in \mathcal{U}_4}$ back to everyone. This locks the server into a single, verifiable, globally agreed-upon cohort!

Round 4: Unmasking & Server Output Generation

Algebraic Unmasking

Users verify $\mathcal{U}_4 \subseteq \mathcal{U}_3$, $|\mathcal{U}_4| \ge t$, and all signatures. For each peer $v \in \mathcal{U}_2 \setminus \{u\}$, user $u$ decrypts ciphertext $e_{v,u}$ to obtain the stored shares. User $u$ then sends to the server:

• For DROPPED users ($v \in \mathcal{U}_2 \setminus \mathcal{U}_3$):
Send share of pairwise key: $s^{SK}_{v,u}$.
• For SURVIVING users ($v \in \mathcal{U}_3$):
Send share of self-mask seed: $b_{v,u}$.

The server collects responses from at least $t$ users (set $\mathcal{U}_5 \subseteq \mathcal{U}_4$). The server now performs:

  1. For dropped $u \in \mathcal{U}_2 \setminus \mathcal{U}_3$: Reconstruct $s^{SK}_u \leftarrow \text{SS.recon}(\{s^{SK}_{u,v}\}_{v \in \mathcal{U}_5}, t)$. Using $s^{SK}_u$ and $s^{PK}_v$, recompute $p_{v,u}$ for all surviving $v \in \mathcal{U}_3$.
  2. For surviving $u \in \mathcal{U}_3$: Reconstruct $b_u \leftarrow \text{SS.recon}(\{b_{u,v}\}_{v \in \mathcal{U}_5}, t)$. Recompute self-mask $p_u = \text{PRG}(b_u)$.
  3. Compute the unmasked sum:
$$z = \sum_{u \in \mathcal{U}_3} y_u - \sum_{u \in \mathcal{U}_3} p_u + \sum_{u \in \mathcal{U}_3, v \in \mathcal{U}_2 \setminus \mathcal{U}_3} p_{v,u} = \sum_{u \in \mathcal{U}_3} \mathbf{x}_u \pmod R$$
"""
Paper Section 6 • Pages 6–10

6. Security Analysis & The Simulation Proofs

How the authors mathematically prove privacy using the ideal-vs-real simulation paradigm and hybrid arguments.

Lemma 6.1: The Pairwise Randomness Lemma • Page 6
"Fix $n, m, R, \mathcal{U}$ with $|\mathcal{U}|=n$, and $\{\mathbf{x}_u\}_{u \in \mathcal{U}}$ where $\forall u \in \mathcal{U}, \mathbf{x}_u \in \mathbb{Z}_R^m$. Then: $$\left\{\{p_{u,v} \xleftarrow{\$} \mathbb{Z}_R^m\}_{u < v}, p_{u,v} := -p_{v,u} \forall u > v : \left\{\mathbf{x}_u + \sum_{v \in \mathcal{U}\setminus\{u\}} p_{u,v} \pmod R\right\}_{u \in \mathcal{U}}\right\} \equiv \left\{\{w_u \xleftarrow{\$} \mathbb{Z}_R^m \text{ s.t. } \sum_{u \in \mathcal{U}} w_u = \sum_{u \in \mathcal{U}} \mathbf{x}_u \pmod R\} : \{w_u\}_{u \in \mathcal{U}}\right\}$$ where '$\equiv$' denotes that the two distributions are identical."

💡 In Plain English: Why Lemma 6.1 is the Mathematical Heart of SecAgg

Lemma 6.1 proves that adding zero-sum pairwise random masks transforms the set of private vectors $\{\mathbf{x}_u\}$ into a set of completely uniform random numbers, with one and only one constraint: their sum equals the true sum $\sum \mathbf{x}_u$.

In other words: The server learns the sum, and mathematically zero other information. Not even subtle statistical correlations, variances, or individual bounds can be extracted.

🏛️ The Simulation Paradigm in Multi-Party Computation (MPC)

How do cryptographers prove that an algorithm reveals "nothing"? They use the Ideal vs. Real Simulation Paradigm: Imagine an adversary $\mathcal{C}$ corrupts the server and some subset of clients. In the "Real" world ($\text{REAL}$), they run the actual protocol with everyone's real secrets. In the "Ideal/Simulated" world ($\text{SIM}$), a simulator is given only the legitimate final output $z = \sum \mathbf{x}_u$ (and corrupt parties' own inputs). The simulator must fabricate all network messages, ciphertexts, and shares on the fly. If the adversary cannot distinguish the Real execution from the Simulated execution ($\text{REAL} \approx_c \text{SIM}$), then the real protocol leaked zero information beyond the allowed sum $z$!

Theorem 6.2: Security Against Clients Only Perfect Simulation $\equiv$

When the server is honest, the joint view of any subset of curious clients $\mathcal{C} \subseteq \mathcal{U}$ leaks zero information about honest clients' inputs: $$\text{REAL}_{\mathcal{C}}^{\mathcal{U}, t, k}(\mathbf{x}_{\mathcal{U}}, \mathcal{U}_1, \dots, \mathcal{U}_5) \equiv \text{SIM}_{\mathcal{C}}^{\mathcal{U}, t, k}(\mathbf{x}_{\mathcal{C}}, \mathcal{U}_1, \dots, \mathcal{U}_5)$$

Proof Intuition: Honest clients only upload their masked vectors $y_u$ to the server. Clients never receive or inspect each other's $y_u$ vectors! Clients only receive lists of user IDs and encrypted shares of other users' keys. The simulator simply runs honest clients with dummy inputs of all zeros ($\mathbf{0}$), and the resulting view seen by the corrupted clients is strictly identical to the real execution!

Theorem 6.3: Honest-but-Curious Server + Corrupt Clients Collusion Computational $\approx_c$

If the server colludes with a set of clients $\mathcal{C}$ with $|\mathcal{C} \setminus \{S\}| < t$, they learn nothing beyond their own inputs and the aggregate sum $z = \sum_{u \in \mathcal{U}_3 \setminus \mathcal{C}} \mathbf{x}_u$: $$\text{REAL}_{\mathcal{C}}^{\mathcal{U}, t, k}(\mathbf{x}_{\mathcal{U}}, \dots) \approx_c \text{SIM}_{\mathcal{C}}^{\mathcal{U}, t, k}(\mathbf{x}_{\mathcal{C}}, z, \dots)$$

Interactive Didactic Sandbox 2

Theorem 6.3 Proof: The 10 Hybrid Arguments Step-by-Step

Click hybrids 0 to 9 to inspect each transformation

⚔️ 6.2 Active Security & The Equivocation Trapdoor in the Random Oracle Model

When the server is actively malicious, it can deviate arbitrarily: drop messages, forge responses, and adaptively choose which clients to disconnect. This introduces a profound simulation hurdle:

The Adaptive Commitment Problem:

Clients compute and upload their masked inputs $y_u$ in Round 2. At this moment, honest clients are "committed" to their data. However, an active server can wait until Round 4 to adaptively choose which clients it aborts! Because the simulator does not know honest inputs in advance, how can it generate believable $y_u$ in Round 2 that later sum up perfectly to whatever arbitrary subset the server decides to unmask in Round 4?

The Random Oracle Trapdoor Solution:

In the Random Oracle model, the simulator controls the hash function $\mathcal{O}$. In Round 2, the simulator sends completely uniform random numbers for $y_u$. In Round 4, once the server commits to the surviving subset $\mathcal{Q}$, the simulator queries the ideal functionality for $z = \sum_{u \in \mathcal{Q}} \mathbf{x}_u$, and then reprograms the Random Oracle on seed $b_u$ so that $\text{PRG}(b_u) \leftarrow y_u - \mathbf{x}_u - \sum p_{u,v}$! This retroactively makes the dummy inputs completely consistent with the true sum!

Figure 5: Parameterization for Different Threat Models
Threat Model Minimum Threshold $t$ Min Inputs in Sum Max Dropouts Tolerated
Client-Only Adversary $t \ge 1$ $t$ $n - t$
Server-Only Adversary ($n_C = 0$) $t \ge \lfloor n/2 \rfloor + 1$ $t > n/2$ $\lceil n/2 \rceil - 1$
Client-Server Collusion ($n_C > 0$) $t \ge \lfloor 2n/3 \rfloor + 1$ $t - n_C \ge n/3$ $\lceil n/3 \rceil - 1$

Why $t \ge \lfloor 2n/3 \rfloor + 1$ is Necessary: If the server colludes with $n_C$ corrupt clients, the server needs $t$ total signatures to complete ConsistencyCheck. Honest clients provide at least $t - n_C$ signatures. If the server tries to create two disjoint valid subsets $\mathcal{Q}_1, \mathcal{Q}_2$, it would require $2(t - n_C)$ honest signatures. But there are only $n - n_C$ honest clients total! Setting $2t > n + n_C$ forces $2(t - n_C) > n - n_C$, making it mathematically impossible for the malicious server to partition the network into two conflicting cohorts!

"""
Paper Section 7 • Pages 11–14

7. Evaluation & Performance Analysis

Theoretical complexity derivations, the Lagrange precomputation trick, and real-world Java benchmarks on WAN networks.

Exact Paper Text • §7.1 Performance Analysis of Client
"Each user’s computation is $O(n^2 + mn)$... Overall communication cost is $2na_K + (5n - 4)a_S + m\lceil \log_2 R \rceil$, where $a_K$ and $a_S$ are the number of bits in a key exchange public key and secret share, respectively... For $R_U = 2^{16}$, $m = 2^{20}$ elements, and $n = 2^{10}$ users, the expansion factor is $1.73\times$; for $m = 2^{24}$ elements and $n = 2^{14}$ users, the expansion factor is $1.98\times$."

📐 Derivation of the Client Communication Expansion Formula

Let each user hold $m$ numbers, each in range $[0, R_U - 1]$. The raw vector requires $m \lceil \log_2 R_U \rceil$ bits. To guarantee that summing $n$ vectors never causes modular overflow in $\mathbb{Z}_R$, we require: $$R = n(R_U - 1) + 1 \implies \lceil \log_2 R \rceil \approx \lceil \log_2 R_U \rceil + \lceil \log_2 n \rceil$$ Each client sends:

  • 2 public keys (Round 0) $\to 2 a_K$ bits
  • Receives $2(n-1)$ public keys $\to 2(n-1) a_K$ bits
  • Sends $2(n-1)$ and receives $2(n-1)$ encrypted shares (Round 1) $\to 4(n-1) a_S$ bits
  • Sends masked vector $y_u$ (Round 2) $\to m \lceil \log_2 R \rceil$ bits
  • Sends $n$ shares in Round 4 $\to n a_S$ bits
$$\text{Total Client Bits} = 2n a_K + (5n - 4)a_S + m\lceil \log_2 R \rceil$$ $$\text{Expansion Factor} = \frac{256(7n - 4) + m\lceil \log_2 R \rceil}{m\lceil \log_2 R_U \rceil} \quad (\text{with } a_K = a_S = 256 \text{ bits})$$

Why Expansion Amortizes: The cryptographic term $256(7n - 4)$ depends only on $n$, completely independent of the model size $m$! As neural networks grow to millions of parameters ($m \ge 10^6$), the overhead of sharing keys shrinks to less than 2% of total bandwidth, leaving only the slight expansion of $\lceil \log_2 R \rceil$ over $\lceil \log_2 R_U \rceil$!

Interactive Didactic Sandbox 3

Bandwidth & Expansion Factor Calculator

Negligible Overhead
Number of Clients ($n$): 1,024
Model Dimension ($m$): 1,000,000
Precision ($R_U$ bits): 16-bit Ints
Raw Upload / Client 2.00 MB
SecAgg Upload / Client 3.46 MB
Expansion Factor 1.73x
Server Total Inbound 3.55 GB
Exact Paper Text • §7.2 Server Optimization: O(n³) to O(n²)
"We note that reconstructing $n$ secrets in the Shamir scheme takes $O(n^3)$ time in the general case... However, in our setting, we can perform all of the reconstructions in $O(n^2)$ time by observing that all of our secrets will be reconstructed from identically-indexed sets of secret shares – that is, $\mathcal{U}'$ is fixed across all secrets, because in round Unmasking, each user that is still alive sends a share of every secret that needs to be reconstructed. Therefore, we can precompute the Lagrange basis polynomials $\ell_u$ in $O(n^2)$ time and $O(n)$ space, then reconstruct each of $n$ secrets in $O(n)$ time as $L(0) = \sum_{u \in \mathcal{U}'} s_u \ell_u \pmod p$."

💡 In Plain English: How Google Solved the $O(n^3)$ Server Bottleneck

Reconstructing a single Shamir secret from $n$ shares requires calculating $n$ Lagrange fractions, which takes $O(n^2)$ arithmetic operations. If the server has to reconstruct $n$ different secrets (one for every user), naive execution would take: $$n \times O(n^2) = O(n^3) \text{ operations!}$$ For $n = 10,000$ users, $n^3 = 1,000,000,000,000$ (one trillion operations), which would freeze the server for hours!

The Brilliant Insight: The $x$-coordinates (user IDs) are identical for every single secret being reconstructed! The surviving cohort is always the exact same set $\mathcal{U}'$. The server calculates the basis coefficients once: $$\ell_u = \prod_{v \in \mathcal{U}' \setminus \{u\}} \frac{v}{v - u} \pmod p$$ This precomputation takes $O(n^2)$ time. Once stored, each of the $n$ secrets can be unlocked with a simple dot-product $\sum s_u \ell_u$ in only $O(n)$ time! Total time for all $n$ secrets: $O(n^2) + n \cdot O(n) = O(n^2)$! An astronomical $10,000\times$ speedup!

Prototype Benchmarks & Key Empirical Takeaways (Figures 6–9)

1. PRG Expansion Dominates Everything

Over 90% of all client and server CPU runtime is spent running AES in counter mode to generate pseudorandom masks. Key agreements, secret sharing, and signature verifications take negligible time (< 5% combined).

2. Server Cost Scales with Dropouts

Each dropped user forces the server to unmask pairwise noise across all $(n-d)$ surviving users. In Figure 8, server unmasking time jumps from 1.2s (0% dropouts) to 61s (10% dropouts) to 142s (30% dropouts) for $n=500$.

3. WAN Deployment Realities (Figure 9)

Tested across geographically dispersed datacenters with real latency: total end-to-end execution took 13.1s for $n=500$ and 23.4s for $n=1,000$ (with 100K 62-bit parameters).

4. Client Bandwidth Is Tiny

Total communication per client was only 0.95 MB for $n=500$ and 1.15 MB for $n=1,000$, well within typical cellular data allowances.

Paper Sections 8, 9, 10 • Pages 14–15

8. Discussion, Related Work & Conclusion

Open challenges (poisoning attacks), comparison with alternative MPC schemes, and concluding remarks.

§8 Open Challenges in Real-World Deployments

1. Denial of Service / Malicious Blame

An active attacker can intentionally send malformed ciphertexts or incorrect shares in Round 4 to force the protocol to abort. Assigning cryptographically provable blame without revealing identities is an unsolved open problem.

2. Model Poisoning & Range Checks

SecAgg guarantees that the server only sees $\sum \mathbf{x}_u$, but does not check if $\mathbf{x}_u$ is valid! A malicious client can submit $\mathbf{x}_u = [10^9, 10^9, \dots]$, destroying the global model. Zero-Knowledge Range Proofs exist, but are currently too heavy for mobile phones.

3. Sparse Graphs (Expander Networks)

Instead of a complete graph where each user masks with all $n-1$ other users, clients could mask with a small random subset ($O(\log n)$ neighbors). However, an adversarial server could exploit graph topology to isolate users.

§9 Comparison with Prior State-of-the-Art MPC Schemes

Scheme / Paradigm Server Trust Model Dropout Robustness Client Comm. Overhead Main Limitation for Mobile FL
SecAgg (This Paper) 1 Untrusted Server High (tolerates up to 33–50%) < 2× raw data size Server unmasking cost scales with dropouts
Prio (Gibbs & Boneh, 2017) Requires 2+ Non-Colluding Servers High (non-interactive) Moderate Requires non-collusion between multiple tech companies
Generic Secret Sharing (Boyle et al.) 1 Server High Prohibitive: $O(n \cdot m)$ Clients must upload full vector shares to peers (Gigabytes!)
Dining Cryptographers (DC-Nets) 1 Server Zero (1 dropout halts entire run) Low Completely unusable in unreliable mobile cellular networks
Additive Masking (Ács & Castelluccia) 1 Server Brittle (fails if recovery drops) Low Leaks self-masks and raw inputs if recovery users disconnect
Threshold Paillier / Homomorphic 1 Server High Moderate Requires trusted dealer for threshold key setup; heavy CPU
§10 Conclusion & Real-World Legacy

Bonawitz et al. created the first practical, dropout-resilient secure aggregation protocol capable of scaling to millions of consumer mobile devices. Today, SecAgg is the cryptographic cornerstone of production Federated Learning across Google Android, Apple iOS, and enterprise privacy systems worldwide.

"""
Paper Appendix A • Pages 17–20

Appendix A: Privacy Against Active Adversaries

Complete mathematical treatment of Theorem A.1, Theorem A.2, the 2ODH reduction, and the 12-Hybrid Equivocation proof.

Theorem A.2: Privacy Against Active Server + Corrupt Clients
"There exists a PPT simulator $\text{SIM}$ such that for all $k, t, \mathcal{U}, \mathcal{C} \subseteq \mathcal{U} \cup \{S\}$ and $\mathbf{x}_{\mathcal{U}\setminus\mathcal{C}}$, letting $n = |\mathcal{U}|$ and $n_C = |\mathcal{C} \cap \mathcal{U}|$, if $2t > n + n_C$, then: $$\text{REAL}_{\mathcal{C}}^{\mathcal{U}, t, k}(M_{\mathcal{C}}, \mathbf{x}_{\mathcal{U}\setminus\mathcal{C}}) \approx_c \text{SIM}_{\mathcal{C}}^{\mathcal{U}, t, k, \text{Ideal}^{\delta}_{\{\mathbf{x}_u\}}}(M_{\mathcal{C}})$$ where $\delta = t - n_C$."

The 12-Hybrid Induction Walkthrough (Hyb 0 through Hyb 11)

Hyb 0 & Hyb 1: Real execution $\to$ Simulator runs protocol with true inputs, emulating Random Oracle $\mathcal{O}$ via dynamic hash table $x \mapsto \mathcal{O}(x)$. Identically distributed.
Hyb 2: Abort if adversary forges a valid signature on honest keys $(c^{PK}_v \parallel s^{PK}_v)$. Indistinguishable by UF-CMA security of the digital signature scheme.
Hyb 3: Replace pairwise shared encryption keys $c_{u,v} = \text{KA.agree}(c^{SK}_u, c^{PK}_v)$ between honest users with uniformly random keys. Indistinguishable under the Two-Oracle Diffie-Hellman (2ODH) assumption.
Hyb 4 & Hyb 5: Abort if adversary alters ciphertext $e_{u,v}$ (INT-CTXT ciphertext integrity). Substitute encrypted shares between honest clients with encryptions of 0 (IND-CPA confidentiality).
Hyb 6: Uniqueness of Consensus Set $\mathcal{Q}$

Simulator aborts if adversary forges a signature on a ConsistencyCheck set. Defines $\mathcal{Q}$ as the unique set of users with $\ge t$ valid signatures. The Proof of Uniqueness: If two conflicting sets $\mathcal{Q}_1 \ne \mathcal{Q}_2$ existed, each must have at least $t - n_C$ honest signatures. Thus, total honest signers would be $2(t - n_C) \le n - n_C \implies 2t \le n + n_C$, directly contradicting the protocol condition $2t > n + n_C$!

Hyb 7 & Hyb 8: Abort if adversary queries Random Oracle on $b_u$ ($u \notin \mathcal{Q}$) or $s_{u,v}$ ($u, v \in \mathcal{Q}$). Since adversary has $< t$ shares, these values are information-theoretically hidden (probability of guessing from $\mathbb{F}$ is negligible $\approx 2^{-256}$).
Hyb 9, Hyb 10 & Hyb 11: The Equivocation Trapdoor

In Round 2, simulator sends purely random dummy vectors for $y_u$. In Round 4, once the server locks in $\mathcal{Q}$, the simulator queries $\text{Ideal}^\delta(\mathcal{Q} \setminus \mathcal{C})$ for sum $z$, samples $\{w_u\}$ constrained to $\sum w_u = z$ (Lemma 6.1), and backpatches the Random Oracle: $$\mathcal{O}(b_u) \leftarrow y_u - w_u - \sum_{v \in \mathcal{F}_u \setminus \mathcal{Q}} \text{PRG}(s_{u,v})$$ The simulator successfully produces a flawless simulation with ZERO knowledge of individual inputs $\mathbf{x}_u$, completing the active adversary proof!

Paper Appendix B • Pages 20–21

Appendix B: Differential Privacy & Secure Aggregation

Why SecAgg reduces Differential Privacy noise standard deviation by an astounding factor of $1/\sqrt{n}$.

💡 In Plain English: The Problem with Local Differential Privacy (LDP)

If users do not trust the server, they must add privacy noise (blurring) to their data locally on their own device before uploading. If 1,000 users each add Gaussian noise of standard deviation $\sigma = 10$, the server adds up all 1,000 vectors. The variance of independent random variables adds up! The sum now contains noise with variance $1,000 \times \sigma^2$, resulting in a noisy, blurred mess that degrades the accuracy of the neural network.

📐 Mathematical Proof of the $1/\sqrt{n}$ Variance Reduction

Let each user's vector $\mathbf{x}_i$ have $\ell_2$-norm bounded by $\Delta/2$, so the $\ell_2$-sensitivity of the sum is $\Delta$. To achieve $(\epsilon, \delta)$-differential privacy via the Gaussian mechanism, we add zero-mean Gaussian noise $\mathcal{N}(0, \sigma^2 \mathbf{I})$ with $\sigma = \frac{\Delta}{\epsilon} \sqrt{2 \ln(1.25/\delta)}$.

1. Local Differential Privacy (LDP)

Each user adds noise $z_i \sim \mathcal{N}(0, \sigma^2 \mathbf{I})$. The average across $U$ users is:

$$\hat{\mathbf{x}}_{\text{LDP}} = \frac{1}{U} \left( \sum_{i=1}^U \mathbf{x}_i + \sum_{i=1}^U z_i \right) \sim \mathcal{N}\left(\bar{\mathbf{x}}, \frac{\sigma^2}{U} \mathbf{I}\right)$$
2. SecAgg + Central DP (Batch Size $n$)

SecAgg securely sums batches of $n$ users before adding a single noise vector $z_j \sim \mathcal{N}(0, \sigma^2 \mathbf{I})$:

$$\hat{\mathbf{x}}_{\text{SecAgg}} = \frac{1}{U} \left( \sum_{i=1}^U \mathbf{x}_i + \sum_{j=1}^{U/n} z_j \right) \sim \mathcal{N}\left(\bar{\mathbf{x}}, \frac{\sigma^2}{n U} \mathbf{I}\right)$$
$$\text{Ratio of Standard Deviations} = \frac{\sqrt{\sigma^2 / (n U)}}{\sqrt{\sigma^2 / U}} = \frac{1}{\sqrt{n}}$$ The 32× Precision Multiplier: For cohorts of size $n = 1,024$, Secure Aggregation reduces the noise standard deviation by $\sqrt{1024} = 32\times$ while providing identical differential privacy guarantees! This allows models to converge cleanly with zero loss in utility!
Paper Appendix C • Page 21

Appendix C: Neural Networks & Federated Learning Updates

The mathematical formulation of Federated Stochastic Gradient Descent (FedAvg) and weighted gradient aggregation.

📐 Federated Averaging (FedAvg) Formulation

Let model parameters be $\Theta \in \mathbb{R}^m$. In each round $t$, a random cohort of users $\mathcal{U}^t \subseteq \mathcal{U}$ is selected. Each user $u$ selects a local minibatch $\mathcal{D}_u^t \subseteq \mathcal{D}_u$. The global minibatch gradient across all selected users is:

$$\nabla \mathcal{L}_f(\mathcal{D}^t, \Theta^t) = \frac{1}{|\mathcal{D}^t|} \sum_{u \in \mathcal{U}^t} \boldsymbol{\delta}_u^t \quad \text{where } \boldsymbol{\delta}_u^t = |\mathcal{D}_u^t| \nabla \mathcal{L}_f(\mathcal{D}_u^t, \Theta^t)$$

The model update rule is: $$\Theta^{t+1} \leftarrow \Theta^t - \eta \frac{\sum_{u \in \mathcal{U}^t} \boldsymbol{\delta}_u^t}{\sum_{u \in \mathcal{U}^t} |\mathcal{D}_u^t|}$$

How SecAgg Computes Weighted Averages in a Single Sum: A user does not need to send their batch size $|\mathcal{D}_u^t|$ separately. Instead, the user simply appends their scalar batch size to the front of their gradient vector: $$\mathbf{x}_u = \big[ |\mathcal{D}_u^t| \ \big\Vert \ \boldsymbol{\delta}_u^t \big]$$ The Secure Aggregation protocol sums the entire concatenated vector! The first entry of the sum reveals $\sum |\mathcal{D}_u^t|$, and the remaining entries reveal $\sum \boldsymbol{\delta}_u^t$, allowing the server to perform the exact weighted average in one single cryptographic pass!
"""
🌌 The Learner