# Data Reconstruction: When You See It and When You Don't

arXiv: https://arxiv.org/abs/2405.15753 · HTML: https://mlsanity.com/paper/2405.15753/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2024.

## Built on by (most cited first, 7 of 7)

- [Unifying Re-Identification, Attribute Inference, and Data Reconstruction Risks in Differential Privacy](https://mlsanity.com/paper/2507.06969/) (2025)
- [A Unified Framework for Adversary-Aware Differential Privacy Bounds](https://mlsanity.com/paper/2507.08158/) (2025)
- [Reconstruction and Secrecy under Approximate Distance Queries](https://mlsanity.com/paper/2511.06461/) (2025)
- [Beyond Indistinguishability: Measuring Extraction Risk in LLM APIs](https://mlsanity.com/paper/2604.18697/) (2026)
- [Training Set Reconstruction from Differentially Private Forests: How Effective is DP?](https://mlsanity.com/paper/2502.05307/) (2025)
- [Bayesian Perspective on Memorization and Reconstruction](https://mlsanity.com/paper/2505.23658/) (2025)
- [SoK: Reconstruction Attacks on Synthetic Tabular Data (Insights from Winning the NIST CRC)](https://mlsanity.com/paper/2606.08372/) (2026)

## Abstract (arXiv)

We revisit the fundamental question of formally defining what constitutes a reconstruction attack. While often clear from the context, our exploration reveals that a precise definition is much more nuanced than it appears, to the extent that a single all-encompassing definition may not exist. Thus, we employ a different strategy and aim to "sandwich" the concept of reconstruction attacks by addressing two complementing questions: (i) What conditions guarantee that a given system is protected against such attacks? (ii) Under what circumstances does a given attack clearly indicate that a system is not protected? More specifically, * We introduce a new definitional paradigm -- Narcissus Resiliency -- to formulate a security definition for protection against reconstruction attacks. This paradigm has a self-referential nature that enables it to circumvent shortcomings of previously studied notions of security. Furthermore, as a side-effect, we demonstrate that Narcissus resiliency captures as special cases multiple well-studied concepts including differential privacy and other security notions of one-way functions and encryption schemes. * We formulate a link between reconstruction attacks and Kolmogorov complexity. This allows us to put forward a criterion for evaluating when such attacks are convincingly successful.