14.3 Differential Privacy, Sensitivity, and Budget: Noise Is Just Part of the Mechanism

Researchers need aggregate health-event statistics across regions. Hiding row-level records still allows adjacent query results to be subtracted, potentially revealing the status of a newly added participant. The platform adds noise, then discovers that one person can contribute thousands of events and analysts can repeat queries indefinitely and average the results. “We added noise” sounds reassuring; it is not yet a provable guarantee.

Differential Privacy (DP) is a mathematical framework of constraints regarding randomized mechanisms, adjacent datasets, and privacy loss. Correct implementation also requires contribution bounds, budget accounting, secure random number generation, and a publishing system.

Learning Objectives

• Understand the definition of adjacent data sets in $(\epsilon ,\delta )$-differential privacy;
• Compute global sensitivity for count, sum, and mean queries;
• Explain clipping, composition, and privacy accounting;
• Explain why casually adding Laplace noise is insufficient for production.

1. The Guarantee Concerns Output Distributions

Define adjacency $D\sim D^{\prime }$ for the chosen protected unit. A randomized mechanism $M$ satisfies $(\epsilon ,\delta )$-DP if the following holds for every adjacent pair and every measurable output set $S$:

$$P[M(D)\in S]\le e^{\epsilon }P[M(D^{\prime })\in S]+\delta$$

Here $\epsilon \ge 0$ and $0\le \delta <1$; probability is over the mechanism’s randomness. The definition constrains the output distribution, not just one observed result.

• $\epsilon$ controls the distinguishability between the two output distributions;
• $\delta$ is additive slack in the inequality and must be tightly controlled; it is not directly a person’s disclosure probability;
• “Adjacent” may mean adding/removing one person or replacing one person’s entire contribution; the report must disclose which definition it uses;
• The protection unit (whether people, equipment, or an event) should be determined by the risk model.

DP is not "zero attack success rate," nor does it hide the overall facts about the dataset itself. It limits the additional influence a single protected unit can have on the released data.

2. Sensitivity determines the noise scale

The global L1 sensitivity of query $f$ is:

$$\mathrm{\Delta }f=\underset{D\sim D^{\prime }}{sup}\Vert f(D)-f(D^{\prime }){\Vert }_1.$$

If each person contributes at most one row, counting sensitivity is typically 1. If one person can contribute 1,000 events, person-level counting sensitivity can reach 1,000; contributions must be capped per person.

Sensitivity depends on adjacency and the entire release scope, not just a per-row cap:

Query	Adjacency	Enforced condition	Global L1 sensitivity
Distinct people	Add/remove one person	Deduplicate stable person IDs	$1$
Event count	Add/remove one person	At most $C$ rows per person across this release	$C$
Total duration	Add/remove one person	One value per person, clipped to $[0,24]$	$24$
Mean duration	Fixed public count $n>0$, replace one person	One value per person, clipped to $[0,24]$	$24/n$

For the last row, one value can change by at most 24 and the sum is divided by unchanged $n$. When the count is private, plugging the actual count into that denominator is insufficient. One option releases a noisy sum and count and composes their budgets. A public denominator floor can handle near-zero noisy counts as post-processing, though small-group error still needs evaluation. See NIST SP 800-226, Appendix B.5.

“One row per person per day, bounded to $[0,24]$” still permits a contribution of 720 to a 30-day total. Bound contributions over the query window and assess clipping rates and group bias. Selecting bounds from private data or publishing clipping rates also requires privacy treatment.

3. Laplace Mechanism Illustration

For numerical queries under pure $\epsilon$-DP, add Laplace noise scaled by $\mathrm{\Delta }f/\epsilon$:

import numpy as np

def illustrative_private_count(person_ids, epsilon, rng):
    if not np.isfinite(epsilon) or epsilon <= 0:
        raise ValueError("epsilon must be finite and positive")
    person_ids = list(person_ids)
    if any(not isinstance(value, str) or not value for value in person_ids):
        raise ValueError("person IDs must be nonempty strings")
    true_count = len(set(person_ids))
    return true_count + rng.laplace(0.0, 1.0 / epsilon)

person_ids = ["synthetic-a", "synthetic-a", "synthetic-b", "synthetic-c"]
rng = np.random.default_rng(42)  # Reproducible arithmetic only; no private release.
released = illustrative_private_count(person_ids, epsilon=0.5, rng=rng)
print(round(released, 3))

The synthetic IDs contain three distinct people; the output is about 4.588. The fixed seed only makes the arithmetic reproducible. A public seed makes noise predictable and cannot protect a real release. The function also lacks budget accounting, secure randomness, concurrency control, and floating-point mechanism guarantees; changing the generator alone would not make it production-ready.

For an ideal real-valued Laplace mechanism, $\epsilon =0.5$ and $\mathrm{\Delta }f=1$ give scale $b=2$. Mean absolute noise is 2, and about 95% of absolute errors are at most $b\ln 20\approx 5.991$. This describes accuracy, not privacy parameter $\delta$. Adjacent counts differ by one, so the triangle inequality bounds every output-density ratio by $e^{1/b}=e^{0.5}$. See the mechanism and proof in Dwork and Roth, Chapter 3.

