Protecting the Undeleted in Machine Unlearning

Let us reconsider the median example, with the goal of releasing an approximate median rather than the exact median. Specifically, consider an algorithm that given a dataset $D$ returns a differentially private (DP) approximation for the median. This breaks the attack described in Section 1.1, as it prevents the attacker from directly learning information about the remaining points from their DP median. Still, by deleting more and more points the attacker gets to see more and more releases (approximate medians), which together might allow it to infer information about the remaining points. If we were to ensure that all releases together satisfy DP, as in the continual observation model of Dwork et al. [10], then this would provably prevent such an attack. However, this can come at a high price in terms of utility. Specifically, Jain et al. [19] presented problems that can be solved efficiently with differential privacy in the single shot setting (where only one output is released), but not in the continual setting, where the input dataset evolves over time and DP must be preserved across all outputs together.

We now briefly describe a variant of one of the attacks of Jain et al. [19], tailored to our setting. Essentially, the only conceptual modification from the attacks presented by Jain et al. [19] is that we highlight the fact that it is not just that DP cannot be maintained in this continual setting, but it is in fact the privacy of “undeleted” points that get compromised.⁵⁵5This also holds in the attacks of Jain et al. [19], but not explicit as this was not their focus; they aimed to show that the error must be large as a function of the size of the evolving dataset (which includes both the deleted and undeleted elements in our context). This will not yet result in the attack described in Theorem 2 as the number of users that the attacker needs to control will be relatively large. Consider the following problem: Given a multiset $T\subseteq [n]$, the goal is to return an approximation to

where ${\mathrm{count}}_T(i)$ is the number of occurrences of $i$ in $T$. Note that $\mathrm{CountMod}$ is a function of sensitivity 1, and hence could be approximated with DP (in the single shot setting) with error roughly $1/\epsilon$.

Now consider a dataset (multiset) $T=D\cup S\subseteq [n]$, where $D$ is a random subset of $[n]$ of size $n/2$, and where $S$ is the multiset of size $3n^2$ containing $3n$ copies of every $i\in [n]$. We consider an attacker that “controls” $S$ (in the sense that it can request the deletion of points from $S$) and aims to learn the dataset $D$. Now observe that by controlling $S$, the attacker can force any mechanism for $\mathrm{CountMod}$ to provide it with answers to counting queries w.r.t. $D$. In more detail, a counting query is defined via a predicate $q:[n]\to \{0,1\}$, and the value of such a query on $D$ is $q(D)\triangleq {\sum }_{i\in D}q(i)$. Given such a counting query $q$, the attacker acts as follows:

1. 1.

   For every $i\in [n]$ such that $q(i)=1$, request the deletion of 2 copies of $i$ from $S$ (and thus from $T$).

2. 2.

   Obtain a release $a_q\approx \mathrm{CountMod}(T)$. Note that $\mathrm{CountMod}(T)=q(D)$, because, by Step 1, for every $i\in [n]$ such that $q(i)=0$ we have that ${\mathrm{count}}_T(i)\mathrm{mod}\mathrm{\hspace{0.33em}3}\ne 2$, and for every $i\in [n]$ such that $q(i)=1$ we have that ${\mathrm{count}}_T(i)\mathrm{mod}\mathrm{\hspace{0.33em}3}=2$ if and only if $i\in D$.

3. 3.

   For every $i\in [n]$ such that $q(i)=1$, request the deletion of one copy of $i$ from $S$ (and thus from $T$). Note that this “resets” the modifications we did in Step 1 in the sense that for every $i$, its number of occurrences in $S$ is a multiple of 3.

This allows the attacker to obtain answers to (at least) $n$ arbitrary counting queries w.r.t. $D$. This is known to allow the attacker to reconstruct $D$ unless the approximation error is $\mathrm{\Omega }(\sqrt{n})$ by the results of [11].

As we mentioned, definitions that aim to mimic/approximate the behavior of perfect retraining are susceptible to “differencing attacks”, such as the simple counting example, where seeing two consecutive releases (before and after a deletion) allows the attacker to learn the deleted point. We now present simple generalizations of this attack that extend to other types of definitions:

