The Sample Complexity of Membership Inference and Privacy Auditing

The gist: In simple, natural settings for Gaussian mean estimation, any successful membership-inference attack requires a sample complexity of at least omega(n) samples, which is many more than what training algorithms use

Main Conceptual Result

The main conceptual result shows that there are simple, natural settings where any successful membership-inference attack requires omega(n) samples from the population—that is, many more samples than were used to train the model We formulate and prove our result in the simple-yet-fundamental case of mean estimation, which has long been an important testbed for theoretical work on membership inference

Problem Setup

The study focuses on Gaussian mean estimation where the population is D = N (mu, Σ) and the training dataset is Sn = (X1,..., Xn) ∼ D⊗n The algorithm A releases muˆ = A(Sn), and it is defined as rho-accurate if E[∥muˆ − μ∥2Σ] ≤ drho2 + d/n

Lower Bound on Sample Complexity

Theorem 1.1 establishes a strong lower bound on the sample complexity of MIA for Gaussian mean estimation, showing that any attacker that succeeds in this optimal regime where d ≈ d(n, ρ), requires a large number of samples m ≳ n + n2/rho2 In particular, in the regime where rho = ω(n−1/2)—that is, when the error of the mean estimator is larger than the sampling error—Theorem 1.1 implies that a successful attack requires m ≳ n2/rho2 = ω(n)

Implications for Practical MIA and Auditing

The results imply that existing methodology for MIA may be underestimating privacy risk because it does not necessarily take full advantage of knowledge the attacker might have, and thus we should be careful about interpreting empirical privacy measurements based on these potentially suboptimal attacks For any test of the restricted form (2), having Θ(n) samples from the distribution is as good as having the distribution itself, but since we can show that having omega(n) samples allows for successful attacks in cases where O(n) samples are insufficient for a successful attack, we know that tests of the general form (1) can be dramatically more powerful

MIA with Known Covariance

In the setting where the attacker knows the covariance of the population but not the mean, Theorem 1.2 provides a lower bound on auxiliary samples required by any sample-based MIA, showing that for d ≈ d(n, ρ), every sample-based MIA requires m ≳ min[n, 1/rho2] samples This contrasts with the case where the attacker knows the covariance but not the mean as we discuss in Section 1.2.2

Technical Overview of Proof

The proof for Theorem 3.1 involves reducing the problem to a zero auxiliary sample case, where it is shown that MIA is difficult with zero auxiliary samples This reduction relies on showing that if membership inference with zero auxiliary samples is difficult, it remains difficult with m auxiliary samples, provided m is smaller than n + n2/rho2 The proof utilizes Lemma 3.7 to show that the total variation distance between two mixture distributions can be bounded by a term involving √n + 1/2 log(d)

MIA for Mean Estimation with Known Covariance

Theorem 4.1 shows that in the case where the covariance matrix is known to the attacker, there is no (Pid.cov d, An,rho)-sample-based MIA where An,rho is the noisy empirical mean defined in Definition 2.4 and Pid.cov d is the distribution family defined in Definition 2.3 This result suggests that knowing the covariance matrix significantly reduces the sample complexity of sample-based MIA, reducing it from Ω(n2/rho2) to O(n) for certain parameter regimes

Tightness and Context

The lower bound in Theorem 3.1 is tight when d ≈ d(n, ρ), which is the threshold under which even an attacker with the full knowledge of the distribution cannot succeed The upper bound in Theorem 3.3 shows there exists an attacker which requires O(d(n, ρ)) samples, indicating that our result is tight in this regime

Sample Complexity of Mahalanobis Distance Estimation

Definition A.2 states that for every 1/2-accurate Mahalanobis norm estimator for y with n samples, we require n ≥ c1d This is contrasted by the result in Theorem 4.1, which shows that in the regime where d ≈ n + n2/rho2, a sample-based MIA requires at least min[1/rho2, n] auxiliary samples to achieve similar performance

Conclusion on Complexity Reduction

Remark 4.2 notes that for ρ > 1/√n, comparing Theorems 1.1 and 1.2 shows that knowing the covariance reduces the required auxiliary samples from Ω(n2/rho2) to O(n) This confirms that knowledge of the covariance matrix significantly reduces the sample complexity of sample-based MIA

Final Bound Comparison

The final bound derived in Equation (34), which is obtained by plugging bounds into Equation (23), shows that TV Ym, X0, μˆ0 to Ym, X1, μˆ1 ≤ √d(n, ρ) + 1 + TV Xf0, μeˆ0 to Xf1, μeˆ1 This bound is achieved by carefully choosing parameters such that the total variation term is made sufficiently small

Upper Bound Strategy

Theorem 3.3 provides a strategy for an (P d, An,d,rho, n,m)-sample-based MIA when m ≥ cd and d ≥ c(n + n2/rho2) The attacker divides its auxiliary samples into three parts of size Θ(d), Θ(min[n, 1/rho2]), and one, using the next Θ(min[n, 1/rho2]) samples to get an estimate of the unknown mean The strategy is inspired by [DSSUV15]

Final Result Summary

The overall finding is that for Gaussian mean estimation, the sample complexity required for an optimal attack is Ω(n + n2/rho2) samples This demonstrates that linear-sized reference data sets used by existing attacks may be insufficient and better attacks may be possible when information about the distribution is easy to obtain The required size of the reference sample can therefore be as large as Ω(n2/rho2)

Final Conclusion

The paper concludes that for Gaussian mean estimation, any successful sample-based MIA requires m ≳ n2ρ2 samples This result is the first to show that the attacker sometimes needs many more samples than the training algorithm uses to train the model Thus, not only are linear-sized reference data sets used by existing attacks necessary in natural settings, they may be insufficient and better attacks may be possible when information about the distribution is easy to obtain The required size of the reference sample can therefore be as large as Ω(n2/rho2).

1. textbfKnowledge of Auxiliary Samples for Membership Inference Attacks (MIA): The improved system can better assess privacy risks by accounting for attacker knowledge using a sample complexity bound of Ω(n + n2/rho2) samples, which is significantly more demanding than the O(n) samples used by existing attacks.

2. textbfCapabilities in High-Dimensional Settings: The system can successfully perform membership inference when the data dimension is large enough to allow for an optimal attack, specifically when d ≥ d(n, ρ) ≜ n + n2/rho2, where d(n, ρ) is the threshold for a fully informed attacker to succeed.

3. textbfDetection of Subspace Structure: The system can leverage auxiliary samples to infer structural information about the population distribution, as demonstrated by Lemma D.12, allowing it to determine if an orthogonal projection operator is an m-dimensional orthogonal projection matrix based on observed projections and data points.

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 N(μ,Σ) in d dimensions, and tries to estimate μ up to some error E[| μ- μ| 2 Σ] at most ρ squared d. Our result shows that for membership inference in this setting, Ω(n + n squared ρ 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 ω(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.