arXiv：cs.LG· Mahdi Haghifam, Adam Smith, Jonathan Ullman·· 3 小时前
成员推断与隐私审计的样本复杂度
The Sample Complexity of Membership Inference and Privacy Auditing
AI 导读
研究显示，在 d 维高斯分布均值估计场景中，想要匹敌完全知情攻击者的成员推断攻击，可能需要 Ω(n + n²ρ²) 个参考样本，首次证明攻击者所需样本数可远超训练算法所用样本数。实践中所有攻击均限于 O(n) 样本形式，因而可能低估了成员推断的真实风险；当分布信息易于获取时，可能存在更强的攻击。该成果将发表于 FOCS 2026。
正文
Abstract: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 $n$ samples from a Gaussian distribution $\mathcal{N}(\mu,\Sigma)$ in $d$ dimensions, and tries to estimate $\hat\mu$ up to some error $\mathbb{E}[\|\hat \mu - \mu\|^2_{\Sigma}]\leq \rho^2 d$. Our result shows that for membership inference in this setting, $\Omega(n + n^2 \rho^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)$ samples and cannot benefit from $\omega(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.
| Comments: | 59 Pages, Updated compared to v1: improved presentation and fixed typos. To appear in FOCS 2026 |
| Subjects: | Machine Learning (cs.LG); Cryptography and Security (cs.CR); Machine Learning (stat.ML) |
| Cite as: | arXiv:2508.19458 [cs.LG] |
| (or arXiv:2508.19458v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2508.19458 arXiv-issued DOI via DataCite |
Submission history
From: Mahdi Haghifam [view email]
[v1]
Tue, 26 Aug 2025 22:19:28 UTC (165 KB)
[v2]
Thu, 8 Oct 2026 02:21:20 UTC (200 KB)
来源：arXiv：cs.LG · arxiv.org