1. 1.

   Consider a learning algorithm $𝒜$ that takes a dataset $D$ containing $n$ numbers, represented in binary (say using $d$ bits). The algorithm ignores the data and returns a random binary vector of length $d$, denoted as $z$. Next, upon receiving a request to delete a point $x$, the algorithm deletes $x$ from the data and returns $z\oplus x$. This, of course, allows the same “differencing attack”. However, note that now the marginal distribution of every single release given by the algorithm is simply uniform over $d$-bit vectors, independent of the data. This shows that definitions that only argue about every single time step individually, like the definition of Chourasia and Shah [6] mentioned above, can be vulnerable to differencing attacks even if they require that the distribution of every release is independent of the data.⁶⁶6For this we need to assume that either the curator is allowed to hold a state (the vector $z$), or that the deletion algorithm receives an input both the point to be deleted (the point $x$) and the previous release (the vector $z$ in our case).

2. 2.

   Somewhat artificially, a similar attack could be leveraged to reveal information about “undeleted” points. The attack begins the same, with the initial release being a random $d$-bit vector $z$. Next, upon receiving a request to delete a point $x$, the algorithm deletes $x$ from the data, samples a random point $y$ from the remaining data points, and returns $z\oplus y$.

We start with the simplest variant of our definition that handles non-adaptive attackers who decide on the sequence of deletions ahead of time. To simplify the presentation, we do not distinguish between the “algorithm” and the “curator” and consider one stateful algorithm $𝒜$ with the following syntax. Initially $𝒜$ is executed on a dataset $D$ and outputs an initial output $z_0\leftarrow 𝒜(D)$. Then, for $k$ rounds $i=1,2,\mathrm{\dots },k$, algorithm $𝒜$ obtains a point $y_i\in D$ and returns a modified output $z_i\leftarrow 𝒜(D,y_1,\mathrm{\dots },y_i)$. The mindset is that $z_i$ represents the result of “deleting” $y_i$ from $D$, but this is not part of the formal definition. We also write $(𝒜(D),𝒜(D,y_1),𝒜(D,y_1,y_2),\mathrm{\dots },𝒜(D,y_1,y_2,\mathrm{\dots },y_k))$ to denote the vector of outcomes obtained by running $𝒜$ on $D$ and then “deleting” one by one the points $y_1,\mathrm{\dots },y_k$.⁷⁷7We stress that algorithm $𝒜$ can have an internal state, which is omitted from this vector notation for simplicity.

In words, there is a simulator that takes only the initial output $𝒜(D)$ and the values of the deleted points $(y_1,\mathrm{\dots },y_{k^{\prime }})$, and can simulate the entire sequence of updated outputs generated by $𝒜$. Intuitively, this formalizes the goal stated above: an attacker observing the entire sequence of unlearning updates learns nothing more about the remaining dataset than what they could already compute themselves from the initial release and the deleted values.

We now extend the definition to the case where an attacker $ℬ$ can adaptively decide on the order of deletions. The attacker is static in the sense that the points it controls (and is allowed to delete) are predetermined. We assume that there are no other deletions in the game. In addition, the attacker might possess some side-information about the other points in the dataset $D$, which we denote as $\mathrm{SideInfo}(D)$. Formally, for a dataset $D=(x_1,\mathrm{\dots },x_n)$, a set $Y\subseteq [n]$ of size $k^{\prime }\le k$ denoting the indices of the points in $D$ controlled by $ℬ$, and a side-information function $\mathrm{SideInfo}$, we consider the following game between algorithm $𝒜$ and the attacker $ℬ$:

$\underset{¯}{\mathrm{𝐒𝐭𝐚𝐭𝐢𝐜𝐆𝐚𝐦𝐞}\mathbf{(}𝓐\mathbf{,}𝑫\mathbf{=}\mathbf{(}{𝒙}_{\mathrm{𝟏}}\mathbf{,}\mathbf{\dots }\mathbf{,}{𝒙}_{𝒏}\mathbf{)}\mathbf{,}𝓑\mathbf{,}𝒀\mathbf{\subseteq }\mathbf{[}𝒏\mathbf{]}\mathbf{,}\mathrm{𝐒𝐢𝐝𝐞𝐈𝐧𝐟𝐨}\mathbf{)}\mathbf{:}}$

