acceptodds
Under review as a conference paper at ICLR 2027

A Sharp Transition in Data Reconstruction under Differential Privacy

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 -dimensional training sample from a -zero-concentrated DP model, knowing all other training data. Our main contribution is to establish a sharp transition at 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 ; on the other hand, we analyze a simple attack on private linear regression with output perturbation, showing that reconstruction is practically feasible for . Remarkably, the transition moves to for data lying in an -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).

Primary area:
learning theory
Keywords:
differential privacy, data reconstruction, high-dimensional data, linear regression

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_RKWcOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work studies the relationship between differential privacy and data reconstruction attacks. It also bridges the gap on how to choose ρ\rho in this setting.

Critical strengths

The theorem made clear point about reconstruction attack with the ratio between dimensionality dd and privacy budget ρ\rho.

Critical weaknesses

The DP method is output perturbation on linear regression models, which is a simple setting and not the main stream of using DP to train ML models.

Questions for authors
  1. Does your analysis extend to training using DP-SGD style methods?
  2. Could you say more about why use Eq. (14) for data reconstruction? Is it optimal measured by normalized MSE?
  3. How do you precisely define reconstruction is impossible?
2 comments

We thank the reviewer for the positive evaluation of our work and for the useful comments. We reply below to all the points raised in the review, and we have uploaded a revision with changes marked in red color.


Weakness and Question 1: extension of the analysis to DP-GD

Thank you for pointing this out. Yes, our approach readily extends to DP-GD, and we included the statement as Theorem 3 in the revised main body, with the corresponding proof added to Appendix D of the revision. In particular, the same attack considered for output perturbation yields the same error upper bound of order d/ρd / \rho for a DP-GD algorithm. We also show evidence of this in the additional experiments in Figure 17, which displays the same qualitative trend as the one displayed in Figure 2 for output perturbation. This extension suggests the broader generality of our proposed transition.

Furthermore, we note that our proofs do not critically rely on the linear regression task, and we expect the same transition to hold in wider generality, e.g. for problems with convex losses, with a strong convexity condition in a neighborhood of the empirical minimizer (which seem to be the key qualitative properties enabling our analysis).


Question 2: optimality of the attack

We use Eq. (15) (numbering as in the revision) because it was motivated by the first-order optimality condition, which shows that F−(θ∗)F_{-}(\theta^{*}) is exactly parallel to the target xtx_t, and we evaluate at the released weights θ~\tilde{\theta} as this is the only available information to use. In general, we do not believe this attack to be optimal under normalized MSE, as the attacker might benefit from specific priors on the data distribution (as in Theorem 5 of the revision, where the attack also involves a projection on the subspace the attacker knows the data to be in). Despite this fact, in the settings of data with differential entropy h(x)≍dh(x) \asymp d, the attack in Theorem 2 has an error bound of d/ρd / \rho, which matches the threshold ρ≍d\rho \asymp d of Theorem 1.


Question 3: definition of impossibility

We define impossibility in terms of a lower bound on the expected reconstruction error (Theorem 1) or the expected reconstruction error up to sign and scale (Theorem 6). Informally, these theorems state that no attacker can estimate the target such that the error is much smaller than the norm of the target (which corresponds to the error of a trivial, all-0 estimator).

Thanks for you clarification, my concerns are addressed.

Reviewer_ArBzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper analyzes parameter regimes (ρ/d\rho/d) for which ρ\rho-zCDP protects or fails to protect against data reconstruction attacks on dd-dimensional models. They provide information-theoretic lower bounds on reconstruction error for a zCDP algorithm and an adversary that knows the algorithm, the hyperparameters, and n−1n-1 out of nn data points: reconstruction (with vanishing reconstruction error) is impossible when ρ≲d\rho \lesssim d. On the other hand, they construct a concrete attack (on zCDP regularized regression privatized via Gaussian output perturbation) with normalized reconstruction error ≲d/ρ\lesssim d/\rho.

Critical strengths

