Differential Privacy

The privacy loss parameter (epsilon, ε) quantifies the maximum allowable difference in the probability of any output when a single individual's data is included or excluded from the dataset. A smaller ε provides stronger privacy but typically reduces the accuracy or utility of the output.

• Definition: An algorithm A is ε-differentially private if for all datasets D and D' differing by at most one element, and for all subsets S of outputs: Pr[A(D) ∈ S] ≤ e^ε * Pr[A(D') ∈ S].
• Interpretation: An ε of 0.1 or 1.0 is common for strong privacy. Values like 10 provide weaker guarantees but higher data utility.
• Role: This is the core mathematical bound that makes the privacy guarantee composable and immune to auxiliary information attacks.

A fundamental property stating that any function applied to the output of a differentially private algorithm remains differentially private. No further analysis of the released result can weaken the original privacy guarantee.

• Implication: Analysts can freely manipulate, combine, or visualize the private output without risk of additional privacy leakage.
• Example: If a private statistical release shows average income by zip code, creating a chart or calculating a derived metric (like regional totals) from that release does not compromise the initial ε guarantee.
• Significance: This enables safe downstream data analysis and sharing, as the privacy guarantee is robust to arbitrary subsequent computation.

These theorems provide rules for calculating the cumulative privacy loss when multiple differentially private analyses are performed on the same dataset. They are essential for designing complex, multi-query systems.

• Sequential Composition: Running k ε-differentially private algorithms results in a total privacy loss of the sum of their epsilons (kε).
• Advanced Composition: Offers tighter bounds, showing that the privacy loss grows roughly with the square root of the number of queries for a fixed total ε.
• Parallel Composition: If analyses are performed on disjoint subsets of the data, the overall privacy loss is only the maximum ε used, not the sum.
• Practical Use: These rules allow privacy budgets (ε) to be allocated and tracked across an entire analytics pipeline or research study.

Differential privacy's guarantee naturally extends to protect small groups. If an algorithm is ε-differentially private for individuals, it provides kε-differential privacy for groups of size k.

• Mechanism: The definition protects datasets differing by one record. By applying the definition repeatedly, the privacy loss for a group scales linearly with group size.
• Limitation: This linear scaling means the guarantee weakens for very large groups. It is designed primarily for individual privacy.
• Example: In a medical study, the inclusion or exclusion of a family of 5 would have a privacy parameter of 5ε, assuming the original algorithm had parameter ε for a single patient.

The privacy guarantee holds regardless of any other information an adversary might possess. This is a critical strength, as it assumes the worst-case scenario where an attacker has unlimited background knowledge.

• Principle: The mathematical definition does not model or make assumptions about an attacker's prior knowledge. The guarantee is about the additional risk from participating in the dataset.
• Contrast: This makes it stronger than older anonymization techniques (like k-anonymity), which can be broken if an attacker combines the released data with external information.
• Consequence: Even if an attacker knows 99% of the dataset, differential privacy still rigorously bounds what can be learned about the remaining 1%.

The core engineering challenge in differential privacy is managing the inherent tension between strong privacy (low ε) and high data utility (accurate results). Noise added for privacy introduces error into outputs.

• Noise Mechanisms: The two primary methods are the Laplace mechanism (for numeric queries) and the Exponential mechanism (for non-numeric selection). The scale of the noise is inversely proportional to ε and the query's sensitivity.
• Sensitivity: A query's global sensitivity measures the maximum possible change in its output when a single data point is altered. Higher sensitivity requires more noise for the same ε.
• Optimization: Techniques like query strategy planning, privacy budget allocation, and using lower-sensitivity algorithms are used to maximize utility for a fixed privacy budget.

The process of creating artificial datasets that mimic the statistical properties and relationships of a real dataset without containing any actual real-world records. It is used for model training, testing, and sharing.

• Key Mechanism: Uses generative models like Generative Adversarial Networks (GANs) or Variational Autoencoders (VAEs).
• Primary Use Case: Bypassing data scarcity, enabling data sharing for research, and preserving privacy.
• Privacy Assurance: High-quality synthetic data should prevent membership inference attacks, meaning an attacker cannot determine if a specific individual's data was in the training set.

A property of a dataset where each record is indistinguishable from at least k-1 other records with respect to a set of quasi-identifiers (e.g., ZIP code, birth date, gender). It aims to prevent re-identification through linkage attacks.

• Key Mechanism: Generalization (reducing precision) and suppression (removing data) of quasi-identifier fields.
• Limitation: Vulnerable to homogeneity attacks (if all k records share the same sensitive attribute) and background knowledge attacks.
• Evolution: Considered a weaker guarantee than differential privacy, which provides a rigorous mathematical bound on privacy loss.