A Reliable Cryptographic Framework for Empirical Machine Unlearning Evaluation

We sincerely thank Reviewer 5sfE for taking the time to review our paper and for their constructive feedback and valuable suggestions of our proposed evaluation framework!:

Domain Transfer. This could be perceived as more of a modeling contribution than a deep algorithmic innovation for the unlearning process…

We would like to clarify that our work is intended as an evaluation framework, instead of a new unlearning algorithm. The lack of rigorous, reliable metrics for assessing unlearning has been a major obstacle in the field, as also highlighted by the recent NeurIPS unlearning competition. Our cryptographic-game-inspired formulation fills this critical gap by providing a theoretically grounded, practically implementable, and empirically robust evaluation metric for unlearning performance. While we draw upon cryptographic principles, we introduce novel modeling and approximation techniques (e.g., the SWAP test and its instantiation under weak MIAs) tailored for the unlearning setting.

Reliance on Weak Adversaries. If more sophisticated MIAs emerge that can leverage the relationship of data points, the effectiveness and robustness of the current evaluation framework in truly reflecting privacy risks might be compromised…

We would like to clarify a potential misinterpretation: the reviewer suggested that “If more sophisticated MIAs emerge …, the effectiveness of the current evaluation framework in truly reflecting privacy risks might be compromised”. However, our evaluation framework can in fact be further strengthened when new and stronger MIAs become available. As we clarify in Section 3.5 and Appendix B.2, our theoretical framework is fully general—it supports strong adversaries that interact multiple times with the oracle or reason over multiple data points jointly (e.g., with covariance structure). The Unlearning Quality metric is defined as a worst-case guarantee over all efficient adversaries, which naturally includes both weak and strong ones. In practice, we adopt weak MIAs in our empirical evaluation because all current state-of-the-art MIAs are weak under our definition—they act independently on each data point. When stronger MIAs become available, our framework can seamlessly accommodate them. In fact, stronger adversaries would only lower the empirical Unlearning Quality, yielding more conservative (and more accurate) estimates of privacy risk. Thus, the flexibility of our metric is a strength, not a limitation.

Nevertheless, we included white-box attacks [2,3] on SST5 dataset with BERT to show that our metric is robust to stronger adversaries. The results are shown below:

We can see that the results remain consistent with those from black-box attacks—the Unlearning Quality is low for the baseline (None), high for exact unlearning (Retrain), and exhibits meaningful variation across approximate methods. This demonstrates that our metric retains its sensitivity and calibration under stronger, white-box adversaries, and further supports the practical robustness and generality of our evaluation framework. We will incorporate these results and discussion into the revised version to emphasize that our framework is not limited by the adversary access mode, and can support future advances in attack methodology.

Difficulty in distinguishing the performance of unlearning algorithms when the model is very private (ε is small) .

We clarify that the lack of significant differentiation between algorithms when ε is small is not a shortcoming, but rather an expected and desirable outcome. When a model is trained with strong differential privacy (small ε), the influence of individual samples is already well-masked, making unlearning inherently easier. In such scenarios, all unlearning methods—whether approximate or exact—perform similarly well, and our metric reflects this reality.

It’s worth noting that this behavior in fact validates and justifies the reliability of our metric: it gives high scores to all methods only when the model is already highly private and thus has little need for aggressive unlearning. As ε increases (weaker DP), we see the expected divergence between algorithms, demonstrating the metric’s sensitivity in regimes where unlearning efficacy truly matters.

Uniform sensitivity distribution. The framework relies on a uniform data splitting strategy for the forget and test sets. Deviations from this i.i.d. setup could complicate theoretical guarantees and empirical analysis.

We refer to Appendix B.2, where we discuss the role of the sensitivity distribution ​ in shaping oracle responses, as well as the implication of uniform splitting. In particular, we highlight that sensitivity distribution models the privacy risks, informing the Unlearning Quality to focus/omit particular points with higher probability, while uniform splitting is akin to the standard assumption in the unlearning literature and aligns with the i.i.d. setup of most unlearning setups.

A combination of these two makes our framework flexible, as our framework and theory support arbitrary non-uniform sensitivity distributions to model data sensitivity or adversarial focus. Our experiments consider a uniform sensitivity distribution for simplicity, and exploring this in practice is an exciting direction we plan to pursue in future work, but it is beyond the scope of the current submission.

Cross-dataset and architecture variability. Do other existing MIA-based evaluation methods (e.g., MIA AUC, IC Test) exhibit similar magnitudes of performance differences across these diverse settings, or is this variability particularly pronounced with the proposed metric?

