Differencing and differential privacy

Why does a query interface leak by arithmetic, and what does differential privacy bound?

Differencing and the query interface

Before differential privacy makes sense, we need the attack that it answers.

Everything above concerns a static release. A live query interface that answers only aggregates (sums, counts, averages) looks safer because no rows leave. It is actually worse.

Generalize this. An adversary who can choose arbitrary predicates can build a system of linear equations over the individual records and solve it. With enough queries, a database that answers only aggregates can be fully reconstructed. This is a theorem, not a rule of thumb, and it is the formal result that ended the "query auditing" approach to statistical databases. The simple countermeasures all fail:

• Minimum group-size thresholds ("refuse if fewer than 10 rows") are defeated by nesting predicates, as in the salary example, where both groups are large.
• Query auditing (refusing queries that would leak) is itself a leak, because a refusal is information. Deciding which queries are safe is also computationally intractable.

This is why the field changed direction. It was not because k-anonymity was careless. It is because you cannot defend a release by inspecting the release. Every defence that looks at an output and decides whether it is safe is defeated by composition, because safety was never a property of any single output.

---

Differential privacy

The reframe: stop asking whether the output is safe. Instead, bound how much the output can depend on any one individual.

A mechanism is differentially private (DP) if, for any two datasets that differ in one individual's record, the probability of any output changes by at most a factor of e^ε. Here ε (epsilon) is a number chosen by the data owner. The consequence is what matters: whatever an adversary concludes about you, they would have concluded almost the same thing if your record had never been in the dataset. Your participation has a bounded effect, whatever else the adversary knows. The definition covers all adversaries and all priors by construction, which is exactly what the syntactic generation could not do.

A common way to build a DP mechanism is to add random noise to the true answer. For a count, you add noise drawn from the Laplace distribution (a bell-like curve with a sharp peak) with scale 1/ε.

Three structural properties follow.

It composes, with arithmetic

Run a mechanism with budget ε₁ and another with ε₂, and the combined release is (ε₁ + ε₂)-private in the basic accounting (tighter analyses give better results). This is the first privacy definition where the question "we published two things; how private is that?" has a computable answer. Composition is not a feature added later. It is the reason the definition is a bound on a mechanism and not a property of an output.

This is the rule we meet here: only bounds compose; states do not. "This table is 5-anonymous" is a state of one table, and it says nothing about two tables together. "This process spends at most ε" is a bound, and bounds add. The same structure appears in other places: percentiles of two services cannot be added to give the percentile of the pair, and isolation levels of two transactions do not combine into an isolation level of both. The cure is always the same: redefine the guarantee as a bound on a process with additive accounting, or accept that you cannot reason about the combination at all. This may be the most transferable idea here. It also explains why most real platforms cannot state what their privacy guarantee is: a combination of weak mechanisms (tokenized here, thresholded there, tagged somewhere else) has no accounting at all, so they can only list which mechanisms they have deployed.

Noise scales with sensitivity divided by ε

Sensitivity is the most that one individual can change the answer. A count has sensitivity 1 (adding or removing one person changes it by at most 1). So the noise has size about 1/ε, whatever the size of the dataset.

A sum over an unbounded domain has unbounded sensitivity (one person could have a huge value). So you must clamp each person's contribution first (for example, cap each bill at 10,000). The clamp is itself a utility decision: it distorts the tail of the data.

This gives a practical rule: DP is nearly free on large aggregates and very costly on small ones. It protects exactly the queries that were never the privacy risk (large totals) and destroys exactly the fine-grained slices that analysts want ("diabetes patients aged 30–34 in one clinic"). This mismatch, more than the mathematics, is why real adoption is narrower than the research literature suggests.

The budget is finite and it depletes

Every query spends some ε. When the total budget is spent, the dataset must stop answering, or the guarantee is void. Example: if the total budget for a dataset is ε = 1.0 and each query costs 0.1, the dataset can answer 10 queries, ever.

This is new in the whole platform. Every other resource (CPU, memory, storage, money) can be refilled or bought. A privacy budget is consumed by reading and cannot be refilled. This is the law: Some budgets are depleted by reading. It forces a governance decision that no data platform is built for: who gets how much ε, and what happens when an analyst spends the quarter's budget on one exploratory notebook?

Honest limits of DP

The unit of protection is whatever "one individual" means in the definition. Event-level DP over a stream of user events protects a single event, not a user. A user who contributes 1,000 events gets a guarantee weaker by roughly a factor of 1,000. User-level DP requires you to bound each user's total contribution. This is real engineering work and is often skipped. It is the most common reason a DP deployment is weaker than it looks.

DP bounds the effect of your record. It does not bound what is learned about you from correlated records. Examples: your family's genome, your household's electricity use, your co-location with a friend. The definition assumes that records are independent contributions, and they are not. This is the law that independence is assumed and rarely true, in its sharpest form: the guarantee is only as strong as the independence assumption, which is a modelling assumption that nobody verifies.

ε has no principled setting. The theory says smaller is better. In practice, deployments use values across a wide range with no agreement on what is acceptable, and deployments with large ε have been criticised as giving little real protection. Anyone who states one canonical "safe" value overstates how much the field agrees.