# Control, Confidentiality, and the Right to be Forgotten

Aloni Cohen Department of Computer and Data Science, University of Chicago.
<EMAIL_ADDRESS>Adam Smith Department of Computer Science, Boston
University<EMAIL_ADDRESS>Marika Swanberg Department of Computer Science,
Boston University<EMAIL_ADDRESS>Prashant Nalini Vasudevan Department of
Computer Science, National University of Singapore<EMAIL_ADDRESS>
###### Abstract

Recent digital rights frameworks stipulate an ability (e.g., the “right to be
forgotten” embodied in the GDPR and CCPA) to request that a data
controller—roughly, any system that stores and manipulates personal
information— _delete_ one’s data.

We ask how deletion should be formalized in complex systems that interact with
many parties and store derivative information. There are two broad principles
at work in existing approaches to formalizing deletion: _confidentiality_ and
_control_.

We build a unified formalism for deletion that encompasses previous approaches
as special cases. We argue that existing work on deletion-as-control (in
particular, “machine unlearning”) can be reframed in the language of
(adaptive) history independence, for which we provide a general definition. We
also show classes of controllers, such as those that publish differentially
private statistics without later updating them, that satisfy intuitive notions
of deletion and our formal definition, but which fall outside the scope of
previous approaches.

###### Contents

  1. 1 Introduction
    1. 1.1 Defining deletion-as-control
    2. 1.2 Examples and relation to prior work
  2. 2 Preliminaries
  3. 3 Deletion-as-control
    1. 3.1 Parties and simplified execution model
    2. 3.2 Definition
      1. 3.2.1 Discussion
    3. 3.3 Real and ideal executions in detail
  4. 4 History Independence and Deletion-as-control
    1. 4.1 History independence
      1. 4.1.1 Strongly History Independent Dictionaries
    2. 4.2 Adaptive History Independence (AHI)
    3. 4.3 AHI and Deletion-as-Control
    4. 4.4 Relating Prior Definitions of Machine Unlearning to (Adaptive) History Independence
  5. 5 Deletion-as-confidentiality and Deletion-as-control
    1. 5.1 Definition
    2. 5.2 Control vs. Confidentiality
  6. 6 Differential Privacy and Deletion-as-control
    1. 6.1 Batch differential privacy
    2. 6.2 Adaptive pan-privacy with continual release
    3. 6.3 From pan-privacy to deletion-as-control
    4. 6.4 Examples of Pan-private Controllers
      1. 6.4.1 Counters
      2. 6.4.2 Learning under Pan-Private Continual Release (and with Deletion)
  7. 7 Parallel Composition
  8. A Lemmas on Couplings and Marginal Distributions
  9. B Differential Privacy Preliminaries
  10. C Strong History Independence and Deletion-as-control

> Someday, this baby and other babies from her cohort will be 30 and there
> will be an absolutely bananas cache of data about what form and hue their
> poops took. Maybe someone will hack it and it will derail a presidential
> campaign news cycle.
>
> Alexandra Petri, from “What I’ve been up to the last four months”

##  1 Introduction

The long-term storage of modern data collection carries serious risks.
Sensitive data can be disclosed through data breaches (Fowler, 2022), large
language models (Carlini et al., 2021), official statistics (JASON, 2022),
interactive systems (Cohen and Nissim, 2020), or sale to law enforcement (Ng,
2022; Kaste, 2022). But there are risks beyond disclosure, such as
manipulation, chilling of free speech due to surveillance, and epistemic
bubbles. The permanence of our digital footprints may chill expression, with
every word weighed against the looming risk of out-of-context blowback in the
indefinite future.

Over the past few years, data protection laws around the world have begun to
challenge this permanence, giving individuals more control over their data.
For example, EU’s General Data Protection Regulation provides an individual
_data subject_ the right to request “the erasure of personal data concerning
him or her” and delineates when a _data controller_ must oblige. Similarly,
the more recent California Consumer Privacy Act provides an individual
consumer the right to “request that a business delete any personal information
about the consumer.”

In the modern data ecosystem, however, it is not easy to articulate what
constitutes such “erasure” of personal data. If data were merely stored in
databases, it could be erased by deleting some records. The environment today,
however, is much more dynamic—data is used to train machine learning models,
compute statistics, some of which may be published, etc Veale et al. (2018b).

We examine what “erasure of personal data” means in this complex environment.
We provide a formulation that unifies and generalizes previous technical
approaches that only partially answer this question, including so-called
_machine unlearning_. Though we make no attempt to strictly adhere to any
specific legal right to erasure, we aim to incorporate more of its contours
than prior technical work on erasure.

Our primary contribution is a formalization of _deletion-as-control_ in
contrast to _deletion-as-confidentiality_ , building on the legal scholarship
of Veale et al. (2018a). Informally, _confidentiality_ requires that parties
other than the controller should be unable to tell whether a data subject
Alice requested erasure from the controller or simply never interacted with
the controller in the first place. This implies, among other things, that
Alice’s erased data is confidential from the other parties, and was so even
before Alice requests its erasure. Such a confidentiality-style approach to
deletion is well suited for certain applications: for example, a private
cloud-storage provider that does not allow any sort of file sharing. This
notion of deletion aligns neatly with cryptographic real/ideal-style
definitions and was explored by Garg, Goldwasser, and Vasudevan (Garg et al.,
2020).

The drawback of deletion-as-confidentiality is that it precludes inherently
social functionalities. Consider a public bulletin board which allows Alice to
post messages for all to see. No controller implementing such a bulletin board
could ever satisfy (Garg et al., 2020)’s definition, because the worlds in
which any given person does or doesn’t post a message are trivially and
inherently distinguishable by an outside observer.

We propose _deletion-as-control_ as a more relaxed notion that allows social
functionalities while still guaranteeing meaningful erasure of data. Here, the
purpose is not so much to hide data from others as to exercise control over
what the data is used for. Until Alice requests erasure, deletion-as-control
should not limit the controller’s usage of her data. But after erasure, the
data controller’s future behavior and internal state should not depend on
Alice’s data _except insofar as that data has already affected other parties
in the world_. In this way, Alice’s autonomy need not imply secrecy; she has a
say about how her data is used regardless of past or future disclosure. A
bulletin board could satisfy deletion-as-control by erasing all traces of
Alice’s data from its servers. Some other party may have recorded Alice’s data
before it was erased, but if not, they can no longer learn anything about it
that they did not already know before the erasure.

Defining deletion-as-control in a way that is both expressive and meaningful
is the central challenge of our work. Our definition unifies and generalizes
three very different approaches to data deletion: deletion-as-confidentiality,
machine unlearning, and differential privacy.

##### Technical contributions and organization

Section 3

We give a new definition of deletion-as-control which applies to general data
controllers and interaction patterns among parties, building on the modeling
of (Garg et al., 2020). Our definition captures meaningful guarantees in a
wider variety of settings than prior approaches (see discussion in Section
1.2).

Section 4

We connect deletion-as-control to the machine unlearning literature by way of
_history independence_ (Micciancio, 1997; Naor and Teague, 2001). An
implementation of a data structure is history independent if its memory
representation reveals nothing more than the logical state of the data
structure. Such implementations necessarily forget data that was deleted, and
are instrumental in constructing controllers that provide deletion guarantees.

We define an approximate and adaptive generalization of history independence
(AHI). We then prove that, roughly, AHI implies deletion-as-control. We also
show how existing definitions of machine unlearning are weakenings of AHI.

Section 5

We prove that any controller that satisfies deletion-as-confidentiality as
defined by (Garg et al., 2020) also satisfies our definition of deletion-as-
control (with some restrictions due to differences in modelling). This bears
out the natural intuition about the relationship between these notions.

Section 6

We describe two ways of compiling differentially private mechanisms into
controllers satisfying deletion-as-control. The first applies to DP mechanisms
that are run in a batch setting on a single, centralized dataset (e.g., query
release). The second applies to mechanisms satisfying an adaptive variant of
_pan-privacy under continual release_ Chan et al. (2011); Dwork et al.
(2010b); Jain et al. (2021).

Appendix 7

We describe a controller that satisfies deletion-as-control but neither
history independence, confidentiality, nor differential privacy. To do so, we
prove that deletion-as-control enjoys a limited form of _parallel
composition_.

###  1.1 Defining deletion-as-control

We define deletion-as-control in a way that allows arbitrary use of a person’s
data before deletion (but not after). The challenge is to provide meaningful
privacy guarantees despite this feature, even in a general setting with an
adaptive and randomized data controller, data subject (Alice), and environment
(representing all parties other than the data controller and distinguished
data subject). This setting is adapted from (Garg et al., 2020).

Our proposal is that after deletion, the data controller should be able to
produce a plausible alternate explanation for its current state that is free
of the deleted Alice’s participation. More specifically, _the state of the
controller after deletion can be plausibly attributed to the interaction
between the controller and the environment alone_. By this we mean that the
state is about as likely—with probability taken over the controller’s random
coins—in the real world as in the hypothetical ‘ideal’ world where the
environment’s messages to the controller are unchanged but where Alice does
not interact with the controller whatsoever. The result is that, after
deletion, the controller’s state depends on the interaction with Alice only
insofar as that interaction affected other parties’ interactions with the
controller.

Importantly, we only require that the controller’s state is plausible in the
ideal world _given_ the messages sent by the environment. _We do not require
the environment’s messages themselves to be plausible in the ideal world._ For
example, suppose, on a public bulletin board, Bob simply copies and reposts
Alice’s posts. Bob’s messages in the ideal world would still contain Alice’s
posts, even though Alice is completely absent in the hypothetical ideal world.
This is unavoidable—we want to allow the controller and the environment to use
the subject’s data arbitrarily before deletion, so the environment’s queries
may depend (directly or indirectly) on the data subject’s inputs.

In a bit more detail, our definition compares real and ideal worlds defined in
a non-standard way.111The non-real world is more ‘hypothetical’ or ‘counter-
factual’ than ‘ideal.’ Regardless, we use the term ‘ideal world’ for
continuity with (Garg et al., 2020) and decades of cryptography. The real
world execution, denoted $\langle\mathsf{C},\mathsf{E},\mathsf{Y}\rangle$,
involves three parties: a data controller $\mathsf{C}$, a special data subject
$\mathsf{Y}$, and an environment $\mathsf{E}$ representing all other parties.
The execution ends after $\mathsf{Y}$ requests deletion and $\mathsf{C}$
processes the request. The real execution specifies (i) $\mathsf{C}$’s state
$\mathsf{state}_{\mathsf{C}}$, (ii) the _queries_
$\vec{\mathsf{q}}_{\mathsf{E}}$ sent by $\mathsf{E}$ to $\mathsf{C}$, and
(iii) the randomness $R_{\mathsf{C}}$ used by $\mathsf{C}$. The ideal world
execution, denoted
$\langle\mathsf{C}(R^{\prime}_{\mathsf{C}}),\mathsf{D}(\vec{\mathsf{q}}_{\mathsf{E}})\rangle$,
involves the the same controller $\mathsf{C}$ and a dummy environment
$\mathsf{D}$ that simply replays the queries $\vec{\mathsf{q}}_{\mathsf{E}}$.
The ideal world randomness $R^{\prime}_{\mathsf{C}}$ is sampled by a simulator
$\mathsf{Sim}(\vec{\mathsf{q}}_{\mathsf{E}},R_{\mathsf{C}},\mathsf{state}_{\mathsf{C}})$.
The ideal execution specifies (i) $\mathsf{C}$’s ideal state
$\mathsf{state}^{\prime}_{\mathsf{C}}$, and (ii) the simulated randomness
$R^{\prime}_{\mathsf{C}}$ used by $\mathsf{C}$.

######  Definition 1.1 ($(\epsilon,\delta)$-deletion-as-Control (simplified)).

Given $\mathsf{C}$, $\mathsf{E}$, $\mathsf{Y}$, and $\mathsf{Sim}$, consider
the following experiment. Sample $R_{\mathsf{C}}\leftarrow\\{0,1\\}^{*}$; run
the real execution
$(\vec{\mathsf{q}}_{\mathsf{E}},\mathsf{state}_{\mathsf{C}})\leftarrow\langle\mathsf{C}(R_{\mathsf{C}}),E,\mathsf{Y}\rangle$;
sample
$R^{\prime}_{\mathsf{C}}\leftarrow\mathsf{Sim}(\vec{\mathsf{q}}_{\mathsf{E}},R_{\mathsf{C}},\mathsf{state}_{\mathsf{C}})$;
and run the ideal execution
$(\vec{\mathsf{q}}^{\prime}_{\mathsf{E}},\mathsf{state}^{\prime}_{\mathsf{C}})\leftarrow\langle\mathsf{C}(R^{\prime}_{\mathsf{C}}),\mathsf{D}(\vec{\mathsf{q}}_{\mathsf{E}})\rangle$.

We say a controller $\mathsf{C}$ is _$(\epsilon,\delta)$ -deletion-as-control
compliant_ if there exists $\mathsf{Sim}$ such that for all $\mathsf{E}$ and
$\mathsf{Y}$: (i) $R^{\prime}_{\mathsf{C}}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ R_{\mathsf{C}}$;
(ii) $\mathsf{state}^{\prime}_{\mathsf{C}}=\mathsf{state}_{\mathsf{C}}$ with
probability at least $1-\delta$.

###  1.2 Examples and relation to prior work

We discuss three prior approaches for defining data deletion: deletion-as-
confidentiality, simulatable deletion, and machine unlearning. For
understanding our and prior approaches to data deletion, it is helpful to have
in mind a few concrete examples of functionalities captured by deletion-as-
control. We briefly describe these touchstone functionalities and then use
them to discuss the prior approaches to data deletion. The terms ‘deletion-as-
confidentiality’ and ‘simulatable deletion’ are new. We introduce them to
clearly distinguish the definitions from each other and from our own.

Private Cloud Storage (Theorem 4.8)

Users can upload files for cloud storage and later download. Only the
originating user may download a file and the files are never used in any other
way. The existence of files is only ever made known to the originating user,
and the controller publishes no other information. To remove a user, the
controller deletes all the user’s files from its internal storage.

Public Bulletin Board (Theorem 4.8)

Users can submit posts to the public bulletin board. The bulletin board simply
displays all user posts currently in the controller’s internal storage, with
no other functionalities (e.g. responding, messaging, etc.). To remove a user,
the controller deletes all of the user’s posts from its internal storage and,
as a result, from the public-facing bulletin board.

DP Machine Learning (Prop. 6.1)

Users contribute data during some collection period. At the end of the period,
the data controller uses differentially private SGD (with strong privacy
parameters, say $\epsilon\ll 1$, $\delta\ll 10^{-20}$) to train a model on the
resulting dataset. After training, the dataset is deleted and the data
controller publishes the model. To remove a user, the controller does
nothing—it simply ignores deletion requests.

Public Directory + DP stats (Thms 6.8, 7.4)

Users upload their name and phone number to be listed in a directory. The data
controller allows anybody to search for a listing in the directory, and each
week reports a differentially private estimate of the number of distinct users
that have looked up a phone number so far (or equivalently, the weekly count
of new users). To remove a user, the controller deletes their listing from the
public directory and its associated data structures, but leaves the data
structures for the DP user statistics unaltered.

Each of the above can be made to satisfy deletion-as-control with the
appropriate use of _history independence (HI)_ and _differential privacy
(DP)_. Neither are solution concepts per se, but they are intimately connected
with deletion. Definitions of deletion that constrain the controller’s
state—deletion-as-control, deletion-as-confidentiality, and simulatable
deletion—all use HI as a crucial ingredient in feasibility results. Moreover,
the machine unlearning literature can be seen as considering specialized
versions of HI. There is also a clear intuitive connection between DP and
deletion. DP provides that the output distribution is not affected too much by
the inclusion or exclusion of any single data subject, say Alice. If Alice had
(approximately) no effect on the DP computation, then deletion should require
no additional work—she is (approximately) deleted from the outset.

Deletion-as-confidentiality

Garg et al. (2020) define a confidentiality-based notion of the right to
erasure for general data controllers. They require that the deleted data
subject Alice leaves (approximately) no trace: the whole view of the
environment along with the state of the controller after deletion should be as
if Alice never existed. The strength of this definition is its strong,
intuitive, interpretable guarantee. But its weakness is that it rules out too
many meaningful functionalities. The stringent indistinguishability
requirement forbids any functionality where users learn about each other.
Versions of the cloud storage and DP machine learning functionalities can
satisfy the definition, using history independence (cf. Section 4). But the
bulletin board and directory are antithetical to deletion-as-confidentiality.
If Bob ever looks up Alice’s messages, confidentiality is impossible.

Simulatable deletion

Godin and Lamontagne (2021) seek to relax deletion-as-confidentiality in order
to capture more functionalities. This definition requires only that the
controller’s state after deletion is simulatable given the environment’s view.
As a result, any information that Bob has already learned about Alice may be
retained indefinitely by the controller. So while versions of cloud storage
and the bulletin board satisfy simulatable deletion using history independence
(cf. Section 4), at least in the latter case the guarantee is all but
meaningless. The bulletin board need not delete Alice’s posts if they have
ever been read!222(Godin and Lamontagne, 2021) actually considers a version of
bulletin board functionality for which simulatable deletion is meaningful.
Crucially, their bulletin board does not track whether a post has been read,
and hence their controller must actually delete Alice’s posts. But if the
bulletin board keeps read receipts, say, it would not have to delete any post
that has ever been read. _More_ tracking would require _less_ deletion.
Moreover, it appears that DP machine learning and the directory with DP
statistics cannot satisfy simulatable deletion. For technical reasons, Godin
and Lamontagne (2021) require data controllers to only use _public_
randomness—ruling our differentially private functionalities.