We would like to point out that the variability observed across datasets and architectures (Appendix C.4) stems primarily from differences in task difficulty and model learning capacity. For example, CIFAR-100 is a harder task than MNIST, and some unlearning methods degrade more noticeably under harder conditions. This variability is expected and also shown in previous literature(e.g., see Figure 2, Table 5-7 in IC test [1]).

Theoretical approximation error bounds. Are there any theoretical bounds or guarantees on the approximation error of the SWAP test relative to the exact "advantage" metric?

While we do not currently provide tight theoretical bounds on the approximation error of the SWAP test, we would like to highlight several facts:

1. The SWAP test is an unbiased estimator of the true advantage, even under arbitrary sensitivity distributions. This is briefly discussed in Appendix B. Hence, under mild assumptions, it can be shown that the expected error between the average of SWAP estimators and the full Unlearning Quality decreases exponentially fast.
2. It inherits the zero-grounding property (Proposition 3.6), which is a key theoretical feature of the exact metric. Empirically, we observe that the SWAP test preserves the monotonicity with respect to ε and ranking consistency across datasets and methods (Table 1 and C.4). Together, these properties suggest that the SWAP test is both principled and reliable, even without explicit error bounds. Formal analysis of its variance and concentration is a promising future direction.

[1] Goel, Shashwat, et al. "Towards adversarial evaluations for inexact machine unlearning." arXiv preprint arXiv:2201.06640(2022).

[2] Nasr, Milad, Reza Shokri, and Amir Houmansadr. "Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning." 2019 IEEE symposium on security and privacy (SP). IEEE, 2019.

[3] Carlini, Nicholas, et al. "Membership inference attacks from first principles." 2022 IEEE symposium on security and privacy (SP). IEEE, 2022.

Dear Reviewer 5sfE,

We sincerely thank the reviewer again for the time and efforts in reviewing our paper! As we are coming to the last three days of mutual discussion, we kindly hope the reviewer could take a look at our earlier response and let us know any remaining concerns.

Thank you!

We sincerely thank Reviewer yVLK for taking the time to review our paper and for their constructive feedback and strong recognition of our proposed evaluation framework!

Duplicates in datasets. How does the new framework overcome the case when two individuals may have identical data inputs. Will MIA mistake the remaining duplicate as the entry to be removed?

This is an intriguing question, but we would argue that, for the purpose of evaluating unlearning algorithms, the scenario where the retain set contains duplicate entries of the forget set is a pathological evaluation setting. Specifically, the ground truth for whether a model has “forgotten” the sample from the forget set becomes ambiguous.

This pathological setting is analogous to evaluating classification accuracy using mislabeled test samples. When the test samples are mislabeled, it is unclear whether one should expect a better classification algorithm should have higher or lower test accuracy on this corrupted test set. Similarly, it is unclear whether a better unlearning algorithm should have higher or lower Unlearning Quality in the pathological setting where the retain set and forget set share duplicates.

We sincerely thank Reviewer K1Yg for taking the time to review our paper and for their constructive feedback and strong recognition of our proposed evaluation framework!

Assumption of Weak Adversaries. Practical evaluation is restricted to weak MIAs (interact only once with the oracle), limiting full assessment of sophisticated attacks.

We would like to clarify that while our empirical evaluation leverages weak (single-interaction) MIAs due to the limitations of current state-of-the-art adversaries, our framework is not restricted to weak adversaries in theory. As detailed in Appendix B.2, our cryptographic game formulation accommodates arbitrary adversaries, including those with multi-sample or oracle access (e.g., strong, white-box, or adaptive MIAs).

Indeed, we acknowledge that stronger adversaries may yield lower Unlearning Quality, and thus our reported values may be over-optimistic. However, in practice, users are encouraged to instantiate the strongest MIA feasible in their deployment scenario to obtain a meaningful approximation of worst-case privacy risk.

We will explicitly include this discussion in the revised version to clarify that our metric’s rigor scales with the strength of the employed adversary.

No Real-World Dataset: Datasets in the experiments are confined to CIFAR-10, a toy dataset.

We want to clarify that in the appendix, we have already included additional datasets (CIFAR-100 and MNIST) to demonstrate robustness across varying dataset complexities.

We agree that incorporating a non-vision modality is important. As such, we are in the process of extending our experiments to include a text corpus (SST5) and pretrained models such as BERT. The results is shown below:

We can see that the results also exhibit similar trends as in the vision domain: the proposed metric distinguishes between unlearning methods more clearly as the privacy budget becomes weaker. Moreover, Retrain consistently achieves near-perfect Unlearning Quality, while approximate methods show meaningful variation based on their aggressiveness and design.

Certified removal parameters are difficult to compute in practice, especially for non-convex or large models.

