Have your data and hide it too: an introduction to differential privacy

Why Private Aggregation Can Still Leak Data

Applications from browser telemetry to photo curation rely on user data, but that data is often sensitive. The Distributed Aggregation Protocol (DAP) addresses this by using multi-party computation to let a data collector learn aggregate statistics without seeing individual reports. Cloudflare is contributing to the DAP standard and maintains an open-source implementation.

Yet private aggregation alone does not guarantee privacy. The aggregate itself can reveal information about individuals. A simple average over a set containing one element discloses that element. Even sums can expose outliers — knowing the average height of a group, for instance, can reveal a great deal about an unusually tall member. Release enough accurate aggregates and attackers may be able to reconstruct an entire database.

Real-world attacks demonstrate this risk. Researchers have shown deanonymization against the U.S. Census, and machine learning models trained on sensitive data are vulnerable too. In one documented attack, researchers extracted personal information from GPT-2 for an individual whose data appeared just once in its training set.

Federated learning — where model updates are aggregated rather than raw data — does not fully solve the problem. An attack from the NeurIPS 2019 paper "Deep Leakage from Gradients" shows how an average model update can be reversed: starting from a random guess, an attacker iteratively refines it until the original training images are nearly recovered.

Adding a Statistical Guarantee: Differential Privacy

Differential privacy (DP) provides a formal layer of protection on top of secure aggregation. It works by adding calibrated noise to aggregates, making it difficult to infer whether any given individual contributed to the result. The privacy level is controlled by a parameter 𝜖 (epsilon). A small 𝜖 means more noise and stronger privacy; a larger 𝜖 trades privacy for accuracy.

Without DP, deployments often rely on ad-hoc protections like minimum batch sizes or attribute redaction. These are essentially patches against known attacks and can fail when assumptions about the data do not hold. Outliers, for example, can still leak through certain aggregation tasks, and complex statistics such as averaged neural network updates can reveal far more than simple sums. DP is a general property that holds even against adversaries whose strategies we have not anticipated.

DP also offers practical advantages over handcrafted rules:

• Standardized privacy parameter. The value of 𝜖 can be compared across applications, from simple counters to federated learning, and can be discussed or published.
• Decoupling privacy from other settings. The privacy guarantee is separate from application parameters like batch size, giving engineers more control over the utility-privacy tradeoff.
• Graceful degradation. Guarantees weaken gradually under repeated aggregation or correlated data, where alternative definitions like k-anonymity can fail catastrophically.
• Resilience to side information. DP holds even when attackers bring external data, such as purchased datasets, to the table.

Making DAP Differentially Private

There are several ways to combine DP with DAP, each with a different threat model:

• Central DP (Collector Randomization). The Collector adds noise after computing the aggregate. This is simple but does not protect the aggregate from the Collector itself.
• Local DP (Client Randomization). Each client adds noise to its report before submission. This protects against malicious Aggregators and Collectors but requires more noise per measurement, harming accuracy.
• Aggregator Randomization. Each Aggregator adds noise to its aggregate share. This sits between the other two: it offers the same threat model as DAP itself — trust that at least one Aggregator is honest — with computational overhead comparable to Central DP.

The Aggregator Randomization approach was the focus of investigation. However, the standard definitions and proofs of DP do not apply directly: DAP is an interactive, multi-party protocol running under computational assumptions, while classical DP assumes an adversary with unbounded run time. Work remains to adapt the framework of Computational Differential Privacy to compose with DAP's existing cryptographic subroutines.

Concrete Example: Private Network Error Logging

Network Error Logging (NEL) is a promising candidate for DP-enhanced DAP. It is useful to collect aggregate connection-error statistics per domain, but individual reports can expose browsing habits. In a simplified scenario, DAP computes a histogram of error types for a single domain:

If an error type is rare, the histogram alone can reveal whether a particular user hit that error. The goal is to release a noisy version of the histogram that does not reveal information about any individual report.

Implementation work proceeded in libprio-rs, a widely-used Rust library for DAP cryptography. A general API for Aggregator Randomization was designed, then implemented for statistical aggregates using the OpenDP discrete Gaussian and discrete Laplace mechanisms, which fit well with modular ring arithmetic. After adapting Cloudflare's Daphne DAP implementation, a toy deployment demonstrated DP-enhanced network error logging end to end.

The Privacy-Utility Tradeoff in Practice

Choosing 𝜖 is more art than science. While the code accepts any positive real number, smaller values produce noisier results, sometimes yielding negative counts (which can be truncated without affecting privacy). For the network error logging data with many reports and few error types, masking a single contribution is easy, and 𝜖 = 1 appears to strike a reasonable balance.

The tradeoff depends heavily on what is being measured. For the common error_type = 8, a strict privacy bound of 𝜖 = 0.01 may still yield acceptable accuracy. For rarer events such as error_type = 15, achieving the same relative accuracy requires a much larger 𝜖 = 0.1.

Batch size is another lever. Waiting for more reports before aggregating improves accuracy at a fixed privacy level, since individual contributions are easier to hide in a larger batch. For a batch of size 1, the DP output is essentially random — privacy holds, but the result is useless. This graceful degradation of utility, rather than privacy, is a deliberate feature that engineers can manage by choosing 𝜖 to suit their accuracy requirements.

There is no consensus on how to select 𝜖. Cynthia Dwork, one of DP's inventors, co-authored a 2019 paper noting the lack of a standard method. Unlike cryptographic key lengths, 𝜖 must be large enough to learn something useful, and what counts as "useful" varies by application.

For practitioners without deep DP expertise, a practical approach is to look for established values used in similar deployments. The U.S. Census Bureau maintains an internal registry, NIST suggests rough ranges in an informal blog post (strong privacy roughly 0 < 𝜖 < 5, and 5 < 𝜖 < 20 can be workable), and a community blog post lists 𝜖 values used by Apple, Google, and others. Another complementary technique is to fix the maximum acceptable error and work backward to find a corresponding 𝜖, then verify it falls in a defensible range.

The Path Forward

Secure aggregation protects the how of computing statistics; differential privacy protects the what. Both layers are necessary for strong privacy guarantees in real-world measurement systems. Open-source implementations and ongoing standardization efforts are making it practical to combine DP with DAP, though the work is not finished. Protocol details such as Aggregators' visibility into report counts and client IP addresses can complicate formal DP guarantees — issues that have already sparked discussion at the IETF. Practical concerns like modular arithmetic, secure noise sampling, and timing attacks further show that meaningful integration of cryptography and differential privacy requires collaboration across both disciplines.