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 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 ρ≪ d; on the other hand, we analyze a simple attack on private linear regression with output perturbation, showing that reconstruction is practically feasible for ρ≫ 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).
Related
- Prophet Inequalities under Local Differential Privacy
- Performative Privacy: When Differential Privacy Maximizes Utility
- Task-aware Kernel Stein certificates for Rényi differential privacy
- Minimax Wasserstein Testing under Differential Privacy
- Asymptotic Anytime-Valid Quantile Inference under Local Differential Privacy
BibTeX
@misc{cairneyleeming2026sharp,
title = {{A Sharp Transition in Data Reconstruction under Differential Privacy}},
author = {Max Cairney-Leeming and Simone Bombari and Marco Mondelli},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37344},
eprint = {2609.37344},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37344},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Sharp Transition in Data Reconstruction under Differential Privacy
AU - Max Cairney-Leeming
AU - Simone Bombari
AU - Marco Mondelli
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37344
UR - https://arxiv.org/abs/2609.37344
AB - 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 ρ≪ d; on the other hand, we analyze a simple attack on private linear regression with output perturbation, showing that reconstruction is practically feasible for ρ≫ 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).
ER -