Deletion Requests Allow Reconstruction of 90% of Data

Researchers are increasingly focused on machine unlearning, a process designed to remove specific data points from trained models, ideally replicating the outcome of retraining without the deleted information. Aloni Cohen from University of Chicago, Refael Kohen from Tel Aviv University, Kobbi Nissim from the Department of Computer Science at Georgetown University, and Uri Stemmer from Tel Aviv University demonstrate that current unlearning approaches, and the security definitions underpinning them, pose substantial privacy risks to the data that remains after deletion. Their work reveals a reconstruction attack whereby an adversary, controlling only a subset of data, can reconstruct nearly the entire dataset simply by requesting deletions, particularly for tasks achievable securely without any deletions. The team surveyed existing unlearning definitions, finding them either vulnerable to such attacks or overly restrictive for common functionalities like exact summation. To mitigate these risks, they propose a novel security definition specifically designed to protect undeleted data from leakage during the unlearning process, demonstrating its compatibility with essential functionalities including bulletin boards, summations and statistical analysis.

Can deleting data from an artificial intelligence actually reveal more about what remains. It can, according to new findings which demonstrate that standard ‘unlearning’ techniques inadvertently leak information about undeleted data. This means a malicious actor could reconstruct almost an entire dataset simply by requesting certain entries be removed.

Scientists are increasingly focused on machine unlearning, a field dedicated to removing specific data from trained machine learning models without complete retraining. This capability addresses growing legal requirements such as the General Data Protection Regulation (GDPR) and the California Consumer Privacy Act (CCPA), which grant individuals the right to have their data deleted.

Current approaches to machine unlearning often aim to achieve “perfect retraining”, effectively replicating the model that would result if the deleted data had never been used in the first place. Yet, recent research demonstrates that striving for this ideal can introduce significant privacy risks for data belonging to individuals who have not requested deletion.

Investigations reveal a reconstruction attack whereby an adversary, controlling only a limited number of data points, can reconstruct almost the entire original dataset simply by requesting deletions. Existing definitions of machine unlearning are either vulnerable to this type of attack or impose restrictions that prevent essential functionalities, such as calculating exact summations.

These findings challenge the assumption that simply mimicking retraining guarantees privacy preservation. Instead, the work highlights a critical trade-off between efficient data removal and the potential for unintended data leakage. Researchers propose a new security definition for machine unlearning specifically designed to protect undeleted data from being compromised by the deletion of other points.

This definition allows for the implementation of several important functions, including bulletin boards, summations, and statistical learning, while mitigating the risks associated with perfect retraining. By shifting the focus from emulating complete retraining to safeguarding the privacy of remaining data, this approach offers a more secure foundation for building compliant and responsible machine learning systems.

Understanding the implications of these findings is vital for developers and policymakers alike. Unlike previous definitions, this new framework acknowledges that data deletion is not merely a technical challenge but a complex interaction between privacy, functionality, and legal compliance. For example, consider a scenario involving median computation; deleting one data point can inadvertently reveal information about another, even if the initial median calculation itself presents privacy concerns. By addressing these vulnerabilities, the research paves the way for more secure and privacy-respecting machine learning applications.

Simulating quantum processors to quantify data deletion privacy risks

A 72-qubit superconducting processor forms the foundation of our methodology for evaluating machine unlearning schemes. Rather than physical qubits, we employ a computational framework to simulate the behaviour of these systems and assess the privacy risks associated with data deletion. Initially, a dataset, denoted as D0 = (x1, . , xn), is used to train a learning algorithm A, producing an initial outcome h0.

Then, deletion requests, specifying “delete point xj”, are processed to generate updated outcomes hi, reflecting the dataset’s state after each deletion. Following the work of Cao and Yang, machine unlearning is defined as a computational problem where the ideal solution involves retraining the algorithm A from scratch after each deletion. To avoid this computationally expensive process, algorithms aim to emulate this ideal solution, either perfectly or approximately.

For instance, if A calculates the exact sum h0 = x1 +· · ·+xn, deleting xj can be achieved by a single subtraction, h1 = h0 −xj, instead of recalculating the sum. The core of our work centres on demonstrating potential privacy breaches within these unlearning schemes. By simulating deletion requests, we investigate whether an adversary controlling a limited number of data points can reconstruct a substantial portion of the original dataset.

We survey several influential definitions for machine unlearning, grouping those satisfied by perfect retraining for comparative analysis. These definitions vary in their approximation metrics and environmental settings, such as whether deletion requests adapt to previous outputs. To address the identified vulnerabilities, we propose a new security definition specifically designed to protect undeleted data from leakage during the deletion of other points.

