Privacy-Preserving Federated Unlearning With Certified Client Removal

Ziyao Liu, Huanyi Ye, Yu Jiang, Jiyuan Shen, Jiale Guo, Ivan Tjuawinata, Kwok-Yan Lam

TL;DR

Starfish is a novel framework for privacy-preserving Federated Unlearning (FU) that allows a central system to "forget" a specific client's data without ever seeing their raw gradients. By leveraging Two-Party Computation (2PC) and clever algorithmic optimizations like selective round processing, it provides a "certified" removal guarantee—mathematically proving the unlearned model is nearly identical to one retrained from scratch—while protecting against data leakage attacks.

What Problem Does This Paper Address?

In Federated Learning (FL), models are trained across many decentralized devices. However, regulations like GDPR grant users the "Right to be Forgotten," requiring their data's influence to be removed from a trained model (Federated Unlearning).

Existing state-of-the-art unlearning methods (like FedRecover) require the server to store historical gradients from all clients to "roll back" and recalibrate the model. The problem? Gradients aren't perfectly private. Research into Deep Leakage from Gradient (DLG) has shown that an adversarial server can reconstruct a user's private images or text just by looking at their uploaded gradients. This creates a paradox: to unlearn a user for privacy reasons, you must store data that inherently violates their privacy.

Methods

The authors propose Starfish, which moves the unlearning process into a secure, multi-party environment.

  1. Two-Party Computation (2PC): Instead of one server, Starfish uses two non-colluding servers. Clients "secret-share" their gradients between these two servers. No single server ever sees the actual gradient values; they only see random-looking "shares."
  2. Selective Round Selection (SecRS): Unlearning every single training round is computationally expensive in 2PC. Starfish identifies the "most influential" rounds—those where the target client's update most closely aligned with the global model's direction (using cosine similarity)—and only performs recalibration on those rounds.
  3. 2PC-Friendly Optimizations:
    • Pre-computation: Clients compute the $\ell_2$-norm of their gradients locally, sparing the servers from performing expensive "secure square root" operations.
  4. Division-to-Multiplication: To sort rounds by influence, the authors replace secure division with a cross-multiplication comparison, significantly reducing communication overhead.
  5. Switching Threshold ($T_\delta$): The system dynamically chooses between two sorting methods based on the number of rounds to maximize efficiency.
  6. L-BFGS Approximation: To avoid having all remaining clients re-train their models, the servers use a quasi-Newton method (L-BFGS) to estimate how the remaining clients would have updated if the target client had never existed.

Datasets

The framework was evaluated on three standard machine learning benchmarks:

  • MNIST: Handwritten digits (the "Hello World" of ML).
  • Fashion-MNIST: Images of clothing items.
  • CIFAR-10: A more complex dataset of 10 different object classes (airplanes, cats, etc.).

Key Insights and Ideas

  • The "Aha" Moment on Round Selection: The authors observed that a client’s contribution isn't uniform across all training rounds. By selecting only the top $\sigma$ fraction of rounds (e.g., 60%), they can achieve unlearning performance nearly identical to processing 100% of rounds, but at a fraction of the 2PC cost.
  • Certified Removal: The paper provides a theoretical bound (Theorem 1) that quantifies the distance between the Starfish-unlearned model and a "gold standard" model retrained from scratch. This moves FU from "heuristic-based" to "provably effective."
  • Engineering around 2PC Bottlenecks: 2PC is notoriously slow for non-linear operations like division and square roots. By shifting these operations to the client or transforming them into linear comparisons, the authors made a theoretically "heavy" cryptographic process practically viable.

Key Results

  • Unlearning Effectiveness: Starfish achieved Test Error Rates (TER) and Attack Success Rates (ASR) comparable to FedRecover (the non-private baseline). It effectively removed backdoor triggers and membership information.
  • Efficiency: Through selective round selection, Starfish achieved a high Average Round-saving Percentage (ARP), meaning it could skip many rounds of computation without losing accuracy.
  • 2PC Gains: The optimized round selection (Method 2) was significantly faster than the naive version. For the MNIST dataset, the online communication for a single unlearning round was reduced to roughly 0.34 GB, making it manageable for modern data centers.

Limitations and Future Work

  • Semi-Honest Assumption: The current threat model assumes servers are "honest-but-curious" (they follow the rules but try to learn what they can). It does not yet account for "active" malicious servers that might intentionally provide wrong calculations to sabotage the model.
  • Communication Overhead: While optimized, 2PC still requires significant data transfer (gigabytes per round). In wide-area network (WAN) settings with high latency, the unlearning process can still take several hours.
  • Active Malicious Defense: The authors suggest that future work could integrate consistency checks or verifiable computation to defend against servers that deviate from the protocol.

Reference: Liu, Z., et al. (2024). Privacy-Preserving Federated Unlearning with Certified Client Removal. arXiv:2404.09724v1.

Summary updated

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.
BibTeX
@article{liu2025privacy,
  author = {Ziyao Liu and Huanyi Ye and Yu Jiang and Jiyuan Shen and Jiale Guo and Ivan Tjuawinata and Kwok-Yan Lam},
  title = {{Privacy-Preserving Federated Unlearning With Certified Client Removal}},
  journal = {IEEE Transactions on Information Forensics and Security},
  year = {2025},
  url = {https://openreview.net/forum?id=rlAWSsSkaD},
}

Loading related content...

Figure