Epsilon-Differential Privacy (ε-DP)

The parameter ε (epsilon) quantifies the privacy loss budget—the maximum distance between the output distributions of a mechanism run on two neighboring datasets. A smaller ε provides stronger privacy.

• ε = 0: Perfect privacy; outputs are identical regardless of any individual's presence.
• ε = 0.1 to 1: Strong privacy; typical for academic benchmarks and high-sensitivity data.
• ε = 1 to 10: Moderate privacy; common in industry deployments balancing utility.
• ε > 10: Weak privacy; often insufficient for formal protection against determined adversaries.

The guarantee is multiplicative: the probability of any output event can increase by at most a factor of e^ε when a single record is added or removed.

When multiple differentially private mechanisms are applied to the same dataset, the total privacy loss accumulates additively. If mechanism M₁ is ε₁-DP and M₂ is ε₂-DP, their sequential application is (ε₁ + ε₂)-DP.

This is the foundation of the privacy budget: an analyst is allocated a total ε, and each query consumes a portion of it. Once the budget is exhausted, no further queries are permitted on that dataset.

• Example: Running three separate queries, each with ε = 0.5, consumes a total budget of ε = 1.5.
• Advanced composition theorems provide tighter bounds for (ε, δ)-DP, showing that privacy loss grows sublinearly with the number of queries under Gaussian noise.

When differentially private mechanisms are applied to disjoint subsets of the data, the total privacy cost is the maximum of the individual ε values, not their sum.

This property enables efficient use of the privacy budget in horizontally partitioned systems. If a dataset is split into non-overlapping partitions and a mechanism is run independently on each, the overall guarantee remains bounded by the worst-case mechanism.

• Example: Running an ε = 0.5 query on each of 10 disjoint user groups still yields an overall ε = 0.5 guarantee.
• This is critical for federated learning and distributed analytics, where data is naturally partitioned across silos or devices.

Any arbitrary computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. Once noise has been injected to satisfy ε-DP, no adversary—regardless of computational power or auxiliary information—can reverse that protection.

This property is unique to differential privacy and does not hold for ad-hoc anonymization techniques like k-anonymity or data masking.

• Implication: Safe to publish, visualize, or feed DP outputs into downstream machine learning models without additional privacy risk.
• Example: A DP-trained model's weights can be shared publicly; an adversary cannot infer training data membership beyond the ε guarantee, even with full white-box access to the model.

ε-DP naturally extends to protect groups of correlated records. If a mechanism is ε-DP for a single record, it is (k·ε)-DP for any group of size k.

This addresses scenarios where an adversary targets a family, a household, or multiple records belonging to the same individual. The privacy loss scales linearly with group size.

• Example: A mechanism with ε = 0.1 for individuals provides ε = 1.0 protection for a group of 10 correlated records.
• User-level privacy is a special case where k equals the maximum number of records per user, ensuring the entire user contribution is protected.

The ε-DP guarantee holds regardless of what side information an adversary possesses. Even if an attacker knows every other record in the dataset except the target's, they cannot confidently determine whether that target's record was included.

This is formalized through the adversary's prior-to-posterior belief ratio, which is bounded by e^ε. No amount of external data—public records, social media, or other databases—can break the mathematical guarantee.

• Contrast: k-anonymity and l-diversity fail catastrophically when linked with external datasets.
• Real-world implication: DP protects against linkage attacks using voter registration, hospital discharge data, or any other auxiliary source.