Machine Unlearning

This recent line of work specializes the question of deletion to the setting
of machine learning. Given a model
$\vec{\theta}\leftarrow\mathsf{Learn}({\vec{x}})$ and a data point
$x^{*}\in{\vec{x}}$, machine unlearning requires sampling a new model
$\theta^{\prime}\leftarrow\mathsf{Unlearn}(\vec{\theta},x^{*},{\vec{x}})$
approximately from the distribution
$\mathsf{Learn}({\vec{x}}\setminus\\{x^{*}\\})$. As retraining from scratch is
always an option, the primary consideration is speed. Machine unlearning does
not allow the DP machine learning functionality as described above. To see
why, consider ${\vec{x}}$ of size $n$ and suppose all $n$ people request
deletion. Machine unlearning would require the final model $\theta^{*}$ be
essentially trivial—it should perform about as well as a the model
$\theta_{0}$ trained on an empty dataset. With the DP learner described above,
$\theta^{*}$ performs just as well as the initial model $\theta$. As for the
other functionalities, machine unlearning does not consider general
interactive functionalities: controllers implementing cloud storage, bulletin
board, and directory with statistics are ruled out. On the other hand, the
concept underpinning machine unlearning—history independence—is more flexible.

Figure 1: Overview of the relationships between definitions and the roles of
specific example controllers.

##  2 Preliminaries

We consider a notion of similarity of distributions closely related to
differential privacy (Appendix B).

######  Definition 2.1.

Given parameter $\epsilon\geq 0$ and $\delta\in[0,1)$, we say two probability
distributions $P$ and $Q$ on the same set ${\mathcal{X}}$ are
_$(\epsilon,\delta)$ -indistinguishable_ and write $P\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ Q$ if, for every
event $E\subseteq{\mathcal{X}}$,

$P(E)\leq e^{\epsilon}Q(E)+\delta\ \text{and}\ Q(E)\leq
e^{\epsilon}P(E)+\delta\,.$

Slightly overloading this notation, we say two random variables $X$ and $Y$
taking values in some output space ${\mathcal{X}}$ are _$(\epsilon,\delta)$
-indistinguishable_, denoted $X\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ Y$ if, for every
event $E\subseteq{\mathcal{X}}$,

$\displaystyle\Pr[X\in E]\leq e^{\epsilon}\Pr[Y\in E]+\delta\ \text{and,}$
$\displaystyle\Pr[Y\in E]\leq e^{\epsilon}\Pr[X\in E]+\delta\,.$

We present some further technical tools in the appendices: a novel coupling
lemma for this notion of indistinguishability (Appendix A) as well as
background on differential privacy (Appendix B).

##  3 Deletion-as-control

We define deletion-as-control in a way that allows arbitrary use of a person’s
data before deletion, but not after. Under such a definition, an adversary
might completely learn the data before it is deleted, and even make it
available after it is deleted! The challenge is to provide a meaningful
guarantee despite this limitation, even in a general setting with adaptive and
randomized data controllers, data subjects, and environments (representing all
parties other than the data controller and distinguished data subject).

###  3.1 Parties and simplified execution model

Our definition uses the real/ideal paradigm from cryptographic definitions,
though not with a typical indistinguishability criterion. (See Section 3.3)
The real world execution, denoted
$\langle\mathsf{C},\mathsf{E},\mathsf{Y}\rangle$, involves three (possibly
randomized) parties: a data controller $\mathsf{C}$, an environment
$\mathsf{E}$, and a special data subject $\mathsf{Y}$. The real interaction is
arbitrary, limited only by the execution model described below. Parties have
authenticated channels over which they may interact freely. While $\mathsf{Y}$
has only a single channel to $\mathsf{C}$, the environment has an unbounded
number of channels (representing unbounded additional parties). While these
channels are authenticated, the controller cannot distinguish the single
channel to $\mathsf{Y}$ from those to $\mathsf{E}$. The interaction continues
until the data subject $\mathsf{Y}$ requests deletion, ending after the data
controller $\mathsf{C}$ processes the request. We denote by
$\mathsf{state}_{\mathsf{C}}$ the final state of the controller.

The ideal world execution, denoted $\langle\mathsf{C},\mathsf{D}\rangle$,
involves the interaction of the same controller $\mathsf{C}$ as well as a
dummy environment $\mathsf{D}$. $\mathsf{D}$ takes as input the transcript
from the real execution, denoted $\tau$, and simply replays only
$\mathsf{E}$’s queries, denoted $\vec{\mathsf{q}}_{\mathsf{E}}$. Observe that
$\mathsf{C}$’s responses and state in the ideal world are not fixed. They
depend on $\mathsf{C}$’s ideal-world randomness, denoted
$R^{\prime}_{\mathsf{C}}$. Moreover, the ideal interaction is defined relative
to a particular instantiation of the real world interaction. In particular,
the queries $\vec{\mathsf{q}}_{\mathsf{E}}$ may depend on $\mathsf{C}$’s real-
world randomness, denoted $R_{\mathsf{C}}$.

The controller’s real-world randomness $R_{\mathsf{C}}$ consists of uniformly
random bits. We denote the distribution of uniform bits $\mathcal{U}$. In the
ideal world, a simulator $\mathsf{Sim}$ takes as input
$(\vec{\mathsf{q}}_{\mathsf{E}},R_{\mathsf{C}},\mathsf{state}_{\mathsf{C}})$
and generates $\mathsf{C}$’s ideal-world randomness, which we denote
$R^{\prime}_{\mathsf{C}}$. When we wish to emphasize the controller’s
randomness in the execution, we write
$\langle\mathsf{C}(R_{\mathsf{C}}),\mathsf{E},\mathsf{Y}\rangle$ and
$\langle\mathsf{C}(R^{\prime}_{\mathsf{C}}),\mathsf{D}\rangle$.

An execution involves parties sending messages to each other until some
termination condition is reached. Starting with $\mathsf{E}$ (real) or
$\mathsf{D}$ (ideal), parties get activated when they receive a message, and
deactivated when they send a message. Only a single party is active at a time.
Parties communicate over authenticated channels. Because $\mathsf{E}$
represents all users besides the distinguished data subject $\mathsf{Y}$,
$\mathsf{E}$ has many distinct channels to $\mathsf{C}$. Importantly,
authentication allows parties to know on which channel a message was received,
but not which party (i.e., $\mathsf{E}$ or $\mathsf{Y}$) is on the other end
of that channel. Each party is initialized with a uniform random tape which
may only be read _once_ over the course of the whole execution. If a party
wishes to re-use bits from its randomness tape, it must store them in its
internal $\mathsf{state}$.

The real execution $\langle\mathsf{C},\mathsf{E},\mathsf{Y}\rangle$ ends when
$\mathsf{Y}$ requests deletion from $\mathsf{C}$. The data subject’s delete
message activates the controller, who can then remove $\mathsf{Y}$’s data. The
ideal execution
$\langle\mathsf{C}(R^{\prime}_{\mathsf{C}}),\mathsf{D}(\vec{\mathsf{q}}_{\mathsf{E}})\rangle$
ends after $\mathsf{D}$ sends its last query from
$\vec{\mathsf{q}}_{\mathsf{E}}$ to $\mathsf{C}$. In both cases, the execution
ends after the final activation of $\mathsf{C}$. We consider the controller’s
state at the end of the execution:
$\mathsf{state}_{\mathsf{C}}=\mathsf{C}(\vec{\mathsf{q}}_{\mathsf{E}};R_{\mathsf{C}})$
in the real world, and
$\mathsf{state}^{\prime}_{\mathsf{C}}=\mathsf{C}(\vec{\mathsf{q}}_{\mathsf{E}};R^{\prime}_{\mathsf{C}})$
in the ideal world. If an execution never ends, the state is defined to be
$\bot$.

######  Remark 3.1 (Keeping time).

In Section 6, we need a global clock. Balancing modelling simplicity with
generality, we allow the environment to control time. Specifically, we
introduce a special query tick that $\mathsf{E}$ can send to $\mathsf{C}$
thereby incrementing the clock. As mere mortals cannot control the passage of
time, we do not allow $\mathsf{Y}$ to query tick.

###  3.2 Definition

We require that the internal state of the controller is about as likely in the
real world and the ideal world, where probability is taken over $\mathsf{C}$’s
random coins. Let $\mathsf{state}_{\mathsf{C}}$ and
$\mathsf{state}^{\prime}_{\mathsf{C}}$ be the internal states in the real and
ideal executions. Consider a random variable $R^{\prime}_{\mathsf{C}}$ which
is sampled uniformly conditioned on
$\mathsf{state}^{\prime}_{\mathsf{C}}=\mathsf{state}_{\mathsf{C}}$ in the
ideal execution where $\mathsf{C}$ uses randomness $R^{\prime}_{\mathsf{C}}$.
Informally, our definition requires that the distributions of
$R^{\prime}_{\mathsf{C}}$ and $R_{\mathsf{C}}$ are close:
$R^{\prime}_{\mathsf{C}}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ R_{\mathsf{C}}$.
So we don’t require that the real and ideal executions are themselves
$(\epsilon,\delta)$-indistinguishable. Instead, we require that the
‘explanations’ in the real and ideal executions are
$(\epsilon,\delta)$-indistinguishable—viewing the controller’s randomness as
the explanation of its state (relative to the environment’s queries).

We extend this idea by considering ways of sampling $R^{\prime}_{\mathsf{C}}$
other than the conditional distribution described above. In general, we allow
a simulator $\mathsf{Sim}$ to sample $R^{\prime}_{\mathsf{C}}$ as a function
of the queries $\vec{\mathsf{q}}_{\mathsf{E}}$ from $\mathsf{E}$ to
$\mathsf{C}$, the real-world randomness $R_{\mathsf{C}}$, and the real-world
state $\mathsf{state}_{\mathsf{C}}$. We require that $R^{\prime}_{\mathsf{C}}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ R_{\mathsf{C}}$
and that $\mathsf{state}^{\prime}_{\mathsf{C}}=\mathsf{state}_{\mathsf{C}}$
except with probability $\delta$. Sampling $R^{\prime}_{\mathsf{C}}$
conditioned on
$\mathsf{state}^{\prime}_{\mathsf{C}}=\mathsf{state}_{\mathsf{C}}$ is a
default simulation strategy that we use throughout the paper, but there are
sometimes much simpler ways to sample $R^{\prime}_{\mathsf{C}}$.

Figure 2: The real (left) and ideal (right) executions. The communications
with the controller $\mathsf{C}$ are meant to be “public API” calls (e.g.
accessing a public website, possibly using login credentials). Notice that the
dummy environment in the ideal world sends message
$\vec{\mathsf{q}}_{\mathsf{E},i}$ regardless of what the previous responses
were.

######  Definition 3.2 (Deletion as control).

Given a controller $\mathsf{C}$, an environment $\mathsf{E}$, a data subject
$\mathsf{Y}$ and a simulator $\mathsf{Sim}$, we consider the following
experiment:

  * •

$R_{\mathsf{C}}\sim\mathcal{U}$

  * •

$(\tau,\mathsf{state}_{\mathsf{C}})\leftarrow\langle\mathsf{C}(R_{\mathsf{C}}),E,\mathsf{Y}\rangle$,
where $\vec{\mathsf{q}}_{\mathsf{E}}\subseteq\tau$ are the messages from
$\mathsf{E}$ to $\mathsf{C}$.

  * •

$R^{\prime}_{\mathsf{C}}\leftarrow\mathsf{Sim}(\vec{\mathsf{q}}_{\mathsf{E}},R_{\mathsf{C}},\mathsf{state}_{\mathsf{C}})$

  * •

$(\tau^{\prime},\mathsf{state}^{\prime}_{\mathsf{C}})\leftarrow\langle\mathsf{C}(R^{\prime}_{\mathsf{C}}),\mathsf{D}(\vec{\mathsf{q}}_{\mathsf{E}})\rangle$

We say a controller $\mathsf{C}$ is _$(\epsilon,\delta)$ -deletion-as-control
compliant_ if there exists $\mathsf{Sim}$ such that for all $\mathsf{E}$ and
$\mathsf{Y}$ and for $R^{\prime}_{\mathsf{C}}$, $R_{\mathsf{C}}$ sampled as
above:

  1. 1.

$R^{\prime}_{\mathsf{C}}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ R_{\mathsf{C}}$,
and

  2. 2.

With probability at least $1-\delta$, either
$\mathsf{state}^{\prime}_{\mathsf{C}}=\mathsf{state}_{\mathsf{C}}$ or
$\mathsf{state}_{\mathsf{C}}=\bot$.

For a particular class of data subjects $\mathcal{Y}$, we say a controller
$\mathsf{C}$ is _$(\epsilon,\delta)$ -deletion-as-control compliant for
$\mathcal{Y}$_ if there exists $\mathsf{Sim}$ such that the above holds for
all $\mathsf{E}$ and for all $\mathsf{Y}\in\mathcal{Y}$.

######  Definition 3.3 (Default simulator).

The default simulator $\mathsf{Sim}^{*}$ samples $R^{\prime}_{\mathsf{C}}$ as
follows:

$\displaystyle\mathsf{Sim}(\vec{\mathsf{q}}_{\mathsf{E}},R_{\mathsf{C}},\mathsf{state}_{\mathsf{C}}):$
$\displaystyle\qquad\text{Return
}R^{\prime}_{\mathsf{C}}\sim\mathcal{U}\big{|}_{\mathsf{C}(\vec{\mathsf{q}}_{\mathsf{E}};R^{\prime})=\mathsf{state}_{\mathsf{C}}}\text{
if such an $R^{\prime}_{\mathsf{C}}$ exists}$
$\displaystyle\qquad\text{Otherwise, return $R^{\prime}\sim\mathcal{U}$}.$

As we show next, $\mathsf{E}$ and $\mathsf{Y}$ can be assumed to be
deterministic without loss of generality.

######  Lemma 3.4 (Deterministic environments and subjects).

Consider a controller $\mathsf{C}$. Suppose that for some $\epsilon,\delta\geq
0$, the controller $\mathsf{C}$ satisfies Definition 3.2 for all deterministic
environments $\mathsf{E}$ and data subjects $\mathsf{Y}$ with simulator
$\mathsf{Sim}$. Then $\mathsf{C}$ satisfies Definition 3.2 (even for
randomized $\mathsf{E}$ and $\mathsf{Y}$) with the same simulator
$\mathsf{Sim}$.

###### Proof.

Fix a controller $\mathsf{C}$, and let $\mathsf{Sim}$ be the simulator which
show that $\mathsf{C}$ satisfies Definition 3.2 for all deterministic
environments and data subjects. Now consider a pair of randomized ITMs
$\mathsf{E}$ and $\mathsf{Y}$ with random coins denoted by $R_{\mathsf{E}}$
and $R_{\mathsf{Y}}$.

For a fixed string $r$, let $E_{r}$ denote the deterministic environment in
which $\mathsf{E}$’s random tape is fixed to $R_{\mathsf{E}}=r$; similarly for
$\mathsf{Y}_{r}$. Given strings $r_{\mathsf{E}}$ and $r_{\mathsf{Y}}$, we can
consider the execution of the deletion game in Definition 3.2 with the
deterministic machines $\mathsf{E}_{r_{\mathsf{E}}}$ and
$\mathsf{Y}_{r_{\mathsf{Y}}}$. Let
$R^{\prime}_{\mathsf{C},r_{\mathsf{E}},r_{\mathsf{Y}}}$ denote the random
coins output by the simulator in that game, and let
$P_{r_{\mathsf{E}},r_{\mathsf{Y}}}$ denote the distribution of
$R^{\prime}_{\mathsf{C},r_{\mathsf{E}},r_{\mathsf{Y}}}$. By hypothesis,
$R^{\prime}_{\mathsf{C},r_{\mathsf{E}},r_{\mathsf{Y}}}\approx_{\epsilon,\delta}R_{\mathsf{C}}$
for every $r_{\mathsf{E}}$ and $r_{\mathsf{Y}}$.

Now consider the deletion game with the randomized machines
$\mathsf{E},\mathsf{Y}$. Let $R^{\prime}_{\mathsf{C}}$ denote the output of
the simulator in that game. Since the simulator $\mathsf{Sim}$ does not depend
on the environment or data subject, the distribution of
$R^{\prime}_{\mathsf{C}}$ conditioned on the event that
$R_{\mathsf{E}}=r_{\mathsf{E}}$ and $R_{\mathsf{Y}}=r_{\mathsf{Y}}$ is exactly
$P_{r_{\mathsf{E}},r_{\mathsf{Y}}}$. Thus, we have

$(R_{\mathsf{E}},R_{\mathsf{Y}},R^{\prime}_{\mathsf{C}})\equiv(R_{\mathsf{E}},R_{\mathsf{Y}},R^{\prime}_{\mathsf{C},R_{\mathsf{E}},R_{\mathsf{Y}}})\approx_{\epsilon,\delta}(R_{\mathsf{E}},R_{\mathsf{Y}},R_{\mathsf{C}})\,,$

