Secure Aggregation in Federated Learning

Pairwise masks that cancel in the sum, and what the server must repair when clients drop out.

Switch to 3D

Presets

Playback

Cohort and ring

How many clients, how many answers are needed, and the size of the modular ring.

Dropout

When clients disappear during the round.

View and animation

Experiments

Full-protocol Monte Carlo and the lying-server attack.

Layers

Model checks

The science

The problem

In federated learning every client trains on private data and sends a model update x_i (here 4 integers) to a server that only needs the sum x_1 + ... + x_n. Secure aggregation lets the server learn that sum without seeing any single x_i. This page simulates a toy version of the pairwise-masking idea of Bonawitz et al. (2017). It uses integer arithmetic modulo q = 2^bits; real systems also quantise floating-point updates to integers first.

Pairwise masks that cancel

Every pair of clients (i, j) with i < j agrees on a secret seed with Diffie-Hellman, g^(sk_i sk_j), and both expand it with a pseudo-random generator into the same mask vector m_ij in Z_q^4. Client i adds +m_ij for every partner above it and -m_ij for every partner below it (that is s_ji = -s_ij mod q). It sends y_i = x_i + sum_{j>i} m_ij - sum_{j<i} m_ji + b_i (mod q), where b_i is an optional self mask expanded from a private seed. If all clients send, every m_ij appears once with a plus and once with a minus, so sum_i y_i = sum_i x_i + sum_i b_i (mod q). A single y_i is uniform on Z_q^4 as long as one partner's seed is unknown to the server (the chi-square check in the 2D page).

Dropout: why the sum breaks

If client j never sends, the masks it shared with each sender i are still inside y_i but nothing cancels them. The server must rebuild exactly those masks. For that, every client Shamir-shares its secret key sk_i and its self-mask seed b_i among all clients: a random polynomial f of degree t - 1 over the field GF(2^31 - 1) with f(0) = the secret, share number k being f(k). Any t shares rebuild the secret by Lagrange interpolation, f(0) = sum_i f(k_i) prod_{l != i} k_l / (k_l - k_i); t - 1 shares give no information.

Unmasking round

The clients that sent are called senders; the ones that still answer the second round are responders (a sender may drop before it). With at least t responders the server (a) rebuilds sk_j of every client that did not send, recomputes the seeds g^(sk_j sk_i) with each sender i, and subtracts those masks, and (b) if double masking is on, rebuilds b_i of every sender and subtracts its self mask. The result equals sum over senders of x_i (mod q) exactly. With fewer than t responders nothing can be rebuilt and the round aborts.

Success probability

A client both sends and answers with probability a = (1 - p1)(1 - p2) (it drops before sending with p1, and a sender drops before unmasking with p2). The number of responders is Binomial(n, a), so P(success) = sum_{k >= t} C(n,k) a^k (1 - a)^(n-k). The server's work is the number of PRG expansions, |S||D| + |S| (senders times dropped clients, plus one self mask per sender), whose mean is n(n-1)p1(1-p1) + n(1-p1). The number of values a client uploads is about 3n + 3 (2 public keys, 2(n-1) shares, 4 masked entries, up to n-1 unmasking shares), so the cost per client grows linearly with the cohort and the total grows with n^2.

Why double masking and an honest-majority threshold

Suppose the server lies and says a client that did send is dropped. If only pairwise masks exist, the survivors hand over shares of sk and the server strips every mask from the received y and reads x (the attack button shows this: 300 of 300 trials). With the self mask the server can at most reach x + b, and honest clients never release both the share of sk_i and the share of b_i for the same client. The threshold should also exceed n/2; otherwise two different server views of who dropped could each collect enough shares (the page warns when t <= n/2).

Checks shown in the page

(1) the Binomial closed form against thousands of complete protocol rounds with real keys, shares and masks; (2) exact modular arithmetic: with no dropout the net masks add to 0 mod q and the server sum equals the true sum, and no successful round with dropout ever returns a wrong sum; (3) Shamir: t shares rebuild 300 of 300 random secrets, t - 1 shares rebuild none.

Simplifications and honesty

This is a teaching model, not a security proof. The key group (31-bit Diffie-Hellman) is far too small to be secure, the PRG is a simple non-cryptographic generator, there are no signatures or authenticated channels, the server is assumed to follow the protocol except in the attack demo, a malicious client is not modelled, and dropouts are independent with the same rate. Real deployments use 256-bit keys, AES-based PRGs, authenticated encryption of the shares and an extra consistency round, and they add differential privacy because the sum itself can still leak information. Update values, ring sizes and all rates here are illustrative.

The ledger and the matrix (2D view)

The ledger lists, for the coordinate you pick, the private value x_i, the net pair mask sum_{j>i} m_ij - sum_{j<i} m_ji, the self mask and the sent value y_i. Its footer adds the columns over the senders: the net pair masks add to 0 only if no sender lost a partner. The matrix shows m_ij for every ordered pair; the cell below the diagonal is -m_ij mod q of its mirror, which the spotlight line verifies. Orange outlines mark pairs with exactly one dropped partner.

What to try
  1. Press the no dropout preset: the pair masks column sums to 0 (green) and the output equals the true sum. Then press the default preset and watch the orange links: masks shared with a dropped client do not cancel until the server rebuilds them.
  2. Untick double masking and press the lying-server attack: the private update is recovered 300 of 300 times. Tick it again: 0 of 300.
  3. Press the threshold = n preset: a single dropout in the unmasking round aborts the whole round. Watch the success curve against the drop rate.
  4. Press the threshold at n/2 preset: the page marks it as unsafe, although the round succeeds more often. The cheapest threshold is not the safe one.
  5. Press the tiny ring preset: with only 8 bits the sums wrap around, yet the modular result is still exact.
  6. Press the 3,000-round experiment and compare the measured success rate with the Binomial prediction.
Probability that the round succeeds against the drop-before-send rate
How many clients answer the unmasking round (probability)
Probability of success against the threshold t
Server unmasking work against the drop rate
Made with 🟠 Blender