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

Researchers need to query injury statistics across different regions. Simply hiding row-level records could still allow adjacent queries to be subtracted, enabling inference about a newly joined sentinel's status. The Prophecy Hall decided to add noise to the counts, but discovered that one person could contribute thousands of events, and analysts could endlessly repeat queries to take averages; "adding noise" did not provide provable guarantees.

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.

This lesson's objectives

• Understand the definition of adjacent data sets in $(\varepsilon,\delta)$-differential privacy;
• Compute the global sensitivity for global counting/sum/average queries;
• Explain clipping, composition, and privacy accounting;
• Why "add Laplace noise on the fly" isn't sufficient for production.

1. Guarantee for output distribution

If dataset $D$ and $D'$ differ by only one person's data, the random mechanism $M$ satisfies:

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

We say that a mechanism satisfies $(\varepsilon,\delta)$-differential privacy if, for all possible output sets $S$, the privacy guarantee holds.

• $\varepsilon$ controls the distinguishability between the two output distributions;
• $\delta$ permits a small probability term that requires strict constraints; "- 'Adjacent' can be defined as adding or removing one person, or replacing one person, and this must be disclosed in the report;"
• 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

Query the global L1 sensitivity of $f$:

$$ \Delta f=\max_{D\sim D'}\lVert f(D)-f(D')\rVert_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.

Truncation to value bounds is necessary when working with means. For example, truncate each person's duration to [0, 24] hours and then define a maximum of one record per person per day. Truncation introduces bias; therefore, the truncation proportion and its impact on the population should be reported.

3. Laplace Mechanism Illustration

For numerical queries under pure $\varepsilon$-DP, add Laplace noise scaled by $\Delta f/\varepsilon$:

import numpy as np

def illustrative_private_count(bounded_person_ids, epsilon, rng):
    if epsilon <= 0:
        raise ValueError("epsilon must be positive")

    # Prerequisite: The upstream has guaranteed that each protected unit contributes at most once
    true_count = len(set(bounded_person_ids))
    sensitivity = 1.0
    return true_count + rng.laplace(0.0, sensitivity / epsilon)

rng = np.random.default_rng()
released = illustrative_private_count(person_ids, epsilon=0.5, rng=rng)

This is a teaching example, not a production system: it lacks budget ledger, cryptographic secure random numbers, concurrency control, query normalization, auditing, and attack protection. In production, use an evaluated DP system and verify its actual implementation guarantees.

4. No universal epsilon grading table

Call epsilon < 0.1 "strong," ≈1 "medium," and >10 "weak", without adjacency definition, protection units, combination counts, delta, and threat modeling, these terms have no meaningful context.

Parameters that need to be logged:

• Who to protect and the adjacent definition;
• How many times and over what duration combinations might be released;
• Attackers' auxiliary information;
• The minimum acceptable utility for decision outcomes;
• Reasons why delta is significant relative to the overall scale;
• Who approves parameters and when are they reviewed.

First, set the overall privacy loss goal, then allocate it between queries and time windows, don't let each analyst independently pick an "appearing small" epsilon.

5. Composition consumes the guarantee

When accessing the same user's data multiple times, privacy loss accumulates. Under the naive sequential composition, the total budget of multiple $\varepsilon_i$ mechanisms can be summed; a more sophisticated accountant provides tighter bounds, but doesn't make infinite queries free.

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

• Identify equivalent/rewritten queries;
• Unified budget ledger with atomic deductions;
• Handle concurrency, failures, and retries;
• Cache the same query's results from the same publication;
• Limit out-of-band traffic across interfaces and multiple data replicas.

"Combining multiple queries to reduce noise" exactly inverts the risk of privacy budget.

6. Post-processing and Side Information

Any post-processing performed by DP 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; it guarantees no reliance on hidden algorithms. However, key, 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, so the server never sees the original value; different trust assumptions result in typically larger statistical noise.

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

8. Risk Register Implementation

[ ] 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
[ ] Count multiple publishes, groupings, and filters toward the combination
[ ] Cutting error and small group utility have been evaluated
[ ] Parameters, code, and release records are auditable

9. What Dynamic Programming Does Not Solve

• The original database was read without authorization;
• Analyze decisions that are unreasonable or discriminatory;
• Errors, biases, or non-representative data;
• The harm caused to groups by the very act of group statistics;
• Non-DP interfaces do not leak 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 is essentially DP: still needs adjacency, sensitivity, and mechanism proofs.
• Epsilon has a unified safety threshold: Interpretation is determined by context and combination.
• 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 deviation.
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.