The problem is interesting and important. In particular, understanding what practical protection is provided by DP at relatively large privacy budget is an important question that has been studied extensively by many prior works from different angles (some of these are not cited by the current work, as discussed below). The paper gives a clean information-theoretic perspective on this question for reconstruction attacks and complements it with a concrete, theoretically analyzed reconstruction attack.

I find the attack result to be the more interesting contribution. Establishing an explicit O(d/ρ)O(d/\rho) reconstruction guarantee for output-perturbed regression is nontrivial. The extension to lower-dimensional data is also somwhat interesting. The paper is generally well written, and the experiments provide some support for the predicted dimensional scaling.

Critical weaknesses
  1. The claimed sharp transition is not established for a common notion of reconstruction error.

The main concern is that the information-theoretic lower bound and the constructive upper bound use different reconstruction metrics.

Theorem 1 lower bounds the expected squared reconstruction error E∣xt−x^t∣2,\mathbb E|x_t-\widehat x_t|^2, whereas Theorem 2 upper bounds min⁡τ∈[−1,1]∣xt−τx^t∣2.\min_{\tau\in[-1,1]}|x_t-\tau\widehat x_t|^2.

The latter is a substantially weaker reconstruction criterion, since it allows the reconstructed point to be rescaled and sign reversed. For example, in the linear regression setting considered here, replacing ((x_t,y_t)) with ((-x_t,-y_t)) leaves the Huberized regression objective unchanged. Under a symmetric data distribution, even an attacker with access to the exact nonprivate optimizer cannot distinguish these two possibilities.

Thus, the results appear to establish an impossibility (lower) bound for actual reconstruction and an upper bound for approximate direction recovery, rather than matching bounds for the same problem. While the latter result is interesting, I do not think it fully justifies the claimed "sharp transition" for data reconstruction as stated.

Relatedly, Appendix G.2 indicates that the image visualizations use the true target to resolve the sign ambiguity and recover the original normalization scale. Since this information is unavailable to the specified adversary, the experiments may overstate the quality of reconstruction achievable by the actual attack.

  1. The novelty of the information-theoretic lower bound is somewhat limited.

Balle et al. (2022), "Reconstructing Training Data with Informed Adversaries", already established that ρ=o(d)\rho=o(d) can prevent accurate reconstruction of high-dimensional examples under natural data distributions, including Gaussian and uniform priors. Their work also introduced a reconstruction approach based on the first-order optimality conditions of convex ERM.

Theorem 1 of the submitted paper provides a useful MSE formulation of the existing impossibility result, using the mutual-information guarantee implied by zCDP. However, the technical argument seems fairly straightforward, and the dimensional protection phenomenon itself is not novel.

Similarly, the proposed attack builds on the same first-order-optimality observation used by Balle et al. The main new technical contribution appears to be analyzing the effect of Gaussian output perturbation and obtaining the O(d/ρ)O(d/\rho) directional reconstruction bound. This is worthwhile, but the paper could be more precise about what is new relative to the prior literature.

  1. (Minor) Missing related work.

The related literature is vast. Many works investigate related questions around whether and why certain values of DP parameters prevent practical attacks. It would be valuable to position the present manuscript more cleanly in the context of these prior works with a more comprehensive related work discussion. Examples of missed related works include "More Granular Differential Privacy Guarantees" by Ghazi et al. and "Why Does Differential Privacy with Large ε Defend Against Practical Membership Inference Attacks?" by Lowy et al. to name a couple. See also works cited therein.

Questions for authors
  1. Can the authors establish matching lower and upper bounds under the same reconstruction-error metric? In particular, can the sign and scale ambiguities in Theorem 2 be resolved without additional knowledge of the target? If not, should the main result be characterized as a sharp transition for directional reconstruction rather than reconstruction of the original sample?

  2. How would the experimental reconstruction results change if the attacker had to determine the sign and scale without using the true target image?

  3. Beyond providing an MSE formulation, what is the main conceptual or technical improvement of Theorem 1 relative to the reconstruction-robustness bounds of Balle et al. (2022)?