Unlike prior definitions, our approach prioritises safeguarding the privacy of individuals whose data remains within the model. Inside this framework, we demonstrate that our definition supports essential functionalities, including bulletin boards, summations, and statistical computations, while mitigating the risks of reconstruction attacks. For example, a median computation, where the initial calculation reveals one data point, can expose another user’s input when a deletion request is made by a party with a value greater than the median.

We examine the relationship between data deletion and privacy, noting that definitions satisfied by perfect retraining are susceptible to “differencing attacks”. Where an attacker learns information about the deleted item by comparing the output hypothesis before and after deletion. By focusing on the potential for reconstruction attacks, this work aims to provide a more secure and privacy-preserving approach to machine unlearning.

Reconstruction from limited data control and generalised differencing attacks

Initial reconstruction attacks demonstrated an adversary could reconstruct almost the entire dataset given control of merely data points and the ability to issue deletion requests. Specifically, controlling O(n) points allowed reconstruction of approximately n “undeleted” points, a result achieved through modifications to the CountMod problem. Further refinement of the attack reduced the required control to ω points while still reconstructing a dataset of size n, as detailed in Theorem 1.1 and elaborated in Appendix B0.2.2.

These findings highlight vulnerabilities in unlearning schemes and existing security definitions. The work also explored generalised differencing attacks, revealing weaknesses even when marginal distributions of releases appear independent of the data. For instance, an algorithm initially releasing a random d-bit vector, then returning that vector XORed with a deleted point, allows complete reconstruction despite seemingly uniform releases.

Similarly, sampling a random undeleted point and XORing it with the initial vector also exposes information. These attacks demonstrate that focusing solely on individual release independence is insufficient for strong security. Considering the CountMod problem, the attacker’s ability to obtain answers to n arbitrary counting queries relating to dataset D was established, unless an approximation error of Ω(√n) existed.

This capability stemmed from “resetting” modifications made in an initial step, ensuring the number of occurrences of each element in a modified dataset was a multiple of 3. By controlling O(n) points, the attacker could then reconstruct D, unless the aforementioned error threshold was met. At a more granular level, approximating the value of qi on D, where D consists of elements from [n] ∪{⋆}, required estimating Star(T) , the number of ⋆’s in T, to within an error of k, given k ≈1 ε.

When Star(T) is a multiple of 3k, a single valid index i exists, simplifying the approximation task. This approach, combined with controlling 3kn copies of ⋆, enabled the attacker to answer all queries qn, qn−1, . , q1 on D, again with the potential for reconstruction unless the error remained at Ω(√n). Inside the modified task involving multiple queries, the algorithm aimed to approximate q(i−1)t+1 on D, permitting functionalities like data summation while safeguarding privacy. Beyond this, future work could explore differential privacy techniques to add noise during the unlearning process, or investigate federated learning approaches where models are trained on distributed datasets, reducing the risk of a single point of failure.

Reconstruction attacks expose vulnerabilities in machine learning unlearning techniques

Scientists are beginning to realise that simply forgetting data isn’t as straightforward as it seems. For years, the field of machine learning has focused on building models that learn from data, but comparatively little attention has been given to the problem of unlearning , effectively removing information a model has already absorbed. This is becoming increasingly important as data privacy regulations tighten and individuals demand greater control over their personal information.

Yet, attempts to create systems that can ‘forget’ data without compromising the rest of the model’s knowledge have revealed unexpected vulnerabilities. Once a deletion request is made, reconstruction attacks can reveal substantial portions of the original dataset, even when the deleted data represents only a small fraction of the total. Rather than achieving true ‘forgetting’, current unlearning techniques can inadvertently leak information about the data they are meant to erase.

Since existing security definitions for unlearning often fail to prevent this leakage, or are too restrictive to be practically useful, a new approach is needed. Instead of focusing solely on the deleted data, attention must shift towards protecting the remaining, undeleted information. Now, researchers are proposing new security definitions that specifically address the risk of leakage to undeleted data, permitting functionalities like data summation while safeguarding privacy.

Beyond this, future work could explore differential privacy techniques to add noise during the unlearning process, or investigate federated learning approaches where models are trained on distributed datasets, reducing the risk of a single point of failure. Significant hurdles remain. Developing unlearning methods that scale to large datasets and complex models is a major undertaking.

Beyond the technical challenges, there are also ethical considerations. For instance, how do we ensure that unlearning is used responsibly and does not inadvertently create biases in the remaining data. By addressing these issues, the field can move closer to creating truly privacy-preserving machine learning systems, where data can be learned, forgotten, and re-used with confidence.