Summary
This paper pertains to a line of work exploring reconstruction attacks (RA) as a complement to the standard membership inference attacks (MIAs) for evaluating the privacy leakage of ML models. The idea is that a model can be made resistant to RAs for large values of the privacy budget epsilon for which it would not be resistant to MIAs. In cases where membership leakage is not considered a privacy issue, the model might be both “safe” as per low RA risk and useful, since less noise would have to be added. Resistance to RAs can be studied theoretically (by upper bounding the RA success in the worst case) and empirically by developing ever stronger attacks. This work proposes contributions on both fronts for models trained using DP-SGD. On the attack front, two new reconstruction attacks are proposed. The first one is based on the gradients of the model after every iteration and the second one tries to infer the correct record among n candidates. On the theoretical front, a new upper bound for RA success is proposed, which is much better than the previous bound. Finally, the attack initially developed for models trained with gradient descent (no mini-batches) is extended to the mini-batch case. The attack success is shown to be sensitive to the mini-batch size.
Strengths
The gradient-based and prior-aware attack methodologies both seem sound, are well explained and motivated, and the authors explored different alternatives to the proposed formulations. The attacks present sufficient novelty.
The empirical evaluation is extensive which is highly appreciated.
Empirically, the new theoretical upper bound on the success of reconstruction significantly improves upon the previous bound of Balle et al. (2022) as shown on Figure 2. Theoretically, the contribution seems significant too, although I did not verify the proof and I found the hypotheses somewhat opaque.
Weaknesses
1. Prior-aware attack: Conceptually, I am not convinced the 1 out of n classification is the right approach to frame the reconstruction problem. The goal of reconstruction is to extract a target record with limited prior knowledge about the record, i.e., reconstruct the record from scratch. The prior-aware attack changes the task to something quite different, by turning it into a distinguishing game, i.e., finding the right record among 2, 5, 10 etc. possible candidates (specifically, for 2 candidates, the task becomes equivalent to MIA under bounded DP). This means that the adversary already knows the record and the only uncertainty left is which one it is among a limited set of options.
2. One problem with the prior-aware attack is that the prior can be made arbitrarily easy or hard. For instance, if the other records in the prior have a different label than the target record, which the adversary is assumed to already know (Appendix A), it is very easy to guess the right image. In the current experiments, do all of the records in the prior belong to the same class as the target record? Similarly, the authors mention that the prior could be motivated by the adversary narrowing down the list of candidates before running the attack. Have the authors explored a list of candidates that are the most similar to the target itself?
3. The research gap addressed by the paper and the significance of the contributions aren’t clear. The empirical results seem solid, but how the findings translate to the real world is unclear. Perhaps the introduction could explain more the real-world implications of the findings. Eg what does it mean that when training a model with epsilon=10, an extremely strong attack (the prior-aware attack) exists that succeeds 60% of the time, 6x better than the random guess (Figure 2)? In light of the results of this paper, does there exist an epsilon such that the newly proposed, state-of-the-art RAs fail but utility remains very good?
4. Clarity: I found Sec. 3.1 and 3.2 hard to follow. Theorem 2 makes some hypotheses but it’s very difficult for me to understand what these mean and whether they’re validated under real-world scenarios. Hopefully, a reviewer with expertise in DP can check these assumptions as well as the proofs, but regardless of this I think the authors should make these sections clearer and more accessible.
5. Tightness of the upper bound: the authors claim that the upper bound is tight, and indeed Fig.2 shows that for epsilon=1, the upper bound and prior-aware attacks perform similarly. However, the upper bound is also very close to the random guess baseline, such that any better than random attack would appear to be tight. I am not convinced that we can conclude that the upper bound is tight, considering the large gaps shown on Figure 3. At least, some analysis or explanations are needed to better understand when the upper bound is tight and when it isn’t.
6. Minor: Can the authors equalize the color maps on Fig. 5 and 15 so that e.g., yellow on the left becomes comparable with yellow on the right?
Questions
1. How sensitive is the empirical upper bound to the parameters of Algorithm 1 used to estimate it, e.g, N?
2. Is the gradient-based attack the first one to successfully reconstruct records from models trained using DP-SGD? The authors state that Balle et al (2022)’s attack doesn’t succeed, but it isn’t clear in the text whether other attacks from prior works succeed. Clarifying this aspect would better highlight the significance of the contribution.
3. Fig. 3 suggests that even with a very strong prior (size=2) there is a gap of up to 5% depending on the value of epsilon, and the gap can be much larger for larger prior size. Can the authors give potential reasons why the prior-aware attack is not tight in these scenarios and potential directions for improving the success of attacks? It seems that the threat model cannot be made stronger, what about the method? Or should future work focus on tightening the theoretical upper bound?
4. Prior-aware attack: Do all of the n candidate records belong to the same class as the target record? The attack could be made artificially easier by selecting candidates with a different label. Similarly, the authors mention that the prior could be motivated by the adversary narrowing down the list of candidates before running the attack. Have the authors explored a list of candidates that are the most similar to the target itself?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The paper doesn’t mention limitations or broader societal impacts but studies the privacy of ML models, a topic with positive societal impact.