where $\equiv$ denotes that two random variables have identical distributions
and we have used the convexity of the $\approx_{\epsilon,\delta}$ relation.
Dropping the first two components, we get that
$R^{\prime}_{C}\approx_{\epsilon,\delta}R_{\mathsf{C}}$, as desired.

Furthermore, by hypothesis, we have that
$\mathsf{state}=\mathsf{state}^{\prime}$ with probability at least $1-\delta$
for each setting of $r_{\mathsf{E}}$ and $r_{\mathsf{Y}}$ (since
$\mathsf{state}$ depends only on $R_{\mathsf{E}}$ and $R_{\mathsf{Y}}$ via the
queries $\vec{\mathsf{q}}_{\mathsf{E}}$). Averaging over $r_{\mathsf{E}}$ and
$r_{\mathsf{Y}}$ shows that the overall probability that
$\mathsf{state}=\mathsf{state}^{\prime}$ is also at least $1-\delta$. ∎

####  3.2.1 Discussion

Our definition imposes a condition on the internal state of the controller at
a moment in time. Namely that, immediately after the data subject $\mathsf{Y}$
is deleted, the state of the controller $\mathsf{state}_{\mathsf{C}}$ can be
plausibly attributed to the interaction between the controller and the
environment alone. This in turn provides a guarantee for anything the
controller may do in the future. Namely, if the real controller was replaced
by the ideal controller at the moment of $\mathsf{Y}$’s deletion, the
environment would never know.

As an alternative, one might consider defining deletion-as-control as
restricting future behavior directly. We prefer to restrict the state as well.
It is simpler to describe—for instance, because there is a natural termination
condition. It is also future-proof. Any controller that satisfied the future-
behavior version but not the state version could choose to, in the future,
violate the guarantee by publishing the state at the time of $\mathsf{Y}$’s
erasure. Imposing the condition on the state directly makes it impossible for
the future behavior of the real and ideal controllers to deviate, rather than
merely possible for them not to.

Our definition provides a guarantee for an individual data subject. What about
groups? At the very least, each member of the group enjoys the individual-
level guarantee (the other individuals can be incorporated into the
environment). We leave the question of the group _as a group_ unanswered.
Briefly, one could consider a group version of the definition with $k$
individuals $\mathsf{Y}_{1}$, …, $\mathsf{Y}_{k}$, and an ideal world where
all $k$ are removed. We conjecture that the individual guarantee provides a
group guarantee with a DP-like degradation in the parameters
$(\epsilon,\delta)$.

For large groups our definition provides no meaningful guarantee. This is a
fundamental difference between our definition and prior work on machine
unlearning. Suppose, for example, that a controller trains a model $\theta$
using data from $n$ people. Then all $n$ people request deletion, leaving the
controller with a model $\theta^{*}$. Definitions from machine unlearning
would require that $\theta^{*}$ be essentially trivial—that $\theta^{*}$
should perform about as well as a the model $\theta_{0}$ trained on an empty
dataset (Section 4.4). On the other hand, deletion-as-control allows
$\theta^{*}$ to perform very well on the learning task. Indeed, Section 6
shows that if the learning algorithm is $(\epsilon,\delta)$ differentially
private, than $\theta^{*}=\theta$ already satisfies $(\epsilon,\delta)$
deletion-as-control.

Finally, we remark that there are dimensions of erasure and the Right to be
Forgotten that are neither captured by deletion-as-control nor prior work. For
example, in real computer systems, updates may take several days or weeks to
fully propagate through redundant copies of databases. Our model does not
account for time, but one could imagine a definition that captures some notion
of _eventual deletion_.

###  3.3 Real and ideal executions in detail

Our definition involves the interaction of three parties in the real execution
($\mathsf{C}$, $\mathsf{E}$, and $\mathsf{Y}$) and two parties in the ideal
execution ($\mathsf{C}$ and $\mathsf{D}$). Formally, the parties in our
definition are interactive Turing machines (ITM) with behavior specified by
code. An execution involves sequentially activating and deactivating the ITMs
until a termination condition is reached. Activations are tied to message-
passing as described below. At any time, at most one ITM is active. We denote
the executions using $\langle\mathsf{C},\mathsf{E},\mathsf{Y}\rangle$ or
$\langle\mathsf{C},\mathsf{D}\rangle$, respectively.

Each ITM has five tapes: work, input, output, randomness, and channel ID. We
require that all ITMs eventually terminate for every setting of tapes. One way
to enforce termination is to ask that every party come with a time bound
limiting the number of steps it executes when activated. We do not model this
particular detail explicitly. An ITM’s $\mathsf{state}$ at a given time
includes only the contents of its work tape at the time.

An ITM may freely read from and write to the work tape. The input tape is
read-only and is reset when an ITM is deactivated. (At the start of the
execution, input tapes are initialized with channel IDs as described below.)
The output tape is write-only and is reset when an ITM is activated.

The randomness tape is initialized with uniform random bits.333One could
instead view the controller’s randomness as consisting of i.i.d. samples from
an efficiently-sampleable distribution that may depend on $\mathsf{C}$ (e.g.,
Laplace noise or Gaussian noise). Uniform bits is without loss of generality,
as the simulator $\mathsf{Sim}$ defined below may be inefficient. To avoid a
priori bounds on running time or randomness complexity, the randomness tape is
countably infinite. It may only be read _once_ over the course of the whole
execution. That is, reading a bit from the randomness tape automatically
advances that tape head one position, and there is no other way to move that
tape head; if an ITM wishes to re-use bits from its randomness tape, it must
copy them to its work tape.444This is a departure from the model of Garg et
al. (2020), wherein the randomness tape may be read multiple times without
counting as part of the state. That would allow a controller to avoid deleting
anything by, for instance, encrypting its state using its randomness as a
secret key—a detail that was overlooked in Garg et al. (2020). Our fix is to
make the randomness read-once. As a result, a party must store in the work
tape any randomness that it will later reuse.

Messages between parties are passed over authenticated channels, represented
by a channel ID $\mathsf{cID}$ associated with two parties $A$ and $B$. A
single pair of parties may have many associated channels. Party $A$ sends a
message by writing $(\mathsf{cID},\mathsf{msg})$ to its output tape, where
$\mathsf{msg}\in\\{0,1\\}^{*}\cup\\{{\text{\sf{delete}}}\\}$, where delete is
a special message (i.e., not in $\\{0,1\\}^{*}$). When $A$ finishes writing
its output, $A$ is immediately deactivated. If $\mathsf{cID}$ corresponds to a
channel ID between $A$ and another party $B$, then
$(\mathsf{cID},\mathsf{msg})$ is written to $B$’s input tape and $B$ is
activated. Otherwise, the special message $\mathsf{fail}$ is written to $A$’s
input tape and $A$ is activated. Importantly, $B$ does not learn the _party_
that sent $\mathsf{msg}$, only the _channel_ $\mathsf{cID}$ over which it was
sent.

Each ITM’s channel ID tape is initialized with the $\mathsf{cID}$’s for
channels over which the ITM can communicate. The channel ID tape is read-once,
just like the randomness tape. In the real execution, $\mathsf{E}$’s tape is
initialized with $\mathsf{cID}$s (countably infinite, as with the randomness
tape). In the ideal execution, $D$’s tape is similarly initialized with
$\mathsf{cID}$s. The first is for communication with $\mathsf{Y}$ and the
remainder are for communication with $\mathsf{C}$. $\mathsf{Y}$’s input tape
is initialized with only one $\mathsf{cID}$ for communication with
$\mathsf{C}$ and one $\mathsf{cID}$ for communication with $\mathsf{E}$.
$\mathsf{C}$’s input is initially empty. It must learn the $\mathsf{cID}$s
from messages it receives, and cannot distinguish its channel with
$\mathsf{Y}$ from its channels with $\mathsf{E}$ or $\mathsf{D}$.

The executions begin with the activation of $\mathsf{E}$ or $\mathsf{D}$.
Parties are deactivated when they write a message to their output tape and the
recipient is activated. If a party halts without writing to its output tape,
$\mathsf{E}$ or $\mathsf{D}$ is activated.

##### The real execution

The real execution involves three (possibly randomized) parties: $\mathsf{C}$,
$\mathsf{E}$, and $\mathsf{Y}$ using randomness
$R_{\mathsf{C}},R_{\mathsf{E}}$, and $R_{\mathsf{Y}}$ respectively. The
execution ends after $\mathsf{Y}$ requests deletion from $\mathsf{C}$. More
precisely, after $\mathsf{Y}$ sends delete to $\mathsf{C}$, $\mathsf{C}$ is
activated one final time. The execution then ends when $\mathsf{C}$ halts or
writes to its output tape. Note that the real execution may never terminate if
$\mathsf{Y}$ never sends delete. We denote the real execution as
$\langle\mathsf{C}(R_{\mathsf{C}}),\mathsf{E}(R_{\mathsf{E}}),\mathsf{Y}(R_{\mathsf{Y}})\rangle$,
and when appropriate, we omit the randomness writing
$\langle\mathsf{C},\mathsf{E},\mathsf{Y}\rangle$.

The execution generates a _transcript_ $\tau$ of all messages sent to and
received by $\mathsf{C}$:
$\tau=((t,\mathsf{sender}_{t},\allowbreak\mathsf{receiver}_{t},\mathsf{cID}_{t},\mathsf{msg}_{t}))_{t}.$
For each $t$: one of $\mathsf{sender}_{t}$ or $\mathsf{receiver}_{t}$ is
always $\mathsf{C}$; $\mathsf{cID}_{t}$ is an id of a channel between
$\mathsf{sender}_{t}$ and $\mathsf{receiver}_{t}$; and
$\mathsf{msg}_{t}\in\\{0,1\\}^{*}\cup\\{{\text{\sf{delete}}}\\}$. We omit the
messages between $\mathsf{E}$ and $\mathsf{Y}$ though the view of the
environment does contain the messages between $\mathsf{E}$ and $\mathsf{Y}$.
The transcript can be further divided into _queries_ and _answers_. The
queries are messages sent to $\mathsf{C}$ (by either $\mathsf{E}$ or
$\mathsf{Y}$). We denote by $\vec{\mathsf{q}}$ the sub-transcript containing
all queries, and by $\vec{\mathsf{q}}_{\mathsf{E}}$ only those messages sent
by $\mathsf{E}$. The answers $\vec{\mathsf{a}}$ are messages to someone from
$\mathsf{C}$. We denote by $\vec{\mathsf{a}}_{\mathsf{E}}\subseteq\tau$ the
ordered messages from $\mathsf{C}$ to $\mathsf{E}$.

The real execution
$\langle\mathsf{C}(R_{\mathsf{C}}),\mathsf{E}(R_{\mathsf{E}}),\mathsf{Y}(R_{\mathsf{Y}})\rangle$
defines a transcript $\tau$, a state $\mathsf{state}_{\mathsf{C}}$, and
randomness $R_{\mathsf{C}}$. The transcript $\tau$ is defined above. The state
$\mathsf{state}_{\mathsf{C}}$ consists of the contents of $\mathsf{C}$’s work
tape at the end of the execution. The randomness $R_{\mathsf{C}}$ is the
prefix of $\mathsf{C}$’s randomness tape that was read at any point during the
real execution.

##### The ideal execution

The ideal execution involves two parties: $\mathsf{C}$ and $\mathsf{D}$. The
dummy party $\mathsf{D}$’s input tape is initialized with the same channel IDs
as $\mathsf{E}$’s tape in the real execution. The dummy simply replays the
queries in $\vec{\mathsf{q}}_{\mathsf{E}}$. At every activation, it sends the
next query in the sequence to $\mathsf{C}$ using the same $\mathsf{cID}$ as in
the real execution. Note that the _answers_ $\mathsf{D}$ receives from
$\mathsf{C}$ may be different from the real-world answers; however,
$\mathsf{D}$ sends the same queries $\vec{\mathsf{q}}_{\mathsf{E}}$
regardless.

The controller $\mathsf{C}$ is exactly as in the real execution except that
its randomness tape is initialized using _simulated_ randomness
$R^{\prime}_{\mathsf{C}}\leftarrow\mathsf{Sim}(\vec{\mathsf{q}}_{\mathsf{E}},R_{\mathsf{C}},\mathsf{state}_{\mathsf{C}})$
instead of _uniform_ randomness $R_{\mathsf{C}}\sim\mathcal{U}$. The simulator
is an (inefficient) algorithm $\mathsf{Sim}$ that takes as input
$\vec{\mathsf{q}}_{\mathsf{E}}$, $\mathsf{state}_{\mathsf{C}}$, and
$R_{\mathsf{C}}$ and produces output $R^{\prime}_{\mathsf{C}}$. Note that
$R_{\mathsf{C}}$ and $R^{\prime}_{\mathsf{C}}$ consist of countably-many bits;
hence $R_{\mathsf{C}}$ and $R^{\prime}_{\mathsf{C}}$ cannot be treated as
conventional inputs and outputs to $\mathsf{Sim}$. Instead, we let
$\mathsf{Sim}$ have read access to an input tape on which $R_{\mathsf{C}}$ is
written. $\mathsf{Sim}$ writes finitely-many bits of output onto its output
tape and halts, at which point all other locations of the output tape are
filled with uniformly random bits. We denote by $R^{\prime}_{\mathsf{C}}$ the
final contents of this output tape.

We denote the ideal execution as
$\langle\mathsf{C}(R^{\prime}_{\mathsf{C}}),\mathsf{D}(\vec{\mathsf{q}}_{\mathsf{E}})\rangle$.
The ideal execution ends after $\mathsf{D}$ sends its last query from
$\vec{\mathsf{q}}_{\mathsf{E}}$ to $\mathsf{C}$. When this happens,
$\mathsf{C}$ is activated one final time. The execution ends when $\mathsf{C}$
halts or writes to its output tape. $\tau^{\prime}$ is the transcript at the
end of the execution and $\mathsf{state}^{\prime}$ is the final state of
$\mathsf{C}$. Note that the ideal-world execution terminates if the real-world
execution terminates. If the execution does not terminate, we define
$\tau^{\prime}=\mathsf{state}^{\prime}=\bot$.

##  4 History Independence and Deletion-as-control

History independence (HI) is concerned with the problem that the memory
representation of a data structure may reveal information about the history of
operations that were performed on it Micciancio (1997); Naor and Teague
(2001); Hartline et al. (2005). HI requires that the memory representation
reveals nothing more than the current logical state of the data structure.
Setting aside a number of technical subtleties, the conceptual connection to
machine unlearning is immediate: if we consider a machine learning model as a
representation of a dictionary data structure with insert and remove (i.e.,
unlearn) operations, a model is HI if and only if it satisfies machine
unlearning.

In this section, we state the definition of (non-adaptive) history
independence (Section 4.1). We then define a more general notion that allows
for implementations that satisfy the conditions of HI _approximately_ and
_adaptively_ (Section 4.2). The generalization is complex since we must
explicitly model adaptivity in the interactions between a data structure and
those issuing queries to it. Briefly, an adaptive adversary $\mathsf{A}$
interacting with the data structure produces two equivalent query sequences.
Adaptive history independence (AHI) requires that the joint distribution of
$\mathsf{A}$’s view and the data structure’s state is the same under both
sequences. Approximate AHI requires these distributions to be
$(\epsilon,\delta)$-close.

We show that data controllers that satisfy approximate AHI also satisfy our
notion of deletion-as-control (Section 4.3) with the same parameters. Finally,
we show how existing definitions of machine unlearning and the corresponding
constructions are all (weakenings of) our general notion of history
independence (Section 4.4).

###  4.1 History independence

An _abstract data type (ADT)_ is defined by a universe of operations
$\\{\mathsf{op}\\}$ and a mapping
$\mathsf{ADT}:(\mathsf{op},{s}_{\mathsf{adt}})\mapsto({s}_{\mathsf{adt}}^{\prime},\mathsf{out}_{\mathsf{adt}})$.
We call ${s}_{\mathsf{adt}},{s}_{\mathsf{adt}}^{\prime}\in\\{0,1\\}^{*}$ the
_logical states_ before and after operation, where
${s}_{\mathsf{adt}}^{\prime}$ is a deterministic function of
${s}_{\mathsf{adt}}$ and $\mathsf{op}$. We call
$\mathsf{out}_{\mathsf{adt}}\in\\{0,1\\}^{*}\cup\\{\bot\\}$ the _logical
output_ , which may be randomized. In subsequent sections we will assume
without loss of generality that operations $\mathsf{op}({id})$ are tagged by
${id}\in\\{0,1\\}^{*}$. We omit the tags where possible to reduce clutter.

Given an initial logical state ${s}_{\mathsf{adt}}^{0}$ and a sequence of
operations $\sigma=(\mathsf{op}^{1},\mathsf{op}^{2},\dots)$, the ADT defines a
sequence of logical states
$({s}_{\mathsf{adt}}^{1},{s}_{\mathsf{adt}}^{2},\dots)$ and a sequence of
outputs
$\overrightarrow{\mathsf{out}}=(\mathsf{out}_{\mathsf{adt}}^{1},\mathsf{out}_{\mathsf{adt}}^{2},\dots)$
by iterated application of $\mathsf{ADT}$. We denote by
$\mathsf{ADT}(\sigma).\mathsf{state}$ the final logical state that results
from this iterated application. When no initial state is specified, it is
assumed to be the empty state.

######  Definition 4.1.

