Sharp privacy budget limit for protecting training data revealed
A Sharp Transition in Data Reconstruction under Differential Privacy
Machine LearningArtificial Intelligence
Summary
This paper looks at how much privacy protection is needed to stop attackers from uncovering individual training data used to build a model. The authors found a clear tipping point in privacy settings: too weak, and attackers can reconstruct data; strong enough, and it becomes practically impossible. They also discovered this tipping point depends on the data's effective dimensionality, not just the raw size. Their experiments with synthetic and real images confirm these findings.
What this means in practice
- •For privacy engineers: Set effective privacy budget levels tailored to the data dimension to prevent data reconstruction attacks in machine learning models.
- •For machine learning system builders: Design private linear regression systems with informed privacy parameters that balance data protection and model utility based on data complexity.
Authors
Max Cairney-Leeming, Simone Bombari, Marco Mondelli
Abstract
Data reconstruction attacks have empirically been successful in recovering training samples from learned models, raising privacy concerns and motivating defenses with guarantees that remain valid against future threats. While differential privacy (DP) provides formal protection, choosing the privacy budget remains a challenge: small budgets severely reduce utility, but it is hard to quantify how large the budget can be without allowing accurate reconstruction. In this work, we study informed attackers who aim to reconstruct a single $d$-dimensional training sample from a $ρ$-zero-concentrated DP model, knowing all other training data. Our main contribution is to establish a sharp transition at $ρ\asymp d$ for data reconstruction: on the one hand, we derive entropy-based lower bounds for any private mechanism and any attack, characterizing a set of target priors for which reconstruction is information-theoretically impossible for $ρ\ll d$; on the other hand, we analyze a simple attack on private linear regression with output perturbation, showing that reconstruction is practically feasible for $ρ\gg d$. Remarkably, the transition moves to $ρ\asymp s$ for data lying in an $s$-dimensional subspace, demonstrating that the privacy budget guaranteeing adequate protection must be assessed in terms of the effective dimension of the data. We validate our findings via experiments on synthetic data and natural images (CIFAR-10, ImageNet).