Differential Privacy

The privacy budget (epsilon, ε) is a non-negative parameter that quantifies the maximum privacy loss permitted across all queries or training iterations. A smaller ε provides stronger privacy guarantees but introduces more noise.

• ε = 0: Perfect privacy, but zero utility—output is pure noise
• ε = 0.1–1.0: Strong privacy, suitable for highly sensitive data
• ε = 1.0–10: Moderate privacy, common in practical deployments
• ε > 10: Weak privacy guarantees, approaching non-private analysis

The budget is consumed cumulatively. Each query or training epoch draws from this finite resource, and once exhausted, no further analysis is permitted without risking re-identification.

When multiple differentially private mechanisms are applied to the same dataset, their privacy losses sum together. If mechanism M₁ provides ε₁-differential privacy and M₂ provides ε₂-differential privacy, the combined release satisfies (ε₁ + ε₂)-differential privacy.

This property is critical for privacy accounting in iterative algorithms like stochastic gradient descent, where each training step consumes a portion of the total budget. Privacy accountants track cumulative spend to ensure the overall ε bound is never exceeded.

• Enables decomposition of complex analyses into simpler private building blocks
• Requires careful budgeting across entire model training lifecycles
• Violations occur if the total ε exceeds the pre-defined threshold

When differentially private mechanisms operate on disjoint subsets of the data, the total privacy loss equals the maximum of the individual losses, not their sum. If a dataset is partitioned into non-overlapping groups and each group is queried with ε-differential privacy, the overall release remains ε-differentially private.

This property is essential for:

• Federated learning, where each client's local data forms a disjoint partition
• User-level privacy, where each individual's records are isolated
• Scalable privacy accounting across distributed systems

Parallel composition enables privacy-preserving computations to scale without linear degradation of the privacy guarantee.

Any computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. Once noise has been injected to satisfy ε-differential privacy, no subsequent analysis, transformation, or machine learning model trained on that output can reverse the privacy protection.

This property is fundamental because it:

• Prevents adversarial post-processing: Attackers cannot "un-noise" the output
• Enables safe sharing: Sanitized outputs can be published, visualized, or used in downstream models without additional privacy risk
• Decouples privacy from utility: Data analysts can freely process private outputs without consulting privacy experts

Post-processing immunity ensures that privacy is a one-way ratchet—it can only improve, never degrade.

Differential privacy naturally extends to protect groups of correlated individuals. If a mechanism provides ε-differential privacy for a single record, it provides (k × ε)-differential privacy for any group of size k.

This property addresses scenarios where:

• Multiple records belong to the same individual (user-level privacy)
• Family members or households share correlated data
• Adversaries possess auxiliary information linking multiple records

To achieve strong group privacy, the per-record ε must be scaled down proportionally. For example, protecting groups of 10 with ε=1 requires each individual record to be protected with ε=0.1.

The formal guarantee of differential privacy is expressed through the privacy loss random variable, which measures how much an adversary's belief about any individual changes after observing the output. For any two neighboring datasets differing by one record, the ratio of output probabilities must be bounded by e^ε.

This is formalized as:

• Pure ε-differential privacy: Pr[M(D) ∈ S] ≤ e^ε × Pr[M(D') ∈ S]
• (ε, δ)-approximate differential privacy: Adds a small failure probability δ, allowing for tighter utility with Gaussian noise mechanisms

The privacy loss random variable enables precise composition accounting and is the foundation for advanced techniques like Rényi differential privacy and zero-concentrated differential privacy.

A finite, quantifiable resource representing the total allowable privacy loss (epsilon) in a differentially private system. Each query or training epoch consumes a portion of this budget. Once the budget is exhausted, no further queries can be answered without risking re-identification. Epsilon values typically range from 0.1 (very private) to 10 (loose guarantees).

• Composition: Privacy loss accumulates additively across queries
• Accounting: Systems must track cumulative epsilon expenditure
• Exhaustion: Budget depletion triggers query denial or data access revocation

A decentralized machine learning technique where a shared global model is trained across multiple edge devices or servers holding local data samples. Only model weight updates—not raw data—are exchanged with a central aggregation server. When combined with differential privacy, federated learning provides local differential privacy guarantees.

• Cross-device FL: Thousands of mobile devices training a shared model
• Cross-silo FL: A small number of organizational data silos collaborating
• DP-FedAvg: The standard algorithm combining federated averaging with Gaussian noise injection

A cryptographic scheme enabling computation directly on ciphertext, producing an encrypted result that, when decrypted, matches the output of operations performed on the plaintext. This allows models to train or infer on encrypted data without ever exposing the underlying records.

• Partially Homomorphic (PHE): Supports only addition or multiplication
• Somewhat Homomorphic (SHE): Supports limited operations before noise overwhelms the signal
• Fully Homomorphic (FHE): Supports arbitrary computation on ciphertext, though with significant computational overhead

A data anonymization property ensuring each released record is indistinguishable from at least k-1 other records with respect to quasi-identifiers (attributes like ZIP code, age, or gender that can be linked to external datasets). This prevents linkage attacks where an adversary cross-references anonymized data with public records.

• k=5: Each record is identical to at least 4 others on quasi-identifiers
• Limitations: Vulnerable to homogeneity and background knowledge attacks
• L-diversity and t-closeness: Extensions addressing k-anonymity's shortcomings

The process of creating artificial datasets using generative models—such as GANs, VAEs, or diffusion models—that retain the statistical properties and structure of real data without containing actual individual records. When trained with differential privacy guarantees, synthetic data provides a mathematically provable privacy shield.

• DP-GAN: A GAN trained with differentially private stochastic gradient descent
• Utility-Privacy Trade-off: Higher privacy (lower epsilon) reduces synthetic data fidelity
• Outlier Preservation: A key challenge; DP noise can erase rare but important patterns

A cryptographic protocol that distributes a computation across multiple parties where no single party can see the others' private inputs. This enables collaborative AI training or inference without exposing raw data to any participant. SMPC relies on secret sharing and garbled circuits.

• Input privacy: Each party's data remains hidden from all others
• Correctness: The output is guaranteed to match a trusted third-party computation
• Common frameworks: ABY3, MP-SPDZ, and CrypTen for machine learning workloads