1. 1.

   Let $z_0\leftarrow 𝒜(D)$.

2. 2.

   The attacker $ℬ$ obtains the controlled points ${D|}_Y\triangleq \{(i,x_i):i\in Y\}$, the side-information $\mathrm{SideInfo}(D)$, and the initial output $z_0$.

3. 3.

   For $\mathrm{\ell }=1,2,\mathrm{\dots },|Y|$:

   1. (a)

      The attacker $ℬ$ chooses an index $j_{\mathrm{\ell }}\in Y\setminus \{j_1,j_2,\mathrm{\dots },j_{\mathrm{\ell }-1}\}$

   2. (b)

      Algorithm $𝒜$ receives a deletion request for the point $x_{j_{\mathrm{\ell }}}$ and returns an updated output $z_{\mathrm{\ell }}$, which is given to $ℬ$.

4. 4.

   The attacker $ℬ$ outputs its view of the interaction, which includes its internal randomness, the indices of the controlled points $Y$, its side-information $\mathrm{SideInfo}(D)$, and all the outputs it received from $𝒜$ during the interaction.

Note that any algorithm $𝒜$ that satisfies Definition 7 also satisfies Definition 5, i.e., Definition 7 is (perhaps) harder to obtain. This holds by taking $ℬ$ to be the attacker that fixes the ordering of the deletions from $Y$ before the interaction begins, and setting $\mathrm{SideInfo}$ to be empty.

In the previous two definitions, the set of indices/points that the attacker controlled was fixed ahead of time. We now handle the case where the attacker can dynamically choose the indices to control and delete. So now $Y$, the set of indices controlled by the attacker, is not fixed in advance. It is initially empty, and throughout the execution, the attacker dynamically decides on indices from $[n]$ to “corrupt”. Once corrupted, these indices are added to $Y$. Formally, given a dataset $D=(x_1,\mathrm{\dots },x_n)$ we consider the following game between a stateful algorithm $𝒜$ and an attacker $\widehat{ℬ}$ with side-information function $\mathrm{SideInfo}$. This game has two modes, parameterized by the bit $b\in \{0,1\}$, where $b=0$ corresponds to a “real world” execution in which the attacker learns the sequence of modified outputs of $𝒜$ after every deletion, and where $b=1$ corresponds to an “ideal world” execution in which this information is hidden from the attacker.

$\underset{¯}{{\mathrm{𝐃𝐲𝐧𝐚𝐦𝐢𝐜𝐆𝐚𝐦𝐞}}_{𝒃}\mathbf{(}𝓐\mathbf{,}\widehat{𝓑}\mathbf{,}𝑫\mathbf{=}\mathbf{(}{𝒙}_{\mathrm{𝟏}}\mathbf{,}\mathbf{\dots }\mathbf{,}{𝒙}_{𝒏}\mathbf{)}\mathbf{,}\mathrm{𝐒𝐢𝐝𝐞𝐈𝐧𝐟𝐨}\mathbf{)}\mathbf{:}}$

1. 1.

   Let $\mathrm{\ell }=0$ and $z_0\leftarrow 𝒜(D)$.

2. 2.

   The attacker $\widehat{ℬ}$ obtains $\mathrm{SideInfo}(D)$ and the initial output $z_0$.

3. 3.

   Initiate $Y=R=\mathrm{\varnothing }$. % Here $Y$ denotes the set of indices controlled by the attacker, and $R$ denotes the indices it had already deleted.

