← 研踪 PaperTrailarXiv:2611.11680 · v1
A Theoretical Reduction From Membership Inference to Reconstruction Attacks Against Learners
首次提交 2026-11-09 07:08
版本更新 2026-11-09 07:08
雷达观测 2026-11-10 13:19
摘要
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 $n$, a membership test with recall at least $q(n)$ and false-positive rate $O(δ^2/n^2)$ yields a reconstruction algorithm that, with probability $1 - O(δ)$, outputs only training points, and recovers $Ω(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)$ training points, even when the underlying distribution has exponentially large support.
作者备注：23 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-09 07:08 · 最新观测版本
A Theoretical Reduction From Membership Inference to Reconstruction Attacks Against Learners
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 $n$, a membership test with recall at least $q(n)$ and false-positive rate $O(δ^2/n^2)$ yields a reconstruction algorithm that, with probability $1 - O(δ)$, outputs only training points, and recovers $Ω(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)$ training points, even when the underlying distribution has exponentially large support.
查看此版本解读 →查看此版本原文 ↗