Privacy & Fairness in ML • Differential PrivacyHard⏱️ ~2 min
Failure Modes and Edge Cases in Differential Privacy
Budget exhaustion and reconstruction attacks are the most common production failures. Releasing many correlated views of the same population without enforcing composition allows adversaries to combine outputs and reconstruct individual records. For example, publishing noisy counts for overlapping demographic slices (age groups, cities, income brackets) lets an attacker difference the results to infer membership of rare individuals. Always sum epsilons across all releases touching the same users and enforce a total budget cap.
Small cohorts and high dimensional queries spread epsilon thin. A histogram with 1,000 bins at total epsilon 1 allocates 0.001 per bin, yielding huge relative error. Sparse cross products like category combinations require tens of thousands of users to recover meaningful signals. Use hierarchical partitioning and heavy hitter discovery algorithms designed for DP, and apply minimum release thresholds to avoid publishing small noisy counts that leak information through differencing attacks.
Temporal correlation is often overlooked: repeated contributions by the same user over time reduce effective privacy if each time step is treated independently. A user contributing daily for a year consumes 365 times the per release epsilon, quickly exhausting budgets. Track longitudinal privacy loss and consider resetting budgets periodically (Apple resets daily for local DP telemetry) or limiting the number of time windows a user can influence. Mis estimated sensitivity, such as forgetting to clip sum contributions or using an incorrect bound, causes under noise and breaks the guarantee.
💡 Key Takeaways
•Reconstruction via correlated releases: publishing noisy counts for overlapping slices (age cross city cross income) allows differencing to infer individuals. Always enforce composition and sum epsilons across releases on the same population.
•High dimensional queries fail: 1,000 bin histogram at epsilon 1 gives 0.001 per bin, making most bins pure noise. Heavy hitter discovery needs tens of thousands of users. Use hierarchical methods and minimum thresholds of 1,000+.
•Temporal correlation drains budgets: daily contributions for a year consume 365 times per release epsilon. Apple resets local DP budgets daily. For central DP, limit time windows per user or use amortized budgets with periodic resets.
•Mis estimated sensitivity breaks privacy: forgetting to clip sum values to a bounded range makes sensitivity unbounded. For count queries, ensure each user contributes at most k times. Audit contribution bounding logic rigorously.
•Local DP adversaries can bias aggregates: malicious clients send crafted noisy reports. Mitigate with secure aggregation (server sees only encrypted sums), per device rate limits, and robust estimation with outlier rejection.
•Approximate DP pitfalls: setting delta too large (for example, 0.01 for a population of 10,000) risks catastrophic leakage. Keep delta negligible, typically 1e-5 or 1e-6, and document the choice with legal review.
📌 Examples
Reconstruction attack: release noisy counts for males age 30 to 40 in Seattle (count 10,005) and all age 30 to 40 in Seattle (count 10,012). Difference reveals 7 non male individuals, violating privacy if noise is small.
High dimensional failure: cross product of 10 categories with 100 values each yields 1,000 bins. At epsilon 1 total, each bin gets epsilon 0.001 and noise dominates signal unless true counts exceed 10,000.
Temporal budget exhaustion: user contributes 1 event per day for 365 days. If each day consumes epsilon 0.1, total is epsilon 36.5, far exceeding typical budgets of 1 to 10. Enforce contribution caps or reset budgets.