We say two sequences of operations $\sigma$ and $\sigma^{\prime}$ are
_logically equivalent_ , denoted $\sigma\stackrel{{\scriptstyle
L}}{{\equiv}}\sigma^{\prime}$, if
$\mathsf{ADT}(\sigma).\mathsf{state}=\mathsf{ADT}(\sigma^{\prime}).\mathsf{state}$.
Logical equivalence is an equivalence relation, and we denote by $[\sigma]$ a
canonical sequence in the equivalence class of sequences
$\\{\sigma^{\prime}:\sigma^{\prime}\stackrel{{\scriptstyle
L}}{{\equiv}}\sigma\\}$.

An _implementation_ (e.g., a computer program for a particular architecture)
is a possibly randomized mapping
$\mathsf{Impl}:(\mathsf{op},{s})\mapsto({s}^{\prime},\mathsf{out})$. We call
${s}$ the _physical state_ and $\mathsf{out}$ the _physical output_. Both may
be randomized. Given an initial state and sequence of operations,
$\mathsf{Impl}$ defines a sequence of physical states and outputs by iterated
application. When no initial state is specified, it is assumed to be the empty
state.

######  Definition 4.2 (History independence (Naor and Teague, 2001)).

$\mathsf{Impl}$ is a _weakly history independent_ implementation of
$\mathsf{ADT}$ _(WHI-implements $\mathsf{ADT}$)_ if

$\sigma\stackrel{{\scriptstyle
L}}{{\equiv}}\sigma^{\prime}\implies\mathsf{Impl}(\sigma).\mathsf{state}\equiv\mathsf{Impl}(\sigma^{\prime}).\mathsf{state},$
(1)

where $\equiv$ denotes equality of distributions. $\mathsf{Impl}$ is a
_strongly history independent_ implementation of $\mathsf{ADT}$ (SHI-
implements ADT) if for all initial states ${s}$

$\displaystyle\sigma\stackrel{{\scriptstyle
L}}{{\equiv}}\sigma^{\prime}\implies\mathsf{Impl}(\sigma,{s}).\mathsf{state}\equiv\mathsf{Impl}(\sigma^{\prime},{s}).\mathsf{state}.$
(2)

One can obtain approximate, nonadaptive versions of history independence by
replacing $\equiv$ with $\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ $ in Definition
4.2. However, because the sequence of queries is specified ahead of time, such
a definition’s guarantees are not meaningful in interactive settings—see
Example 4.3.

We do not define correctness of an implementation of an ADT. Thus every ADT
trivially admits a SHI implementation (e.g., $\mathsf{Impl}$ always outputs
$\bot$). Omitting correctness simplifies the specification of the ADT while
allowing flexibility—for example, if approximate correctness suffices for an
application. The usefulness of an implementation requires separate analysis.
However, history independence simplifies this step: it suffices to analyze the
utility for the canonical sequences of operations $[\sigma]$ instead of
arbitrary sequences $\sigma$.

####  4.1.1 Strongly History Independent Dictionaries

To illustrate history independence, consider the dictionary ADT, which models
a simple key-value store. Looking ahead, we will use history independent
dictionaries to build deletion-compliant controllers from differential
privacy. For our purposes, the keys will be party IDs ${id}$; the values can
be arbitrary. The ADT supports operations
${\text{\sf{insert}}}({id}),{\text{\sf{delete}}}({id})$, $\mathsf{get}({id})$,
and $\mathsf{set}({id},value)$, where $\mathsf{set}$ associates the key
corresponding to ${id}$ with $value$, and $\mathsf{get}$ returns the most
recently set value. We assume that ${\text{\sf{insert}}}({id})$ is equivalent
to $\mathsf{set}({id},\top)$ where $\top$ is a special default value.

Dictionaries are typically implemented as hash tables, but such data
structures are generally not history independent. For example, in hashing with
open addressing, deletions are typically done lazily (by marking the cell for
a deleted key with a special, “tombstone” value). So one can tell whether an
item was deleted but also learn the deleted item’s hash value. Storing a
dictionary as a sorted list is inefficient—updates generally take time
$\Omega(n)$, where $n$ is the current number of keys—but it enjoys strong
history independence. The sorted representation depends only on the logical
contents of the dictionary, not on the order of insertions nor which items
were inserted then deleted. Since we do not focus on efficiency here, the
reader may think of the sorted list as our default implementation of a
dictionary. 555In fact, a strongly history independent hash table
implementation with constant expected-time operations was described by
Blelloch and Golovin (2007).

###  4.2 Adaptive History Independence (AHI)

The history independence literature gives no guarantees against adaptively-
chosen sequences of queries, because the two sequences $\sigma$ and
$\sigma^{\prime}$ are fixed before the implementation’s randomness is sampled.

######  Example 4.3.

Consider an implementation $\mathsf{Impl}$ of a dictionary with two
operations: ${\text{\sf{insert}}}({id})$ and ${\text{\sf{delete}}}({id})$.
Upon initialization, $\mathsf{Impl}$ outputs the first $n$ bits of its uniform
randomness tape, denoted $r$, and stores it in state ${s}^{1}=r$. If the first
operation is ${\text{\sf{insert}}}(r)$, $\mathsf{Impl}$ will store the
subsequent sequence of operations it its state. Otherwise, $\mathsf{Impl}$
ignores all subsequent operations, setting ${s}=r$. $\mathsf{Impl}$ produces
no outputs other than the initial $\mathsf{out}^{1}=r$. $\mathsf{Impl}$
satisfies $(0,2^{-n})$-approximate nonadaptive strong history independence:
for any sequences $\sigma$ and $\sigma^{\prime}$ fixed in advance, and for any
initial ${s}$,
$\mathsf{Impl}(\sigma,{s}).\mathsf{state}=r=\mathsf{Impl}(\sigma^{\prime},{s})$,
except with probability $2\cdot 2^{-n}$. However, an adaptive adversary that
sees $\mathsf{out}^{1}=r$ can easily produce distinct
$\sigma\stackrel{{\scriptstyle L}}{{\equiv}}\sigma^{\prime}$ such that
$\mathsf{Impl}(\sigma).\mathsf{state}=\sigma\neq\sigma^{\prime}=\mathsf{Impl}(\sigma^{\prime}).\mathsf{state}$.

Inspired by (Gupta et al., 2021), we extend the well-studied notion of history
independence to the _adaptive_ setting, where the sequence $\sigma$ of
operations is chosen adaptively by an algorithm interacting with an
implementation of an ADT.

We consider an interaction $\langle\mathsf{Impl}(R),\mathsf{A}\rangle$ between
an algorithm $\mathsf{A}$ and the implementation $\mathsf{Impl}$ with random
tape $R\sim\mathcal{U}$(Figure 3). In the interaction, $\mathsf{A}$ adaptively
outputs an operation
$\mathsf{op}^{i}\leftarrow\mathsf{A}(\mathsf{op}^{1},\mathsf{out}^{1},\dots,\mathsf{op}^{i-1},\mathsf{out}^{i-1})$,
and receives the output $\mathsf{out}^{i}$ in return. The interaction defines
a sequence of operations $\sigma$ and corresponding outputs
$\overrightarrow{\mathsf{out}}$. Eventually, $\mathsf{A}$ outputs a sequence
$\sigma^{*}$ that is logically equivalent to the sequence $\sigma$ of
operations performed so far. $\mathsf{Impl}$ is executed on $\sigma^{*}$ and
alternate randomness $R^{*}$, resulting in
${s}^{*}=\mathsf{Impl}(\sigma^{*};R^{*}).\mathsf{state}$. We consider two
variants: $R^{*}=R$, or $R^{*}\sim\mathcal{U}$ independent of $R$.

We consider the adversary’s ability to distinguish the real state
${s}=\mathsf{Impl}(\sigma;R).\mathsf{state}$ and the logically equivalent
state ${s}^{*}$, given its view
$V_{\mathsf{Impl},\mathsf{A}}=(\sigma,\sigma^{*},\overrightarrow{\mathsf{out}})$.
Our definition of adaptive history independence requires that the joint
distributions of $(V_{\mathsf{Impl},\mathsf{A}},{s})$ and
$(V_{\mathsf{Impl},\mathsf{A}},{s}^{*})$ be $(\epsilon,\delta)$-close. We
restrict ourselves to adversaries $\mathsf{A}$ such that
$\langle\mathsf{Impl},\mathsf{A}\rangle$ always terminates, which we call
_valid_ adversaries.

######  Definition 4.4 (Adaptive (weak) history independence).

An implementation $\mathsf{Impl}$ of an $\mathsf{ADT}$ is
$(\epsilon,\delta)$-history independent (AHI) if for all valid adversaries
$\mathsf{A}$:

$(V_{\mathsf{Impl},\mathsf{A}},{s})\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
(V_{\mathsf{Impl},\mathsf{A}},{s}^{*})$

where the distributions are given by the following probability experiment. The
experiment has two versions (identical or independently drawn randomness):

1:$R\sim\mathcal{U}$

2:Either $R^{*}=R$ (identical randomness), or $R^{*}\sim\mathcal{U}$
(independent randomness)

3:$(\sigma,\overrightarrow{\mathsf{out}},{s})\leftarrow\langle\mathsf{Impl}(R),\mathsf{A}\rangle$

4:$\mathsf{A}$ outputs $\sigma^{*}$

5:${s}^{*}\leftarrow\mathsf{Impl}(\sigma^{*};R^{*}).\mathsf{state}$

6:If $\sigma^{*}\not\stackrel{{\scriptstyle L}}{{\equiv}}\sigma$, then
${s}^{*}\leftarrow{s}$

7:$V_{\mathsf{Impl},\mathsf{A}}\leftarrow(\sigma,\sigma^{*},\overrightarrow{\mathsf{out}})$

We say an implementation $\mathsf{Impl}$ is $(\epsilon,\delta)$-AHI if it
satisfies either version of the definition (identical or independently drawn
randomness).

Note that for both versions of Definition 4.4, $R$ and $R^{*}$ are identically
distributed. One can generalize the definition to allow for any joint
distribution over $(R,R^{*})$ such that the two marginal distributions are
identical (all of our proofs would still go through for this general notion).
However, we avoid this generality since the two versions that we present are
sufficient for our needs.

The AHI definiton here corresponds to the approximate, adaptive version of
weak history independence (Definition 4.2), which considers only the state
state at a single point in time. This suffices for our purposes. One could
generalize Definition 4.4 to allow an adversary to see the full internal state
in the real execution at multiple points in time; this would correspond to
strong history independence. We leave such an extension for future work.

Figure 3: Adaptive history independence game, from Definition 4.4

##### From Strong Nonadaptive HI to Adaptive History Independence

To illustrate the definition, consider the case of strongly history
independent dictionaries. The hash table construction of Blelloch and Golovin
(2007) is a randomized data structure with the following property: for every
setting of the random string $R=r$, and for every two logically equivalent
sequences $\sigma,\sigma^{*}$, the data structure stores the same table
${s}(\sigma,r)={s}(\sigma^{*},r)$. (In fact, essentially all $(0,0)$-strongly
HI data structures can be modified to satisfy this strong guarantee (Hartline
et al., 2005)).

The data structure’s answers will thus depend only on the logical data set.
However, they might also depend on the randomness $r$—for instance, the
answers might leak the length of the probe sequence needed to find a given
element or other internal information. In an adaptive setting, queries might
depend on $r$ via the previous answers. To emphasize this dependence, we write
the realized query as $\sigma(r)$.

This construction satisfies $(0,0)$-adaptive HI with identical randomness
(where $R^{\prime}=R$ in Step 2 of Definition 4.4) but not the version with
fresh randomness ($R^{\prime}\perp R$). To see why it satisfies the definition
with identical randomness, consider the tuples
$(\sigma(R),\sigma(R)^{*},\overrightarrow{\mathsf{out}},{s}(\sigma,R))$ and
$(\sigma(R),\sigma(R)^{*},\overrightarrow{\mathsf{out}},{s}(\sigma^{*},R))$
resulting from the game in Def. 4.4. By logical equivalence, the tuples are
the same, and hence identically distributed. On the other hand, if we select
$R^{\prime}$ independently of $R$, then the adversary will, in general, see a
difference between $\sigma(R)$ and ${s}(\sigma^{*},R^{\prime})$ (for instance,
the hash functions corresponding to $R$ and $R^{\prime}$ will be different
with high probability).

###  4.3 AHI and Deletion-as-Control

We prove two theorems showing that data controllers that implement ADTs with
history independence satisfy deletion-as-control. Before that, two
technicalities remain. First, the statement only makes sense if the ADT itself
supports some notion of deletion. Second, there is a mismatch between the
syntax of ADTs/implementations and the deletion-as-control execution. Next we
define _ADTs supporting logical deletion_ and _controllers relative to an
implementation_ to handle the two issues, then state and prove the main
theorems of this section.

Consider an ADT where operations $\\{\mathsf{op}({id})\\}$ are tagged with an
identifier ${id}\in\\{0,1\\}^{*}$ (e.g., the channel IDs). For a sequence
$\sigma$ of operations and an ${id}^{*}$, let $\sigma_{-{id}^{*}}$ be the
sequence of operations with every operation with identifier ${id}^{*}$ removed
(that is, $\mathsf{op}({id}^{*})$ for all values of $\mathsf{op}$).

######  Definition 4.5 (Logical Deletion).

ADT supports _logical deletion_ if there exists an operation delete such that
for all sequences of operations $\sigma$ and for all IDs ${id}^{*}$:
$\left(\sigma\|{\text{\sf{delete}}}({{id}^{*}})\right)\stackrel{{\scriptstyle
L}}{{\equiv}}\sigma_{-{id}^{*}}$.

Logical deletion is important for ensuring the correctness property of
deletion compliance (that the states in the two worlds are identical).
Conversely, if an ADT does not support logical deletion, then one would expect
any controller that faithfully implements the ADT to violate the deletion
requirement.

The notion of logical deletion applies to a wide variety of abstract data
types, not only dictionaries. For example, consider a public bulletin board,
where users can post messages visible to everyone. The natural ADT would allow
creation of new users, insertion and maybe deletion of specific posts, and
deletion of an entire user account. This latter operation would undo all
previous actions involving that account.

We consider a family of data controllers $\mathsf{C}$ that are essentially
just implementations of ADTs that can interface with the execution.

######  Definition 4.6 (Controller relative to an implementation).

Let $\mathsf{Impl}$ be an implementation of an $\mathsf{ADT}$. We define the
controller $\mathsf{C}_{\mathsf{Impl}}$ relative to $\mathsf{Impl}$ as the
controller that maintains state $\mathsf{state}$ and works as follows:

  * •

On input $(\mathsf{cID},\mathsf{msg})$:

    * –

$(\mathsf{state}^{\prime},\mathsf{out})\leftarrow\mathsf{Impl}(\mathsf{op}(\mathsf{cID}),\mathsf{state})$,
where $\mathsf{op}\leftarrow\mathsf{msg}$.

    * –

Write $(\mathsf{cID},\mathsf{out})$ to the output tape.

  * •

On input $\mathsf{fail}$: Halt.

We say $\mathsf{C}$ is history independent (adaptively/strongly/weakly) if
$\mathsf{Impl}$ is history independent (adaptively/strongly/weakly).

######  Theorem 4.7.

For any ADT that supports logical deletion and any SHI implementation
$\mathsf{Impl}$, the controller $\mathsf{C}=\mathsf{C}_{\mathsf{Impl}}$
satisfies $(0,0)$-deletion-as-control with the simulator that outputs
$R^{\prime}_{\mathsf{C}}=R_{\mathsf{C}}$.

Without the condition on the simulator, this is a corollary of the theorem
below. The proof in Appendix C uses a foundational result in the study of
history independence. Roughly, that SHI implies canonical representations for
each logical state of the ADT (Hartline et al., 2005).

######  Theorem 4.8.

For any ADT that supports logical deletion and any $\mathsf{Impl}$ of the ADT
satisfying $(\epsilon,\delta)$-AHI (with either variant of Definition 4.4),
the controller $\mathsf{C}=\mathsf{C}_{\mathsf{Impl}}$ is
$(\epsilon,\delta)$-deletion-as-control compliant.

The proof uses a simple, novel result on indistinguishability, dubbed the
Coupling Lemma, which we present and prove in Appendix A.

###### Proof of Theorem 4.8.

Fix any deterministic $\mathsf{E}$ and $\mathsf{Y}$. By Lemma 3.4 this is
without loss of generality. Throughout this proof, we drop the subscript
$\mathsf{Impl}$ from the controller $\mathsf{C}_{\mathsf{Impl}}$, and drop the
subscript $\mathsf{C}_{\mathsf{Impl}}$ from the controller’s state
$\mathsf{state}_{\mathsf{C}_{\mathsf{Impl}}}$ and randomness
$R_{\mathsf{C}_{\mathsf{Impl}}}$.

Definition 4.4 considers two variants of AHI, depending on how the randomness
$R$ used in the initial $\mathsf{Impl}$ evaluation (with sequence $\sigma$)
relates to the randomness $R^{*}$ used in the logically equivalent evaluation
(with sequence $\sigma^{*}$). (Either $R$ and $R^{*}$ are sampled i.i.d. or
$R^{*}=R$.) Let $\mathfrak{D}$ be the joint distribution over $(R,R^{*})$ for
which $\mathsf{Impl}$ enjoys the $(\epsilon,\delta)$-AHI guarantee. Observe
that the marginal distribution of $R^{*}$ is $\mathcal{U}$.

