Differentially Private Statistical Disclosure Control

DP-SDC replaces heuristic de-identification with a mathematically provable guarantee. The privacy loss parameter (ε) bounds the maximum information leakage about any single respondent. A mechanism M satisfies ε-differential privacy if for any two neighboring datasets differing by one record, the output distributions are nearly indistinguishable.

• Pure ε-DP: Achieved via the Laplace Mechanism, adding noise calibrated to L1 sensitivity.
• Approximate (ε, δ)-DP: Uses the Gaussian Mechanism, allowing a small failure probability δ for tighter utility.
• Interpretation: ε ≤ 1 provides strong privacy; ε > 10 offers weak protection.

The amount of noise injected is directly proportional to a query's sensitivity—the maximum change in output when a single record is added or removed. DP-SDC requires precise sensitivity analysis for every released statistic.

• L1 Sensitivity: Used for the Laplace mechanism; measures absolute difference.
• L2 Sensitivity: Used for the Gaussian mechanism; measures Euclidean distance.
• High-sensitivity queries (e.g., median, max) require significantly more noise than low-sensitivity queries (e.g., count, mean with bounded data).
• Example: A counting query has sensitivity 1; a sum query has sensitivity equal to the data range.

DP-SDC treats privacy as a finite, consumable resource. A total privacy budget (ε_total) is allocated across all releases. The Composition Theorem dictates that sequential queries sum their privacy losses.

• Basic Composition: k queries each with ε_i consume a total budget of Σ ε_i.
• Advanced Composition: Tighter bounds using Rényi Differential Privacy (RDP) or Moments Accountant for iterative algorithms.
• Budget Depletion: Once the budget is exhausted, no further queries are permitted on the sensitive dataset to prevent reconstruction attacks.
• Parallel Composition: Queries on disjoint data partitions do not sum; only the maximum ε applies.

A critical property of DP-SDC is resilience to arbitrary post-processing. Any computation applied to a differentially private output—whether rounding, normalization, visualization, or machine learning—cannot weaken the original privacy guarantee.

• Implication: Analysts can safely manipulate sanitized statistics without risk of reversing the privacy protection.
• No additional budget cost: Post-processing does not consume the privacy budget.
• Contrast with heuristics: Traditional SDC methods like suppression or swapping can be undone by clever post-processing; DP outputs cannot.
• Formal basis: This property is a direct consequence of the data processing inequality in information theory.

DP-SDC employs a suite of mechanisms tailored to different data types and query structures, all unified under the DP framework.

• Laplace Mechanism: Adds Laplace(Δf/ε) noise for numerical queries with bounded L1 sensitivity.
• Gaussian Mechanism: Adds Gaussian noise scaled to L2 sensitivity for (ε, δ)-DP.
• Exponential Mechanism: For non-numeric outputs (e.g., choosing the best split in a decision tree), selects items with probability proportional to exp(ε * utility / (2 * sensitivity)).
• Report Noisy Max: Efficiently identifies the top-k items from a set of candidates under DP.
• Sparse Vector Technique: Releases only answers that exceed a noisy threshold, conserving budget for significant findings.

The sensitivity of a query is the maximum change in its output when a single record is added or removed. It is the crucial calibration parameter for noise injection.

• L1 Sensitivity: Used by the Laplace Mechanism for pure ε-DP. Ideal for counting queries and medians.
• L2 Sensitivity: Used by the Gaussian Mechanism for approximate (ε, δ)-DP. Better suited for high-dimensional vector queries.

The Laplace mechanism adds noise drawn from a Laplace distribution scaled by Δf/ε, ensuring the output distribution is statistically indistinguishable between neighboring datasets.

The privacy budget (ε) is a finite, non-renewable resource representing the total allowable privacy loss. Every differentially private query consumes a portion of this budget. The Composition Theorem formally tracks this cumulative degradation:

• Basic Composition: The budget scales linearly—k queries each with ε_i consume a total budget of Σε_i.
• Advanced Composition: Provides a tighter, sub-linear bound, enabling more queries under a fixed total budget.

Once the budget is exhausted, further access to the raw sensitive data must be denied to prevent privacy exhaustion and reconstruction attacks.

A trust model where noise is added on the user's device before data is ever collected by a central server. The aggregator never sees raw records, protecting privacy even against a compromised or untrusted server.

• Randomized Response: The classic LDP mechanism. A user flips a biased coin to decide whether to answer a sensitive question truthfully or randomly, providing plausible deniability.
• Trade-off: LDP typically requires significantly more data to achieve the same utility as the central model because noise is injected independently by each user, resulting in a lower signal-to-noise ratio.

Differentially Private Stochastic Gradient Descent is the core algorithm for training deep neural networks with provable privacy. It modifies standard SGD with two critical steps:

1. Gradient Clipping: The L2 norm of each per-example gradient is bounded to a fixed threshold C, limiting the maximum influence of any single training record.
2. Noise Injection: Calibrated Gaussian noise is added to the sum of clipped gradients before the model weights are updated.

The Moments Accountant is then used to track the cumulative privacy loss (ε, δ) across thousands of training iterations, providing a tight bound on the total privacy budget consumed.

A powerful resilience property of differential privacy. Any arbitrary computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. An adversary can perform any post-hoc analysis, combine the output with external datasets, or apply machine learning models to it, and the original ε-DP guarantee remains intact. This ensures that privacy is not a fragile property that degrades through standard data science workflows, making it safe to release DP-sanitized statistics for open-ended exploration.