Differential Privacy

When multiple differentially private queries are performed on the same dataset, the total privacy loss accumulates linearly. If you run a query with privacy budget ε₁ and another with ε₂, the total guarantee is bounded by (ε₁ + ε₂)-differential privacy. This property forces engineers to track a global privacy budget across an entire analysis session, ensuring that an adversary cannot simply ask many slightly noisy questions to reconstruct the underlying data. The cumulative budget is often called the epsilon spend.

When queries are executed on disjoint, non-overlapping subsets of a database, the total privacy cost is bounded by the maximum of the individual budgets, not their sum. If you partition records by user ID and query each partition with budget ε, the overall guarantee remains ε-differential privacy. This property is the mathematical engine behind scalable private analytics and federated learning, allowing organizations to compute statistics across isolated data silos without multiplying the privacy risk.

Any arbitrary computation applied to the output of a differentially private mechanism does not degrade the privacy guarantee. Once noise has been calibrated and added, an adversary cannot increase the information leakage through any subsequent analysis, transformation, or side-channel observation. This resilience to post-processing is a critical property: it means data scientists can safely visualize, aggregate, or run machine learning models on private outputs without needing to re-certify the privacy budget, as long as they never touch the raw data again.

The standard definition protects against an adversary distinguishing between datasets that differ by a single record. Group privacy extends this to datasets differing by k records: if a mechanism is ε-differentially private, it provides kε-differential privacy for groups of size k. This means protecting a family or a cohort inherently requires a larger privacy budget. The guarantee weakens linearly with group size, which is why differential privacy is fundamentally designed to protect individuals, not clusters of correlated records.

The parameter ε (epsilon) quantifies the maximum allowable divergence between the output distributions on neighboring datasets. A smaller ε provides stronger privacy but requires more noise:

• ε = 0: Perfect privacy, zero utility (identical outputs regardless of input)
• ε = 0.1–1: Strong privacy, typical for sensitive census or medical data
• ε = 1–10: Moderate privacy, common in industry deployments
• ε > 10: Weak guarantee, approaching triviality Selecting ε is a policy decision balancing utility against risk, not a purely technical parameter.

The amount of noise required to achieve a given ε depends on the sensitivity of the query—the maximum change in the query's output when a single record is added or removed. For a counting query, sensitivity is 1 (a single record changes the count by at most 1). For a sum query on unbounded values, sensitivity could be arbitrarily large. Clipping or bounding inputs is essential to control sensitivity: without it, the noise required to mask one extreme outlier would destroy all utility in the data.

The cumulative privacy loss parameter (ε) that quantifies the total leakage allowed across multiple queries before the formal differential privacy guarantee is exhausted. Each query consumes a portion of the budget; once depleted, no further queries can be answered without violating the privacy contract. Advanced composition theorems track sequential and parallel expenditures, making budget accounting a critical component of production differential privacy systems.

The foundational numeric query technique for achieving pure ε-differential privacy. It adds noise drawn from a Laplace distribution calibrated to the query's global sensitivity (Δf) divided by ε. For a counting query with sensitivity 1, the mechanism adds Lap(1/ε) noise. This guarantees that changing a single record alters the output distribution by at most a factor of e^ε, providing the canonical mathematical proof of the privacy guarantee.

A relaxation of the Laplace mechanism used when transitioning from pure ε-differential privacy to approximate (ε, δ)-differential privacy. It adds noise from a Gaussian distribution calibrated to the query's L2 sensitivity rather than L1. The δ parameter represents a small failure probability—typically cryptographically small (e.g., 10^-5)—allowing tighter composition bounds and better utility for high-dimensional queries like gradient sanitization in private deep learning.

Defensive techniques against attacks that determine whether a specific record was present in a model's training set. Differential privacy provides a formal upper bound on membership inference advantage: an adversary cannot distinguish training set membership with confidence exceeding e^ε. This connects the abstract privacy parameter to a concrete, measurable security property, making DP-trained models the gold standard for resisting extraction attacks.

A syntactic privacy model ensuring each record is indistinguishable from at least k-1 others with respect to quasi-identifiers. Unlike differential privacy's mathematical guarantee, k-anonymity is vulnerable to homogeneity attacks (when sensitive values are identical within an equivalence class) and background knowledge attacks. Differential privacy supersedes k-anonymity by providing a semantic, adversary-independent guarantee rather than a syntactic property of the released dataset.

The intentional alteration of original data values through noise addition, swapping, or rounding to preserve statistical patterns while obscuring individual records. Differential privacy formalizes perturbation by requiring the noise distribution to satisfy the ε-differential privacy condition. Ad-hoc perturbation without this mathematical foundation—such as simple random noise—can fail catastrophically against signal reconstruction attacks that average out uncorrelated noise across multiple queries.