To prove that the controller $\mathsf{C}$ is deletion-as-control compliant, we
will use the following simulator $\mathsf{Sim}$:
$\mathsf{Sim}(\vec{\mathsf{q}}_{\mathsf{E}},R,\mathsf{state})$ samples
$(\widetilde{R},\widetilde{R}^{*})$ from $\mathfrak{D}$ conditioned on the
following event:

$\vec{\mathsf{q}}_{\mathsf{E}}(\widetilde{R})=\vec{\mathsf{q}}_{\mathsf{E}}\quad\land\quad\mathsf{C}(\vec{\mathsf{q}}_{\mathsf{E}};\widetilde{R}^{*})=\mathsf{state},$

where $\vec{\mathsf{q}}_{\mathsf{E}}(\widetilde{R})$ are the queries from
$\mathsf{E}$ to $\mathsf{C}$ in the execution
$\langle\mathsf{C}(\widetilde{R}),\mathsf{E},\mathsf{Y}\rangle$.
$\mathsf{Sim}$ outputs $R^{\prime}=\widetilde{R}^{*}$. The real execution’s
state is $\mathsf{state}=\mathsf{C}(\vec{\mathsf{q}}(R);R)$. The ideal
execution’s state is
$\mathsf{state}^{\prime}=\mathsf{C}(\vec{\mathsf{q}}_{\mathsf{E}}(R);R^{\prime})$.

######  Claim 4.9.

Define $f$ and $g$ as follows:

$\displaystyle f(R)$ $\displaystyle=\bigl{(}\vec{\mathsf{q}}_{\mathsf{E}}(R),\
\mathsf{C}(\vec{\mathsf{q}}(R);R)\bigr{)}$ $\displaystyle g(R,R^{*})$
$\displaystyle=\bigl{(}\vec{\mathsf{q}}_{\mathsf{E}}(R),\
\mathsf{C}(\vec{\mathsf{q}}_{\mathsf{E}}(R);R^{*})\bigr{)},$

Then $(R,R^{*})\sim\mathfrak{D}\implies f(R)\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ g(R,R^{*}).$

The proof of the claim is below. We use the claim to complete the proof of the
theorem. Consider a procedure that samples $R\sim\mathcal{U}$, and then
samples
$(\widetilde{R},\widetilde{R}^{*})\sim\mathfrak{D}\big{|}_{f(R)=g(\widetilde{R},\widetilde{R}^{*})}$
(if possible, otherwise uniformly). Observe that this is exactly the
distribution of $R\sim\mathcal{U}$ and the intermediate vales
$(\widetilde{R},\widetilde{R}^{*})$ sampled by $\mathsf{Sim}$ defined above.
Applying the Coupling Lemma (Lemma A.1) to the preceding claim, we get that
the joint distribution over $(R,\widetilde{R},\widetilde{R}^{*})$ satisfies
$(\widetilde{R},\widetilde{R}^{*})\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ \mathfrak{D}$,
and $f(R)=g(\widetilde{R},\widetilde{R}^{*})$ with probability at least
$1-\delta$.