4. No universal epsilon grading table

Labels such as “strong” for epsilon < 0.1, “medium” for ≈1, and “weak” for >10 lack sufficient meaning without adjacency, protected units, composition, delta, and the threat model.

Parameters that need to be logged:

• Who to protect and the adjacent definition;
• How often releases will occur and over what period they will compose;
• Attackers' auxiliary information;
• The minimum acceptable utility for decision outcomes;
• Why the chosen delta is justified relative to population size;
• Who approves parameters and when are they reviewed.

Set an overall privacy-loss goal and allocate it across queries and time windows. Each analyst choosing an epsilon that looks small cannot enforce a shared budget.

5. Composition consumes the guarantee

Releases involving the same person’s data require composition. Basic sequential composition gives a $(\sum _i{\epsilon }_i,\sum _i{\delta }_i)$ bound; a more advanced accountant may tighten it under the relevant assumptions. The budget is a guarantee bound, not measured harm. Parallel composition requires disjoint protected units and valid partition rules; different dates for the same person do not meet that condition.

Rerunning the same query and averaging independent noise improves accuracy but continuously consumes budget. The system must:

• Identify equivalent/rewritten queries;
• Maintain a unified budget ledger with atomic deductions;
• Handle concurrency, failures, and retries;
• Cache the same query's results from the same publication;
• Control bypasses through other interfaces and data replicas.

For example, 100 independent releases at $\epsilon =0.5$ each have a basic composition bound of 50. Averaging scale-2 noise reduces variance from 8 to $8/100$; that accuracy improvement accompanies additional releases. A purpose-built joint mechanism can sometimes improve utility within a fixed total budget, but its complete mechanism and proof must be evaluated.

Displaying the cached result of one release again adds no new raw-data access. Bind the cache key to the snapshot, query parameters, contribution rules, and mechanism version; recomputing on another snapshot is another release. Reusing an answer must not become reusing the same noise for different queries, because subtraction would cancel that noise.

6. Post-processing and Side Information

Any post-processing of a DP release that no longer accesses the original data does not further weaken its DP guarantee. This allows sorting, visualization, and deterministic formatting to reuse the same released result.

DP design allows attackers broad auxiliary information; its guarantee does not depend on hiding the algorithm. However, keys, random state, unprotected intermediate tables, and debug logs in the implementation still require secure controls.

7. Central vs. Local Models

• Central DP: The trusted service receives raw data and uniformly enforces the mechanism; typically offers better utility, but requires strong security and governance of the central entity.
• Local DP: Data is randomized before leaving the device. The server receives a randomized report, which does not guarantee it can never guess the original value; these different trust assumptions typically require more statistical noise.

Distributed and shuffle models also exist. The choice depends on trust boundaries, adversaries, and system architecture, rather than epsilon alone.

8. Implementation Checks

[ ] Adjacency relationships and protection units are clearly defined
[ ] The number of contributions and value range per person has been strictly defined
[ ] The mechanism aligns mathematically with the accountant's calculations
[ ] Random number and floating-point implementations have been evaluated
[ ] Budget deduction is atomic, durable, and cannot be bypassed
[ ] Intermediate results, logs, and cache do not leak true values
[ ] Account for composition across releases, groupings, and filters
[ ] Clipping bias and small group utility have been evaluated
[ ] Parameters, code, and release records are auditable

9. What Differential Privacy Does Not Solve

• Unauthorized access to the raw database;
• Unreasonable processing purposes or discriminatory decisions;
• Errors, biases, or non-representative data;
• The harm caused to groups by the very act of group statistics;
• Non-DP interfaces leaking the same data;
• Identity mapping outside of the model or publishing system.

It's a formal guarantee of the publish/learn mechanism, not a complete privacy program.

Common Misconceptions

• Adding random noise means DP: Adjacency, sensitivity, and a valid mechanism proof are still needed.
• Epsilon has a unified safety threshold: Interpretation is determined by context and composition.
• Each event sensitivity is 1: Personal contributions must be capped when protecting human units.
• Query failures do not consume budget: If the result or side effect is observable, handling must follow system design decisions.

Practice

1. Define event-level and person-level adjacency relations, and compute count sensitivity.
2. Select the clipping range for average working hours and analyze the bias.
3. Design an atomic budget ledger to handle concurrency, retries, and duplicate queries.
4. Audit a "noisy API" to identify budget and bypass gaps.

Summary

The core of differential privacy isn't a noise button; it's an auditable overall guarantee: the protection units, contribution bounds, mechanisms, budget allocations, and system boundaries must all be consistent.

The final lesson applies privacy requirements to day-to-day operations: how to consistently enforce access authorization, data retention and deletion, request responses, vendor management, and incident response.