Dropout-Resilient SecAgg Key Recovery

Secure aggregation works because every client’s pairwise masks cancel in the sum. A client that drops out after uploading breaks that cancellation, and the server is left with a sum containing an unmatched mask — mathematically indistinguishable from noise, and completely unusable. The recovery protocol exists to reconstruct exactly the missing masks without ever revealing a surviving client’s own contribution, and getting its two-secret structure right is what separates a protocol that survives a mobile fleet from one that fails whenever a phone enters a lift. This page implements it, under secure aggregation protocols in Federated Learning Workflows for Geospatial Data.

Parameter Configuration and Calibration

threshold $t$ — shares needed to reconstruct. Reconstruction succeeds only if at least $t$ clients survive to the recovery round. Derive it from the measured dropout distribution of the worst region, not the fleet mean, and add margin: a round that cannot unmask has spent every participant’s battery and budget for nothing.
cohort $n$ and the security floor. $t$ must also be large enough that a colluding subset below $t$ cannot reconstruct anything. The usual constraint is $t > n/2$ , which bounds collusion at under half the cohort while still tolerating a nearly-half dropout.
recovery_deadline — how long the server waits before running recovery. Too short and clients that were merely slow are treated as dropped, wasting their work; too long and the round’s latency is set by its slowest failure. One to two times the median upload time is typical.
double_masking — the two secrets every client shares. Each client shares both its pairwise seed contributions and its own self-mask seed. The server must be able to recover exactly one of the two per client, never both, which is the property that makes the protocol safe against a server that lies about who dropped out.

Situation	Server recovers	Must never recover
Client dropped before uploading	its pairwise seeds	—
Client uploaded and survived	its self-mask seed	its pairwise seeds
Client uploaded then vanished	its pairwise seeds	its self-mask seed
Server falsely claims a drop	nothing (clients refuse)	both

Size t from the worst region's measured dropout, not the fleet mean. A round that cannot unmask has spent every participant's battery and budget for nothing.

Reference Implementation

python

from __future__ import annotations

import hashlib
import secrets
from dataclasses import dataclass, field
from typing import Iterable, Mapping, Sequence

PRIME = 2 ** 127 - 1


def _eval_poly(coeffs: Sequence[int], x: int) -> int:
    acc = 0
    for c in reversed(coeffs):
        acc = (acc * x + c) % PRIME
    return acc


def split_secret(secret: int, *, threshold: int, shares: int) -> list[tuple[int, int]]:
    """Shamir-split a seed so any `threshold` shares reconstruct it."""
    if not 1 < threshold <= shares:
        raise ValueError("need 1 < threshold <= shares")
    coeffs = [secret % PRIME] + [secrets.randbelow(PRIME) for _ in range(threshold - 1)]
    return [(x, _eval_poly(coeffs, x)) for x in range(1, shares + 1)]


def recover_secret(shares: Sequence[tuple[int, int]], *, threshold: int) -> int:
    """Lagrange-interpolate the constant term from at least `threshold` shares."""
    if len(shares) < threshold:
        raise ValueError(f"need {threshold} shares, got {len(shares)}")
    picked = list(shares)[:threshold]
    total = 0
    for i, (xi, yi) in enumerate(picked):
        num, den = 1, 1
        for j, (xj, _) in enumerate(picked):
            if i == j:
                continue
            num = (num * (-xj)) % PRIME
            den = (den * (xi - xj)) % PRIME
        total = (total + yi * num * pow(den, PRIME - 2, PRIME)) % PRIME
    return total


@dataclass
class RecoveryRound:
    """The server's view: who uploaded, who survived, and what may be recovered."""

    cohort: list[str]
    threshold: int
    uploaded: set[str] = field(default_factory=set)
    survived: set[str] = field(default_factory=set)

    def dropped(self) -> set[str]:
        return set(self.cohort) - self.survived

    def recoverable(self) -> dict[str, str]:
        """Which secret the server may request for each client.

        The invariant that makes double-masking safe: for any one client the server
        may learn its pairwise seeds OR its self-mask seed, never both. A server
        that could obtain both for a surviving client would recover that client's
        individual update, which is the entire property SecAgg provides.
        """
        plan: dict[str, str] = {}
        for client in self.cohort:
            if client in self.survived:
                plan[client] = "self_mask"       # cancels the client's own self-mask
            elif client in self.uploaded or client not in self.survived:
                plan[client] = "pairwise"        # cancels masks it shared with others
        return plan

    def can_recover(self) -> bool:
        return len(self.survived) >= self.threshold

    def audit(self) -> list[str]:
        """Refuse plans that would let the server unmask an individual."""
        problems = []
        plan = self.recoverable()
        for client, which in plan.items():
            if client in self.survived and which == "pairwise":
                problems.append(f"{client}: pairwise seeds requested for a SURVIVING client")
            if client not in self.survived and which == "self_mask":
                problems.append(f"{client}: self-mask requested for a DROPPED client")
        if not self.can_recover():
            problems.append(
                f"only {len(self.survived)} of {len(self.cohort)} survived; "
                f"threshold is {self.threshold} — the round cannot be unmasked"
            )
        return problems

Validation Checkpoint

python

