Paper 2025/1409

Oblivious Exact (Un)Learning of Extremely Randomized Trees

Abstract

Recent regulations such as the GDPR have given the right to be forgotten to users, which requires that they can ask for the deletion of their data. Yet, enforcing such deletions for machine learning (ML) models remains challenging, especially when servers are untrusted or may ignore requests. To address this issue, we present the first ML model to support oblivious exact unlearning, in which the deletion is computationally indistinguishable from regular training or inference. This ensures that unlearning can be enforced without revealing its occurrence to the server. Our construction is based on Extremely Randomized Trees (ERTs), which are well-suited for encrypted training and efficient unlearning. More precisely, their randomized data-independent structure enables exact sample removal without retraining. We instantiate our protocol within the TFHE framework by designing a non-interactive procedure for encrypted updates, traversals and inference. Our implementation shows that encrypted ERTs train up to 2.4× faster than prior encrypted random forests while maintaining a comparable accuracy.