5 comments

We thank the reviewer for the insightful comments. We reply to all the points raised in the review below, and we have uploaded a revision with changes marked in red color.


Question 1 and Weakness 1: discrepancy between lower and upper bound

We agree that there is a small discrepancy between the metrics of Theorem 1 and Theorem 2. We made this choice to improve readability, and as we originally commented (at lines 302-303 of the revision) it is possible to rewrite the lower bound in Theorem 1 to use the same metric as Theorem 2, keeping the same dependence on the dimension. In particular, whenever ρ≤h(xt’)\rho \leq h(x_t’), we have

E[min⁡τ∣∣xt−τx^∣∣22]E∣∣xt∣∣22≥18πe⋅12πeexp⁡(2d(h(xt′)−ρ)).\frac{ \mathbb E[\min_\tau || x_t - \tau\hat x ||_2^2] }{ \mathbb E||x_t||_2^2} \geq\frac{1}{8\pi e}\cdot\frac{1}{2\pi e} \exp\left(\frac{2}{d}\left(h(x_t')-\rho\right)\right).

We have now included the full argument to achieve this bound in Theorem 6 (as well as in Theorem 7 for the low-dimensional setting).

We note that the error up to sign and scale in the equation above describes the component of the target xtx_t orthogonal to the attacker's estimated direction. The mechanism reveals at most ρ\rho nats about xtx_t, so at least h(xt)−ρh(x_t) - \rho nats of uncertainty remain. The norm and sign of the target is a scalar with a bounded second moment, and so it has bounded entropy. The orthogonal (d−1)(d-1)-dimensional component therefore retains nearly all of the remaining uncertainty, and by our original rate-distortion argument, this forces a large expected error.

In practice, we expect the probability distribution of natural images not to be sign invariant, so it is “visually easy” to recognize a natural image or a negative image (see Figure 15 of the revision). Thus, if the attack results in a negative image, the attacker can easily figure this out and flip the sign a posteriori. We have included more visualisations without this post-processing (Figures 11,12 and 14 of the revision), which show the same behaviour as the original figures, with some clearly negative images of elephants in Figures 11 and 12.


Weakness 2 and Question 3: novelty with respect to Balle et al. (2022)

Balle et al. (2022) study the same reconstruction-under-privacy setting that we do, but with two key differences.

First, we provide matching upper and lower bounds for reconstruction error under DP, establishing the threshold scaling ρ≍d\rho \asymp d for the analyzed mechanisms (output perturbation and DP-GD). Their analysis of the attack success only concerns non-private models, which is a deterministic setting with a closed-form solution. DP introduces the challenges of studying clipping, noise addition, and early stopping (for DP-GD), and our analysis shows constructively how these quantitatively affect the quality of the reconstruction attack. This reveals the transition at ρ≍d\rho \asymp d and characterizes how reconstruction performance depends on the algorithm’s hyperparameters, both in Theorem 2 for output perturbation and Theorem 3 for DP-GD, which complements empirical observations of hyperparameter-dependent reconstruction performance from (Hayes et al., 2023; Kaissis et al., 2023). To the best of our knowledge, these tight results on the possibility of reconstruction from final private model parameters (for output perturbation and now DP-GD) have not appeared in prior work.

Secondly, our entropy-based formulation has advantages compared to the one based on small-ball probabilities appearing in Balle et al.’s bounds: entropy is a well established quantity with closed-form expressions for many distributions, providing an interpretable characterization of prior uncertainty on the target; our bound is tighter than the guarantees obtained from their bounds for several distributions, as shown in the revised Figure 1, now also including the multivariate Student-tt and mixtures with rare low-variance components.

AuthorsOpenReview ↗

(continued)

Question 2: how to determine the sign and scale of the target

As mentioned before, the attack results without sign information are shown in Figures 11 and 12 of the revision, which contain both natural images and their negatives (see, e.g., the elephants which are negative images). All these reconstructed images are such that the metric min⁡τ∈[−1,1]∣∣xt−τx^∣∣22\min_{\tau\in[-1,1]} || x_t-\tau\widehat{x}||_2^2 from Theorem 2 is sufficiently small. In practice, if an attacker is ultimately interested in minimizing ∣∣xt−x^∣∣22|| x_t - \widehat{x} ||_2^2, they can use their visual prior to identify negatives. For clarity, we note that the attacker never had access to the sign and scale of the target to produce x^\widehat{x}, and this was solely used in evaluation (e.g., the metric in Eq. (16) of Theorem 2) and visualisation.

Scale can also be addressed similarly, as we demonstrate in Figures 11,12 and 14 in the revision. Since the reconstruction's scale is unknown, we scale it by the largest factor that yields a valid RGB image (i.e. pixels within [0,1][0,1]) after adding back the public mean. An attacker can implement this without any target information, and these images are visually very similar to the originals (Figures 4,10 and 13).


Weakness 3: missing related work

We thank the reviewer for these references. We have added both, with a short discussion, to the "Large privacy budgets" paragraph of Section 2 of the revision.

For context, both papers study different and complementary problems: Ghazi et al. (2023) consider DP guarantees for changing only some attributes of a record. We instead work with standard privacy guarantees and reconstruction attacks of the whole record, not just some attributes.

Lowy et al. (2024) also argue that weaker privacy guarantees are still useful, from a different perspective, as they protect against a kind of membership inference attacks. This is a very different attack model to the one we study, and our guarantees also only depend on the target’s entropy instead of uncertainty about the rest of the dataset.

Both works, like Aerni et al. (2024) and Cyffers et al. (2025) which we already cite, support the view that a large budget need not mean weak protection against practical attacks. Our contribution to this line of research is to identify the threshold at which the budget becomes meaningful for reconstruction, ρ≲d\rho \lesssim d, and to show that this is sharp by establishing an attack that achieves it.

Dear Reviewer ArBZ,

While we would like to thank you again for your review, we would kindly appreciate your feedback on our rebuttal.

We would also like to point out that your original concerns substantially overlap with those of reviewer N3TV, who was satisfied with our response. Our revision also includes, as suggested, further discussion with related work and reconstruction analysis on a DP-GD trained model.

Reviewer_N3TVOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the relationship between differential privacy budgets and training-data reconstruction under a strong, informed-adversary model. The authors derive an entropy-based lower bound on reconstruction error for arbitrary zCDP mechanisms and analyze reconstruction attacks against private linear regression using output perturbation. Their results demonstrate that the effective privacy budget scales with the data dimension, or more specifically, with the dimension of the subspace containing the data.

Critical strengths
  1. The research topic is important.
  2. The presentation of the paper is clear.
Critical weaknesses
  1. My primary concern is the experimental settings do not fully match the theoretical assumptions. Theorem 2 relies on specific distributional assumptions, including Gaussian label noise. However, the image experiments use deterministic binary class labels. Furthermore, the theory's simplified scaling assumes the sample size is at least proportional to the dimension, whereas several experiments use substantially larger dimensions than sample sizes. The entropy-based lower bound assumes a continuous target distribution with finite differential entropy. This assumption also does not directly hold for the normalized image representations, which have a fixed norm. These differences limit how directly the experiments validate the claimed theoretical transition.

  2. The lower and upper bounds do not establish reconstruction under the same error metric: While Theorem 1 bounds the ordinary reconstruction MSE, Theorems 2 and 4 measure error after optimizing over a sign-and-scale factor. The latter is a weaker recovery objective. Such distinction is particularly important because the regression objective is invariant under simultaneously negating the target feature and label. For the symmetric synthetic data distribution, the true target's sign is not identifiable, even in the absence of privacy noise. Thus, the upper bound does not establish successful reconstruction of the original target in this setting.

  3. Another concern is the claimed sharp transition has limited generality. The impossibility result applies to arbitrary zCDP mechanisms, but the constructive result is restricted to Huber-based linear regression with output perturbation. This establishes a tight scaling for a particular mechanism and recovery objective, rather than a general transition across private learning algorithms. The techniques also build on established information-theoretic bounds and optimality-condition-based reconstruction attacks. I suggest give a clearer discussion of which technical insights go beyond prior work, particularly Balle et al. (2022).

Questions for authors
  • Can you provide an executable reconstruction procedure that resolves these ambiguities using only information available to the attacker? In particular, how can the sign ambiguity be resolved for the symmetric synthetic data distribution?
  • How sensitive is the observed transition to the learning algorithm and privacy mechanism? Would the same scaling be expected for DP-SGD or other common private learning procedures?
3 comments

We thank the reviewer for the helpful comments. We reply below to all the points raised in the review, and we have uploaded a revision with changes marked in red.


Weakness 1: experiments not fully matching theoretical assumptions

Thanks for pointing this out. We have run additional experiments with data sampled from a truncated Gaussian distribution so that ∥∣x∥∣2≤d\|| x \||_2 \leq\sqrt{d}, which has differential entropy h(x)=Θ(d)h(x) = \Theta(d), and d≤nd \leq n. In this way, the experimental setting fully matches the theoretical assumptions. The plots are displayed in Figure 7 of the revision, and we confirm that they have the same qualitative profile of Figure 2, which contains our original experiments on synthetic data.

Furthermore, we remark that our theoretical assumptions (such as n=Ω(d)n = \Omega(d) and z∼N(0,ζ2)z \sim \mathcal N(0, \zeta^2) to obtain the threshold in Eq. (17)) are chosen for technical convenience, to make the analysis simpler and the statements clearer, keeping the core message of our work. In fact, we expect the transition at ρ≍d\rho \asymp d to hold in wider generality, as demonstrated in Figure 2 for synthetic spherical data and Figures 3 and 4 for natural images with deterministic labels.

In the revision, we also have included a new Figure 8 where we perform the same experiments on non-rescaled images, which yields in the same qualitative results as the original experiments on rescaled images in Figure 3. To conclude, we remark that our theoretical results framed in terms of differential entropy can be adapted to rescaled (degenerate) data, as done in Theorem 4 of the revision for the case of data lying on a lower dimensional subspace.


Weakness 2: lower bound and upper bounds do not use the same metric

We agree that there is a small discrepancy between the metrics of Theorem 1 and Theorem 2. We made this choice to improve readability, and as we originally commented (at lines 302-303 of the revision) it is possible to rewrite the lower bound in Theorem 1 to use the same metric as Theorem 2, keeping the same dependence on the dimension. In particular, whenever ρ≤h(xt’)\rho \leq h(x_t’), we have

E[min⁡τ∣∣xt−τx^∣∣22]E∣∣xt∣∣22≥18πe⋅12πeexp⁡(2d(h(xt′)−ρ)).\frac{ \mathbb E[\min_\tau || x_t-\tau\hat x ||_2^2] }{ \mathbb E||x_t||_2^2 } \geq \frac{1}{8\pi e}\cdot\frac{1}{2\pi e} \exp\left(\frac{2}{d}\left(h(x_t')-\rho\right)\right).

We have now included the full argument to achieve this bound in Theorem 6 (as well as in Theorem 7 for the low-dimensional setting).

We note that the error up to sign and scale in the equation above describes the component of the target xtx_t orthogonal to the attacker's estimated direction. The mechanism reveals at most ρ\rho nats about xtx_t, so at least h(xt)−ρh(x_t) - \rho nats of uncertainty remain. The norm and sign of the target is a scalar with a bounded second moment, and so it has bounded entropy. The orthogonal (d−1)(d-1)-dimensional component therefore retains nearly all of the remaining uncertainty, and by our original rate-distortion argument, this forces a large expected error.


Weakness 3 and Question 2: dependence of the observed transition to the learning algorithm and results for DP-GD

Thank you for the suggestion of gradient-based algorithms. Our approach readily extends to DP gradient descent (DP-GD), and we included the statement as Theorem 3 in the revised main body, with the corresponding proof added to Appendix D of the revision. In particular, the same attack considered for output perturbation yields the same error upper bound of order d/ρd / \rho for a DP-GD algorithm. We also show evidence of this in the additional experiments in Figure 17 of the revision, which displays the same qualitative trend as the one displayed in Figure 2 for output perturbation. This extension suggests the broader generality of our proposed transition.

Furthermore, we note that our proofs do not critically rely on the linear regression task, and we expect the same transition to hold in wider generality, e.g. for problems with convex losses, with a strong convexity condition in a neighborhood of the empirical minimizer (which seem to be the key qualitative properties enabling our analysis).

To conclude, we remark that the transition of data reconstruction at ρ≍d\rho \asymp d does not hold uniformly for any private algorithm, and in particular it depends on the choice of the hyper-parameters. For example, if one considers Cclip≫1C_{\mathrm{clip}} \gg 1 in Eq. (16), Theorem 2 does not recover anymore the d/ρ≲1d / \rho \lesssim 1 transition, due to the excessive private noise (which also makes the performances of the algorithm sub-optimal, see the two left panels of Figure 2). Theoretically studying the effect of the private hyper-parameters on reconstruction is also part of our contribution, as these, to the best of our knowledge, were investigated only empirically, see (Hayes et al., 2023).

AuthorsOpenReview ↗

(continued)

Weakness 3: novelty with respect to Balle et al. (2022)

Balle et al. (2022) study the same reconstruction-under-privacy setting that we do, but with two key differences.

First, we provide matching upper and lower bounds for reconstruction error under DP, establishing the threshold scaling ρ≍d\rho \asymp d for the analyzed mechanisms (output perturbation and DP-GD). Their analysis of the attack success only concerns non-private models, which is a deterministic setting with a closed-form solution. DP introduces the challenges of studying clipping, noise addition, and early stopping (for DP-GD), and our analysis shows constructively how these quantitatively affect the quality of the reconstruction attack. This reveals the transition at ρ≍d\rho \asymp d and characterizes how reconstruction performance depends on the algorithm’s hyperparameters, both in Theorem 2 for output perturbation and Theorem 3 for DP-GD, which complements empirical observations of hyperparameter-dependent reconstruction performance from (Hayes et al., 2023); Kaissis et al., 2023). To the best of our knowledge, these tight results on the possibility of reconstruction from final private model parameters (for output perturbation and now DP-GD) have not appeared in prior work.

Secondly, our entropy-based formulation has advantages compared to the one based on small-ball probabilities appearing in Balle et al.’s bounds: entropy is a well established quantity with closed-form expressions for many distributions, providing an interpretable characterization of prior uncertainty on the target; our bound is tighter than the guarantees obtained from their bounds for several distributions, as shown in the revised Figure 1, now also including the multivariate Student-tt and mixtures with rare low-variance components.


Question 1: sign & scale ambiguity in practice

It is not possible, in theory, to resolve the sign ambiguity when the loss function and data distribution are symmetric. In practice, we expect the probability distribution of natural images not to be sign invariant, so it is “visually easy” to recognize a natural image or a negative image (see Figure 15 of the revision). Thus, if the attack results in a negative image, the attacker can easily figure this out and flip the sign a posteriori. We have included more visualisations without this post-processing (Figures 11,12 and 14 of the revision), which show the same behaviour as the original figures, with some clearly negative images of elephants in Figures 11 and 12.

Scale can also be addressed similarly, as we demonstrate in Figures 11,12 and 14 in the revision. Since the reconstruction's scale is unknown, we scale it by the largest factor that yields a valid RGB image (i.e. pixels within [0,1][0,1]) after adding back the public mean. An attacker can implement this without any target information, and these images are visually very similar to the originals (Figures 4,10 and 13).

Thanks the authors for the clear clarification. Most of my concerns have been addressed and I decide to raise my score. Good luck!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.