Distributed Differential Privacy

The core mechanism where noise is generated jointly by multiple parties using secure multi-party computation (MPC). Each party contributes randomness to a function that outputs a single noise value sampled from a distribution like Laplace or Gaussian, without any party learning the final noise value. This prevents a single point of failure where a compromised aggregator could remove the noise and expose private data. The protocol ensures the noise is correctly sampled from the target distribution even if some parties are malicious.

The foundational theoretical framework for distributed DP, introduced by Cynthia Dwork, Guy Rothblum, and Christos Papadimitriou. It formalizes how mutually distrustful parties can compute a function on their combined data while ensuring each party's view satisfies differential privacy. The model proves that if each party's local computation is differentially private, the joint protocol remains private even against coalitions of adversarial participants. This is the cryptographic backbone for practical systems like Google's Prochlo.

Distributed DP is often paired with secure aggregation protocols in federated learning. Clients compute model updates on local data, then use MPC to securely sum these updates while simultaneously adding calibrated noise. The central server receives only the noisy aggregated result, never seeing individual contributions. This dual protection—cryptographic hiding during aggregation plus formal DP noise—provides defense-in-depth against both inference attacks on the aggregate and compromise of the aggregation infrastructure.

Distributed DP operates under a stronger threat model than central DP. It assumes no single trusted curator exists and that some parties may be actively malicious. The protocol guarantees:

• Privacy against the aggregator: The party computing the final result learns only the noisy output.
• Privacy against collusion: Even if a subset of parties collude, they cannot learn another honest party's data beyond the DP guarantee.
• Correctness: Malicious parties cannot cause an incorrect result without detection, enforced through verifiable secret sharing and MACs.

An alternative distributed model where a trusted shuffler or mix-network permutes and anonymizes user submissions before they reach an analyzer. The Encode, Shuffle, Analyze architecture formalized by Bittau et al. uses this approach: each user applies a local randomizer to their data, a shuffler permutes all reports, and the analyzer computes on the anonymized batch. The shuffling amplifies privacy—local randomization that provides weak DP becomes much stronger after shuffling, a phenomenon known as privacy amplification by shuffling.

A production implementation of distributed DP for telemetry data collection. Prochlo uses a three-party architecture: Encoders (client devices) apply local randomization, Shufflers permute and batch the encrypted reports, and Analyzers decrypt and aggregate the shuffled batches with additional noise. The system enforces a privacy budget per user and provides differential privacy guarantees against a curious-but-honest shuffler. It demonstrates distributed DP at scale, processing billions of reports daily while preserving user privacy.