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

CardsList
  1. The Sample Complexity of Membership Inference and Privacy Auditing

    Aug 26, 2025Mahdi Haghifam, Adam Smith, Jonathan UllmanMembership Inference AttacksSample Complexity

  2. A Simple Presentation of Robust Membership Inference Attacks

    Oct 27, 2026Renaud Gaucher, Ephraim Linder, Adam Smith +2Membership Inference Attacks