$\mathsf{Sim}$ outputs $R^{\prime}=\widetilde{R}^{*}$. Because the marginal
distribution of $\widetilde{R}^{*}$ is $\mathcal{U}$, we have that
$R^{\prime}\ {\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
\mathcal{U}$. The equality of $f$ and $g$ implies that
$\mathsf{state}^{\prime}=\mathsf{C}(\vec{\mathsf{q}}_{\mathsf{E}}(R);R^{\prime})=\mathsf{C}(\vec{\mathsf{q}}(R);R)=\mathsf{state}$.
Hence, $\mathsf{C}_{\mathsf{Impl}}$ satisfies $(\epsilon,\delta)$-deletion-as-
control with the simulator $\mathsf{Sim}$. ∎

###### Proof of Claim 4.9.

We will use the adaptive history independence of $\mathsf{Impl}$. We define an
AHI adversary $\mathsf{A}=\mathsf{A}_{\mathsf{E},\mathsf{Y}}$ (see Figure 4)
which gets query access to the implementation $\mathsf{Impl}$ in the AHI game.
$\mathsf{A}$ emulates the execution
$\langle\mathsf{C},\mathsf{E},\mathsf{Y}\rangle$ internally, querying
$\mathsf{Impl}$ as needed to implement $\mathsf{C}$. When the execution
terminates, $\mathsf{A}$ outputs $\sigma^{*}=\vec{\mathsf{q}}_{\mathsf{E}}$,
the queries sent from $\mathsf{E}$ to $\mathsf{C}$. The actual sequence of
queries received by $\mathsf{Impl}$ in the real execution is
$\sigma=\vec{\mathsf{q}}$, including all queries from both $\mathsf{E}$ and
$\mathsf{Y}$.

We claim that $\sigma^{*}\stackrel{{\scriptstyle L}}{{\equiv}}\sigma$. To see
why, observe that $\sigma^{*}=\sigma_{-\mathsf{Y}}$ is the query sequence with
all queries from $\mathsf{Y}$ removed. Moreover, $\sigma$ ends in
${\text{\sf{delete}}}(\mathsf{Y})$. By the hypothesis that $\mathsf{ADT}$
supports logical deletion $\sigma\stackrel{{\scriptstyle
L}}{{\equiv}}\sigma_{-\mathsf{Y}}=\sigma^{*}$.

Figure 4: Reduction from $(\epsilon,\delta)$-AHI to
$(\epsilon,\delta)$-deletion-as-control.

By the $(\epsilon,\delta)$-AHI of $\mathsf{Impl}$,
$(V_{\mathsf{Impl},\mathsf{A}},{s})\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
(V_{\mathsf{Impl},\mathsf{A}},{s}^{*})$. By construction, the state
${s}=\mathsf{Impl}(\sigma;R).\mathsf{state}$ is exactly the controller’s state
${s}=\mathsf{C}(\vec{\mathsf{q}};R)$ in the real execution
$\langle\mathsf{C}(R),\mathsf{E},\mathsf{Y}\rangle$. Likewise, the state
${s}^{*}=\mathsf{Impl}(\sigma^{*};R^{*})$ is exactly the the controller’s
state ${s}^{\prime}=\mathsf{C}(\vec{\mathsf{q}}_{\mathsf{E}};R^{*})$ in the
ideal execution
$\langle\mathsf{C}(R^{*}),\mathsf{D}(\vec{\mathsf{q}}_{\mathsf{E}})\rangle$.
$\mathsf{A}$’s view $V_{\mathsf{Impl},\mathsf{A}}$ consists of
$(\sigma,\sigma^{*},\overrightarrow{\mathsf{out}})=(\vec{\mathsf{q}}(R),\vec{\mathsf{q}}_{\mathsf{E}}(R),\overrightarrow{\mathsf{out}})$.
Hence,

$f(R)=(\vec{\mathsf{q}}(R),{s}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
(\vec{\mathsf{q}}(R),{s}^{\prime}=g(R,R^{*}).\qed$ (3)

###  4.4 Relating Prior Definitions of Machine Unlearning to (Adaptive)
History Independence

We claim that AHI captures the essence of existing definitions of “machine
unlearning” (that is, protocols that update a machine learning model to
reflect deletions from the training data). Each definition in the literature
corresponds to a special case of history independence, though each weakens the
definition in one or more ways (even when their constructions satisfy the
stronger, general notion). For illustration, we discuss the approach of Gupta
et al. (2021) in detail.

The basic correspondence comes via considering an abstract data type, which we
dub the Updatable ML, that extends a dictionary: it maintains a multiset
${\vec{x}}$ of labeled examples from some universe ${\mathcal{Z}}$. In
addition to allowing ${\text{\sf{insert}}}()$ and ${\text{\sf{delete}}}()$
operations, it accepts a possibly randomized operation predict which outputs a
predictor (or other trained model) $\psi$ trained on ${\vec{x}}$. The accuracy
requirement for $\psi$ is generally not fully specified, not least because
many current machine learning methods don’t come with worst-case guarantees.
The literature on machine unlearning generally requires that the distribution
of the final predictor $\psi$ (e.g., the model parameters) is approximately
the same as it would be for a minimal sequence of operations that leads to the
same training data set. In particular, _deleting an individual $\mathsf{Y}$
should mean that $\psi$ looks roughly the same as if $\mathsf{Y}$ had never
appeared in ${\vec{x}}$_. One could satisfy the requirement by simply
retraining $\psi$ from scratch every time the data set changes, but this would
be computationally expensive. The literature therefore focuses on methods that
allow for faster updates.

##### Specializing History Independence to Updatable ML.

First, we spell out how AHI (Definition 4.4) specializes to the Updatable ML
ADT. Given a sequence of updates and prediction queries
$\sigma=(u_{1},...,u_{t})$, let $\left[{\sigma}\right]$ denote a canonical
equivalent sequence of updates. For example, $\left[{\sigma}\right]$ may (a)
discard any insertion/deletion pairs that operate on the same element, with
the insertion appearing first, and (b) list the remaining operations in
lexicographic order. In an interaction with an implementation $\mathsf{Impl}$
that is initialized with an empty data set, an adversary makes a sequence of
queries $\sigma$ (of which only the updates actually affect the state) and,
eventually, terminates at some time step $t$. Let ${s}$ the resulting state of
the controller based on randomness $R$, and let ${\vec{x}}_{t}$ be the final
logical data set. After the interaction ends, the adversary outputs some
logically equivalent sequence $\sigma^{*}$ (for example, it could choose the
canonical sequence $\sigma^{*}=\left[{\sigma}\right]$). Finally, run
$\mathsf{Impl}$ from scratch with randomness $R^{\prime}$ and queries
$\sigma^{*}$ to get state ${s}^{*}$. The logical data set ${\vec{x}}_{t}$ is
the same for $\sigma$ and $\sigma^{*}$ by construction. Definition 4.4
requires that

$(\sigma,{s})\ {\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
(\sigma,{s}^{*})\,.$ (4)

##### Definitions from the Literature.

The exact definition of deletion varies from paper to paper (and some papers
do not define terms precisely). All formulate the problem in terms of what we
call the Updatable ML ADT. We claim their definitions are variations on
adaptive history independence (Eq. 5), each with one or more of the following
weakenings:

Restricted queries

Some papers consider only a subset of allowed operations—e.g., in Ginart et
al. (2019); Ullah et al. (2021); Sekhari et al. (2021) data is inserted as a
batch, and then only deletions occur.

One output versus future behavior

Some consider only the output of the system at one time (e.g., Neel et al.
(2020); Sekhari et al. (2021); Gupta et al. (2021)), while others also
consider the internal state (e.g., Ginart et al. (2019)). The narrower
approach does not constrain the future behavior of the system. Among those
definitions that consider the full state, none discuss issues of internal
representations; in this section, we also elide this distinction, assuming
that datasets can be represented internally using strongly history-independent
data structures.

Nonadaptive queries

Except for Gupta et al. (2021), the literature considers only adversaries that
specify the set of queries to be issued in advance.

For constructions that are $(0,0)$-HI (that is, in which the real and ideal
distributions are identical), this comes at no loss of generality. However,
the nonadaptive and adaptive versions of $(\epsilon,\delta)$-HI for $\delta>0$
are very different (Gupta et al., 2021). Even in Gupta et al. (2021), the
length $t$ of the query sequence is chosen nonadaptively.

Symmetric vs asymmetric indistinguishability

Ginart et al. (2019); Gupta et al. (2021) consider a one-sided weakening of
$(\epsilon,\delta)$-indistinguishability (discussed in Remark 4.10).

The definitions of Ginart et al. (2019); Ullah et al. (2021); Bourtoule et al.
(2021) consider exact variants of unlearning (with $\epsilon=\delta=0$), while
others Guo et al. (2020); Sekhari et al. (2021); Neel et al. (2020); Gupta et
al. (2021); Golatkar et al. (2020a, b) consider approximate variants.

Despite generally formulating weaker definitions, the algorithms in the
literature often satisfy the full definition of history independence. In
particular, because the constructions in Ginart et al. (2019); Cao and Yang
(2015) are fully deterministic, it is easy to see that they satisfy adaptive,
$(0,0)$-strong history independence (by Theorem 1 in Hartline et al. (2005)).
Some constructions satisfy additional properties, such as storing much less
information than the full data set ${\vec{x}}_{t}$ (e.g., Sekhari et al.
(2021); Cao and Yang (2015)).

##### Adaptive Machine Unlearning (Gupta et al. (2021))

We discuss the relationship to one previous definition—that of Gupta et al.
(2021)—in detail, since the definition is subtle and the relationship is
technically nontrivial. In our notation, the data structure maintains several
quantities: a data set ${\vec{x}}$, a collection of models $\vec{\theta}$,
some supplementary data supp used for updating, and the most recently output
predictor $\psi$. We say that an implementation of the Updatable ML ADT meets
the syntax of Gupta et al. (2021) if its state can be written
${s}=({\vec{x}}_{t},\vec{\theta}_{t},\text{supp}_{t},\psi_{t})$. Given an
initial data set ${\vec{x}}_{0}$, the execution proceeds for $t$ steps. At
each step $i$, the adversary (called the “update requester”) sends an update
$u_{i}$, which is either an insertion or deletion. The data structure then
updates its state to obtain
$({\vec{x}}_{i},\vec{\theta}_{i},\text{supp}_{i},\psi_{i})$ and returns
$\psi_{i}$ to the adversary.

The condition required by Gupta et al. is described by three parameters
$\alpha,\beta,\gamma>0$. For every time $t$ and initial dataset
${\vec{x}}_{0}$, with probability $1-\gamma$ over the updates
$\vec{u}=u_{1},...,u_{t}$ that arise in an interaction between the data
structure (initialized with ${\vec{x}}_{0}$ and randomness $R$) and the
adversary, the models $\vec{\theta}_{t}$ should be distributed similarly to
the models $\vec{\theta}_{0}^{*}$ one would get in a counterfactual execution
in which the data structure was initialized with the data set
${\vec{x}}_{0}^{*}={\vec{x}}_{t}$ (that is, $\vec{u}$ applied to
${\vec{x}}_{0}$) resulting from the real execution in canonical form (say, in
sorted order), and no updates were made. They require:

$\Pr_{\vec{u}=(u_{1},...,u_{t})}{\left({\vec{\theta}_{t}\big{|}_{{\vec{x}}_{0},u_{1},...,u_{t}}\quad\approx_{\alpha,\beta}\quad\vec{\theta}_{0}^{*}\big{|}_{{\vec{x}}_{0}^{*}}}\right)}\geq
1-\gamma\,$ (5)

$\text{where}\ {\vec{x}}_{0}^{*}=(\vec{u}\text{ applied to }{\vec{x}}_{0}).$

######  Remark 4.10.

Gupta et al. actually require only a one-sided version of the condition on
distributions enforced by $(\alpha,\beta)$-closeness. Specifically, no event
should be much more likely in the models resulting from a real interaction
than in ones generated from scratch with the resulting data set. This
condition is inherited from a definition proposed by Ginart et al. (2019). As
far as we know, all the actual algorithms designed for machine unlearning
satisfy the stronger, symmetric version of the definition in Equation (5).

######  Proposition 4.11 (AHI implies Adaptive Machine Unlearning).

Let $\mathsf{Impl}$ be a data structure that implements the Updatable ML ADT
and satisfies $(\epsilon,\delta)$-approximate history independence with fresh
randomness (Definition 4.4). If $\mathsf{Impl}$ fits the syntax of machine
unlearning, then for all $\beta>0$, it also satisfies _$(\alpha,\beta,\gamma)$
-unlearning_ (Equation (5)) with $\alpha=3\epsilon$ and
$\gamma=\frac{2\delta}{\beta}+\frac{2\delta}{1-\exp(-\epsilon)}$.

###### Proof.

Consider an Updatable ML data structure $\mathsf{Impl}$ that satisfies
approximate HI and fits the syntax of Gupta et al. (2021), that is, its state
${s}$ can be written
$({\vec{x}}_{t},\vec{\theta}_{t},\text{supp}_{t},\psi_{t})$.

Let UpReq be an update requester for the machine unlearning definition. UpReq
first chooses a time step $t$ at which it will terminate and an initial data
set ${\vec{x}}_{0}$, and then executes an interaction with $\mathsf{Impl}$
during which it makes update queries $\vec{u}=(u_{1},...,u_{t})$ and receives
predictors $\psi_{1},...\psi_{t}$. Let ${\vec{x}}_{t}$ be the final logical
data set. We define a corresponding adversary $\mathsf{A}$ for history
independence as follows:

1:procedure $\mathsf{A}$(given black-box access to UpReq)

2: Run UpReq to obtain $t$ and ${\vec{x}}_{0}$.

3: Compute a sequence of updates $\vec{u}$ such that
$\vec{u}_{0}\circ\emptyset={\vec{x}}_{0}$

4: Output queries $\vec{u}_{0}$ followed by the operation predict

5: Receive $\psi_{0}$

6: for $i=1$ to $t$ do

7: Run UpReq on input $\psi_{i-1}$ to get next update $u_{i}$

8: Output query $u_{i}$ followed by predict

9: Receive $\psi_{i}$

10: Output $\sigma^{*}=[\sigma]=[\vec{u}]$ where
$\vec{u}=\vec{u}_{0}\|u_{1},...,u_{t}$, and $\sigma$ is the full realized
sequence (namely, $\vec{u}$ with interleaved predict queries).

To apply HI, we consider an interaction between $\mathsf{Impl}$ and
$\mathsf{A}$, followed by a new execution of $\mathsf{Impl}$ with queries
$\sigma^{*}$ (which equals $[\vec{u}]$ for this adversary) and fresh
randomness. Let ${\vec{x}}_{t}$ be the final data set (in both executions).
Equation (4) implies that

$(\sigma,\underbrace{{\vec{x}}_{t},\vec{\theta}_{t},\text{supp}_{t},\psi_{t}}_{{s}})\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
(\sigma,\underbrace{{\vec{x}}_{t},\vec{\theta}^{*}_{0},\text{supp}^{*}_{0},\psi^{*}_{0}}_{{s}^{*}})\,.$

In particular, since the realized updates $\vec{u}$ form a subsequence of
$\sigma$, we have

$(\vec{u},\vec{\theta}_{t})\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
(\vec{u},\vec{\theta}_{0}^{*})\,.$ (6)

To draw the connection with Adaptive Machine Learning, we must define what it
means to initialize $\mathsf{Impl}$ with a nonempty data set (since such
initialization occurs in the definition of Adaptive Machine Unlearning). On
input a nonempty data set ${\vec{x}}_{0}$, we can compute the canonical
sequence of updates $\vec{u}_{0}$ that would lead to ${\vec{x}}_{0}$ (as in
Step 3 in $\mathsf{A}$ above) and run $\mathsf{Impl}$ with $\vec{u}$ as its
first queries, before real interactions occur. With this definition, the
triple $(\vec{u},\vec{\theta}_{t},\vec{\theta}_{0}^{*})$ is distributed
exactly as in (5). By Lemma A.3, with probability at least $1-\gamma$ over
$\vec{u}$, we have $\vec{\theta}_{t}|_{\vec{u}}\
{\stackrel{{\scriptstyle{\tiny\epsilon^{\prime},\delta^{\prime}}}}{{\approx}}}\
\vec{\theta}_{0}^{*}$, where $\epsilon^{\prime}=3\epsilon$ and
$\gamma=\frac{2\delta}{\delta^{\prime}}+\frac{2\delta}{1-\exp(-\epsilon)}$, as
desired. ∎

The converse implication does not hold, but we claim that it would after some
modifications of the definition of (Gupta et al., 2021):

  * •

The indistinguishability condition of (Gupta et al., 2021) (Equation (5))
applies only to the current collection of models $\vec{\theta}_{t}$; as such,
it does not constrain the system’s entire future behavior but only the
distribution of the output at a particular time (see Section 3.2.1). History
independence requires indistinguishability of the entire state
$({\vec{x}}_{t},\vec{\theta}_{t},\text{supp}_{t})$.

  * •

In (Gupta et al., 2021), the stopping time $t$ is determined before the
execution begins. In contrast, the History Independence adversary may choose
the stopping point adaptively.

  * •

As discussed in Remark 4.10, the indistinguishability condition of (Gupta et
al., 2021) is one-sided. Our definition of history independence requires the
stronger, symmetric guarantee.

We do not include a formal statement of the equivalence, since by the time one
spells out the strengthened model, the equivalence is nearly a tautology. The
only difference not listed above is whether one requires indistinguishability
of the states ${s}$ and ${s}^{*}$ conditioned on the updates $\vec{u}$—as in
Eq. (5)—or rather indistinguishability of the pairs $(\vec{u},{s})$ and
$(\vec{u},{s}^{*})$—as in Equation 4. These turn out to be equivalent up to
changes of parameters, as shown by Lemma A.3.

We conjecture that the protocols of Gupta et al. (2021) satisfy adaptive
history independence. A formal proof of this statement would require an
appropriately symmetric strengthening of the max-information bound of (Rogers
et al., 2016) (Thm 3.1 in ver. 2 on arXiv).

##  5 Deletion-as-confidentiality and Deletion-as-control

We study the relationship between the notion of deletion as confidentiality
from Garg et al. (2020) (hereafter “the GGV definition”) and our notion of
deletion-as-control (Definition 3.2). Similar to Definition 3.2, deletion-as-
confidentiality also considers two executions, real and ideal. At the end of
the two executions, they compare the _view_ of the environment
$V_{\mathsf{E}}$ and the state of the controller
$\mathsf{state}_{\mathsf{C}}$. Simplifying away (important but technical)
details, the real GGV execution is roughly the same as in deletion-as-control.
The ideal GGV execution simply drops all messages between $\mathsf{Y}$ and
$\mathsf{C}$. Informally, deletion-as-confidentiality requires that
$\mathsf{E}$’s view and $\mathsf{C}$’s final state are indistinguishable in
the real and ideal worlds.

In Section 5.1, we define _deletion-as-confidentiality_ —the definition
closest in spirit to the GGV definition but in our execution model. (We cannot
directly compare our definition to GGV as they are defined in different models
of interaction, stemming from a need in deletion-as-control to ‘sync’ the real
and ideal executions.) In Section 5.2, we show that for many data subjects
$\mathsf{Y}$, deletion-as-confidentiality for $\mathsf{Y}$ implies deletion-
as-control for $\mathsf{Y}$ (Theorem 5.3). Finally, we show that the
implication cannot hold for all data subjects due to the differences in the
execution models (Theorems 5.4 and 5.5).

###  5.1 Definition

Below, we define deletion-as-confidentiality by describing how it differs from
deletion-as-control. After the definition, we briefly explain how our
adaptation of deletion-as-confidentiality differs from that in Garg et al.
(2020).

Similar to Definition 3.2, deletion-as-confidentiality also considers two
executions—real and ideal. The real execution is almost the same as before,
involving the three parties $\mathsf{C}$, $\mathsf{E}$, and $\mathsf{Y}$. We
will be interested in the _view_ of the environment $\mathsf{E}$, denoted
$V_{\mathsf{E}}^{real}$ and the state of the controller $\mathsf{C}$, denoted
$\mathsf{state}_{\mathsf{C}}^{real}$, at the end of the execution.
$V_{\mathsf{E}}^{real}$ consists of $\mathsf{E}$’s randomness $R_{\mathsf{E}}$
and the transcript of its messages
$\tau_{\mathsf{E}}^{real}=(\vec{\mathsf{q}}_{\mathsf{E}}^{real},\vec{\mathsf{a}}_{\mathsf{E}}^{real})$.
(Both the view and state are $\bot$ if the execution does not terminate.) The
GGV definition requires that controller’s state and the environment’s view are
indistinguishable in the real world and in the ideal world wherein the data
subject never communicates with anybody. This definition inherently requires
that $\mathsf{C}$ can never reveal any information about one user’s data or
participation to another data or participation to another. Any information
about user $\mathsf{Y}$ that $\mathsf{C}$ reveals to the $\mathsf{E}$ becomes
part of $\mathsf{E}$’s view in the real world. If $\mathsf{Y}$ later requests
deletion, this information would not be part of $\mathsf{E}$’s view in the
ideal world.

The first major difference between GGV and deletion-as-control is the ideal
execution. The ideal GGV execution also involves the same three parties
$\mathsf{C}$, $\mathsf{E}$, and $\mathsf{Y}$—no dummy party $\mathsf{D}$ as in
deletion-as-control. The difference between the real and ideal GGV executions
is that ideal GGV execution drops all messages between $\mathsf{Y}$ and
$\mathsf{C}$. This execution results in some view $V_{\mathsf{E}}^{ideal}$ and
some state $\mathsf{state}_{\mathsf{C}}^{ideal}$.

The second major difference between the GGV execution and deletion-as-control
concerns how the execution terminates. Recall that in the deletion-as-control
game, the real execution ends as soon as $\mathsf{C}$ processes $\mathsf{Y}$’s
first delete message (i.e., the next time $\mathsf{C}$ halts). And the ideal
execution ends when all of $\mathsf{E}$’s queries from the real execution have
been replayed by the dummy $\mathsf{D}$. In contrast, the real and ideal GGV
executions ends when $\mathsf{E}$ sends a special finish message to
$\mathsf{C}$. At that point, one of two things happens. If $\mathsf{Y}$’s last
message to $\mathsf{C}$ was delete, then the execution immediately terminates.
Otherwise, $\mathsf{Y}$ sends delete to $\mathsf{C}$, and the execution ends
as soon as $\mathsf{C}$ processes that message. This difference means that the
execution’s end time can depend on $\mathsf{Y}$’s view in deletion-as-control,
but not in GGV. Theorem 5.5 leverages this gap to construct a controller that
satisfies GGV but not deletion-as-control. This difference reflects our two
fundamentally different approaches to defining the ideal execution.
$\mathsf{Y}$ has no affect on the GGV ideal execution, and hence $\mathsf{E}$
must end the execution. Deletion-as-control introduces a mechanism to “sync”
the real and ideal executions, thereby allowing $\mathsf{Y}$ to end both
executions.

The last major difference between GGV and deletion-as-control is the
indistinguishability requirement between the real and ideal executions. The
GGV definition requires that the joint distribution of the variables
$(V_{\mathsf{E}}^{real},\mathsf{state}_{\mathsf{C}}^{real})$ is close to that
of $(V_{\mathsf{E}}^{ideal},\mathsf{state}_{\mathsf{C}}^{ideal})$. That is,
the view of the environment $\mathsf{E}$ and the state of the controller
$\mathsf{C}$ should be nearly the same irrespective of whether the subject
$\mathsf{Y}$ sent its data to the controller and then deleted it, or did not
send its data at all. In contrast, deletion-as-control imposes no requirement
on $V_{\mathsf{E}}$. Moreover, GGV only requires indistinguishability for
$\mathsf{Y}$’s that do not send any messages to $\mathsf{E}$. Without this
restriction the definition would be far too limiting. For most useful
controllers, $\mathsf{Y}$ would be able to tell whether its messages are being
delivered to $\mathsf{C}$ or not (for example, by receiving an acknowledgement
of data receipt), and if it conveys this information to $\mathsf{E}$,
$\mathsf{E}$’s view will become different in real and ideal executions.

######  Definition 5.1 ($(\epsilon,\delta)$ Deletion-as-Confidentiality for
$\mathsf{Y}$).

For a data subject $\mathsf{Y}$, a controller $\mathsf{C}$ is
$(\epsilon,\delta)$-_deletion-as-confidentiality compliant for $\mathsf{Y}$_
if for all $\mathsf{E}$, in the executions involving $\mathsf{C}$,
$\mathsf{E}$, and $\mathsf{Y}$,

$(V_{\mathsf{E}}^{real},\mathsf{state}_{\mathsf{C}}^{real})\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
(V_{\mathsf{E}}^{ideal},\mathsf{state}_{\mathsf{C}}^{ideal}).$

######  Definition 5.2 (Deletion-as-Confidentiality, adapted from Garg et al.
(2020)).

Let $\mathcal{Y}_{\mathsf{silent}}$ be the set of data subjects $\mathsf{Y}$
that never send any messages to $\mathsf{E}$. $\mathsf{C}$ is
_$(\epsilon,\delta)$ -deletion-as-confidentiality compliant_ if it is
$(\epsilon,\delta)$-deletion-as-confidentiality compliant for all
$\mathsf{Y}\in\mathcal{Y}_{\mathsf{silent}}$.

The version of deletion-as-confidentiality in Definition 3.2 differs from the
original definition of Garg et al. (2020) in a few important ways. First,
(Garg et al., 2020) allows users to request deletion of the information shared
in specific interactions between $\mathsf{Y}$ and $\mathsf{C}$. To do this,
they define protocols that produce protocol-specific deletion tokens.
Simplifying, we take deletion of a user’s data to be all or nothing. Second,
(Garg et al., 2020) allows users to delete many times, whereas we focus on a
single deletion. Third, $\mathsf{C}$’s randomness tape is not read-once in
(Garg et al., 2020). As explained in Footnote 4, this allows a controller to
evade deletion by encrypting its state with its randomness. Finally, the
execution model of (Garg et al., 2020) does not have authenticated channels.
As they show, authentication is necessary for non-trivial functionalities. In
light of this, we chose to build authentication into our execution model (in
the form of channel IDs).

###  5.2 Control vs. Confidentiality

In spirit, deletion-as-confidentiality imposes a stronger indistinguishability
requirement than deletion-as-control. The former requires that no information
about the deleted data is ever revealed, whereas the latter only requires that
the effect of the deleted data is not present _after_ the deletion happens.
One might thus expect that any $\mathsf{C}$ that satisfies Definition 5.2
would also satisfy Definition 3.2.

But deletion-as-control captures more general environments and data subjects
than deletion-as-confidentiality. First, deletion-as-control allows
$\mathsf{Y}$ to communicate freely with $\mathsf{E}$, whereas deletion-as-
confidentiality does not (i.e., $\mathsf{Y}\in\mathcal{Y}_{\mathsf{silent}}$).
Second, deletion-as-control imposes a requirement as soon as $\mathsf{Y}$
deletes, whereas deletion-as-confidentiality only requires
indistinguishability after $\mathsf{E}$ terminates the execution (which may be
much later).

Let $\mathcal{Y}_{\mathsf{silent}}$ be as in Definition 5.2 and
$\mathcal{Y}_{\mathsf{dummy}}$ be the set of $\mathsf{Y}$ that only delete
when instructed by $\mathsf{E}$. Let
$\mathcal{Y}_{\mathsf{lift}}=\mathcal{Y}_{\mathsf{silent}}\cap\mathcal{Y}_{\mathsf{dummy}}$.

######  Theorem 5.3.

For any $\mathsf{C}$ and any $\mathsf{Y}\in\mathcal{Y}_{\mathsf{lift}}$, if
$\mathsf{C}$ is $(\epsilon,\delta)$-deletion-as-confidentiality compliant for
$\mathsf{Y}$, then it is also $(\epsilon,\delta)$-deletion-as-control
compliant for $\mathsf{Y}$.

Theorems 5.4 and 5.5 show that the restriction in Theorem 5.3 that
$\mathsf{Y}\in\mathcal{Y}_{\mathsf{lift}}=\mathcal{Y}_{\mathsf{dummy}}\cap\mathcal{Y}_{\mathsf{silent}}$
is necessary.

###### Proof of Theorem 5.3.

Fix any controller $\mathsf{C}$ that is $(\epsilon,\delta)$-deletion-as-
confidentiality compliant for subset of $\mathsf{Y}$’s that call delete only
when instructed to by $\mathsf{E}$. Then, in particular, $\mathsf{C}$ is
deletion-as-confidentiality compliant for _deterministic_ environments
$\mathsf{E}$ and data subjects $\mathsf{Y}$ in this class. By Lemma 3.4, it is
sufficient to consider deterministic $(\mathsf{E},\mathsf{Y})$ pairs to prove
deletion-as-control compliance.

Fix a deterministic environment $\mathsf{E}$ and data subject $\mathsf{Y}$
that calls delete only when instructed to by $\mathsf{E}$. Then, by Definition
5.1, we have

$(V_{\mathsf{E}}^{real},\mathsf{state}_{\mathsf{C}}^{real})\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
(V_{\mathsf{E}}^{ideal},\mathsf{state}_{\mathsf{C}}^{ideal}),$ (7)

where the randomness in the two distributions is only over the controller’s
randomness $R_{\mathsf{C}}$. Furthermore, since $\mathsf{Y}$ only deletes when
$\mathsf{E}$ instructs it to, the GGV game and deletion-as-control game result
in the same $\mathsf{state}_{\mathsf{C}}$ upon termination.

We will construct a simulator $\mathsf{Sim}$ that satisfies Definition 3.2 for
$\mathsf{C}$, $\mathsf{E}$, $\mathsf{Y}$. Recall that $\mathsf{Sim}$’s task is
as follows. For some randomly sampled value $R_{\mathsf{C}}$ and the resulting
transcript $\tau=(\vec{\mathsf{q}},\vec{\mathsf{a}})$ and controller state
$\mathsf{state}_{\mathsf{C}}$, the simulator is given
$R_{\mathsf{C}},\mathsf{state}_{\mathsf{C}}$, and
$\vec{\mathsf{q}}_{\mathsf{E}}$ (the sequence of messages sent by $\mathsf{E}$
to $\mathsf{C}$). The simulator is required to produce a
$R^{\prime}_{\mathsf{C}}$ such that when $\mathsf{C}$ interacts with the dummy
environment $\mathsf{D}(\vec{\mathsf{q}}_{\mathsf{E}})$ using randomness
$R^{\prime}_{\mathsf{C}}$, it results in the same state
$\mathsf{state}_{\mathsf{C}}$ with probability at least $1-\delta$; further,
$R^{\prime}_{\mathsf{C}}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ R_{\mathsf{C}}$
(with randomness coming from sampling the two).

In our case, we will use the “default simulator” (from Definition 3.3), which
works as follows:

$\displaystyle\mathsf{Sim}(\vec{\mathsf{q}}_{\mathsf{E}},r_{\mathsf{C}},\mathsf{state}_{\mathsf{C}}):$
$\displaystyle\qquad\text{Return
}R^{\prime}_{\mathsf{C}}\sim\mathcal{U}\big{|}_{\mathsf{C}(\vec{\mathsf{q}}_{\mathsf{E}};R^{\prime})=\mathsf{state}_{\mathsf{C}}}\text{
if such an $R^{\prime}_{\mathsf{C}}$ exists}$
$\displaystyle\qquad\text{Otherwise, return $R^{\prime}\sim\mathcal{U}$}.$

If such an $R^{\prime}_{\mathsf{C}}$ exists, then the final state of
$\mathsf{C}$ when interacting with $\mathsf{D}(\vec{\mathsf{q}}_{\mathsf{E}})$
using randomness $R^{\prime}_{\mathsf{C}}$ will be equal to
$\mathsf{state}_{\mathsf{C}}$. This is because, in $\mathsf{C}$’s view, this
interaction is identical to the ideal execution of Definition 5.1 with
$\mathsf{C}$ using randomness $R^{\prime}_{\mathsf{C}}$ and
$\mathsf{E},\mathsf{Y}$. It remains to prove that $R^{\prime}_{\mathsf{C}}$
exists with probability at least $1-\delta$ and that the distribution of
$R^{\prime}_{\mathsf{C}}$ is $(\epsilon,\delta)$-close to that of
$R_{\mathsf{C}}$.

We can now apply Lemma A.1 to prove both of the statements. Define the
following deterministic functions:

$\displaystyle f(X)$
$\displaystyle=(V_{\mathsf{E}}^{real}(X),\mathsf{state}_{\mathsf{C}}^{real}(X)),\text{
and}$ $\displaystyle g(Y)$
$\displaystyle=(V_{\mathsf{E}}^{ideal}(Y),\mathsf{state}_{\mathsf{C}}^{ideal}(Y)),$

where $V_{\mathsf{E}}^{real}(X)$ denotes the view of $\mathsf{E}$ when $X$ is
used as the randomness for $\mathsf{C}$ in the real world. Let
$X=R_{\mathsf{C}}$, $Y=R_{\mathsf{C}}$, and let $P\equiv Q$ be the
distribution that both $X$ and $Y$ are sampled from. Then, by Equation (7),
$f(X)\ {\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ g(Y)$.
Lastly, the simulator $\mathsf{Sim}$ defined samples $R_{\mathsf{C}}^{\prime}$
from the conditional distribution described in Lemma A.1. Thus, by the lemma,
we have that $R_{\mathsf{C}}^{\prime}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ R_{\mathsf{C}}$
and that
$(V_{\mathsf{E}}^{real}(X),\mathsf{state}_{\mathsf{C}}^{real}(X))=(V_{\mathsf{E}}^{ideal}(Y),\mathsf{state}_{\mathsf{C}}^{ideal}(Y))$
with probability at least $1-\delta$. In particular, we have that
$\mathsf{state}_{\mathsf{C}}^{real}=\mathsf{state}_{\mathsf{C}}^{ideal}$ with
probability at least $1-\delta$.

Thus, the simulator $\mathsf{Sim}$ for $\mathsf{C}$ satisfies both conditions
of $(\epsilon,\delta)$-deletion-as-control for deterministic
$(\mathsf{E},\mathsf{Y})$ and by Lemma 3.4, $\mathsf{C}$ also satisfies
$(\epsilon,\delta)$-deletion-as-control for randomized
$(\mathsf{E},\mathsf{Y})$, where $\mathsf{Y}$ calls delete only when
instructed to by $\mathsf{E}$. Lastly, since $\mathsf{Sim}$ does not rely on
the code of $\mathsf{Y}$ or $\mathsf{E}$, we can use the same simulator for
_all_ $\mathsf{Y}$’s in the class of data subjects that calls delete only when
instructed to by $\mathsf{E}$. ∎

######  Theorem 5.4.

There exists $\mathsf{C}$ and
$\mathsf{Y}\in\mathcal{Y}_{\mathsf{dummy}}\setminus\mathcal{Y}_{\mathsf{silent}}$
such that (i) $\mathsf{C}$ satisfies $(0,0)$-deletion-as-confidentiality, and
(ii) $\mathsf{C}$ does not satisfy
$(\epsilon^{\prime},\delta^{\prime})$-deletion-as-control for $\mathsf{Y}$ any
$\epsilon^{\prime}<\infty$, $\delta^{\prime}<1$.

###### Proof.

Consider $\mathsf{C}$ that implements a write-only SHI dictionary modified as
follows. Recall that communications in our execution model are in the form
$(\mathsf{cID},\mathsf{msg})$, where $\mathsf{cID}$ is a channel ID known only
to the communicating parties. If $\mathsf{C}$ receives message
$\mathsf{msg}=\mathsf{cID}$ with channel ID
$\mathsf{cID}^{\prime}\neq\mathsf{cID}$, then it ignores all subsequent delete
messages of the form $(\mathsf{cID},{\text{\sf{delete}}})$. In words, the user
communicating on channel $\mathsf{cID}^{\prime}$ can instruct $\mathsf{C}$ to
ignore deletion requests from the user communicating on channel
$\mathsf{cID}$.

It is easy to see that $\mathsf{C}$ satisfies $(0,0)$-deletion-as-
confidentiality. First, $V_{\mathsf{E}}$ is identical in the real and ideal
executions because the dictionary is write-only and $\mathsf{C}$ sends no
messages. Second $\mathsf{state}_{\mathsf{C}}$ is identical in the real and
ideal executions because the dictionary is SHI.

Recall $\mathcal{Y}_{\mathsf{dummy}}\setminus\mathcal{Y}_{\mathsf{silent}}$ is
the set of data subjects $\mathsf{Y}$ that send messages to $\mathsf{E}$ and
only delete when instructed by $\mathsf{E}$. Consider $\mathsf{Y}$ that
inserts itself into the dictionary, sends its $\mathsf{cID}_{\mathsf{Y}}$ to
$\mathsf{E}$, and then calls delete. Consider $\mathsf{E}$ that sends
$\mathsf{cID}_{\mathsf{Y}}$ to $\mathsf{C}$ as soon as it receives it from
$\mathsf{Y}$. By construction, $\mathsf{state}_{\mathsf{C}}$ contains
$\mathsf{Y}$’s data at the end of the real execution, but
$\mathsf{state}^{\prime}_{\mathsf{C}}$ in the dummy execution does not. Thus,
if the implementation $\mathcal{D}$ is perfectly correct, there are no
$R_{\mathsf{C}}$, $R^{\prime}_{\mathsf{C}}$ such that
$\mathsf{state}_{\mathsf{C}}=\mathsf{state}^{\prime}_{\mathsf{C}}$. This
violates Definition 3.2 for any $\delta<1$ and any $\epsilon<\infty$. ∎

######  Theorem 5.5.

For any $\delta>0$, there exists $\mathsf{C}$ and
$\mathsf{Y}\in\mathcal{Y}_{\mathsf{silent}}$ such that (i) $\mathsf{C}$
satisfies $(0,\delta)$-deletion-as-confidentiality for $\mathsf{Y}$, and (ii)
$\mathsf{C}$ does not satisfy $(\epsilon^{\prime},\delta^{\prime})$-deletion-
as-control for $\mathsf{Y}$ for any $\epsilon<\infty$, $\delta^{\prime}<1$.

###### Proof of Theorem 5.5.

Let $T>1/\delta$. Consider $\mathsf{C}$ implementing a write-only SHI
dictionary $\mathcal{D}$ modified as follows. Upon receiving the first message
from a channel $\mathsf{cID}$, sample $t_{\mathsf{cID}}\in[1,T]$ uniformly at
random, store it in the dictionary with key $\mathsf{cID}$, and reply with
$t_{\mathsf{cID}}$. Upon receiving delete from $\mathsf{cID}$, check the
current size of the dictionary. If $|\mathcal{D}|=t_{\mathsf{cID}}$, remove
$\mathsf{cID}$ the next time $\mathsf{C}$ is activated. Otherwise, remove
$\mathsf{cID}$ immediately.

Consider $\mathsf{Y}$ that (i) sends ${\text{\sf{insert}}}()$ to $\mathsf{C}$
on its first activation, (ii) receives $t_{\mathsf{cID}_{\mathsf{Y}}}$ in
response, and (iii) sends delete to $\mathsf{C}$ after
$t_{\mathsf{cID}_{\mathsf{Y}}}-1$ additional activations.

######  Claim 5.6.

$C^{*}$ satisfies $(0,\delta)$-deletion-as-confidentiality for
$\mathsf{Y}^{*}$.

###### Proof.

Fix $\mathsf{E}$ and $\mathsf{Y}\in\mathcal{Y}_{\mathsf{silent}}$. Because
$\mathcal{D}$ is write-only, $V_{\mathsf{E}}$ is exactly the same in the real
and ideal deletion-as-confidentiality executions. That view consists of $k$
calls to ${\text{\sf{insert}}}()$ sent to $\mathsf{C}$ and the responses
$t_{1},\dots,t_{k}$.

In contrast, $\mathsf{state}^{real}_{\mathsf{C}}$ may differ at the end of the
real and ideal executions. But only if
$|\mathcal{D}|=t_{\mathsf{cID}_{\mathsf{Y}}}$ when $\mathsf{Y}$ calls delete.
In particular,
$\mathsf{state}^{real}_{\mathsf{C}}\neq\mathsf{state}^{ideal}_{\mathsf{C}}$
requires $\mathsf{E}$ to make exactly $t_{\mathsf{cID}_{\mathsf{Y}}}-1$ calls
to $\mathsf{C}.{\text{\sf{insert}}}()$ over the course of the execution. But
$\mathsf{E}$ has no information about $t_{\mathsf{cID}_{\mathsf{Y}}}$ besides
its prior distribution. From $\mathsf{C}$ it receives only the $t_{i}$, which
are independent. From $\mathsf{Y}$ it receives nothing, as
$\mathsf{Y}\in\mathcal{Y}_{\mathsf{silent}}$. Therefore, the probability that
$\mathsf{state}^{real}_{\mathsf{C}}\neq\mathsf{state}^{ideal}_{\mathsf{C}}$ is
at most $1/T$.

$\displaystyle
d_{TV}\biggl{(}(V_{\mathsf{E}}^{real},\mathsf{state}_{\mathsf{C}}^{real}),(V_{\mathsf{E}}^{ideal},\mathsf{state}_{\mathsf{C}}^{ideal})\biggr{)}$
$\displaystyle=d_{TV}\biggl{(}\mathsf{state}_{\mathsf{C}}^{real},\mathsf{state}_{\mathsf{C}}^{ideal}\biggr{)}<\frac{1}{T}$

Hence $(V_{\mathsf{E}}^{real},\mathsf{state}_{\mathsf{C}}^{real})\
{\stackrel{{\scriptstyle{\tiny 0,\frac{1}{T}}}}{{\approx}}}\
(V_{\mathsf{E}}^{ideal},\mathsf{state}_{\mathsf{C}}^{ideal}).$ ∎

######  Claim 5.7.

$C^{*}$ does not satisfy $(\epsilon^{\prime},\delta^{\prime})$-deletion-as-
control for $\mathsf{Y}^{*}$ for any $\epsilon<\infty$, $\delta^{\prime}<1$.

###### Proof.

Consider $\mathsf{E}$ that repeats two operations: (i) activate $\mathsf{Y}$,
and (ii) send ${\text{\sf{insert}}}()$ to $\mathsf{C}$ along a new channel.
The execution $\langle\mathsf{C}(R_{\mathsf{C}}),\mathsf{Y},\mathsf{E}\rangle$
always ends with $\mathsf{Y}$ calling delete when
$|\mathcal{D}|=t_{\mathsf{cID}_{\mathsf{Y}}}$. By construction, $\mathcal{D}$
does not remove $\mathsf{Y}$ from $\mathcal{D}$. So at the end of the real
execution, $\mathsf{state}_{\mathsf{C}}$ contains the dictionary $\mathcal{D}$
that includes $\mathsf{Y}$.

In contrast, the dummy execution
$\langle\mathsf{C}(R^{\prime}_{\mathsf{C}}),\mathsf{D}(\vec{\mathsf{q}}_{\mathsf{E}})\rangle$
includes no calls to ${\text{\sf{insert}}}()$ from $\mathsf{Y}$. So at the end
of the dummy execution, $\mathsf{state}^{\prime}_{\mathsf{C}}$ contains the
dictionary $\mathcal{D}^{\prime}$ that does not include $\mathsf{Y}$. Thus, if
the implementation $\mathcal{D}$ is perfectly correct, there are no
$R_{\mathsf{C}}$, $R^{\prime}_{\mathsf{C}}$ such that
$\mathsf{state}_{\mathsf{C}}=\mathsf{state}^{\prime}_{\mathsf{C}}$. This
violates Definition 3.2 for any $\delta<1$ and any $\epsilon<\infty$. ∎

This completes the proof of Theorem 5.5. ∎

##  6 Differential Privacy and Deletion-as-control

This section describes two ways of compiling
$(\epsilon,\delta)$-differentially private mechanisms $\mathcal{M}$ into
controllers satisfying $(\epsilon,\delta)$-deletion-as-compliance. The first
applies to DP mechanisms that are run in a batch setting on a single,
centralized dataset: data summarization, query release, or DP-SGD, for example
(Section 6.1). The second applies to mechanisms satisfying pan-privacy under
continual release (Section 6.3). Along the way we define non-adaptive event-
level pan privacy (one intrusion) with continual release, first defined by
Chan et al. (2011); Dwork et al. (2010b), and an adaptive variant, building on
the adaptive continual release definition of Jain et al. (2021)(Section 6.2).
Both of our compilers make use of a SHI dictionary $\mathcal{D}$ (Section
4.1.1).

There is a strong intuitive connection between (approximate) history
independence and deletion-as-control, as illustrated by the results of the
previous section. This intuition is so strong that many prior works on machine
unlearning essentially equate deletion with history independence (Section
4.4).

However, _the examples of this section show that our notion of deletion-as-
control is much broader than history independence_. For instance, consider a
controller as follows. At some time $t_{0}$ the controller computes a
differentially-private approximation $\mathsf{out}_{t_{0}}$ to the current
number of users in the data set, and the controller stores
$\mathsf{out}_{t_{0}}$ and makes it available at all later times. Intuitively,
this controller does not satisfy any version of history independence: even if
every user request deletion at time $t_{0}+1$, the stored
$\mathsf{out}_{t_{0}}$ is unchanged—making this history easy to distinguish
from one where the all users deleted at time $t_{0}-1$. It could, however,
still satisfy deletion-as-control.

Throughout this section we consider systems with a global clock. This allows
for controllers that publish the number of weekly active users, say. For
simplicity and generality, we allow the environment to control time.
Specifically, we introduce a special query tick that only $\mathsf{E}$ can
send to $\mathsf{C}$ to increment the clock.

###  6.1 Batch differential privacy

Let $\mathcal{M}:\mathcal{D}\mapsto\mathcal{M}(\mathcal{D})$ be a non-
interactive differentially private mechanism $\mathcal{M}$. Algorithm 1
defines a simple controller $\mathsf{C}_{\mathcal{M}}^{\mathsf{batch}}$ that
satisfies deletion-as-control. It works in three phases: before tick, during
tick, and after tick. At the beginning,
$\mathsf{C}_{\mathcal{M}}^{\mathsf{batch}}$ populates a dataset $\mathcal{D}$
stored as a SHI dictionary from its input stream, returning $\bot$ in response
to every query. When it receives the tick, it evaluates
$\mathcal{M}(\mathcal{D})$, stores the result as $\mathsf{out}$, and erases
the dictionary $\mathcal{D}$. For all future queries,
$\mathsf{C}_{\mathcal{M}}^{\mathsf{batch}}$ simply returns $\mathsf{out}$. We
assume for simplicity that the mechanism $\mathcal{M}$ is a function only of
the logical contents of $\mathcal{D}$, and is independent of its memory
representation.

Algorithm 1 $\mathsf{C}_{\mathcal{M}}^{\mathsf{batch}}$ satifying deletion-as-
control from batch DP mechanism $\mathcal{M}$

1:procedure Initialize $\triangleright$ Run on first activation

2: Initialize a SHI dictionary $\mathcal{D}$

3: Initialize $\mathsf{out}=\bot$ $\triangleright$ $\bot$ is never returned by
$\mathcal{M}$

4:

5:procedure Activate($\mathsf{op}({id})$)

6: if $(\mathsf{op}\neq\text{\sf tick})\land(\mathsf{out}=\bot)$ then

7: // before tick

8: $\mathcal{D}.\mathsf{op}({id})$ $\triangleright$ Insert/modify/delete item

9: Return $\bot$

10: else if $(\mathsf{op}=\text{\sf tick})$ then

11: // during tick

12: Set $\mathsf{out}\leftarrow\mathcal{M}(\mathcal{D})$

13: Delete $\mathcal{D}$ $\triangleright$ eg: iteratively call
$\mathcal{D}.{\text{\sf{delete}}}({id})$

14: Return $\mathsf{out}$

15: else

16: // after tick

17: Return $\mathsf{out}$

######  Proposition 6.1.

  1. 1.

If $\mathcal{M}$ is $(\epsilon,\delta)$-DP, then
$\mathsf{C}_{\mathcal{M}}^{\mathsf{batch}}$ satisfies
$(\epsilon,\delta)$-deletion-as-control.

  2. 2.

For any $\epsilon>0$, suppose $\mathcal{M}$ is the Laplace mechanism with
parameter $\epsilon$ applied to a count of the number of record in its input.
Then $\mathsf{C}_{\mathcal{M}}^{\mathsf{batch}}$ satisfies
$(\epsilon,\delta)$-deletion-as-control but is _not_
$(\epsilon^{\prime},\delta^{\prime})$-HI for any $\epsilon^{\prime}<\infty$
and $\delta^{\prime}<1$.

The second part of the proposition really applies to any DP mechanism that
releases useful information about its inputs—the argument relies just on the
fact that $\mathcal{M}$ acts differently on the empty data set than it does on
a data set with many records.

###### Proof.

(1) To reduce clutter, let
$\mathsf{C}=\mathsf{C}_{\mathcal{M}}^{\mathsf{batch}}$ throughout this proof.
The simulator is described in Algorithm 2. We must show that for all
deterministic $\mathsf{E}$ and $\mathsf{Y}$ (i) $R^{\prime}_{\mathsf{C}}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ R_{\mathsf{C}}$,
and (ii)
$(\mathcal{D}^{\prime},\mathsf{out}^{\prime})=(\mathcal{D},\mathsf{out})$ with
probability at least $1-\delta$.

Fix deterministic $\mathsf{E}$ and $\mathsf{Y}$. Until a tick query,
$\mathsf{C}$’s output is determinstically $\bot$. Hence, all queries that
precede tick are fixed in advance—including whether the sequence contains a
tick at all. If there is no tick, then the whole sequence is fixed.

We consider two cases depending on whether the real sequence of queries
$\vec{\mathsf{q}}$ includes tick. Suppose there is no tick in
$\vec{\mathsf{q}}$. By construction, $\mathsf{C}$’s state $\mathsf{out}=\bot$
and $\mathcal{D}$ may be non-empty.
$\mathsf{Sim}(\vec{\mathsf{q}}_{\mathsf{E}},R_{\mathsf{C}},\mathsf{out})$
outputs $R^{\prime}_{\mathsf{C}}=R_{\mathsf{C}}$. Consider $\mathcal{D}$ in
the real execution resulting from queries $\vec{\mathsf{q}}$ and randomness
$R_{\mathsf{C}}$, and $\mathcal{D}^{\prime}$ in the ideal execution resulting
from $\vec{\mathsf{q}}_{\mathsf{E}}$ and $R^{\prime}_{\mathsf{C}}$. The only
difference between $\vec{\mathsf{q}}$ and $\vec{\mathsf{q}}_{\mathsf{E}}$ is
$\mathsf{Y}$’s queries. Because $\vec{\mathsf{q}}$ ends with delete from
$\mathsf{Y}$, and dictionaries support logical deletion, the logical contents
of $\mathcal{D}$ and $\mathcal{D}^{\prime}$ are identical. Applying Theorem 1
from Hartline et al. (2005)666The theorem states that reversible $(0,0)$-SHI
data structures have canonical representations, up to initial randomness.,
$\mathcal{D}^{\prime}=\mathcal{D}$. In this case, the simulation is perfect.

Suppose there is a tick in $\vec{\mathsf{q}}$. By construction, $\mathsf{C}$’s
state $\mathcal{D}$ is empty and $\mathsf{out}\neq\bot$. The simulator samples
$R^{\prime}_{\mathsf{C}}$ uniformly conditioned on
$\mathsf{out}^{\prime}=\mathsf{out}$ (if such $R^{\prime}_{\mathsf{C}}$
exists, uniformly otherwise). Consider $\mathcal{D}$ in the real execution
resulting from queries $\vec{\mathsf{q}}$, and $\mathcal{D}^{\prime}$ in the
ideal execution resulting from $\vec{\mathsf{q}}_{\mathsf{E}}$. $\mathcal{D}$
and $\mathcal{D}^{\prime}$ represent fixed neighboring datasets: differing
only on $\mathsf{Y}$. Take $f(R)=\mathcal{M}(\mathcal{D};R)$ and
$g(R)=\mathcal{M}(\mathcal{D}^{\prime};R)$. Because $\mathcal{M}$ is
$(\epsilon,\delta)$-DP, $f(R)\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ g(R)$. The
simulator samples $R^{\prime}_{\mathsf{C}}$ as in the statement of Lemma A.1.
Applying that lemma completes the proof.

(2) When $\mathcal{M}$ is the Laplace mechanism,
$\mathsf{C}_{\mathcal{M}}^{\mathsf{batch}}$ satisfies deletion as control by
part (1). To see why it does not satisfy even weak, nonadaptive history
independence, consider a (nonadaptive) sequence $\sigma_{n}$ of $n$ distinct
insertions, followed by a tick, followed by $n$ corresponding deletions. The
minimal equivalent sequence $\sigma^{*}=[\sigma_{n}]$ consists only of the
tick. The value $\mathsf{out}$ generated at the tick will follow
$n+\mathsf{Lap}(1/\epsilon).$ If we consider the event
$E_{n}={\left\\{{\mathsf{out}<n/2}\right\\}}$, then $E_{n}$ occurs with
probability at least $1-\exp(\epsilon n/2)$ in the real world. However, if we
were to run a dummy execution of the controller
$\mathsf{C}_{\mathcal{M}}^{\mathsf{batch}}$ with $\sigma^{*}$, the probability
of $E_{n}$ would be at most $\exp(\epsilon n)$, regardless of whether we use
the same randomness $R$ as in the real world or a fresh string $R^{\prime}$.
Suppose, for contradiction, that $\mathsf{C}_{\mathcal{M}}^{\mathsf{batch}}$
satisfies $(\epsilon^{\prime},\delta^{\prime})$-HI. Then

$\displaystyle 1-\exp(-\epsilon n)\leq\Pr_{\text{real}}(E_{n})$
$\displaystyle\leq\exp(\epsilon^{\prime})\cdot\Pr_{\text{dummy}}(E_{n})$
$\displaystyle\leq\exp(\epsilon^{\prime}-\epsilon n)+\delta^{\prime}\,.$

For any $\epsilon^{\prime}>0$ and $\delta^{\prime}<1$, we can get a
contradiction by choosing
$n>\frac{1}{\epsilon}\ln{\left({\frac{e^{\epsilon^{\prime}}+1}{1-\delta^{\prime}}}\right)}$.
∎

Algorithm 2 $\mathsf{Sim}$ for
$\mathsf{C}=\mathsf{C}_{\mathcal{M}}^{\mathsf{batch}}$

1:input $R_{\mathsf{C}}$, $\vec{\mathsf{q}}_{\mathsf{E}}$, $\mathsf{out}$

2:if $\text{\sf tick}\notin\vec{\mathsf{q}}_{\mathsf{E}}$ then

3: $R^{\prime}_{\mathsf{C}}\leftarrow R_{\mathsf{C}}$

4:else

5: Run the default $\mathsf{Sim}$ (Def. 3.3) Namely, sample
$R^{\prime}_{\mathsf{C}}$ uniformly conditioned on
$\mathsf{out}^{\prime}=\mathsf{out}$, where
$\mathsf{out}^{\prime}=\mathsf{C}(\vec{\mathsf{q}}_{\mathsf{E}};R_{\mathsf{C}}^{\prime})$
is the output of $\mathsf{C}$ in the ideal execution (with queries
$\vec{\mathsf{q}}_{\mathsf{E}}$). If no such $R^{\prime}_{\mathsf{C}}$ exists,
sample $R^{\prime}_{\mathsf{C}}$ uniformly at random.

6:Return $R^{\prime}_{\mathsf{C}}$

###  6.2 Adaptive pan-privacy with continual release

In this section, we formalize the definition of adaptive pan-privacy with
continual release (against a single intrusion), extending the non-adaptive
versions originally defined in Chan et al. (2011); Dwork et al. (2010b). The
continual release setting concerns an _online controller_ that processes a
stream of elements and produces outputs at regular time intervals. We say two
streams are (event-level) _neighboring_ if they differ in at most one stream
item. We consider privacy against an adversary that can adaptively choose
neighboring streams (one of which is processed by the online mechanism) and
inspect the internal state of the online algorithm once. This adaptive game
defines the adversary’s view. Informally, adaptive pan-privacy under continual
release requires that, for all adaptive adversaries, the adversary’s view for
the two streams is $(\epsilon,\delta)$-close.

##### Preliminaries

A _stream_ $\mathbf{x}\in(\\{\text{\sf regular},\text{\sf intrusion},\text{\sf
challenge}\\}\times\mathcal{X})^{*}$ consists of elements of the form
$(\mathsf{code},\mathsf{op}({id}))$. The _control code_
$\mathsf{code}\in\\{\text{\sf regular},\text{\sf intrusion},\text{\sf
challenge}\\}$ controls the execution of the pan-privacy continual release
security game and is never seen by the mechanism itself (see Algorithm 3). The
_data operation_ $\mathsf{op}({id})\in\mathcal{X}$ is sent to the pan-private
mechanism. The universe of data operations $\mathcal{X}$ includes a special
tick operation (which requires no $id$ tag) which indicates to the mechanism
that one time step has passed.

######  Definition 6.2 (Online Algorithm).

An _online algorithm_ $\mathcal{M}$ is initialized with a time horizon $T$ and
is defined by an internal algorithm $I$. Algorithm $\mathcal{M}$ processes a
stream of elements through repeated application of
$I:(\mathsf{op}({id}),\mathsf{state}_{\mathcal{M}})\mapsto(\mathsf{state}^{\prime}_{\mathcal{M}},\mathsf{out})$,
which (with randomness) maps a stream element and the current internal state
to a new internal state and an output (which may consist of $\bot$). For
simplicity, we only consider online algorithms that produce outputs when a
tick occurs. That is, $\mathsf{op}({id})\neq\text{\sf tick}$ implies that
$\mathsf{out}=\bot$. The internal state of $\mathcal{M}$ includes a clock
which counts the number of ticks that have previously occurred in the stream.
When $\mathcal{M}$’s internal number of clock ticks reaches $T$, it stops
processing new stream elements and always outputs $\bot$.

Any stream $\mathbf{x}$ with a single instance of challenge naturally gives
rise to two neighboring sequences of data operations
$\mathbf{x}^{(\mathtt{in})}$ and $\mathbf{x}^{(\mathtt{out})}$ which include
or exclude the challenge operation, respectively.

######  Definition 6.3 (Event-level neighboring sequences).

For stream $\mathbf{x}$ containing a single insteance of challenge, we define
two _event-level neighboring sequences_ $\mathbf{x}^{(\mathtt{in})}$ and
$\mathbf{x}^{(\mathtt{out})}$ as follows:

$\displaystyle\mathbf{x}^{(\mathtt{in})}$
$\displaystyle:=\\{\mathsf{op}({id})\mid(\text{\sf
regular},\mathsf{op}({id}))\in\mathbf{x}\text{ or }$
$\displaystyle\qquad(\text{\sf challenge},\mathsf{op}({id}))\in\mathbf{x}\\}$
$\displaystyle\mathbf{x}^{(\mathtt{out})}$
$\displaystyle:=\\{\mathsf{op}({id})\mid(\text{\sf
regular},\mathsf{op}({id}))\in\mathbf{x}\\}.$

##### Event-level pan privacy

We formalize the definition of non-adaptive pan-privacy with continual release
(against a single intrusion), based on (Chan et al., 2011; Dwork et al.,
2010b). Although our version of the definition is identical in spirit to
previous definitions, our setting has two complications which are notationally
challenging but not conceptually so. First, the algorithm $\mathcal{M}$ may
process any number of sequence items before producing an output. Second, we
consider sequences as neighboring if they differ by insertion or deletion of
items, which causes a discrepancy in sequence indices. We have chosen to write
the non-adaptive definition so that it is clearly a special case of the
adaptive version, defined later in the section.

Let $\mathbf{x}$ be a stream with a single intrusion. For online algorithm
$\mathcal{M}$ and $\mathtt{side}\in\\{\mathtt{in},\mathtt{out}\\}$, we denote
by
$V_{\mathcal{M},\mathbf{x}}^{(\mathtt{side})}=(\mathsf{state},\overrightarrow{\mathsf{out}})$
the view of an attacker who sees (i) the sequence of outputs
$\overrightarrow{\mathsf{out}}$ produced by
$\mathcal{M}(\mathbf{x}^{(\mathtt{side})})$, and (ii) a snapshot of
$\mathsf{state}_{\mathcal{M}}$ of the internal state of $\mathcal{M}$ at the
time indicated by intrusion in $\mathbf{x}$.

######  Definition 6.4 (Non-Adaptive Event-Level PP with CR (Chan et al.,
2011; Dwork et al., 2010b)).

An online algorithm $\mathcal{M}$ satisfies $(\epsilon,\delta)$-non-adaptive
event-level pan-privacy in the continual release model if for all streams
$\mathbf{x}$ with at most one challenge and at most one intrusion:

$V_{\mathcal{M},\mathbf{x}}^{(\mathtt{in})}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
V_{\mathcal{M},\mathbf{x}}^{(\mathtt{out})}.$

##### Adaptive pan privacy

We define adaptive event-level pan privacy with continual release against a
single intrusion, following the continual-release model of Jain et al. (2021)
(which did not allow for intrusions). In this game, the adversary $\mathsf{A}$
decides when to increment timesteps (i.e., by querying $(\text{\sf
regular},\text{\sf tick})$), when to issue a single challenge query, when to
intrude, and when to terminate the game (i.e., using $\mathsf{code}=\bot$).
Depending on whether $\mathtt{side}$ is $\mathtt{in}$ or $\mathtt{out}$,
$\mathcal{M}$ is either given the challenge query or not. Thus, the
neighboring data streams we consider differ by the insertion or deletion of a
single query. We require that for the challenge query,
$\mathsf{op}\neq\text{\sf tick}$. We assume for simplicity that
$\mathcal{M}(\mathsf{op}({id}))$ produces no output unless
$\mathsf{op}=\text{\sf tick}$.

Algorithm 3 Privacy game $\Pi_{\mathcal{M},\mathsf{A}}^{(\mathtt{side})}$ for
the adaptive event-level pan privacy with continual release model. The game
halts if any assertion fails.

1:procedure RunGame(time horizon $T\in\mathbb{N}$)

2: // initialize global variables

3: $\mathcal{M}.\textsc{Initialize}(T)$

4: $\mathsf{intruded}\leftarrow\text{\sf false}$

5: $\mathsf{challenged}\leftarrow\text{\sf false}$

6:

7: // interaction between $\mathsf{A}$ and $\mathcal{M}$

8: $\mathsf{out}\leftarrow\bot$

9: repeat

10: $(\mathsf{code},\mathsf{op}({id}))\leftarrow\mathsf{A}(out)$

11: $\mathsf{out}\leftarrow\textsc{Activate}(\mathsf{code},\mathsf{op}({id}))$

12: until $\mathsf{code}=\bot$

13:

14:procedure Activate($\mathsf{code},\mathsf{op}({id})$)

15: if $\mathsf{code}=\text{\sf intrusion}$ then

16: Assert: $\mathsf{intruded}=\text{\sf false}$

17: $\mathsf{intruded}\leftarrow\text{\sf true}$

18: return $\mathsf{state}_{\mathcal{M}}$

19:

20: if $\mathsf{code}=\text{\sf regular}$ then

21: return $\mathcal{M}(\mathsf{op}({id}))$ $\triangleright$ If
$\mathsf{op}\neq\text{\sf tick}$, then $\mathcal{M}(\mathsf{op}({id}))=\bot$

22:

23: if $\mathsf{code}=\text{\sf challenge}$ then

24: Assert: $(\mathsf{challenged}=\text{\sf false})$ and
$(\mathsf{op}\neq\text{\sf tick})$

25: $\mathsf{challenged}\leftarrow\text{\sf true}$

26: if $\mathtt{side}=\mathtt{in}$ then

27: Run $\mathcal{M}(\mathsf{op}({id}))$ $\triangleright$ By assumption
$\mathsf{op}({id})\neq\text{\sf tick}$ and
$\mathcal{M}(\mathsf{op}({id}))=\bot$

28: return $\bot$

29:

30: else

31: return $\bot$

######  Definition 6.5.

We denote by _$V_{\mathcal{M},\mathsf{A}}^{(\mathtt{side})}$_ the _view of
$\mathsf{A}$_ in the game $\Pi_{\mathcal{M},\mathsf{A}}^{(\mathtt{side})}$,
consisting of $\mathsf{A}$’s internal randomness and the transcript of all
messages $\mathsf{A}$ sends and receives.777One could instead define
$\mathsf{A}$’s view as its internal state at the end of the game. Our version
of the view contains enough information to compute that internal state and is
simpler to work with.

######  Definition 6.6 (Adaptive Event-Level PP with CR).

A mechanism $\mathcal{M}$ is _$(\epsilon,\delta)$ -DP in the adaptive event-
level pan-privacy with continual release model_ if for all adversaries
$\mathsf{A}$,

$V_{\mathcal{M},\mathsf{A}}^{(\mathtt{in})}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
V_{\mathcal{M},\mathsf{A}}^{(\mathtt{out})}.$

######  Remark 6.7.

The definition above makes sense in a setting where the state
$\mathsf{state}_{\mathcal{M}}$ does not have information about the mechanism’s
future random coins. If the adversary could deduce future randomness, then
security would be unachievable: an adversary could intrude at time 0, learn
all the algorithm’s randomness, and then easily tell whether the mechanism had
received $x^{*}$ or not.

An alternative, which does allow for the adversary learning future randomness,
is to require that the challenge is possible only before intrusion
(specifically, Line 24 additionally assert that $\mathsf{intruded}=\text{\sf
false}$). This definition is satisfiable by interesting mechanisms—for
example, a mechanism that initializes a counter with Laplace noise, then adds
subsequent stream elements $x$ in $[0,1]$ to the counter, and outputs the