Abstract
In recent years, Federated Unlearning (FU) has gained attention for addressing the removal of a client's influence from the global model in Federated Learning (FL) systems, thereby ensuring the "right to be forgotten" (RTBF). State-of-the-art methods for unlearning use historical data from FL clients, such as gradients or locally trained models. However, studies have revealed significant information leakage in this setting, with the possibility of reconstructing a user's local data from their uploaded information. Addressing this, we propose Starfish, a privacy-preserving federated unlearning scheme using Two-Party Computation (2PC) techniques and shared historical client data between two non-colluding servers. Starfish builds upon existing FU methods to ensure privacy in unlearning processes. To enhance the efficiency of privacy-preserving FU evaluations, we suggest 2PC-friendly alternatives for certain FU algorithm operations. We also implement strategies to reduce costs associated with 2PC operations and lessen cumulative approximation errors. Moreover, we establish a theoretical bound for the difference between the unlearned global model via Starfish and a global model retrained from scratch for certified client removal. Our theoretical and experimental analyses demonstrate that Starfish achieves effective unlearning with reasonable efficiency, maintaining privacy and security in FL systems.
Introduction
Federated Learning (FL) allows multiple clients to collaboratively train a model without sharing raw data. However, the "Right to be Forgotten" (RTBF), mandated by regulations like GDPR, requires that a client's data influence be removable from the final model. This process, known as Federated Unlearning (FU), typically requires the server to store historical gradients to "roll back" and recalibrate the model.
Recent research into Deep Leakage from Gradient (DLG) has shown that these stored gradients are not perfectly private; an adversarial server can often reconstruct sensitive user data from them. This creates a privacy paradox: the very data needed to fulfill a privacy request (unlearning) inherently violates the user's privacy.
The Starfish Framework
To address this challenge, we propose Starfish, a framework that moves the unlearning process into a secure, multi-party environment. Starfish leverages Two-Party Computation (2PC) to ensure that no single server ever has access to raw client gradients.
System Architecture
In the Starfish architecture, two non-colluding servers manage the unlearning process. Clients "secret-share" their gradients between these two servers. Consequently, each server only sees random-looking "shares" of the data, and the actual gradient values are never exposed.
Unlearning Workflow
The Starfish unlearning process is designed to be both secure and efficient. It follows a pipeline that minimizes the computational burden of 2PC while maintaining high unlearning fidelity.
The workflow consists of several key stages:
- Selective Round Selection (SecRS): Unlearning every training round is computationally prohibitive in a 2PC setting. Starfish identifies the "most influential" rounds—those where the target client's update most closely aligned with the global model's direction—and only performs recalibration on those rounds.
- Gradient & Model Estimation: To avoid requiring all remaining clients to re-train, the servers use a quasi-Newton method (L-BFGS) to estimate how the remaining clients would have updated the model if the target client had never participated.
- Error Correction: The system applies corrections to the estimated model to ensure it remains accurate and effectively "forgets" the target data.
2PC-Friendly Optimizations
Because 2PC is notoriously slow for non-linear operations, Starfish incorporates several algorithmic optimizations:
- Pre-computation: Clients compute the $\ell_2$-norm of their gradients locally, sparing the servers from expensive secure square root operations.
- Division-to-Multiplication: Secure division is replaced with cross-multiplication comparisons during round selection, significantly reducing communication overhead.
- Dynamic Switching: The system chooses between different sorting methods based on a switching threshold ($T_\delta$) to maximize efficiency depending on the number of rounds.
Experimental Results
Starfish was evaluated on standard benchmarks including MNIST, Fashion-MNIST, and CIFAR-10. The results demonstrate that Starfish achieves unlearning effectiveness comparable to non-private baselines like FedRecover.
Key findings include:
- Efficiency: By selecting only a fraction of influential rounds (e.g., 60%), Starfish achieves a high Average Round-saving Percentage (ARP) without sacrificing model accuracy.
- Certified Removal: The framework provides a theoretical bound quantifying the distance between the unlearned model and a "gold standard" model retrained from scratch, moving FU toward provable effectiveness.
- Communication: Optimized round selection significantly reduced online communication. For MNIST, the communication for a single unlearning round was reduced to approximately 0.34 GB.
Conclusion and Future Work
Starfish successfully bridges the gap between federated unlearning and data privacy. By utilizing 2PC and targeted algorithmic optimizations, it provides a practical way to implement the "Right to be Forgotten" without risking gradient leakage. Future research will explore defenses against "active" malicious servers that might attempt to sabotage the unlearning process through incorrect computations.
Summary updated