Differential Privacy

The Laplace Mechanism is the canonical algorithm for achieving differential privacy for numeric queries (e.g., counts, sums, averages). It works by adding noise drawn from a Laplace distribution to the true query result. The scale of the noise is calibrated to the sensitivity of the query (the maximum change a single individual's data can cause) divided by the privacy parameter epsilon (ε).

• Key Formula: Noisy_Result = True_Result + Laplace(Δf / ε)
• Use Case: Publishing private census statistics or aggregate metrics from user databases.
• Property: Provides pure (ε)-differential privacy.

The Gaussian Mechanism is an alternative for numeric queries that adds noise from a Gaussian (normal) distribution. It is often preferred in practice because the sum of Gaussian noises remains Gaussian, simplifying composition analyses. It requires a slightly relaxed privacy definition, (ε, δ)-differential privacy, where δ is a small probability of privacy failure.

• Key Difference: Noise scale is proportional to √(2ln(1.25/δ)) * (Δf / ε).
• Use Case: Iterative algorithms like deep learning, where many queries are composed.
• Advantage: The tails of the Gaussian distribution decay faster than Laplace, sometimes yielding more useful noisy outputs.

The Exponential Mechanism is used for non-numeric queries where the output is a discrete object, like selecting the best candidate from a set (e.g., "most common disease" or "optimal routing path"). It assigns a probability to each possible output based on a utility function that scores how good an output is for a given dataset. Outputs with higher utility are exponentially more likely to be chosen.

• Core Idea: Probabilistic selection, not additive noise.
• Utility Function: Defines the quality of an output. Sensitivity is calculated on this function.
• Use Case: Private decision-making, feature selection, or releasing a sanitized version of a frequent itemset.

Report Noisy Max is a fundamental and efficient building block for private selection. Given a set of numeric queries (e.g., counts for different categories), it adds independent noise (via Laplace or Gaussian) to each one and returns only the identity of the query with the highest noisy value, not the values themselves.

• Privacy Benefit: Often requires less noise than revealing all noisy counts.
• Example: Finding the most popular product category in private sales data without revealing the exact sales counts for any category.
• Variation: Report Noisy Max with Threshold only reports a winner if its noisy value exceeds a predefined limit, otherwise returns "no winner."

The Sparse Vector Technique (SVT) is an advanced mechanism designed for the scenario where we ask a long sequence of queries but only expect a few to have significant results. It uses a noisy threshold to filter queries.

1. Set a noisy threshold.
2. For each query, check if its answer exceeds the threshold.
3. If "above," release a noisy version of that answer and count it against the privacy budget.
4. If "below," simply say "below" at a very low privacy cost.

• Efficiency: Provides a way to screen many queries without paying the full composition cost for each.
• Caution: Requires careful, correct implementation to avoid subtle privacy bugs.

Composition is the principle governing how privacy loss accumulates when multiple differentially private mechanisms are applied to the same dataset. It is the mathematical foundation for building complex private programs from simple mechanisms.

• Basic Composition: The epsilons of sequential mechanisms sum. ε_total = ε₁ + ε₂ + ...
• Advanced Composition: Provides a tighter (better) bound for the composition of many mechanisms, especially with Gaussian noise. It formalizes the trade-off between ε and δ.
• Parallel Composition: If mechanisms are applied to disjoint subsets of the data, the overall privacy guarantee is only the maximum of the individual epsilons, not the sum. This is key for efficient algorithm design.

The privacy budget (epsilon, ε) is the core resource in differential privacy, quantifying the maximum allowable privacy loss. In synthetic data generation, this budget is carefully allocated across the entire data synthesis pipeline.

• Composition Theorems track cumulative privacy loss when multiple queries are made on the sensitive data.
• Post-Processing Immunity ensures that any analysis performed on the already-private synthetic data incurs no additional privacy loss.
• Example: A pipeline might allocate ε=1.0 for computing marginal statistics and ε=0.5 for modeling correlations, ensuring the total ε=1.5 does not exceed the system's global privacy guarantee.

Synthetic data is often generated by first running differentially private queries on the real dataset to learn its underlying distribution. Common mechanisms include:

• Laplace Mechanism: Adds calibrated noise from the Laplace distribution to the output of numeric queries (e.g., counts, averages).
• Exponential Mechanism: Selects the best output from a set of candidates (e.g., the most frequent category) in a private manner, useful for categorical data.
• Gaussian Mechanism: Used for high-dimensional queries where noise is drawn from a Gaussian distribution, often applied under concentrated differential privacy (zCDP). These noisy statistics then serve as constraints for a generative model, ensuring the synthetic data matches the private view of the real data's properties.

Machine learning models like Generative Adversarial Networks (GANs) or Variational Autoencoders (VAEs) can be trained under differential privacy to become private data generators.

• Differentially Private Stochastic Gradient Descent (DP-SGD) is the standard algorithm, which clips per-example gradients and adds Gaussian noise during model training.
• The trained private generator can then produce an unlimited number of synthetic records without consuming additional privacy budget.
• Challenges: Adding noise for privacy often degrades the fidelity and utility of the generated data, creating a direct trade-off between privacy (ε) and data quality (often measured by downstream model performance).

This approach synthesizes data by privately releasing a set of low-dimensional marginals (e.g., 2-way or 3-way contingency tables) from the sensitive dataset and then generating synthetic records that are consistent with these noisy marginals.

• Methods: Algorithms like Private-PGM (Private Probabilistic Graphical Models) use the noisy marginals to infer a compact, approximate joint distribution.
• Advantage: It scales better to high-dimensional data than attempting to model the full joint distribution directly under privacy constraints.
• Use Case: Generating synthetic patient health records where the private statistics might include correlations between age, diagnosis code, and medication, but not the full individual history.

A critical application is formally evaluating the trade-off curve between data utility and the privacy guarantee (ε).

• Utility Metrics: Measured by how well a model trained on the synthetic data performs on a hold-out real test set, or by statistical similarity metrics like Total Variation Distance or Wasserstein Distance between real and synthetic distributions.
• The Fundamental Limit: There is an inherent tension; lower ε (stronger privacy) typically results in lower utility. The goal is to find the "knee" of the curve where utility remains acceptable for the intended analytical task.
• Task-Aware Tuning: The optimal ε value differs if the synthetic data is intended for logistic regression versus training a deep neural network, requiring careful benchmarking.

Differential privacy is often combined with other privacy-enhancing technologies (PETs) in a defense-in-depth strategy for synthetic data.

• Secure Multi-Party Computation (MPC): Allows multiple parties to jointly compute the statistics needed for synthesis without revealing their individual datasets, after which differential privacy noise is applied.
• Federated Learning: Models can be trained across decentralized devices with DP-SGD, and the resulting private model can serve as a synthetic data generator.
• k-Anonymity via Synthesis: Instead of generalizing real records, synthetic data can be generated to satisfy k-anonymity-like properties by ensuring every combination of quasi-identifiers in the synthetic set appears for at least k synthetic "individuals."

A privacy model for releasing structured datasets where each record is indistinguishable from at least k-1 other records with respect to a set of quasi-identifier attributes (e.g., ZIP code, age, gender). It protects against identity disclosure by ensuring an individual cannot be uniquely identified.

• Implementation: Achieved through generalization (reducing precision, e.g., 'Age 32' → 'Age 30-35') and suppression (removing unique values).
• Limitation: Vulnerable to homogeneity attacks (if all k records share the same sensitive attribute) and background knowledge attacks. It is a syntactic, rather than a rigorous mathematical, guarantee like differential privacy.

A stronger variant of differential privacy where noise is added to an individual's data on their own device before it is ever collected by a central aggregator. This provides a privacy guarantee against a curious or malicious data collector.

• Mechanism: Each user perturbs their true value using a randomized algorithm (e.g., the RAPPOR algorithm for collecting browser statistics) and sends only the noisy report.
• Trade-off: Provides stronger trust models but typically requires more users to achieve the same level of statistical utility compared to centralized DP, where noise is added after aggregation.

The process of creating artificial datasets that mimic the statistical properties and relationships of a real, sensitive dataset. When combined with differential privacy, it creates privacy-preserving synthetic data.

• DP-Synthetic Data: A generative model (like a GAN or diffusion model) is trained with a differentially private algorithm. The resulting model can then produce unlimited synthetic records that preserve global dataset statistics but contain no traceable link to any real individual.
• Primary Use: Enables safe data sharing for development, testing, and collaboration, as the synthetic data carries a formal privacy guarantee.