4. 4.

   While and the attacker $\widehat{ℬ}$ has not ended the loop:

   1. (a)

      Set $\mathrm{\ell }\leftarrow \mathrm{\ell }+1$.

   2. (b)

      The attacker $\widehat{ℬ}$ chooses a set of indices $I_{\mathrm{\ell }}\subseteq [n]$, possibly empty, under the restriction that $|Y\cup I_{\mathrm{\ell }}|\le k$, and learns $x_i$ for every $i\in I_{\mathrm{\ell }}$. Set $Y\leftarrow Y\cup I_{\mathrm{\ell }}$.

   3. (c)

      The attacker $\widehat{ℬ}$ chooses a set of indices $J_{\mathrm{\ell }}\subseteq Y\setminus R$, possibly empty. Set $R\leftarrow R\cup J_{\mathrm{\ell }}$.

   4. (d)

      If $b=0$ and $J_{\mathrm{\ell }}\ne \mathrm{\varnothing }$ then $𝒜$ receives a deletion request for the points in $J_{\mathrm{\ell }}$ and returns an updated output $z_{\mathrm{\ell }}$, which is given to the attacker. If $b=1$, do nothing.

   5. (e)

      The attacker $\widehat{ℬ}$ chooses whether to continue or to end the loop.

5. 5.

   The attacker $\widehat{ℬ}$ outputs $v$. % In a “real world” execution, where $b=0$, this $v$ can be thought of as the view of the attacker $\widehat{ℬ}$ at the end of the execution. However, in an “ideal world” execution, where $b=1$, we think of $\widehat{ℬ}$ as a simulator that aims to simulate some other attacker, and so the value $v$ is not necessarily the view of $\widehat{ℬ}$ itself, but rather a “simulated view” that should correspond to the view of the simulated attacker at the end of a real world execution.

6. 6.

   The output of the game is $(Y,v)$. % We include $Y$ in the output of the game to force the simulator (when $b=1$) to choose its corruptions similarly to the real world attacker (when $b=0$). Otherwise, for example, the simulator could corrupt $k$ indices and use them to simulate a real-world attacker that only corrupts $k/2$ indices.

Note that any algorithm $𝒜$ that satisfies Definition 8 also satisfies Definition 7, i.e., Definition 8 is (perhaps) harder to obtain. This holds by taking $ℬ$ to be the attacker that fixes the set $Y$ before the interaction begins.

Suppose that we are interested in an algorithm that initially takes a dataset $D$ containing $n$ elements from a domain $X$ and releases an approximation $z_0$ to the median of $D$. Then, for $k$ rounds, the algorithm receives the $i$-th deletion request and outputs a modified answer $z_i$. We evaluate the approximation of the median for the (remaining) data at any given moment using its rank error. That is, if the current dataset is $D_i$ and the algorithm returns an answer $z_i$, then the error of $z_i$ w.r.t. $D_i$ is defined as

We aim to design an algorithm for approximating the median, while satisfying our security definition, that guarantee small worst-case error across all their $(k+1)$ releases. Naively, one could solve this task by first computing and releasing the exact median, and then ignoring all deletion requests. This stateless algorithm satisfies our security definition and guarantees error at most $k$ deterministically. Alternatively, we could extend Example 10 to this setting as follows.

Example 12 suggests the following informal recipe for fitting a functionality $f$ to our framework:

1. (1)

   Identify a set of sufficient statistics for the function $f$.

2. (2)

   Estimate these statistics with differential privacy.

3. (3)

   Throughout the execution, maintain these statistics as a function of the deleted points.

Of course, this recipe is only useful when the set of sufficient statistics we identify is compatible with differential privacy. It turns out that this is indeed the case for some functionalities that were studied by prior work on machine unlearning.

In particular, Cao and Yang [3] presented the following “SQ framework” for machine unlearning: Let $f$ be any function which can be computed in the non-adaptive statistical query (SQ) model. That is, there exists a collection of predicates $C$ such that for any dataset $D$, the value of $f(D)$ can be computed by post-processing ${\{{\sum }_{x\in D}c(x)\}}_{c\in C}$, i.e., the sum of each of the predicates in $C$ on the elements in $D$. As Cao and Yang [3] showed, tracking ${\{{\sum }_{x\in D}c(x)\}}_{c\in C}$ throughout the execution allows us to maintain the current value of $f$ without recomputing it from scratch. When $|C|$ is relatively small, this results in an efficient algorithm for perfect retraining. This SQ framework is particularly suited for our definition, as computing the initial values of ${\{{\sum }_{x\in D}c(x)\}}_{c\in C}$ can be done in a DP manner (again, assuming that $|C|$ is small). Afterwards, as in Examples 10 and 12, we could update these values as a function of the deleted points alone.