Differential Privacy

Differential privacy is quantified by two parameters: epsilon (ε) and delta (δ).

• Epsilon (ε): The privacy loss parameter. A smaller ε provides stronger privacy, as it bounds the log-likelihood ratio of any output occurring with or without an individual's data. An ε of 0 is perfect privacy but yields no utility.
• Delta (δ): A failure probability. Pure differential privacy uses δ=0. The relaxed (ε, δ)-DP allows a tiny, bounded probability (e.g., δ = 10^-5) of a catastrophic privacy violation, enabling more practical algorithms like the Gaussian mechanism. This pair provides a rigorous, composable measure of risk.

The foundational algorithm for achieving pure ε-differential privacy for numeric queries (e.g., counts, sums, averages).

• Process: It adds random noise to the true query result. The noise is drawn from a Laplace distribution, centered at zero.
• Key Parameter: Sensitivity (Δf): The maximum amount a single record can change the query's output. The scale of the Laplace noise is set to Δf / ε.
• Example: A query counting "How many patients have Disease X?" has a sensitivity of 1 (adding/removing one patient changes the count by at most 1). To achieve ε=0.5, add noise from Laplace(0, 1/0.5 = 2).

The primary algorithm for achieving the relaxed (ε, δ)-differential privacy, often preferred for its better utility with high-dimensional queries.

• Process: Adds noise drawn from a Gaussian (Normal) distribution to the query result.
• Noise Scaling: The standard deviation (σ) of the Gaussian noise is scaled by the sensitivity (Δf) and a complex function of ε and δ. Crucially, σ is proportional to √(2ln(1.25/δ)) * (Δf/ε).
• Use Case: Ideal for complex machine learning tasks like stochastic gradient descent, where many queries are made, and the Gaussian distribution's lighter tails (compared to Laplace) often yield more useful model updates.

A versatile algorithm for achieving differential privacy when the desired output is non-numeric (e.g., selecting the best candidate, rule, or text label).

• Process: It doesn't add noise. Instead, it randomly samples an output from the set of all possible outputs, with a probability exponentially weighted by a utility function.
• Utility Function (u): Assigns a score to each possible output, measuring its quality for the dataset. Outputs with higher utility scores are exponentially more likely to be chosen.
• Example: Selecting the most common medical diagnosis in a private dataset. The utility score for each diagnosis is its count. The mechanism privately outputs a diagnosis, heavily favoring the true most common one but with a controlled chance of picking a runner-up.

The mathematical rules that track cumulative privacy loss when multiple DP mechanisms are applied to the same data, which is critical for complex analyses like model training.