It is worth noting that we use certified removal only for the purpose of theoretical analysis, connecting our metric to well-established definitions from the literature. This connection provides formal grounding (see Theorem 3.5), but is not required for implementation or evaluation, since the definition of our metric does not rely on certified removal.

Full computation of the proposed metric can still be computationally expensive

We highlight that our metric has comparable costs to existing MIA evaluation pipelines. Concretely, the cost of the SWAP test is approximately 2× that of a standard MIA pipeline—primarily due to evaluating both swapped splits. Therefore, our methods can be applied to scenarios where existing MIA-based evaluations can be used.

The possibility that the metric may also be over-optimistic under strong attacks is not discussed.

We agree that our current experimental results may be over-optimistic due to the limitations of available MIAs. We will add a discussion to explicitly acknowledge that Unlearning Quality should be interpreted relative to the strength of the MIA used in practice. In other words, one can always enforce the strongest MIA to date relevant to their application to obtain a practically meaningful measure of Unlearning Quality.

However, we also note that our metric is fundamentally different from existing MIA-performance-based scores: it enjoys zero-grounding under retraining, consistency under differential privacy, and is provably upper-bounded by theoretical guarantees (e.g., Theorem 3.5). In particular, the calibration properties of the proposed metric cannot be achieved by merely strengthening the performance of MIAs.

White-box MIAs. Will white-box MIAs hurt the robustness of the metric?

While our empirical evaluation used black-box MIAs for efficiency, we stress that our framework accommodates both black-box and white-box adversaries. This is discussed in Appendix B.2. We have added classic white-box attacks as in [1,2] on SST5 dataset with BERT. The results is shown below:

We can see that the results remain consistent with those from black-box attacks—the Unlearning Quality is low for the baseline (None), high for exact unlearning (Retrain), and exhibits meaningful variation across approximate methods. This demonstrates that our metric retains its sensitivity and calibration under stronger, white-box adversaries, and further supports the practical robustness and generality of our evaluation framework.

We will incorporate these results and discussion into the revised version to emphasize that our framework is not limited by the adversary access mode, and can support future advances in attack methodology.

Generalization across architectures, modalities, or imbalanced datasets.

It’s worth noting that our framework is model-agnostic and modality-agnostic by design. The cryptographic game only assumes an unlearned model and a forget/test split—it is the MIA’s task to adapt its attack strategy to the data distribution and architecture. Nevertheless, we have added the results of BERT finetuned on SST5. Please refer to the “No real-world dataset” section for experimental results.

Non-uniform sensitivity distributions

We have provided a high-level discussion in Appendix B.2, where we define the sensitivity distribution $\mathbb{P}_{\mathcal{D}}$ and allow arbitrary biases toward specific samples. This enables the metric to reflect heightened privacy risk from more sensitive data points, addressing more difficult samples, or accommodating class imbalances.

Our design ensures that such distributions are respected during evaluation via the oracle sampling. As a result, the metric captures the influence of both distributional skew and sample difficulty, offering a more realistic view of privacy risk than uniform sampling alone.

[1] Nasr, Milad, Reza Shokri, and Amir Houmansadr. "Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning." 2019 IEEE symposium on security and privacy (SP). IEEE, 2019.

[2] Carlini, Nicholas, et al. "Membership inference attacks from first principles." 2022 IEEE symposium on security and privacy (SP). IEEE, 2022.

We sincerely thank Reviewer FFru for taking the time to review our paper and for their constructive feedback and recognition of our proposed evaluation framework!

On the use of computationally bounded adversaries

We would like to clarify that our theoretical framework does not require the adversary to be computationally bounded. In fact, Theorem 3.5 holds even for computationally unbounded adversaries, meaning our Unlearning Quality metric can naturally generalize to a “statistical” notion without needing to assume computational limitations (see main paper, Theorem 3.5 and Appendix B.3). Thus, the core theoretical foundation of our framework remains valid in both settings. That said, we explicitly focus on computationally bounded adversaries for practical purposes. As with differential privacy, empirical evaluation and implementation inherently require working with efficient algorithms. Moreover, existing MIA techniques are themselves limited in computational power, and our approximation methods (e.g., the SWAP test) are grounded in this practical setting. In this way, the use of weak or computationally bounded adversaries serves as a realistic approximation for empirical evaluation—analogous to the use of efficient distinguishers in applied cryptography. We have updated the discussion in the main text to better articulate the above tradeoff between theoretical generality and practical feasibility. We thank the reviewer again for prompting us to clarify this important point.

"There is significant overlap between this paper and another recent paper [1] up on arXiv..."

We will cite it in the updated version of our paper. As noted, the timing suggests the work appeared after the NeurIPS abstract deadline, but we agree it is important to acknowledge concurrent developments and position our contributions accordingly.