def _validate() -> None:
    # 1. Shamir round-trip: any t shares reconstruct, fewer do not.
    secret = secrets.randbelow(PRIME)
    shares = split_secret(secret, threshold=4, shares=7)
    assert recover_secret(shares[:4], threshold=4) == secret
    assert recover_secret(shares[2:6], threshold=4) == secret
    try:
        recover_secret(shares[:3], threshold=4)
    except ValueError:
        pass
    else:
        raise AssertionError("fewer than t shares must not reconstruct")

    # 2. Different share subsets must agree — otherwise the polynomial is wrong.
    assert recover_secret(shares[1:5], threshold=4) == recover_secret(shares[3:7], threshold=4)

    cohort = [f"c{i}" for i in range(10)]
    good = RecoveryRound(cohort=cohort, threshold=6,
                         uploaded=set(cohort), survived=set(cohort[:8]))

    # 3. A healthy round recovers pairwise seeds for dropouts and self-masks only
    #    for survivors.
    plan = good.recoverable()
    assert all(plan[c] == "self_mask" for c in cohort[:8])
    assert all(plan[c] == "pairwise" for c in cohort[8:])
    assert good.audit() == []

    # 4. Too many dropouts must fail loudly rather than produce a wrong aggregate.
    collapsed = RecoveryRound(cohort=cohort, threshold=6,
                              uploaded=set(cohort), survived=set(cohort[:4]))
    assert not collapsed.can_recover()
    assert any("cannot be unmasked" in p for p in collapsed.audit())

    # 5. A malicious plan that would unmask an individual must be caught.
    sneaky = RecoveryRound(cohort=cohort, threshold=6,
                           uploaded=set(cohort), survived=set(cohort))
    sneaky.survived.remove("c0")          # server pretends c0 dropped...
    sneaky.survived.add("c0")             # ...then also claims it survived
    forced = dict(sneaky.recoverable())
    forced["c0"] = "pairwise"
    problems = [f"{c}: pairwise seeds requested for a SURVIVING client"
                for c, w in forced.items() if c in sneaky.survived and w == "pairwise"]
    assert problems, "requesting both secrets for one client must be detectable"

    print("SecAgg recovery: all assertions passed")


_validate()

This table is the security argument in four rows. Obtaining both secrets for one client recovers that client's gradient — which is the entire property SecAgg provides.

Assertion 5 is the reason for double masking. A server that could obtain a client’s pairwise seeds and observe that the client’s masked update was included would recover that client’s individual gradient — which is exactly the disclosure the protocol exists to prevent. The clients’ refusal to release both, enforced by the audit rule, is what closes it.

Incident Response and Edge Cases

The round cannot be unmasked. Nothing partial is recoverable; the aggregate is discarded. Log the survivor count, publish nothing, and treat repeated occurrences as a threshold-sizing problem rather than an infrastructure one.
Dropout is concentrated in one region. Correlated failure — a network outage, a firmware rollout. A threshold sized on fleet-wide dropout will fail here. Size it against the worst region’s distribution, or run recovery per region with regional thresholds.
A client returns after being declared dropped. Its late upload must be discarded, not folded in: its pairwise seeds have already been reconstructed, so including its masked update would let the server unmask it. Make this an explicit branch, because the natural implementation instinct is to accept the late data.
The server asks a client for a share it should not have. Clients must refuse and report it. The audit function above is the server-side conscience; the client-side check is the one that actually matters, since a compromised server will not run its own audit.
Recovery is slow at large cohorts. Reconstruction is $O(t^2)$ per secret and there is one secret per client, so the cost grows quickly. Batch the interpolation across secrets sharing an evaluation point set, and keep the threshold no larger than the security requirement demands.

Recovery, not masking, is what caps cohort size. Batch the interpolation across secrets sharing an evaluation point set before reaching for a smaller cohort.

Frequently Asked Questions

Why does each client hold two secrets rather than one?

Because the server must be able to cancel a dropped client's pairwise masks and, separately, cancel a surviving client's self-mask — but never both for the same client. With a single secret, recovering it for a dropped client would also expose the pairwise relationships of everyone who shared masks with it. The two-secret construction makes the two recoveries independent.

Can a partial aggregate be published if recovery fails?

No. The unrecovered masks are uniformly random over the group, so the sum carries no information about the underlying updates — it is not a noisy answer, it is no answer. Discard the round.

How should the threshold be chosen?

From two constraints at once: above half the cohort for collusion resistance, and below the survivor count you can rely on in the worst region for liveness. If the two constraints do not leave a gap, the cohort is too small or too unreliable, and the answer is a larger or better-selected cohort rather than a compromised threshold.

Does recovery leak anything about the dropped client?

It reveals that the client dropped, and it reveals the masks it shared — but not its update, because it never uploaded one, or its upload is discarded. The residual signal is participation metadata, which is why dropout counts should be coarsened before they appear on any dashboard.

Secure Aggregation Protocols — the parent protocol and its masking construction.
Implementing SecAgg Masking for Spatial Gradients — the quantisation and modulus this recovery operates over.
Shamir Secret Sharing for GPS Coordinate Protection — the same sharing primitive applied to coordinates.
Hierarchical Regional Aggregation Topologies — where regional thresholds become necessary.

Up one level: Secure Aggregation Protocols · Section: Federated Learning Workflows for Geospatial Data.