cs.LGNov 8, 2026

A Theoretical Reduction From Membership Inference to Reconstruction Attacks Against Learners

Authors: Amnon Levi, Yuval Dagan

Organizations: School of Computer Science and AI, Tel Aviv University, Tel Aviv, Israel

Abstract

We study reconstruction attacks, which recover training data from a learned model. In our adversarial model, the adversary designs a hard instance, drawn from a parameterized family of data distributions, and is given the parameter used to generate it. Our main contribution is a general reduction showing that, in this model, membership inference (determining whether a given datapoint was used for training) implies reconstruction: for a training set of size nn, a membership test with recall at least q(n)q(n) and false-positive rate O(δ2/n2)O(δ^2/n^2) yields a reconstruction algorithm that, with probability 1−O(δ)1 - O(δ), outputs only training points, and recovers Ω(n⋅q(n))Ω(n \cdot q(n)) of them in expectation. This reduction applies to any learning algorithm. For stochastic convex optimization (SCO), we make the reduction computationally efficient over exponentially large domains via structured distributions whose support is partitioned into polynomially many categories of exponentially many elements each, so that reconstruction iterates over categories rather than the full support. Combining this with an existing membership inference result for SCO, we prove that any learning algorithm achieving low excess risk over all distributions admits a polynomial-time reconstruction attack recovering Ω(n)Ω(n) training points, even when the underlying distribution has exponentially large support.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Aug 26, 2025

The Sample Complexity of Membership Inference and Privacy Auditing

A membership-inference attack gets the output of a learning algorithm, and a target individual, and tries to determine whether this individual is a member of the training data or an independent sample from the same distribution. A successful membership-inference attack typically requires the attacker to have some knowledge about the distribution that the training data was sampled from, and this knowledge is often captured through a set of independent reference samples from that distribution. In this work we study how much information the attacker needs for membership inference by investigating the sample complexity-the minimum number of reference samples required-for a successful attack. We study this question in the fundamental setting of Gaussian mean estimation where the learning algorithm is given nn samples from a Gaussian distribution N(μ,Σ)\mathcal{N}(μ,Σ) in dd dimensions, and tries to estimate μ^\hatμ up to some error E[∥μ^−μ∥Σ2]≤ρ2d\mathbb{E}[\|\hat μ- μ\|^2_Σ]\leq ρ^2 d. Our result shows that for membership inference in this setting, Ω(n+n2ρ2)Ω(n + n^2 ρ^2) samples can be necessary to carry out any attack that competes with a fully informed attacker. Our result is the first to show that the attacker sometimes needs many more samples than the training algorithm uses to train the model. This result has significant implications for practice, as all attacks used in practice have a restricted form that uses O(n)O(n) samples and cannot benefit from ω(n)ω(n) samples. Thus, these attacks may be underestimating the possibility of membership inference, and better attacks may be possible when information about the distribution is easy to obtain.
Oct 27, 2026

A Simple Presentation of Robust Membership Inference Attacks

In a membership inference attack, an attacker is given the data of a particular individual, and tries to determine if that individual was included in a particular dataset, given some kind of statistics derived from the dataset or a model trained on the dataset. Roughly, a membership inference attack is robust if it succeeds even when the statistics are highly noisy, regardless of how that noise is introduced. We give a simple presentation of robust membership inference attacks for mean estimation, covering both multivariate Gaussian distributions and binary product distributions. We also give a summary of the literature on robust membership inference, covering history, extensions, and connections to other research areas.
Aug 24, 2026

DIME: Query-Efficient Framework for Membership Inference on Diffusion Models

Membership inference attacks expose whether individual records were used to train a model, yet existing attacks on diffusion models are largely heuristic and can require substantial query budgets. We introduce DIME (Denoiser Ideal Membership Error), a theoretically grounded and query-efficient framework for membership inference on diffusion models. Our starting point is an exact characterization of the optimal diffusion denoiser for a finite training set, which reveals that membership leakage is governed by the denoiser's implicit reconstruction error. This error decomposes into two complementary signals: a bias term, capturing reconstruction accuracy, and a previously unexplored local crowding term, capturing the geometry of nearby training examples. Both admit efficient estimators using only model queries, yielding a practical attack with as few as two queries. Across CIFAR-10/100, STL10-U, CelebA, and ImageNet, DIME consistently outperforms prior attacks at comparable or substantially lower query cost, improving TPR at 1% FPR by up to 3×3\times; remarkably, its two-query variant can outperform existing 30-query baselines. Finally, we suggest, discuss, and evaluate specific defenses to counteract such powerful membership tests.