• Basic Composition: The epsilons add up. If you run k mechanisms, each with ε_i privacy, the total privacy loss is sum(ε_i). Simple but pessimistic.
• Advanced Composition: Provides a tighter bound, especially for large k. For k mechanisms each with ε, the total privacy loss scales with ~ε√(2k ln(1/δ')) for a new, slightly larger δ'. This is fundamental for iterative algorithms.
• Post-Processing Immunity: Any computation on the output of a DP mechanism, without accessing the raw data, cannot weaken the DP guarantee. This allows for safe further analysis.

Two fundamental architectures for deploying differential privacy.

• Central Model (Trusted Curator): Raw data is sent to a trusted server, which applies a DP algorithm (like Laplace/Gaussian mechanisms) before releasing results. Provides higher accuracy for the same privacy budget but requires trust in the central entity.
• Local Model: Each individual perturbs their own data before sending it to the server (e.g., via Randomized Response). No trusted central party is needed, offering stronger privacy against the server itself, but requires significantly more noise per person, reducing aggregate accuracy.
• Hybrid Approaches: Systems like Federated Learning with DP often use a local model for device updates and a central model for secure aggregation.

In medical research, differential privacy enables analysis across sensitive patient records from multiple hospitals. Key applications include:

• Federated learning aggregates model updates from local institutions after applying DP noise, allowing collaborative training without sharing raw Electronic Health Records (EHRs).
• Releasing disease prevalence statistics or treatment outcome studies without revealing an individual's participation.
• Protecting queries on genomic datasets to study associations between genetic markers and diseases, mitigating membership inference attacks.

Differentially private stochastic gradient descent (DP-SGD) is a fundamental algorithm for training machine learning models with a provable privacy guarantee. During training, it:

1. Clips the gradient of each training example to bound its influence (sensitivity).
2. Adds Gaussian noise to the aggregated gradient before updating the model weights. This allows organizations to train models on sensitive data (e.g., financial transactions, personal messages) and publicly release the model, with a certificate that it does not memorize or leak specifics of its training data, defending against model inversion attacks.

Banks and fintech companies use differential privacy for internal risk analysis and secure data sharing.

• Aggregate risk reporting: Analyzing patterns of fraudulent transactions across a network without revealing details of specific accounts or individuals.
• Secure multi-party computation can be combined with DP for privacy-preserving credit scoring models that use data from multiple institutions.
• Publishing synthetic financial datasets that maintain realistic statistical properties (e.g., correlations between income, location, and spending) for external research and model testing, derived from real data using DP mechanisms.

Differential privacy is a cornerstone for creating privacy-preserving synthetic datasets. A DP algorithm analyzes the real sensitive dataset and generates a new, artificial dataset that has similar statistical properties but contains no real individual records.

• The privacy-utility trade-off is managed by the epsilon parameter: lower epsilon yields stronger privacy but may reduce the statistical fidelity of the synthetic data.
• This synthetic data can then be used freely for software development, model training, and analytics, eliminating legal and ethical concerns about the original data. It is a key tool for complying with regulations like GDPR while enabling data collaboration.

Epsilon-delta privacy, denoted as (ε, δ)-differential privacy, is a relaxation of pure differential privacy. It allows a small, bounded probability δ (e.g., 10⁻⁵) of a privacy violation, providing a more flexible privacy-utility trade-off for complex analyses like training deep neural networks. This formulation is essential for mechanisms like the Gaussian mechanism, which adds calibrated Gaussian noise.

• Key Use: Enables analysis of high-dimensional queries where pure DP would require excessive noise.
• Formal Guarantee: The algorithm is ε-differentially private with probability at least (1 - δ).

These are the core noise-adding algorithms for achieving differential privacy on numerical queries.

• Laplace Mechanism: Achieves pure ε-differential privacy. Adds noise drawn from a Laplace distribution, scaled by the query's sensitivity divided by ε. Ideal for counts, sums, and histograms.
• Gaussian Mechanism: Achieves (ε, δ)-differential privacy. Adds noise from a Gaussian (normal) distribution. The noise scale depends on sensitivity, ε, and δ. More suitable for complex, iterative algorithms like SGD.

Both mechanisms mathematically calibrate noise to mask the contribution of any single individual.

These are syntactic privacy models for de-identified datasets, contrasting with differential privacy's statistical guarantee.

• k-Anonymity: Ensures each record is indistinguishable from at least k-1 others on quasi-identifiers (e.g., ZIP, age, gender). Achieved via generalization and suppression.
• l-Diversity: Strengthens k-anonymity by requiring each group to have at least l "well-represented" values for sensitive attributes, mitigating attribute disclosure.
• t-Closeness: Further requires the distribution of a sensitive attribute within any group to be within distance t of its overall population distribution.

Limitation: These models are vulnerable to composition attacks and do not provide robust mathematical guarantees against an adversary with auxiliary information.

Homomorphic encryption is a cryptographic technique that allows computations to be performed directly on encrypted data. A server can execute an operation (e.g., addition, multiplication) on ciphertexts, producing an encrypted result that, when decrypted, matches the result of the operation on the plaintexts.

• Relation to DP: HE provides confidentiality during computation, while DP provides privacy in the output. They are complementary: HE can protect data during processing, and DP can be applied to the decrypted results before release.
• Use Case: Enables privacy-preserving machine learning where a model is trained on encrypted client data without the server ever decrypting it.

Federated learning is a decentralized training paradigm where a global model is learned across multiple devices or servers (clients) holding local data. Clients compute model updates on their local data and send only these updates (e.g., gradients) to a central server for aggregation, rather than the raw data itself.

• Privacy Synergy with DP: FL provides a form of data minimization. To further protect the updates, Differential Privacy can be applied by adding noise to the gradients before they are sent (DP-FL), providing a formal guarantee against reconstruction attacks.
• Key Challenge: Managing the privacy-utility trade-off across heterogeneous, non-IID (Independent and Identically Distributed) client data.

The privacy-utility trade-off is the fundamental tension in all privacy-preserving data analysis. Increasing privacy protection (e.g., by adding more noise in a DP mechanism) inherently reduces the accuracy, fidelity, or utility of the released data, model, or analysis.

• Quantification in DP: Governed by the epsilon (ε) parameter. A smaller ε means stronger privacy but noisier outputs (lower utility). A larger ε means weaker privacy but more accurate outputs (higher utility).
• Engineering Consideration: This trade-off is not a bug but a feature, requiring explicit, quantified decisions. System designers must choose an acceptable epsilon based on the sensitivity of the data and the required accuracy for the downstream task.