Differential Privacy

ε-Differential Privacy is the core definition, providing a worst-case, quantifiable bound on privacy loss. A randomized algorithm M satisfies ε-DP if, for all neighboring datasets D and D' (differing by one record) and all possible outputs S, the probability of any output changes by at most a multiplicative factor of exp(ε).

• Formal Guarantee: Pr[M(D) ∈ S] ≤ exp(ε) * Pr[M(D') ∈ S]
• Interpretation: ε is the privacy budget or privacy loss parameter. A smaller ε (e.g., 0.1) implies stronger privacy, as the output distributions are nearly indistinguishable. An ε of 0 provides perfect privacy but typically renders outputs useless.
• Worst-Case Nature: The guarantee holds for the worst-case record and the worst-case output, making it extremely robust against strong adversaries.

(ε, δ)-Differential Privacy is a relaxed, more practical variant of the pure definition. It allows for a small, additive probability δ where the pure ε guarantee can fail.

• Formal Guarantee: Pr[M(D) ∈ S] ≤ exp(ε) * Pr[M(D') ∈ S] + δ
• Interpretation: The parameter δ represents a probability of catastrophic failure. For example, δ = 10^-5 means there is a 1 in 100,000 chance that the algorithm's output could reveal complete information about an individual. δ must be cryptographically small (substantially less than 1/n, where n is the dataset size).
• Utility Benefit: This relaxation often enables the addition of less noise (e.g., using the Gaussian mechanism instead of the Laplace mechanism), significantly improving the utility of query answers while maintaining a strong, meaningful privacy guarantee.

The Post-Processing Immunity property states that any function applied to the output of a differentially private algorithm cannot weaken its privacy guarantee.

• Core Principle: If M satisfies (ε, δ)-DP, then for any arbitrary deterministic or randomized function f (that does not re-examine the original raw data), the composed algorithm f(M(D)) also satisfies (ε, δ)-DP.
• Practical Implication: This allows for safe downstream analysis. Analysts can freely manipulate, transform, or visualize the private output without needing additional privacy budget. For example, rounding numbers, creating aggregates of aggregates, or using the output as features in another model are all safe operations.
• Security Benefit: It simplifies system design and auditing, as privacy guarantees are preserved through entire data pipelines after the initial private release.

The Sequential Composition theorem provides a rule for calculating the total privacy cost when multiple differentially private analyses are performed on the same dataset.

• Basic Rule: If mechanism M1 satisfies (ε1, δ1)-DP and M2 satisfies (ε2, δ2)-DP, then releasing the results of both on the same dataset satisfies (ε1+ε2, δ1+δ2)-DP.
• Advanced Composition: More sophisticated composition theorems (like Advanced Composition) often provide tighter bounds, especially for many queries. They show that the ε parameter grows roughly with the square root of the number of queries for a fixed δ.
• Budget Management: This property is the foundation for privacy budget accounting. Systems like Google's RAPPOR or the US Census Bureau's TopDown algorithm track a cumulative ε and δ as queries are answered, halting when a pre-defined total budget is exhausted to prevent privacy degradation.

The Parallel Composition theorem states that applying differentially private mechanisms to disjoint subsets of a dataset consumes less privacy budget than sequential composition.

• Core Rule: If a dataset is partitioned into disjoint subsets (D1, D2, ... Dk), and a mechanism Mi satisfying (ε, δ)-DP is applied to subset Di, then the overall release of all outputs satisfies (ε, δ)-DP.
• Key Insight: Privacy loss is incurred per individual's data. If mechanisms operate on data of disjoint sets of individuals, their privacy losses do not add up.
• System Design Impact: This enables highly efficient private analytics. For example, computing a histogram where each bin count is based on a different group of people (e.g., counts per state) can be done with a per-bin ε cost, not a summed cost. This is fundamental to the design of algorithms for private histogram release.

Group Privacy describes how the privacy guarantee degrades when considering datasets that differ by k records instead of a single record.

• Formal Degradation: If an algorithm M satisfies ε-DP, then for datasets D and D' differing by at most k records, the guarantee becomes: Pr[M(D) ∈ S] ≤ exp(k * ε) * Pr[M(D') ∈ S]. For (ε, δ)-DP, the degradation is more complex but follows a similar linear scaling in k for ε.
• Implication: The privacy guarantee protects individuals, but the protection for a correlated group (like a household) weakens linearly with group size. This is not a flaw but a mathematical feature, highlighting that protecting all correlations within a large group perfectly is impossible while providing utility.
• Design Consideration: This property informs the definition of "neighboring datasets." For data with strong correlations (e.g., genetic databases), defining neighbors as the addition/removal of a small family might be more appropriate, requiring a correspondingly smaller base ε to achieve the desired group-level protection.

A privacy attack against a machine learning model that aims to determine whether a specific data record was part of the model's training set.

• Attack Vector: The adversary, typically with query access to the model, analyzes the model's predictions (e.g., confidence scores) on a target record. Records the model was trained on often exhibit different prediction behavior.
• Privacy Risk: Reveals that an individual's sensitive data was used for training, which can be a breach of confidentiality in regulated domains like healthcare.
• DP as a Defense: Differential privacy is a provable defense against membership inference attacks. The formal (ε, δ)-guarantee bounds the probability that an attacker can correctly infer membership, making the model's output statistically indistinguishable whether any single record was included or not.

A property of a published dataset stating that 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).

• Key Mechanism: Achieved through generalization (e.g., replacing exact age with an age range) and suppression (removing rare data points).
• Limitation: Protects against re-identification when linked with external datasets but does not protect the sensitive attributes (e.g., medical diagnosis) within the anonymized group. Vulnerable to homogeneity attacks if all k individuals share the same sensitive attribute.
• Contrast with DP: k-Anonymity is a syntactic property of the dataset. Differential privacy is a semantic, output-centric guarantee about the information leakage from a computation, providing stronger protection against a wider class of attacks, including those using auxiliary information.