Differential Privacy

Epsilon (ε) is the primary parameter that quantifies the privacy loss incurred by a single query. A smaller epsilon (e.g., ε=0.1) provides stronger privacy guarantees by injecting more noise, while a larger epsilon (e.g., ε=10) yields higher accuracy but weaker protection.

• Composition: Privacy loss accumulates additively across multiple queries. A sequence of queries with budgets ε₁, ε₂, ε₃ consumes a total budget of ε₁+ε₂+ε₃.
• Typical ranges: Apple uses ε=4 for emoji suggestions; the US Census Bureau used ε=19.61 for the 2020 decennial census redistricting data.
• Zero epsilon (ε=0) implies perfect privacy but zero utility—the output is pure random noise.

Delta (δ) represents the probability that the privacy guarantee fails catastrophically. In (ε, δ)-differential privacy, δ bounds the chance that an adversary can learn something about an individual beyond the ε guarantee.

• Typical values: δ should be cryptographically small—much less than 1/N where N is the dataset size. Common choices are 10⁻⁵ to 10⁻⁹.
• Pure vs. Approximate DP: When δ=0, the mechanism satisfies pure ε-differential privacy. When δ>0, it satisfies approximate differential privacy, which permits mechanisms like the Gaussian mechanism.
• A non-zero δ acknowledges that absolute guarantees may be impossible in high-dimensional settings while remaining practically meaningful.

Sensitivity measures how much a single individual's data can change the output of a query. It determines the minimum noise scale required to achieve a given privacy guarantee.

• Global Sensitivity (GS): The maximum difference in query output across all possible neighboring datasets differing by one record.
• Local Sensitivity (LS): The maximum difference for a specific dataset, which can leak information if used directly—requiring smoothing techniques.
• Example: A counting query has GS=1 (one person changes the count by at most 1). A sum query on salaries bounded to [$0, $500K] has GS=$500K, requiring proportionally more noise.

The Laplace mechanism is the canonical method for achieving pure ε-differential privacy on numeric queries. It adds noise drawn from a Laplace distribution centered at zero with scale parameter b = GS/ε.

• How it works: For a query f with global sensitivity GS, output f(D) + Lap(GS/ε).
• Optimality: The Laplace mechanism is optimal for L1 sensitivity—it minimizes expected error among all ε-differentially private mechanisms for a given sensitivity.
• Use case: Ideal for counting queries, histograms, and low-dimensional numeric aggregates where pure DP is required.

The Gaussian mechanism achieves (ε, δ)-approximate differential privacy by adding noise from a normal distribution. It is essential for high-dimensional queries where the Laplace mechanism would require excessive noise.

• Noise calibration: Standard deviation σ = (GS · √(2·ln(1.25/δ))) / ε.
• Advantage over Laplace: The Gaussian mechanism's noise scales with L2 sensitivity rather than L1, making it more efficient for vector-valued queries and gradient computations in differentially private stochastic gradient descent (DP-SGD).
• DP-SGD: The foundational algorithm for differentially private deep learning relies on the Gaussian mechanism to clip and noise per-example gradients during training.

Post-processing immunity is a fundamental theorem stating that any computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. Once noise is injected, privacy is preserved forever.

• Formal statement: If M satisfies ε-differential privacy, then for any function g (even adversarial), g(M(D)) also satisfies ε-differential privacy.
• Practical implication: Analysts can freely visualize, aggregate, filter, or transform DP outputs without consuming additional privacy budget or risking re-identification.
• Contrast with anonymization: Unlike k-anonymity or pseudonymization, which can be broken by linking attacks, DP's post-processing immunity provides a composable, future-proof guarantee against auxiliary information.