Skip to content

A Sharp Transition in Data Reconstruction under Differential Privacy

Sep 2026 · arXiv.org · Vol abs/2609.37344 · 0 citations · 54 references
Computer Science Mathematics

TL;DR

This work studies informed attackers who aim to reconstruct a single $d$-dimensional training sample from a $\rho$-zero-concentrated DP model, knowing all other training data, and derives entropy-based lower bounds for any private mechanism and any attack, demonstrating that the privacy budget guaranteeing adequate protection must be assessed in terms of the effective dimension of the data.

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 $\rho$-zero-concentrated DP model, knowing all other training data. Our main contribution is to establish a sharp transition at $\rho \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 $\rho \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 $\rho \gg d$. Remarkably, the transition moves to $\rho \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).

View source

Similar papers

#machine learning Preprint Oct 2026

Adaptive Model Inversion Attacks Generalize a Privacy-Robustness Tradeoff

In this paper, we show that standard evaluations of high-resolution Model Inversion Attacks (MIAs) significantly underestimate training-data privacy leakage. State-of-the-art privacy defenses, standard training techniques such as MixUp and Adversarial Training, and undefended models all leak training images at rates 1....

Shailen Smith, Rasmus Torp, Adam Breuer · 0 citations
Open access Sep 2026

Distortion-Constrained Minimax Data Sanitization with Multiple Adversaries

We study a privacy-preserving data-sharing setting where a privatizer transforms private data into a sanitized release observed by an authorized reconstructor and two unauthorized adversaries, each with access to side information correlated with the private data. An adversary is considered stronger when it estimates th...

Amirarsalan Moatazedian, Yauhen Yakimenka, Re-Mi A. Chou et al. · 0 citations
Review Oct 2026

Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits

Saturated Propose-test-release, a general mechanism that privately releases the output of a discrete selector with probability one once its stability certificate reaches a finite threshold, is introduced and a computable support-stability score is constructed.

Jian-Zhong Gu, T. Cai · 1 citation
#machine learning Preprint Sep 2026

Predicting Privacy Leakage from Weight Spectral Density

The results indicate that neural network spectra may contain information about privacy leakage that is not fully captured by conventional measures of overfitting, motivating spectral analysis as a promising direction for scalable privacy auditing.

R. Preen, Jim Smith · 0 citations
#artificial intelligence Preprint Aug 2026

FISGuard: Defending Against Membership Inference via Fixed Input Subspaces

FISGuard reduces the ProjRes attack AUC to near the random-guessing level of 0.5 in most settings, while maintaining downstream task performance close to that of the undefended model and introducing only limited computational overhead, thereby achieving a favorable privacy--utility trade-off.

Hao-Cheng Jiang, Hua Shen · 0 citations
Preprint Aug 2026

Privacy Without Regret: Differentially Private Inference-Time Alignment

Private Inference-Time Pessimism (PrivITP) is introduced, which combines $\chi^2$-regularized rejection sampling with a two-phase Gaussian mechanism, and achieves ex-post $(\epsilon,\delta)$-DP with a privacy cost independent of the number of responses, cleanly decouples the regularization parameter from the privacy pa...

I. Jain, Nandini Bhattad, Sayak Ray Chowdhury · 0 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.