Differential Privacy (DP)

ε-Differential Privacy is the original, strongest definition. It provides a worst-case, multiplicative bound on how much the probability of any output can change if a single individual's data is added or removed from the dataset.

• Formal Guarantee: For all neighboring datasets D and D' differing by one record, and for all outputs S, Pr[M(D) ∈ S] ≤ e^ε * Pr[M(D') ∈ S].
• Interpretation: The parameter ε (epsilon) is the privacy budget. A smaller ε (e.g., 0.1) offers stronger privacy but noisier results. ε=0 offers perfect privacy but useless outputs.
• Example: The Laplace Mechanism achieves ε-DP by adding noise scaled to Δf/ε, where Δf is the function's sensitivity.

(ε, δ)-Differential Privacy is a relaxation of pure DP that allows a small additive probability δ of the privacy guarantee failing. This enables more efficient mechanisms for complex operations like training deep neural networks.

• Formal Guarantee: Pr[M(D) ∈ S] ≤ e^ε * Pr[M(D') ∈ S] + δ.
• Interpretation: The δ parameter represents a tiny, acceptable probability of a catastrophic privacy failure (e.g., δ < 1/n, where n is the dataset size). It is often interpreted as the probability that pure ε-DP is broken.
• Primary Use Case: The Gaussian Mechanism achieves (ε, δ)-DP and is the foundation for DP-SGD, as Gaussian noise has better analytical properties for iterative algorithms.

The privacy loss is a random variable that quantifies the actual log-ratio of probabilities for a specific output. The privacy budget ε is a worst-case bound on this loss.

• Composition: A core property is sequential composition. If mechanism M1 is ε1-DP and M2 is ε2-DP, then releasing both results satisfies (ε1+ε2)-DP. This allows tracking a cumulative budget across multiple queries.
• Advanced Composition: Tighter bounds exist for (ε, δ)-DP, allowing for sub-linear growth in ε over many compositions (e.g., k compositions of (ε, δ)-DP mechanisms yields roughly (ε√k, kδ)-DP).
• Budget Management: Systems must track and exhaust the total allowable budget ε_total for an analysis, after which no further queries can be answered without violating the guarantee.

A fundamental and powerful property: Any function applied to the output of a differentially private mechanism cannot weaken its privacy guarantee.

• Formal Statement: If M satisfies (ε, δ)-DP and g is any arbitrary, data-independent function, then g(M(D)) also satisfies (ε, δ)-DP.
• Implication for ML: A model trained with DP-SGD is itself a differentially private output. Therefore, any use of that model—making predictions, generating features, or even publishing its weights—does not consume additional privacy budget. The privacy cost is incurred once during training.
• Critical Distinction: This only holds if the post-processing function does not access the raw data again. Fine-tuning the model with the same data would be a new query and require more budget.

Differential Privacy gracefully extends its guarantee to protect small groups of individuals, with the protection weakening linearly with group size.

• Group Privacy: If a mechanism is ε-DP for datasets differing by one record, it is kε-DP for datasets differing by k records. This formalizes the intuition that protecting large conspiracies is impossible.
• Global Sensitivity (Δf): This is the maximum possible change in a function's output when one record is altered: Δf = max ||f(D) - f(D')|| for all neighboring D, D'. It is a property of the function, not the data.
• Role in Mechanisms: The amount of noise added (e.g., Laplace noise scale = Δf/ε) is directly proportional to global sensitivity. Designing low-sensitivity queries is key to achieving utility under DP.

These are the two primary models for deploying differential privacy, differing in where noise is added and who is trusted.

• Local Model: Each individual adds DP noise to their own data before sending it to an untrusted curator. Stronger privacy (trusts no one) but requires much more noise per person, leading to poor utility for complex statistics. Used in Google's RAPPOR for crowd-sourced statistics.
• Central Model: A trusted curator holds the raw dataset and applies a DP mechanism before releasing results. Far better utility for the same ε, as noise is added once to the aggregate. This is the standard model for DP-SGD and federated learning with secure aggregation.
• Federated Context: Federated learning with DP often uses a hybrid: clients add some noise locally (for privacy against the server), and the server may add more after secure aggregation.

Before model training, organizations often need to understand their decentralized data landscape. DP enables Federated Analytics for private population statistics.

• Private histograms: Learn the distribution of app usage or feature values across users without seeing individual records.
• Private sums & averages: Calculate aggregate metrics like total revenue or average sensor reading with a provable privacy budget. This is foundational for data exploration and quality checks in privacy-sensitive domains like healthcare and finance, where raw data cannot leave its source.

DP mechanisms can be used to generate high-fidelity synthetic datasets that preserve the statistical properties of the original sensitive data while providing formal privacy guarantees.

• A DP algorithm analyzes the real dataset and produces a new, artificially generated dataset.
• Machine learning models can then be trained directly on this synthetic data, bypassing privacy concerns. This is crucial for software testing, model development, and data sharing in regulated industries, as it eliminates the legal risk of holding real personal information.

Selecting the best model configuration (hyperparameters) requires evaluating multiple candidate models, which can leak information. DP Hyperparameter Tuning frameworks address this by:

• Treating the entire tuning process (multiple training runs) as a single DP computation.
• Allocating portions of the total privacy budget (epsilon) to each training round or evaluation.
• Using DP mechanisms to select the best-performing configuration. This ensures the final chosen model and its performance metrics do not reveal undue information about individuals in the training set.

For models that learn continuously from streaming data (e.g., recommendation systems), a one-time privacy guarantee is insufficient. DP for Online/Continual Learning employs:

• Privacy budget accounting across time: Techniques like the moments accountant track cumulative privacy loss (epsilon) over many sequential updates.
• Composition theorems: Rigorously combine the privacy cost of each learning step. This allows systems to promise a total lifetime privacy guarantee (e.g., epsilon=2.0 over one year of updates), enabling trustworthy long-term adaptation without retraining from scratch.

In Vertical Federated Learning, different organizations hold different features for the same users (e.g., a bank has credit history, a retailer has purchase history). DP secures the initial critical step: Private Set Intersection (PSI).

• DP-enhanced PSI protocols allow parties to securely discover their common users without revealing users unique to one party.
• The size of the intersection itself can be revealed with DP noise, preventing inference about specific unmatched individuals. This privacy-preserving alignment is essential for launching compliant cross-industry collaborative training without a trusted third party.

A decentralized machine learning paradigm where a shared global model is collaboratively trained across multiple client devices or servers holding local data samples, without exchanging the raw data itself. Clients compute updates on their local data and send only model parameters (e.g., gradients or weights) to a central server for secure aggregation.

• Core Principle: Keep raw data on-device; share only model insights.
• Use Case: Training a next-word prediction model across millions of smartphones without accessing personal messages.
• Key Challenge: Managing statistical heterogeneity (Non-IID Data) and communication costs.

A form of cryptography that allows computations to be performed directly on encrypted data. The encrypted result, when decrypted, matches the result of operations performed on the plaintext. In privacy-preserving ML, HE enables a server to perform aggregation on encrypted model updates from clients.

• Functionality: Enables Encrypt(A) + Encrypt(B) = Encrypt(A+B).
• Trade-off: Provides strong confidentiality but introduces significant computational overhead compared to DP.
• Common Use: Securely combining financial data from multiple banks for a joint credit risk model.

A cryptographic protocol that enables multiple parties to jointly compute a function over their private inputs while revealing nothing beyond the final output. Unlike HE, which often involves a single computational party, MPC is inherently distributed.

• Key Property: No single party sees another's raw input; only the final aggregated result is revealed.
• Application in FL: Used to build Secure Aggregation protocols, where a server learns the sum of client updates but not any individual contribution.
• Example: Three hospitals compute the average patient treatment outcome without sharing individual patient records.

The foundational algorithm for training machine learning models with differential privacy guarantees. It modifies standard Stochastic Gradient Descent by:

1. Clipping the influence (gradient) of each individual training example.
2. Adding calibrated noise (typically Gaussian) to the aggregated gradient before the model update step.

• Privacy Budget: The amount of noise added is controlled by parameters epsilon (ε) and delta (δ), which constitute the privacy budget.
• Ubiquitous Use: The standard method for applying DP in federated learning on the client side before sending updates to the server.

A secure, isolated area within a main processor (e.g., Intel SGX, ARM TrustZone) that guarantees confidentiality and integrity for code and data loaded inside. It acts as a 'black box' for computation.

• Hardware-Based Security: Protects data even from the host operating system or cloud provider.
• Use in FL: Clients or a server can perform model aggregation inside a TEE, ensuring updates are decrypted and processed only within this secure enclave.
• Advantage vs. Crypto: Often faster than pure cryptographic methods like HE but requires specific hardware support.

The property of a distributed system (like a federated learning server) to tolerate a fraction of participants that may behave arbitrarily or maliciously—known as Byzantine faults—without corrupting the global model outcome.

• Threat Model: Defends against Poisoning Attacks, where malicious clients submit crafted updates to degrade model performance or insert backdoors.
• Robust Aggregation: Algorithms must go beyond simple averaging (FedAvg) to use techniques like coordinate-wise median, trimmed mean, or Krum to filter out anomalous updates.
• Critical Need: Essential for open participation federated learning scenarios (Cross-Device FL) where device security cannot be guaranteed.