# Temporal Motifs in Smart Grid

Rucha Bhalchandra Joshi
<EMAIL_ADDRESS>Machine Learning And Building (MLAB),
School of Computer Sciences
National Institute of Science Education and Research, Bhubaneswar - 752050,
India
Homi Bhabha National Institute, Anushaktinagar, Mumbai - 400094, India  Annada
Prasad Behera
<EMAIL_ADDRESS>Machine Learning And Building (MLAB),
School of Computer Sciences
National Institute of Science Education and Research, Bhubaneswar - 752050,
India
Homi Bhabha National Institute, Anushaktinagar, Mumbai - 400094, India
Subhankar Mishra
<EMAIL_ADDRESS>Machine Learning And Building (MLAB),
School of Computer Sciences
National Institute of Science Education and Research, Bhubaneswar - 752050,
India
Homi Bhabha National Institute, Anushaktinagar, Mumbai - 400094, India

###### Abstract

A complex network can be characterized by patterns. Such frequently occurring
significant patterns are called motifs and in a time dependent network, they
are called temporal motifs. One of the temporal networks where temporal motifs
are observed and play a major role; is the Smart Grid. The energy consumption
pattern across the appliances, houses, communities and entire cities help
energy utility companies and consumers plan their electricity generation and
consumption. The temporal motifs for the smart grid constitutes of the
consumers and producers and the edge or connection represents energy flow
between two participants of the network, these connections last till the power
is being consumed/generated. This paper formally defines the temporal motifs
for smart grid network and proposes a way to create such temporal motifs in
the network. We also discuss how the temporal motifs fit into the hierarchical
structure of power distribution system of Smart Grid.

Keywords— Smart Grid, Temporal Motifs, Complex Systems, Cyber-physical Systems

##  1 INTRODUCTION

Many complex systems can be abstracted with the help of networks. The entities
participating in the systems are modeled as nodes and the relations by which
they are linked to each other are modeled as the edges of a network graph.
Abstractions help us study the complex system such as food chain, citation
network. Time dependent systems can be abstracted as temporal networks. Some
notable examples of temporal network are Facebook, Email as well as recent
networks such as Bitcoin. Structure of the temporal network changes with time.
Since the edges in temporal graphs depend on time, their presence is
determined only at a given time. To understand the behaviour of the temporal
network, it is essential to consider the time of occurrence of temporal edges.

One such system is smart grid network. A smart grid has various entities, such
as producers, consumers, transmitters of power, participating in the network.
The hierarchical structure of the smart grid has been discussed by [Aggarwal
et al., 2010, Mishra et al., 2016] where the power distribution in the grid is
according to the voltage. [Rech and Harth, 2012] discussed the existence of
the consumption sector of the hierarchy wherein the lowermost layer consists
of the last links of distribution grid connecting consumers to the main grid.
A transformer supplies the power to the consumers that are connected to it.
So, the second layer from the bottom consists of transformers. The third layer
is of substations that supply power to the transformers in second layer. This
hierarchy goes up along with all the participating entities in the grid
network. Pattern of distribution of power consumption over the period of time
form motifs. These motifs depicts the behaviour of the participating entities.

In a smart grid, the meters can get the data pertaining to each of the
appliances used in the house that consumes amount of electricity. Smart meter
keeps track of the consumption of each of the rooms or any other
infrastructure that consumes electricity. Hence, at household level, the
electricity consumption and distribution is known with the help of smart
meters. The inferences about the usage of electricity at the lowermost layer
in a smart grid can be drawn by taking this consumption data into
consideration.

Our contributions are as follows:

  * •

We formally define temporal motifs that occur in smart grid network.

  * •

We show a method for constructing such temporal motifs in smart grid network.

  * •

We discuss temporal motifs in smart grid with overlapping window and fitting
the temporal motifs in the hierarchical structure of the smart grid.

The remainder of the paper is organized as follows: Section 2 discusses the
related work. We discuss the background work in Section 3. Section 4 gives the
detailed explanation of our proposed model. We present a case study and
discussion of temporal motifs in smart grid network are in Section 3 and 4
respectively. We present the conclusions in Section 6.

##  2 RELATED WORK

Motifs [Milo et al., 2002] are the basic building blocks of a complex network.
They are recurring, significant patterns of interconnections. The network
motifs are defined to study the structural design principles of complex
networks in various fields such as biochemistry, neurobiology, ecology,
engineering and so on.

Motifs, defined as the frequently occurring and significant patterns in time,
can be used to characterize the time series data [Lin et al., 2003]. Motifs in
temporal networks have been defined in order to understand their role in the
temporal networks such as the network of emails, phone calls, social media
etc. [Paranjape et al., 2017]. However, they only consider the occurrence of
the edges one at a time without any duration attached to the existence of the
edges.

Motif based pattern detection technique was proposed to discover regular
behaviour of smart meter users [Funde et al., 2018]. The model proposed by
[Funde et al., 2018] considers one appliance at a time and detects the motifs
formed by it. They develop temporal association rule mining to find the
relation between usage of energy by various appliances in a particular time
period. However, considering only one appliance at a time does not tell a
complete story about the consumption pattern of the members of the house.

##  3 BACKGROUND WORK

###  3.1 Temporal Graph and Motif

In a temporal graph $G=(V,E)$ where $V$ is set of vertices and $E$ is set of
edges, the temporal edges are represented as $(u,v,t)$ where $u,v\in V$ and a
timestamp $t$ is associated with the edge. Temporal motif is a collection of
edges in a particular sequence that form a particular structure in a given
time window $\delta$. Since the timestamps are attached with each of the edges
in temporal network, the motif is the structure occurring within time $\delta$
from the occurrence time of first edge. This time window of size $\delta$ is
slid over the time as we consider the next motif. When we consider the
temporal edges in smart grid, the edges occur at different times but they last
for a duration of time. Smart grid is a specific application of temporal
network where the edges have a time of occurrence and it remains in the
network till the appliance that caused it to occur was switched off or no
longer draws any energy from the meter. This differentiates our work from the
previous work as edges stay alive for a certain duration. We say that an edge
occurs at a given time when the appliance corresponding to the node connecting
the edge is turned on. The smart meter captures the energy at particular time
interval in a sequence, hence we have to assign a window time to it rather
than the actual start time of the consumption. The energy consumption by same
appliance may vary at different times.

###  3.2 Topology of Smart Grid

Figure 1: Topology of Power Grid

The power distribution grid is arranged according to the voltage [Aggarwal et
al., 2010]. The various levels of the hierarchy are connected using the
voltage networks, here power plants are connected via high voltage networks
and the level of household appliances is connected using a voltage network.
The smart grid is defined to consist of nodes $N$ and interconnected edges
$E$; where nodes represent the actors and are connected to $\\#b$ other nodes
($b$ is branching factor). The levels of this hierarchy is denoted by $L$
[Rech and Harth, 2012].

##  4 SMART GRID TEMPORAL MOTIFS

We propose a model (Figure 2) for creation of temporal star motifs with
associated symbol corresponding to the energy consumption. We also show how
these motifs help to draw inferences from the hierarchy of the participants of
a smart grid network. In our proposed model the edges of the motifs have been
tagged with symbols associated with corresponding energy consumption levels
and time window. These timestamps are indicatives of window frame numbers.
They imply the order of occurrences of the motif structures.

Figure 2: Overview of motif creation process for smart grids

Consider $m_{i}$ to be meter reading (total) at a given time $i$. We consider
a time series $T={m_{1},m_{2},...,m_{t}}$. Each $m_{i}$ consists of the values
corresponding to internal distribution of energy among all the appliances
utilizing the energy at a given time $i$. Let $A$ be the set of appliances.
Let $c^{j}_{i}$ be the energy consumed by the $j^{th}$ appliance at time $i$.
Therefore,

$m_{i}=\sum_{j\in A}c^{j}_{i}$

###  4.1 Motif Creation

A star motif is defined as a graph of $k$ nodes in total, out which one node
(the center node) has $k-1$ neighbors, which is the center node while all the
other nodes have only one neighbor each. An example of star motif is shown in
Fig. 3.

Figure 3: Example of a star motif. There are 5 nodes in total. One center node
and four neighbors to the center node. The direction of the edges between the
center node and the neighboring nodes depends on the relationship between
them. Figure 4: Example of a static star motif in a house

We consider a particular consumer where there are various appliances in a
house that contribute to overall consumption of energy in the house. All of
which are essentially connected to the main smart meter. We create a star
motif of these appliances along with the smart meter. Fig 4 shows a star motif
within a house where we consider the smart meter in the house to be the center
node and all the appliances to be the rest of the nodes which are only
connected to the center node. The nodes for the appliances that draw energy
from the meter are represented using an edge from meter (center node) to the
appliance (corresponding neighboring node). For any other equipment that
generates energy (e.g. solar panel), the edge goes from the equipment to the
center node.

###  4.2 Symbolic Representation

  1. 1.

Data Preprocessing and Min-max Normalization. Time series data preprocessing
is done to normalize the data. We consider smart meter data which keeps track
of consumption of each of the appliance. We perform min-max normalization so
that the values after normalization lies between $[0,1]$. The normalized value
$y$, of a data point $x$, is given by

$y=\frac{(x-min)}{(max-min)}$

where $min$ is the minimum and $max$ is the maximum data value in the dataset.

  2. 2.

Piecewise Aggregate Approximation. On the normalized data, we apply Piecewise
Aggregate Approximation (PAA) to discretize the data. By selecting the right
parameters in PAA, it can be altered to suit the needs of the application at
hand. The normalized time series data is divided into $w$ windows. The average
of values in every window is calculated.

  3. 3.

Matching Symbols to Energy Levels. After PAA, we represent the energy
consumption of each of the appliance with a symbol. Number of energy levels
and their corresponding symbols is another parameter that can be set according
to use case. The symbol values represent the levels of energy consumption over
normalized data. The data values range between 0 and 1, so we decide on number
of symbol to be used and range of each of energy consumption corresponding to
each symbol. The number of energy levels vary application to application.

###  4.3 Symbol assignments to edges of a motif

The edges in static motif that we created in first step, for a house is
assigned timestamps associated with the time window in which we are
determining the associated symbol. In the static motifs, edges are between the
main line and an appliance. The temporal edge occurs in smart grid in the
window in which an appliance is turned on.

We define the temporal edge for grid network as quadruple represented as
$(u,v,t_{w},x)$. Table 1 describes each component of the quadruple. We perform
the operations described in the previous steps on the data, to get the symbols
associated for each of the appliance in the same set of time windows. Then,
for a particular window, consider all the appliances along with meter as
nodes, while the energy production and consumption among appliances determine
the directions between the edges and the level of energy consumption is given
by the symbol associated with the edge. The time window is in which we are
determining the consumption level is given by the timestamp corresponding to
the time window.

Variable |  Description
---|---
$u$ |  Supplier of power (any appliance that produces or supplies power)
$v$ |  Consumer of power (any appliance that consumes power)
$t_{w}$ |  Timestamp of the time window corresponding to the edge
$x$ |  Symbol corresponding to the level of energy consumption assigned to the edge n the given window
Table 1: Description of variables associated with a temporal edge in smart
grid

The complete data of consumption in a grid can be represented as the
collection of the temporal edges we defined earlier.

Figure 5: Example of star motif in a house

###  4.4 Temporal Motifs for Electric Grid Network

As shown in Fig. 5, along with assignments of symbols to the edges in static
motif, note that this motif structure occurs in a particular time duration,
since each of the symbols assigned to the edges represent the level of
consumption in a particular time period. The motif helps us to look at the
consumption and distribution of energy among all appliances in a time slot in
a house. The collection of such motifs over a time windows of size $\delta$ is
defined to be a temporal motif for energy consumption data.

##  5 CASE STUDY

We take an example to demonstrate the steps to create temporal motifs in smart
grid network. We take a part of Pecan Street Dataport [Dataport,] from 15
minute dataset. We consider a house with data-id 27, which is located at New
York. For this house, we consider the consumption values for the time period
04:00:00 to 07.00.00 on 2019-05-01.

###  5.1 Motif Creation

Figure 6: Static Motif for house ID 27

The underlying star motif for this house ID is shown in Fig.6. This is derived
based on the appliances used in the house.

###  5.2 Symbolic Representation

  1. 1.

Data Preprocesssing and Min-max Normalization. Preprocessing and min-max
normalization of data is done according to formulas mentioned in Section 1 to
get the normalized data.

  2. 2.

Piecewise Aggregate Approximation. Since the data has a duration of 3 hours,
with windows size of 1 hour, the number of windows $w=3$. For any given time
window there is a value attached to it which is average of the values
corresponding to the timestamps in the window.

  3. 3.

Matching Symbols to Energy Levels. We consider 4 symbols $a,b,c$ and $d$, they
correspond to four consumption levels. Very low consumption is represented by
a symbol $a$, $b$ represents average energy consumption, $c$ represents more
than average consumption of energy while very high energy consumption is
represented by symbol $d$.

We define the range for each of the symbols as shown in Table.2.

Symbol | Range
---|---
$a$ | $0\leq value<0.25$
$b$ | $0.25\leq value<0.5$
$c$ | $0.5\leq value<0.75$
$d$ | $0.75\leq value\leq 1$
Table 2: Range for each of the symbols

###  5.3 Symbol assignments to edges of a motif

Each edge in the static motif created in Section 5.1 has a symbol that
corresponds to the average of the values of consumption on each edge in a
window. The symbols are assigned to the edges. An example of a motif in House
ID 27 for time window labelled $t_{1}$ for duration on 1 hour is shown in
Fig.7(a).

(a) Motif at time $t_{1}$

(b) Motif at time $t_{2}$

(c) Motif at time $t_{3}$

Figure 7: Temporal motifs in smart grid network

###  5.4 Temporal Motifs for Electric Grid Network

. A sequence of motifs created in Section 5.3 may have different symbols
associated with their edges in different time windows, since the energy
consumption varies over time. Such a sequence is the temporal motif in a smart
grid network. The final temporal motif with 3 time windows is shown in Fig.7.
Increase in consumption level is indicated by symbols inside upward pointing
triangles, whereas the decrease in consumption is indicated by symbols inside
triangles facing downward in the temporal motifs.

##  6 DISCUSSION

#### Overlapping Temporal Motifs

While we only consider the window for finding the symbols associated with
edges to be non-overlapping, other possibilities to be considered are
overlapping window and the absolute consumption values. Considering absolute
values is too specific because the consumption of energy on one day may not be
exactly the same as that on the next day. Hence assigning symbols based on
absolute values at a given time may not help infer anything useful about the
data. In a time period, if the average data consumption is considered then it
gives the approximate consumption level of the appliance.

Overlapping window can be considered if it is needed for the application under
consideration. We slide the window over the time duration with some
predetermined time overlapping in two consecutive windows. This would help in
maintaining the information related to continuity of the data to some extent
depending on how much the overlap is.

#### Fitting Temporal Motifs into Smart Grid hierarchy

We propose this model for residential type of locality. This is easily
scalable to other types of localities as well, such as industrial, commercial
etc and can be extended to fit other hierarchical levels in the smart grid as
well as other complex networks. To study the role that these motifs play in
smart grid network, it is essential that we consider the hierarchy of the
participants of the network. The hierarchy described in [Rech and Harth, 2012]
is discussed below to suit for the requirement of our model.

  * •

The very basic level in the hierarchy consists of the appliances in a
household. As discussed earlier the motifs which are formed at this layer are
based on electricity consumption of each of the appliances at various times.

  * •

The layer above the layer of appliances is of houses in a locality or a
community residing at a particular location. The motifs would consist of the
houses in the locality and the point of supply of electricity to all these
houses as nodes. The consumption of each of the houses at various times would
determine the edges and the direction of the edges. These motifs can be
defined in similar fashion as we did earlier by determining the suitable
parameter values.

  * •

Similarly, the next layer consists of communities which together form a city.

  * •

More layers can be thought of and considered on top of the previously
mentioned layers so as to build the model of motifs that will help enable us
to study and determine various aspects of a smart grid network.

##  7 CONCLUSION

Temporal motifs play an important role in characterizing networks. The change
in usage of power over time helps to study the behaviour of the consumers. We
have formally defined the temporal motifs in smart grid network. We have also
described the construction of such temporal motifs in smart grid network,
without overlapping windows, how to fit them in the hierarchical structure of
the network. In future we will use motifs to draw inferences about
participants of the grid network. We will also look at impact of this model on
the energy distribution policies.

## ACKNOWLEDGEMENTS

This research was partially supported by NRDMS/UG/S.Mishra/Odisha/E-01/2018

## References

  * [Aggarwal et al., 2010] Aggarwal, A., Kunta, S., and Verma, P. K. (2010).  A proposed communications infrastructure for the smart grid.  In 2010 Innovative Smart Grid Technologies (ISGT), pages 1–5, Gaithersburg, MD, USA. IEEE.
  * [Dataport, ] Dataport.  https://dataport.pecanstreet.org/.  Pecan Street Inc. Dataport, accessed on 24 January 2020.
  * [Funde et al., 2018] Funde, N., Dhabu, M., and Balande, U. (2018).  Motif-Based Pattern Detection Method for Smart Energy Meter Data.  In 2018 3rd International Conference for Convergence in Technology (I2CT), pages 1–5, Pune. IEEE.
  * [Lin et al., 2003] Lin, J., Keogh, E., Lonardi, S., and Chiu, B. (2003).  A symbolic representation of time series, with implications for streaming algorithms.  In Proceedings of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, DMKD ’03, page 2–11, New York, NY, USA. Association for Computing Machinery.
  * [Milo et al., 2002] Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., and Alon, U. (2002).  Network Motifs: Simple Building Blocks of Complex Networks.  Science, 298(5594):824–827.
  * [Mishra et al., 2016] Mishra, S., Li, X., Pan, T., Kuhnle, A., Thai, M. T., and Seo, J. (2016).  Price modification attack and protection scheme in smart grid.  IEEE Transactions on Smart Grid, 8(4):1864–1875.
  * [Paranjape et al., 2017] Paranjape, A., Benson, A. R., and Leskovec, J. (2017).  Motifs in temporal networks.  Proceedings of the Tenth ACM International Conference on Web Search and Data Mining - WSDM ’17.
  * [Rech and Harth, 2012] Rech, D. and Harth, A. (2012).  Towards a decentralised hierarchical architecture for smart grids.  In Proceedings of the 2012 Joint EDBT/ICDT Workshops on \- EDBT-ICDT ’12, page 111, Berlin, Germany. ACM Press.


final value on the first clock tick, satisfies the weaker, alternative
definition.

###  6.3 From pan-privacy to deletion-as-control

Algorithm 4 describes a general transformation from an event-level pan private
algorithm to a controller satisfying deletion-as-control. It uses as a
building block a strongly history independent dictionary $\mathcal{D}$
(Section 4.1.1). For each ${id}$, the controller passes the first operations
$\mathsf{op}({id})$ to the underlying pan private mechanism $\mathcal{M}$. It
also passes all tick, which produce output.
$\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$ uses the dictionary $\mathcal{D}$ to
check whether a given ${id}$ has already issued a query to $\mathcal{M}$. To
delete, ${id}$ is removed from $\mathcal{D}$ but $\mathcal{M}$ is unaffected.
(Note that a deleted user can then issue a new query to $\mathcal{M}$; we make
no guarantees for such users.)

We assume that the randomness tape of $\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$
defined in Algorithm 4 is partitioned into two independent strings:
$R_{\mathcal{M}}$ to be used by the mechanism $\mathcal{M}$, and
$R_{\mathcal{D}}$ to be used by $\mathcal{D}$. Additionally, we assume that
the state of $\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$ can be partitioned into
one part containing $\mathsf{state}_{\mathcal{M}}$ and another part with
$\mathsf{state}_{\mathcal{D}}$. Beyond from $\mathsf{state}_{\mathcal{M}}$ and
$\mathsf{state}_{\mathcal{D}}$, the controller
$\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$ uses only ephemeral state and no
additional randomness.

Algorithm 4 $\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$ Deletion Compliant
Controller Based on Event-Level Pan-Private Algorithm

1:procedure Initialize(Time horizon $T\in\mathbb{N}$, privacy parameters
$\epsilon,\delta$, query access to event-level pan-private algorithm
$\mathcal{M}$)

2: Initialize $\mathcal{M}$ with parameters $(\epsilon,\delta,T)$

3: Initialize an empty SHI dictionary $\mathcal{D}$

4:

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

6: if $\mathsf{op}=\text{\sf tick}$ then $\triangleright$ By assumption
$\mathsf{Y}$ can never query tick

7: return $\mathcal{M}(\text{\sf tick})$

8: if $\mathsf{op}={\text{\sf{delete}}}$ then

9: $\mathcal{D}.{\text{\sf{delete}}}({id})$ $\triangleright$ If
${id}\notin\mathcal{D}$, nothing happens.

10: return $\bot$

11: if ${id}\in\mathcal{D}$ then

12: return $\bot$

13: if ${id}\notin\mathcal{D}$ then

14: $\mathcal{D}.{\text{\sf{insert}}}({id})$

15: $\mathcal{M}(\mathsf{op}({id}))$

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

######  Theorem 6.8.

If a controller $\mathcal{M}$ satisfies $(\epsilon,\delta)$-adaptive event-
level pan-privacy with continual-release, then the composed controller
$\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$ as described in Algorithm 4 satisfies
$(\epsilon,\delta)$-deletion-as-control.

We will prove the statement by showing that
$\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$ satisfies
$(\epsilon,\delta)$-deletion-as-confidentiality (Lemma 6.9) and then apply
Theorem 5.3 to prove that $\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$ satisfies
$(\epsilon,\delta)$-deletion-as-control.

######  Lemma 6.9.

If a controller $\mathcal{M}$ satisfies $(\epsilon,\delta)$-adaptive event-
level pan-privacy with continual release, then the composed controller
$\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$ as described in Algorithm 4 satisfies
$(\epsilon,\delta)$-deletion-as-confidentiality (Definition 5.1).

###### Proof.

To reduce clutter, let $\mathsf{C}=\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$
throughout this proof. Fix a controller $\mathcal{M}$ that satisfies
$(\epsilon,\delta)$-adaptive event-level pan-privacy, and fix $\mathsf{E}$ and
$\mathsf{Y}$ in the deletion-as-confidentiality game. We must show that
$(V_{\mathsf{E}},\mathsf{state}_{\mathsf{C}})\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
(V_{\mathsf{E}}^{\mathit{ideal}},\mathsf{state}_{\mathsf{C}})$ using the pan-
privacy hypothesis. Recall that in the deletion-as-confidentiality game,
$\mathsf{Y}$ does not send any messages to $\mathsf{E}$.

Below, we construct an adversary
$\mathsf{A}=\mathsf{A}_{\mathsf{E},\mathsf{Y}}$ for the adaptive pan-privacy
game of $\mathcal{M}$ (see Figure 5). After adaptively querying $\mathcal{M}$
(as in Algorithm 3), $\mathsf{A}$ produces output $Z$. We will argue two key
properties: First, if $\mathtt{side}=\mathtt{in}$, then $Z=Z^{(\mathtt{in})}$
will be distributed as $(V_{\mathsf{E}},\mathsf{state}_{\mathsf{C}})$. The
latter is the view of the environment and state of the controller in the real
confidentiality execution (Definition 5.1). Second, if
$\mathtt{side}=\mathtt{out}$, then $Z^{(\mathtt{out})}$ will be distributed as
$(V_{\mathsf{E}}^{\mathit{ideal}},\mathsf{state}_{\mathsf{C}}^{\mathit{ideal}})$,
the corresponding quantities in the ideal confidentiality execution. The
adaptive pan-privacy of $\mathcal{M}$ implies that $\mathsf{A}$’s views with
$\mathtt{side}\in\\{\mathtt{in},\mathtt{out}\\}$ are
$(\epsilon,\delta)$-indistinguishable. Post-processing implies that
$Z^{(\mathtt{in})}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
Z^{(\mathtt{out})}$, completing the proof.

Figure 5: How $\mathsf{A}$ emulates a real GGV execution among $\mathsf{E}$,
$\mathsf{Y}$, and $\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$.

Adversary $\mathsf{A}$ emulates a real GGV execution among $\mathsf{E}$,
$\mathsf{Y}$, and $\mathsf{C}$, passing messages among them and performing
each party’s computations as defined in Section 5 and depicted in Figure 5. To
emulate $\mathsf{E}$ and $\mathsf{Y}$, $\mathsf{A}$ simply runs their code. To
emulate $\mathsf{C}$, $\mathsf{A}$ maintains an internal SHI dictionary
$\mathcal{D}$ as in Algorithm 4 (using state $\mathsf{state}_{\mathcal{D}}$)
but does not emulate $\mathcal{M}$ directly. Instead, $\mathsf{A}$ makes a
queries in the pan-privacy game by calling Activate in Algorithm 3 as follows.
Let ${id}_{\mathsf{Y}}$ be $\mathsf{Y}$’s ${id}$. When the emulated parties
$\mathsf{E}$ or $\mathsf{Y}$ sends message $({id},\mathsf{op})$ intended for
emulated $\mathsf{C}$, $\mathsf{A}$ does the following:

  1. 1.

If $\mathsf{op}$ is a special message from $\mathsf{E}$ to terminate the alive
phase of execution: Run $\mathcal{D}.{\text{\sf{delete}}}({id}_{\mathsf{Y}})$,
call $\textsc{Activate}(\text{\sf intrusion},\bot)$. Upon receiving
$\mathsf{state}_{\mathcal{M}}$, end the GGV execution and output
$Z=(V_{\mathsf{E}},\mathsf{state}_{\mathsf{C}})$ where $V_{\mathsf{E}}$ is the
view of the emulated $\mathsf{E}$ and
$\mathsf{state}_{\mathsf{C}}=(\mathsf{state}_{\mathcal{M}}\|\mathsf{state}_{\mathcal{D}})$.

  2. 2.

Else if $\mathsf{op}={\text{\sf{delete}}}$: Run
$\mathcal{D}.{\text{\sf{delete}}}({id})$ and send response $\bot$ to party
${id}$ (on behalf of the emulated $\mathsf{C}$).

  3. 3.

Else if ${id}\in\mathcal{D}$: Send response $\bot$ to party ${id}$ (on behalf
of the emulated $\mathsf{C}$).

  4. 4.

Else if ${id}\neq{id}_{\mathsf{Y}}$: $\mathcal{D}.{\text{\sf{insert}}}({id})$,
$\textsc{Activate}(\text{\sf regular},\mathsf{op}({id}))$, and forward the
response from $\mathcal{M}$ to party ${id}$ (on behalf of the emulated
$\mathsf{C}$).

  5. 5.

Else: Call $\textsc{Activate}(\text{\sf challenge},\mathsf{op}({id}))$ and
forward the response to $\mathsf{Y}$ (on behalf of the emulated $\mathsf{C}$).

Let $\mu^{\mathit{GGV}}$ be the sequence of queries to $\mathcal{M}$ made by
the emulated $\mathsf{C}$ (all calls to Line 15 of Algorithm 4). Each query in
$\mu^{\mathit{GGV}}$ results in a single call to Activate. These in turn may
result in a query to $\mathcal{M}$ on Lines 21 and 27 of Algorithm 3. But, due
to the pan-privacy game some of these queries may not actually reach
$\mathcal{M}$: if $\mathtt{side}=\mathtt{out}$ (Line 26), or if an assertion
is violated (Lines 16 or 24). Let $\mu^{\mathit{PP},\mathtt{side}}$ be the
sequence of queries that actually reach $\mathcal{M}$ for
$\mathtt{side}\in\\{\mathtt{in},\mathtt{out}\\}$ (i.e., all calls to Lines 21
and 27).

######  Claim 6.10.

Consider an execution of the adversary $\mathsf{A}$ above in the pan-privacy
game with mechanism $\mathcal{M}$. Then, with probability 1:

  1. 1.

$\mu^{\mathit{PP},\mathtt{in}}=\mu^{\mathit{GGV},\mathit{real}}$, and

  2. 2.

$\mu^{\mathit{PP},\mathtt{out}}=\mu^{\mathit{GGV},\mathit{ideal}}$.

###### Proof.

_Part 1 $(\mathtt{side}=\mathtt{in})$:_ As explained before the claim, every
query to $\mathcal{M}$ made by the emulated $\mathsf{C}$ corresponds to a call
to Activate (and vice-versa). Every call to Activate results in a query in
$\mu^{\mathit{PP},\mathtt{in}}$ unless $\mathtt{side}=\mathtt{out}$ or one of
the assertions in Algorithm 3 (Lines 16 and 24) is violated. Because
$\mathtt{side}=\mathtt{in}$, it suffices to show that the assertions are never
violated. One assertion requires that intrusion is only called once (Line 16).
This is by the construction of $\mathsf{A}$ above.

The second assertion requires that challenge is called only once and only with
$\mathsf{op}\neq\text{\sf tick}$ (Line 24). This follows three properties of
$\mu^{\mathit{GGV}}$. First, challenge is only called when $\mathsf{Y}$ makes
a non-delete query. Second, $\mathsf{Y}$ cannot make tick queries. Finally,
$\mu^{\mathit{GGV}}$ contains at most one non-delete query from $\mathsf{Y}$.
This follows automatically from the restrictions on $\mathsf{Y}$ in the
deletion-as-confidentiality game; specifically, after $\mathsf{Y}$ makes a
delete query to $\mathsf{C}$, it may not send any additional messages to
$\mathsf{C}$.

_Part 2 $(\mathtt{side}=\mathtt{out})$:_ By construction of $\mathsf{A}$,
$\mathsf{Y}$’s queries in $\mu^{\mathit{GGV}}$ causes $\mathsf{A}$ to send a
challenge query in the pan-privacy game. The only difference from Part 1 is
that these queries are never sent to $\mathcal{M}$ in the pan-privacy game
(Line 26 of Algorithm 3). And, although the emulated $\mathsf{Y}$ receives
$\bot$ responses from $\mathsf{A}$ (on behalf of $\mathsf{C}$)–which it would
not get in the ideal world–$\mathsf{Y}$ can not send messages to $\mathsf{E}$
and so can not influence the view of $\mathsf{E}$ at all. ∎

Next we show that $Z^{(\mathtt{in})}$ is distributed as
$(V_{\mathsf{E}},\mathsf{state}_{\mathsf{C}})$. Consider a real-world GGV
execution where all parties use the same randomness as in $\mathsf{A}$’s
emulated execution. If $\mathtt{side}=\mathtt{in}$, the view of the real-world
GGV environment $V_{\mathsf{E}}^{\mathit{GGV},real}$ is identical to the view
of the emulated environment $V_{\mathsf{E}}^{\mathit{PP},\mathtt{in}}$. From
$\mathsf{E}$’s view, the only difference between the two executions is how
$\mathcal{M}$ is implemented and queried. By Part 1 of 6.10, the queries
processed by $\mathcal{M}$ are identical in the two executions. Hence
$\mathsf{E}$’s views of the two executions are identical. Likewise, the states
$\mathsf{state}_{\mathsf{C}}=(\mathsf{state}_{\mathcal{D}}\|\mathsf{state}_{\mathcal{M}})$
are identical in the two executions.

Finally we show that $Z^{(\mathtt{out})}$ is distributed as
$(V_{\mathsf{E}}^{\mathit{ideal}},\mathsf{state}_{\mathsf{C}}^{\mathit{ideal}})$.
Consider an ideal-world GGV execution where all parties use the same
randomness as in $\mathsf{A}$’s emulated execution. In the ideal GGV
execution, $\mathsf{Y}$ cannot send messages to $\mathsf{C}$, whereas in the
emulated execution it can; however, by part 2 of 6.10, the queries processed
by $\mathcal{M}$ are identical in the two executions. Hence $\mathsf{E}$’s
views of the two executions are identical. Likewise, the states
$\mathsf{state}_{\mathsf{C}}=(\mathsf{state}_{\mathcal{D}}\|\mathsf{state}_{\mathcal{M}})$
are identical in the two executions.

Lastly, $Z^{(\mathtt{side})}$ is a post-processing of
$V_{\mathsf{A},\mathcal{M}}^{(\mathtt{side})}$ in the adaptive pan-privacy
game. Hence, by event-level $(\epsilon,\delta)$-adaptive-pan-privacy with
continual release, we have $Z^{(\mathtt{in})}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
Z^{(\mathtt{out})}$. Finally, since the dictionary $\mathcal{D}$ is SHI, the
state $\mathsf{state}_{\mathcal{D}}$ in the emulation is identically
distributed to $\mathsf{state}_{\mathcal{D}}$ in the GGV real and ideal worlds
(since in all cases $\mathsf{Y}$’s removal from $\mathcal{D}$ is
undetectable). This implies that
$(V_{\mathsf{E}},\mathsf{state}_{\mathsf{C}})\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
(V_{\mathsf{E}}^{\mathit{ideal}},\mathsf{state}_{\mathsf{C}}^{\mathit{ideal}})$,
completing the proof. ∎

###### Proof of Theorem 6.8.

Our proof combines Lemma 6.9 and Theorem 5.3. To reduce clutter, let
$\mathsf{C}=\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$ throughout this proof. Fix
an $(\epsilon,\delta)$-adaptive event-level pan-private controller
$\mathcal{M}$ with continual release. Then, by Lemma 6.9, the controller
$\mathsf{C}$ described in Algorithm 4 satisfies $(\epsilon,\delta)$-deletion-
as-confidentiality. Recall that deletion-as-confidentiality only considers the
subset of data subjects $\mathcal{Y}_{\mathsf{lift}}$ satisfing two
requirements. First, $\mathsf{Y}$ does not send messages to $\mathsf{E}$.
Second, $\mathsf{Y}$ only delete’s when instructed to by $\mathsf{E}$. If we
restrict to this class $\mathcal{Y}_{\mathsf{lift}}$ of data subjects, then by
Theorem 5.3, $\mathsf{C}$ is $(\epsilon,\delta)$-deletion-as-control compliant
for $\mathcal{Y}_{\mathsf{lift}}$.

What remains to argue is that for $\mathsf{C}$ specifically, we can restrict
to $\mathcal{Y}_{\mathsf{lift}}$ without loss of generality (using the same
simulator $\mathsf{Sim}$ as for $\mathsf{Y}\in\mathcal{Y}_{\mathsf{lift}}$).
It suffices to show that for any $(\mathsf{E},\mathsf{Y})$ there exists
$(\mathsf{E}^{\prime},\mathsf{Y}^{\prime})$ with
$\mathsf{Y}^{\prime}\in\mathcal{Y}_{\mathsf{lift}}$ such that the transcripts
in the executions
$\langle\mathsf{C}(R_{\mathsf{C}}),\mathsf{E},\mathsf{Y}\rangle$ and
$\langle\mathsf{C}(R_{\mathsf{C}}),\mathsf{E}^{\prime},\mathsf{Y}^{\prime}\rangle$
are identical. Intuitively, this holds because $\mathsf{C}$ only ever sends
$\bot$ to $\mathsf{Y}$. Recall that $\mathsf{Y}$ cannot make any tick queries,
which is the only way for $\mathcal{M}(\mathsf{op}({id}))$ (or $\mathsf{C}$)
to produce non-$\bot$ output. Hence, the view of $\mathsf{Y}$ can easily be
simulated by $\mathsf{E}$, and the restriction that $\mathsf{Y}$ does not
communicate with $\mathsf{E}$ is without loss of generality. From there, we
can restrict $\mathsf{Y}$ to be a dummy party without loss of generality,
satisfying the requirements of $\mathcal{Y}_{\mathsf{lift}}$.

Fix any $\mathsf{E}$, $\mathsf{Y}$. Figure 6 depicts $\mathsf{E}^{\prime}$ and
$\mathsf{Y}^{\prime}$. The subject $\mathsf{Y}^{\prime}$ forwards messages
from $\mathsf{E}^{\prime}$ to $\mathsf{C}$, but sends no messages to
$\mathsf{E}^{\prime}$. The environment $\mathsf{E}^{\prime}$ emulates
$\mathsf{E}$ and $\mathsf{Y}$ in its head and emulates their interactions with
other parties as follows:

  * •

$\mathsf{E}^{\prime}$ passes messages between emulated parties $\mathsf{E}$
and $\mathsf{Y}$ freely.

  * •

$\mathsf{E}^{\prime}$ forwards queries from $\mathsf{E}$ intended for
$\mathsf{C}$; similarly, $\mathsf{E}^{\prime}$ forwards responses from
$\mathsf{C}$ to $\mathsf{E}$.

  * •

$\mathsf{E}^{\prime}$ forwards queries from $\mathsf{Y}$ intended for
$\mathsf{C}$ to the external $\mathsf{Y}^{\prime}$ (who then forwards this to
$\mathsf{C}$). When reactivated, $\mathsf{E}^{\prime}$ sends the response
$\bot$ to $\mathsf{Y}$.

Figure 6: Construction of $\mathsf{E}^{\prime}$ and $\mathsf{Y}^{\prime}$ with
internal emulated parties $\mathsf{E}$, $\mathsf{Y}$ interacting with
$\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$.

By construction, $\mathsf{Y}^{\prime}$ satisfies the condition that it only
sends delete if $\mathsf{E}^{\prime}$ tells it to, and it never sends any
message to $\mathsf{E}^{\prime}$. Hence,
$\mathsf{Y}^{\prime}\in\mathcal{Y}_{\mathsf{lift}}$. By the construction in
Algorithm 4, $\mathsf{C}$ always sends $\bot$ in response to $\mathsf{Y}$’s
queries. Using this, it is easy to show that the emulation is perfect. Hence,
the transcripts seen by $\mathsf{C}$ in the two executions
$\langle\mathsf{C}(R_{\mathsf{C}}),\mathsf{E},\mathsf{Y}\rangle$ and
$\langle\mathsf{C}(R_{\mathsf{C}}),\mathsf{E}^{\prime},\mathsf{Y}^{\prime}\rangle$
are identical.

∎

###  6.4 Examples of Pan-private Controllers

####  6.4.1 Counters

Perhaps the most widely studied algorithm that is pan-private under continual
release is the tree mechanism of Dwork et al. (2010a); Chan et al. (2011).
Although originally formulated without pan-privacy, it relies on the
composition of summations over different time intervals. Each of these can be
made pan-private against a single intrusion by adding noise when the counter
is initialized and again at release (Dwork et al., 2010b). The overall
mechanism retains the same asymtptotic guarantees, since the noise at most
doubles, and enjoys pan-privacy. We summarize its properties here:

######  Proposition 6.11 (Combining Dwork et al. (2010b) with Dwork et al.
(2010a); Chan et al. (2011)).

There is an $(\epsilon,\delta)$-adaptively event-level pan-private under
continual-release algorithm that takes a time horizon $T$ and a sequence of
inputs $x_{1},x_{2},...\in[0,1]$ and at the $t$-th tick, for $t\in[T]$,
releases $\mathsf{out}_{t}$ such that

$\mathsf{out}_{t}=\sum_{\begin{subarray}{c}i\,:\,{x_{i}}\text{ received}\\\
\text{by time }t\end{subarray}}x_{i}+Z_{t},$

where $Z_{t}$’s are distributed (independently of $x_{i}$’s but not each
other) as $Z_{t}\sim N(0,\sigma_{t}^{2})$ with
$\sigma_{t}=O\left(\frac{\sqrt{\log^{3}T\log(1/\delta)}}{\epsilon}\right)$.

In Section 7, we use the tree mechanism as a building block to construct a
controller that satisfies deletion-as-control but not history independence,
confidentiality, nor differential privacy. Moreover, one can use the tree
mechanism to construct a controller that satisfies deletion-as-control but not
history independence (cf. Proposition 6.1). The controller could, for example,
use the tree mechanism to count the number of distinct users $n$ it has seen.
Applying Theorem 6.8, a controller could publish $n+N(0,\sigma_{t}^{2})$ even
after all users have requested deletion, all while satisfying deletion-as-
control. This is impossible under history independence.

####  6.4.2 Learning under Pan-Private Continual Release (and with Deletion)

As an example, we show how the results of this section allow one to maintain a
model trained via gradient descent with relatively little noise—the
algorithm’s error is similar to that of state of the art federated machine
learning algorithms.

Consider the following optimization problem: given a loss function
$\ell:\Theta\times\mathcal{X}\to\mathbb{R}$ and a data set
${\vec{x}}=(x_{1},...,x_{n})$, we aim to find $h\in\Theta$ which approximately
minimizes

${\mathcal{L}}_{{\vec{x}}}(h)=\sum_{i=1}^{n}\ell(h;x_{i})\,.$ (8)

For convergence analysis, it is often convenient to assume that $\Theta$ is
convex and $\ell(\cdot;x)$ is convex in its first argument (for every choice
of $x$). Nevertheless, we generally seek solutions that apply more
broadly—where the privacy or deletion guarantees hold regardless of convexity,
and convergence guarantees plausibly hold as long as the loss function is
roughly convex near its minimum.

Algorithms for this problem that are differentially private under continual
release were studied for online learning (e.g. Smith and Thakurta (2013)) and
efficient distributed learning (Kairouz et al., 2021). They access the data
via the tree-based mechanism for continual release of a sum from Proposition
6.11 (in this case, releasing the sum of the gradients of users’ contributions
to the overall loss function over the evaluation of a first-order optimization
algorithm).

Assume $\ell$ is $1$-Lipschitz in $h$ (that is, suppose
$\Theta\in\mathbb{R}^{d}$ and for all $h,h^{\prime}$ and $x$, we have
${\left|{\ell(h;x)-\ell(h^{\prime};x)}\right|}\leq{\left\|{h-h^{\prime}}\right\|_{2}}$).

######  Proposition 6.12 (Corollary of Theorem 5.1 from arXiv v3 of Kairouz et
al. (2021)).

There is an $(\epsilon,\delta)$-adaptively pan-private, continual-release
algorithm that takes takes a time horizon $T$ and a sequence of inputs
$x_{1},x_{2},...$ and at the $t$-th tick releases a model $h_{t}$ such that,
for every $t\in[T]$, data set ${\vec{x}}_{t}\in{\mathcal{Z}}^{n}$ (consisting
of records received by tick $t$), $h^{*}\in\Theta$, and $\beta>0$, with
probability at least $1-\beta$ over the coins of the algorithm,

$\displaystyle{\mathcal{L}}_{{\vec{x}}_{t}}(h_{t})-{\mathcal{L}}_{{\vec{x}}_{t}}(h^{*})=O{\left({{\left\|{h^{*}}\right\|}\cdot{\left({\frac{1}{\sqrt{n}}+d^{1/4}\sqrt{\frac{\ln^{2}(1/\delta)\ln(1/\beta)}{\epsilon
t}}}\right)}}\right)}$

This result immediately yields a controller that satisfies
$(\epsilon,\delta)$-deletion as control and maintains a model whose accuracy
tracks that of the best model trained on all the arrivals so far (where
repeated arrivals of the same user are ignored). In contrast to the HI-style
algorithms proposed for machine unlearning, this controller does not update
the model when a user is deleted.

##  7 Parallel Composition

In this section, we show that our definition does more than unify approaches
to deletion based on history independence, confidentiality, and differential
privacy. We describe a controller that satisfies deletion-as-control but none
of the other three notions. To prove that the controller satisfies deletion-
as-control, we prove that the definition enjoys a limited form of _parallel
composition_ : a controller that is built from two constituent sub-
controllers, each of which is run independently (Figure 7), will be deletion
compliant if the component controllers are compliant and satisfy additional
conditions. We focus on a special case that suffices for our needs, and leave
a general treatment of composition of deletion-as-control for future work.

To anchor the discussion, we consider the touchstone composed controller
“Public Directory with DP Statistics,” described in Algorithm 5. It provides a
public directory (e.g., a phone book) which, in addition to answering
directory queries, periodically reports the total number of users that have
made queries to the directory. We build the touchstone controller $\mathsf{C}$
from two SHI dictionaries $\mathcal{D}$ and $\mathcal{U}$ (Section 4.1.1) and
the pan-private tree mechanism $\mathcal{M}$ (Proposition 6.11). $\mathcal{D}$
implements the directory functionalities of reading and writing. $\mathcal{M}$
keeps track of an approximate count of users—current and former—that have
looked up an entry in $\mathcal{D}$ for the first $T$ epochs (e.g., the time
between ticks). $\mathcal{U}$ is an auxiliary dictionary used to ensure that
$\mathcal{M}$ counts distinct users.

Algorithm 5 Public directory with usage statistics

1:procedure Initialize(time horizon $T\in\mathbb{N}$, privacy parameters
$\epsilon,\delta$) $\triangleright$ Run on first activation

2: Initialize two SHI dictionaries $\mathcal{D}$ for the directory and
$\mathcal{U}$ for users.

3: Initialize the tree mechanism $\mathcal{M}$ with parameters
$(\epsilon,\delta,T)$

4:

5:procedure Activate($\mathsf{cID},\mathsf{op}(arg)$)

6: if $\mathsf{op}={\text{\sf{delete}}}$ then

7: $\mathcal{D}.{\text{\sf{delete}}}(\mathsf{cID})$

8: $\mathcal{U}.{\text{\sf{delete}}}(\mathsf{cID})$

9: return $\bot$

10: if $\mathsf{op}=\mathsf{set}$ then

11: $\mathcal{D}.\mathsf{set}(\mathsf{cID},arg)$

12: return $\bot$

13: if $\mathsf{op}=\mathsf{get}$ then

14: if $\mathsf{cID}\notin\mathcal{U}$ then

15: $\mathcal{U}.\mathsf{set}(\mathsf{cID},1)$

16: Insert the value 1 into $\mathcal{M}$’s data stream

17: return $\mathcal{D}.\mathsf{get}(arg)$

18: if $\mathsf{op}=\mathsf{getCount}$ then

19: return $\mathcal{M}(\text{\sf tick})$

Figure 7: Parallel composition of controllers $\mathsf{C}_{0}$ and
$\mathsf{C}_{1}$.

To prove that $\mathsf{C}$ satisfies deletion-as-control, we prove that one
can build deletion-as-control controllers from two constituent sub-controllers
by parallel composition. We consider the special case where one sub-controller
satisfies $(0,0)$-deletion-as-control and implements a _deterministic
functionality_ , and where both sub-controllers are _query-response
controllers_. We define these next. Note that the controllers given in Section
4.2 and Section 6 are all query-response controllers. While we restrict our
attention to a single controller of each type, the result immediately extends
by induction to many query-response controllers satisfying $(0,0)$ deletion-
as-control with deterministic functionalities.

######  Definition 7.1 (Deterministic functionality).

A controller $\mathsf{C}$ has a _deterministic functionality_ if for all
$\mathsf{E}$, $\mathsf{Y}$, the transcript of
$\langle\mathsf{C}(R_{\mathsf{C}}),\mathsf{E},\mathsf{Y}\rangle$ is
independent of $R_{\mathsf{C}}$.

######  Definition 7.2 (Query-response controller).

$\mathsf{C}$ is a _query-response_ controller if it always replies to the same
party that activated it. Namely, when $\mathsf{C}$ is activated with
$(\mathsf{cID},\mathsf{msg})$ on its input tape, it always halts with
$(\mathsf{cID},\mathsf{msg}^{\prime})$ on its output tape for some
$\mathsf{msg}^{\prime}$.

The example controllers we discuss are generally query-response. But a
messaging server, for example, might not be: a request from Alice to send
something Bob could result in a push from the server to Bob.

######  Definition 7.3 (Parallel composition).

Let $\mathsf{C}_{0}$ and $\mathsf{C}_{1}$ be controllers. We define their
_parallel composition_ , denoted $\mathsf{C}_{0\|1}$, to be the controller
that emulates $\mathsf{C}_{0}$ an $\mathsf{C}_{1}$ internally. When activated
with $\mathsf{op}_{id}$, $\mathsf{C}_{0\|1}$ computes
$\mathsf{out}_{0}\leftarrow\mathsf{C}_{0}(\mathsf{op}_{id})$ and
$\mathsf{out}_{1}\leftarrow\mathsf{C}_{1}(\mathsf{op}_{id})$ and returns
$\mathsf{out}_{0\|1}=(\mathsf{out}_{0},\mathsf{out}_{1})$. The controllers
$\mathsf{C}_{0}$ and $\mathsf{C}_{1}$ are emulated with disjoint portions of
$\mathsf{C}_{0\|1}$’s randomness tape $R_{0\|1}=(R_{0},R_{1})$ and work tape
$\mathsf{state}_{0\|1}=(\mathsf{state}_{0},\mathsf{state}_{1})$.

######  Theorem 7.4.

Let $\mathsf{C}_{0}$ and $\mathsf{C}_{1}$ be query-response controllers and
let $C_{0\|1}$ be their parallel composition. If $\mathsf{C}_{0}$ satisfies
$(\epsilon,\delta)$-deletion-as-control, and if $\mathsf{C}_{1}$ satisfies
$(0,0)$-deletion-as-control and has deterministic functionality, then
$\mathsf{C}_{0\|1}$ satisfies $(\epsilon,\delta)$-deletion-as-control.

###### Proof.

Define the parallel simulator
$\mathsf{Sim}_{0\|1}(\vec{\mathsf{q}}_{\mathsf{E}},R_{0\|1},\mathsf{state}_{0\|1})$
as outputting $R^{\prime}_{0\|1}=(R^{\prime}_{0},R^{\prime}_{1})$ where each
half is computed using the corresponding simulator. That is, for each
$i\in\\{0,1\\}$:

$R^{\prime}_{i}\sim\mathsf{Sim}_{i}(\vec{\mathsf{q}}_{\mathsf{E}},R_{i},\mathsf{state}_{i}).$

By hypothesis, all of the following hold for all $\mathsf{E}$, $\mathsf{Y}$.

  * •

$(R^{\prime}_{0}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ R_{0})$ AND
$(R^{\prime}_{1}\equiv R_{1})$,

  * •

$(\mathsf{state}_{1}=\mathsf{state}^{\prime}_{1})$ OR
$(\mathsf{state}_{1}=\bot)$

  * •

With probability at least $1-\delta$:
$(\mathsf{state}_{0}=\mathsf{state}^{\prime}_{0})$ OR
$(\mathsf{state}_{0}=\bot)$.

We must show that for all $\mathsf{E}$, $\mathsf{Y}$, both of the following
hold in the real-ideal probability experiment given in Definition 3.2.

  * •

$R^{\prime}_{0\|1}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ R_{0\|1}$

  * •

With probability at least $1-\delta$:
$\mathsf{state}_{0\|1}=\mathsf{state}^{\prime}_{0\|1}\neq\bot$ or
$\mathsf{state}_{0\|1}=\bot$ (i.e., the real execution doesn’t terminate).

We consider the state first. First, observe the following:

$\displaystyle(\mathsf{state}_{0}=\bot)$
$\displaystyle\implies(\mathsf{state}_{1}=\bot),\text{ and}$
$\displaystyle(\mathsf{state}_{0}\neq\bot)$
$\displaystyle\implies(\mathsf{state}_{1}\neq\bot)\implies(\mathsf{state}_{1}=\mathsf{state}^{\prime}_{1})$

This is because both $\mathsf{state}_{0}$ and $\mathsf{state}_{1}$ result from
a single real execution
$\langle\mathsf{C}_{0\|1},\mathsf{E},\mathsf{Y}\rangle$ that either terminates
($\mathsf{state}_{0\|1}=\bot$) or does not ($\mathsf{state}_{0\|1}\neq\bot$).
Hence,

$\displaystyle\Pr\left[\mathsf{state}_{0\|1}\in\\{\mathsf{state}^{\prime}_{0\|1},\bot\\}\right]$
$\displaystyle\qquad=\Pr\left[\mathsf{state}_{0}\in\\{\mathsf{state}^{\prime}_{0},\bot\\}\right]\geq
1-\delta$

It remains to show that $R^{\prime}_{0\|1}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ R_{0\|1}$.
Below, we prove that $R^{\prime}_{0}$ and $R^{\prime}_{1}$ are independent
random variables. This suffices because $(R^{\prime}_{0}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ R_{0})$ and
$(R^{\prime}_{1}\equiv R_{1})$.

Let $\vec{\mathsf{q}}$ be the queries received by $\mathsf{C}_{0\|1}$ in the
real execution. By construction, these are also the queries received by the
emulated $\mathsf{C}_{0}$ and $\mathsf{C}_{1}$. Observe that for
$i\in\\{0,1\\}$ there exists randomized $S_{i}$ such that $R^{\prime}_{i}\sim
S_{i}(R_{i},\vec{\mathsf{q}})$. Namely, $R^{\prime}_{i}$ only depends on
$R_{i}$ and $\vec{\mathsf{q}}$. This is because
$R^{\prime}_{i}\leftarrow\mathsf{Sim}_{i}(R_{i},\vec{\mathsf{q}}_{\mathsf{E}},\mathsf{state}_{i})$
where $\vec{\mathsf{q}}_{\mathsf{E}}$ and $\mathsf{state}_{i}$ are
deterministic functions of $R_{i}$ and $\vec{\mathsf{q}}$ (and the code of
$\mathsf{C}_{0\|1}$, $\mathsf{E}$, $\mathsf{Y}$ which are fixed).

The above implies two useful facts. First, $R^{\prime}_{1}$ is independent of
$R^{\prime}_{0}$ conditioned on $\vec{\mathsf{q}}$. This follows from the fact
that $R^{\prime}_{i}\sim S_{i}(R_{i},\vec{\mathsf{q}})$, combined with the
fact that $R_{1}$ and $R_{0}$ are independent (by construction). Second,
$R^{\prime}_{1}$ is independent of the random variable $\vec{\mathsf{q}}$.
That is, for all $r^{\prime}_{1}$ and $q$,
$\Pr[R^{\prime}_{1}=r^{\prime}_{1}|\vec{\mathsf{q}}=q]=\Pr[S_{1}(R_{1},\vec{\mathsf{q}})=r^{\prime}_{1}|\vec{\mathsf{q}}=q]=\Pr[S_{1}(R_{1},q)=r^{\prime}_{1}]=\Pr[R^{\prime}_{1}=r^{\prime}_{1}].$
The middle equality uses the independence of $\vec{\mathsf{q}}$ and $R_{1}$,
which follows from the hypothesis that $\mathsf{C}_{1}$ has a deterministic
functionality.

Fix $r^{\prime}_{0}$ and $r^{\prime}_{1}$. We check independence of
$R^{\prime}_{0}$ and $R^{\prime}_{1}$ as follows.

$\displaystyle\Pr[R^{\prime}_{0}=r^{\prime}_{0}\land
R^{\prime}_{1}=r^{\prime}_{1}]$
$\displaystyle=\Pr[R^{\prime}_{0}=r^{\prime}_{0}]\cdot\sum_{q}\Pr[\vec{\mathsf{q}}=q|R^{\prime}_{0}=r^{\prime}_{0}]\cdot\Pr[R^{\prime}_{1}=r^{\prime}_{1}|\vec{\mathsf{q}}=q,R^{\prime}_{0}=r^{\prime}_{0}]$
$\displaystyle=\Pr[R^{\prime}_{0}=r^{\prime}_{0}]\cdot\sum_{q}\Pr[\vec{\mathsf{q}}=q|R^{\prime}_{0}=r^{\prime}_{0}]\cdot\Pr[R^{\prime}_{1}=r^{\prime}_{1}|\vec{\mathsf{q}}=q]$
$\displaystyle=\Pr[R^{\prime}_{0}=r^{\prime}_{0}]\cdot\Pr[R^{\prime}_{1}=r^{\prime}_{1}]\cdot\sum_{q}\Pr[\vec{\mathsf{q}}=q|R^{\prime}_{0}=r^{\prime}_{0}]$
$\displaystyle=\Pr[R^{\prime}_{0}=r^{\prime}_{0}]\cdot\Pr[R^{\prime}_{1}=r^{\prime}_{1}]$

The second equality uses the independence of $R^{\prime}_{1}$ and
$R^{\prime}_{0}$ conditioned on $\vec{\mathsf{q}}$. The third equality uses
the independence of $R^{\prime}_{1}$ and $\vec{\mathsf{q}}$. ∎

######  Corollary 7.5.

Algorithm 5 satisfies $(\epsilon,\delta)$-deletion-as-control.

###### Proof.

Let $\mathsf{C}_{0}$ be the controller
$\mathsf{C}_{\mathcal{M}}^{\mathsf{pp}}$ defined relative to the pan-private
tree mechanism $\mathcal{M}$ (Algorithm 4). Let $\mathsf{C}_{1}$ be the
controller relative to a SHI dictionary (Definition 4.6). By construction,
$\mathsf{C}_{0}$ and $\mathsf{C}_{1}$ are query-response controllers and
$\mathsf{C}_{1}$ has a deterministic functionality. $\mathsf{C}_{0}$ satisfies
$(\epsilon,\delta)$ deletion-as-control and $\mathsf{C}_{1}$ satisfies
$(\epsilon,\delta)$ deletion-as-control (Theorems 6.8 and 4.8 respectively).
Algorithm 5 is equivalent to the parallel composition $\mathsf{C}_{0\|1}$ of
$\mathsf{C}_{0}$ and $\mathsf{C}_{1}$. By parallel composition, Algorithm 5
satisfies $(\epsilon,\delta)$ deletion-as-control. ∎

## References

  * Blelloch and Golovin [2007] G. E. Blelloch and D. Golovin.  Strongly history-independent hashing with applications.  In _48th Annual IEEE Symposium on Foundations of Computer Science (FOCS)_ , 2007.  doi: 10.1109/FOCS.2007.36.
  * Bourtoule et al. [2021] L. Bourtoule, V. Chandrasekaran, C. A. Choquette-Choo, H. Jia, A. Travers, B. Zhang, D. Lie, and N. Papernot.  Machine unlearning.  In _42nd IEEE Symposium on Security and Privacy_ , 2021.  doi: 10.1109/SP40001.2021.00019.
  * Cao and Yang [2015] Y. Cao and J. Yang.  Towards making systems forget with machine unlearning.  In _2015 IEEE Symposium on Security and Privacy_ , pages 463–480. IEEE, 2015.
  * Carlini et al. [2021] N. Carlini, F. Tramer, E. Wallace, M. Jagielski, A. Herbert-Voss, K. Lee, A. Roberts, T. Brown, D. Song, U. Erlingsson, et al.  Extracting training data from large language models.  In _30th USENIX Security Symposium (USENIX Security 21)_ , pages 2633–2650, 2021.
  * Chan et al. [2011] T.-H. H. Chan, E. Shi, and D. Song.  Private and continual release of statistics.  _ACM Transactions on Information and System Security (TISSEC)_ , 14(3):1–24, 2011.
  * Cohen and Nissim [2020] A. Cohen and K. Nissim.  Linear program reconstruction in practice.  _Journal of Privacy and Confidentiality_ , 10(1), Jan. 2020\.  doi: 10.29012/jpc.711.  URL https://journalprivacyconfidentiality.org/index.php/jpc/article/view/711.
  * Dwork et al. [2006] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor.  Our data, ourselves: Privacy via distributed noise generation.  In _International Conference on the Theory and Applications of Cryptographic Techniques_ , EUROCRYPT ’06, pages 486–503, St. Petersburg, Russia, 2006.
  * Dwork et al. [2010a] C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum.  Differential privacy under continual observation.  In L. J. Schulman, editor, _Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010_ , pages 715–724. ACM, 2010a.  doi: 10.1145/1806689.1806787.
  * Dwork et al. [2010b] C. Dwork, M. Naor, T. Pitassi, G. N. Rothblum, and S. Yekhanin.  Pan-private streaming algorithms.  In _ICS_ , pages 66–80, 2010b.
  * Dwork et al. [2016] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith.  Calibrating noise to sensitivity in private data analysis.  _J. Priv. Confidentiality_ , 2016.  doi: 10.29012/jpc.v7i3.405.
  * Fowler [2022] B. Fowler.  Data breaches break record in 2021.  _CNET_ , 2022.  URL https://www.cnet.com/news/privacy/record-number-of-data-breaches-reported-in-2021-new-report-says/.
  * Garg et al. [2020] S. Garg, S. Goldwasser, and P. N. Vasudevan.  Formalizing data deletion in the context of the right to be forgotten.  _CoRR_ , abs/2002.10635, 2020.  URL https://arxiv.org/abs/2002.10635.
  * Ginart et al. [2019] A. Ginart, M. Guan, G. Valiant, and J. Y. Zou.  Making ai forget you: Data deletion in machine learning.  In _Advances in Neural Information Processing Systems_ , pages 3513–3526, 2019.
  * Godin and Lamontagne [2021] J. Godin and P. Lamontagne.  Deletion-compliance in the absence of privacy.  In _2021 18th International Conference on Privacy, Security and Trust (PST)_ , pages 1–10. IEEE, 2021.
  * Golatkar et al. [2020a] A. Golatkar, A. Achille, and S. Soatto.  Eternal sunshine of the spotless net: Selective forgetting in deep networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 9304–9312, 2020a.
  * Golatkar et al. [2020b] A. Golatkar, A. Achille, and S. Soatto.  Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations.  _arXiv preprint arXiv:2003.02960_ , 2020b.
  * Guo et al. [2020] C. Guo, T. Goldstein, A. Hannun, and L. van der Maaten.  Certified data removal from machine learning models, 2020.
  * Gupta et al. [2021] V. Gupta, C. Jung, S. Neel, A. Roth, S. Sharifi-Malvajerdi, and C. Waites.  Adaptive machine unlearning.  _arXiv preprint arXiv:2106.04378_ , 2021.
  * Hartline et al. [2005] J. D. Hartline, E. S. Hong, A. E. Mohr, W. R. Pentney, and E. C. Rocke.  Characterizing history independent data structures.  _Algorithmica_ , 42(1):57–74, 2005.
  * Jain et al. [2021] P. Jain, S. Raskhodnikova, S. Sivakumar, and A. D. Smith.  The price of differential privacy under continual observation.  _CoRR_ , abs/2112.00828, 2021.  URL https://arxiv.org/abs/2112.00828.
  * JASON [2022] JASON.  Consistency of data products and formal privacy methods for the 2020 Census.  Panel Report JSR 21-02, JASON, The MITRE Corporation, 1 2022.
  * Kairouz et al. [2021] P. Kairouz, B. McMahan, S. Song, O. Thakkar, A. Thakurta, and Z. Xu.  Practical and private (deep) learning without sampling or shuffling.  In M. Meila and T. Zhang, editors, _Proceedings of the 38th International Conference on Machine Learning (ICML)_ , 2021.
  * Kasiviswanathan and Smith [2014] S. P. Kasiviswanathan and A. D. Smith.  On the ‘semantics’ of differential privacy: A bayesian formulation.  _Journal of Privacy and Confidentiality_ , 2014.  Available as v3 of https://arxiv.org/abs/0803.3946.
  * Kaste [2022] M. Kaste.  Nebraska cops used Facebook messages to investigate an alleged illegal abortion.  _NPR_ , 2022.  URL https://www.npr.org/2022/08/12/1117092169/nebraska-cops-used-facebook-messages-to-investigate-an-alleged-illegal-abortion.
  * Micciancio [1997] D. Micciancio.  Oblivious data structures: applications to cryptography.  In _Proceedings of the twenty-ninth annual ACM symposium on Theory of computing_ , pages 456–464, 1997.
  * Naor and Teague [2001] M. Naor and V. Teague.  Anti-persistence: History independent data structures.  In _Proceedings of the thirty-third annual ACM symposium on Theory of computing_ , pages 492–501, 2001.
  * Neel et al. [2020] S. Neel, A. Roth, and S. Sharifi-Malvajerdi.  Descent-to-delete: Gradient-based methods for machine unlearning, 2020\.
  * Ng [2022] A. Ng.  Homeland Security records show ’shocking’ use of phone data, ACLU says.  _Politico_ , 2022.  URL https://www.politico.com/news/2022/07/18/dhs-location-data-aclu-00046208.
  * Rogers et al. [2016] R. Rogers, A. Roth, A. Smith, and O. Thakkar.  Max-information, differential privacy, and post-selection hypothesis testing.  In _IEEE Symposium on Foundations of Computer Science_ , FOCS ’16, pages 487–494, 2016.  https://arxiv.org/abs/1604.03924.
  * Sekhari et al. [2021] A. Sekhari, J. Acharya, G. Kamath, and A. T. Suresh.  Remember what you want to forget: Algorithms for machine unlearning.  _arXiv preprint arXiv:2103.03279_ , 2021.
  * Smith and Thakurta [2013] A. Smith and A. G. Thakurta.  (nearly) optimal algorithms for private online learning in full-information and bandit settings.  In _27th Annual Conference on Neural Information Processing Systems_ , 2013.
  * Ullah et al. [2021] E. Ullah, T. Mai, A. Rao, R. Rossi, and R. Arora.  Machine unlearning via algorithmic stability.  _arXiv preprint arXiv:2102.13179_ , 2021.
  * Veale et al. [2018a] M. Veale, R. Binns, and J. Ausloos.  When data protection by design and data subject rights clash.  _International Data Privacy Law_ , 8(2):105–123, 2018a.
  * Veale et al. [2018b] M. Veale, R. Binns, and L. Edwards.  Algorithms that remember: model inversion attacks and data protection law.  _Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , 376(2133):20180083, 2018b.

##  Appendix A Lemmas on Couplings and Marginal Distributions

######  Lemma A.1 (Coupling Lemma).

Let $P,Q$ be probability distributions on sets $\mathcal{X}$ and
${\mathcal{Y}}$, respectively, and let $f:\mathcal{X}\to{\mathcal{Z}}$ and
$g:{\mathcal{Y}}\to{\mathcal{Z}}$ be (deterministic) functions with the same
codomain ${\mathcal{Z}}$. Suppose that $f(X)\approx_{\epsilon,\delta}g(Y)$
when $X\sim P$ and $Y\sim Q$.

Consider the collection of distributions
$\\{Q_{x}\in\Delta({\mathcal{Y}}):x\in\mathcal{X}\\}$ on the set
${\mathcal{Y}}$, where $Q_{x}$ denotes the distribution on $Y$ conditioned on
the event that $g(Y)=f(x)$ (that is
$Q_{x}=Q|_{{\left\\{{y:g(y)=f(x)}\right\\}}}$). In the case that
$g^{-1}(f(x))$ is empty, $Q_{x}$ assigns probability to a default value
$\bot\in{\mathcal{Y}}$.

If we select $X\sim P$ and then sample $Y^{\prime}\sim Q_{X}$ (so that
$\Pr(Y^{\prime}=y|X=x)=Q_{x}(y)$), then

  1. 1.

$Y^{\prime}\approx_{\epsilon,\delta}Y$, and

  2. 2.

$f(X)=g(Y^{\prime})$ with probability at least $1-\delta$ over $(X,Y)$.

For example, consider an $(\epsilon,\delta)$-DP mechanism $\mathcal{M}$ using
randomness $R\sim\mathcal{U}$, and let $\mathbf{x},\mathbf{x}^{\prime}$ be a
pair of neighboring inputs. Take $f(R)=\mathcal{M}(\mathbf{x};R)$ and
$g(R)=\mathcal{M}(\mathbf{x}^{\prime};R)$. Lemma A.1 gives a way to jointly
sample randomness $(R,R^{\prime})$ such that $R\sim\mathcal{U}$, $R^{\prime}\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\ \mathcal{U}$,
and with probability at least $1-\delta$:
$\mathcal{M}(\mathbf{x};R)=\mathcal{M}(\mathbf{x}^{\prime};R^{\prime})$. For
simple DP mechanisms, it is easy to understand what this sampler does. For
instance, let $\mathsf{Lap}(1/\epsilon;R)$ be an algorithm that samples from
the Laplace distribution when $R\sim\mathcal{U}$ is uniform. Consider
$\mathcal{M}(\mathbf{x};R)=f(\mathbf{x})+\mathsf{Lap}(1/\epsilon;R)$ for some
$f$ with sensitivity 1. The sampler in Lemma A.1 samples $R\sim\mathcal{U}$,
and samples $R^{\prime}$ uniformly conditioned on
$\mathsf{Lap}(1/\epsilon;R^{\prime})=f(\mathbf{x}^{\prime})-f(\mathbf{x})$.

###### Proof.

Consider the randomized map $G^{*}:{\mathcal{Z}}\to{\mathcal{Y}}$ that inverts
$g$ for inputs drawn from $Q$—namely, $G^{*}(z)$ returns a random element
according to $Q|_{{\left\\{{y:g(y)=z}\right\\}}}$ and returns the default
element $\bot$ with probability 1 if $g^{-1}(z)$ is empty. Running $G^{*}$ on
$g(Y)$ returns a sample distributed identically to $Y$ conditioned on $g(Y)$.
That is,

${\Big{(}{g(Y),\ G^{*}(g(Y))}\Big{)}}\equiv{\Big{(}{g(Y),\ Y}\Big{)}}.$

Since the $\approx_{\epsilon,\delta}$ relation is preserved by processing, and
since $f(X)\approx_{\epsilon,\delta}g(Y)$, we have

${\Big{(}{g(Y),\ G^{*}(g(Y))}\Big{)}}\approx_{\epsilon,\delta}{\Big{(}{f(X),\
G^{*}(f(X))}\Big{)}}.$

Now for every $x\in\mathcal{X}$, the random variable $G^{*}(f(x))$ is
distributed as $Q_{x}$. Therefore, $G^{*}(f(X))$ is distributed as
$Y^{\prime}$ from the theorem statement and
$Y^{\prime}\approx_{\epsilon,\delta}Y$ (the first requirement of the theorem).
Furthermore, $g(Y^{\prime})$ equals $f(X)$ except when $f(X)$ lies outside the
image of $g$. Since $f(X)\approx_{\epsilon,\delta}g(Y)$, the value $f(X)$ lies
outside the image of $g$ with probability at most $\delta$. This establishes
the theorem’s second requirement. ∎

##### A computable analogue of Lemma A.1

To demonstrate deletion-as-control compliance, we need a simulator to sample
ideal-world randomness $R^{\prime}_{\mathsf{C}}$ whose marginal distribution
is close to the uniform distribution while also guaranteeing that
$\mathsf{state}^{\prime}_{\mathsf{C}}=\mathsf{state}_{\mathsf{C}}$. A natural
strategy is to sample $R^{\prime}_{\mathsf{C}}$ from distribution conditioned
on the equality of the states. Applying Lemma A.1, the resulting distribution
suffices for our purposes in this paper, where $X=R_{\mathsf{C}}$ and
$Y=R^{\prime}_{\mathsf{C}}$. But there is a technicality that needs to be
dealt with. In full generality, the conditional distributions $Q_{x}$ in that
lemma may not be sampleable in finite time. This will not be a problem for us,
as our applications of the lemma will be restricted to functions that depend
only a finite prefix of $R_{\mathsf{C}}$ and $R^{\prime}_{\mathsf{C}}$. For
completeness, we state a computable analogue of Lemma A.1. Elsewhere, we will
elide this technicality and invoke the simpler Lemma A.1.

######  Lemma A.2 (Computable Coupling Lemma).

Let $P$, $Q$, $\mathcal{X}$, ${\mathcal{Y}}$, ${\mathcal{Z}}$, $f$, $g$, and
$Q_{x}$ as in Lemma A.1. Let $\mathcal{X}=\\{0,1\\}^{*}={\mathcal{Y}}$.
Suppose that $g(y)$ depends only on a finite prefix of $y\in\\{0,1\\}^{*}$.
Suppose also that for all $x\in\\{0,1\\}^{*}$, either $f(x)$ depends only on a
finite prefix of $x\in\\{0,1\\}^{*}$, or $g^{-1}(f(x))=\emptyset.$ Then for
any $x$, $Y\sim Q_{x}$ can be written as $Y_{1}\|Y_{2}$ where $|Y_{1}|$ is
finite and $Y_{2}$ is uniform in $\\{0,1\\}^{*}$ and independent of $Y_{1}$.

In our applications, $X$ and $Y$ will be $R_{\mathsf{C}}$ and
$R^{\prime}_{\mathsf{C}}$ respectively. $f$ and $g$ will be functions of the
real and ideal executions, respectively. By construction, an ideal execution
is always finite, and therefore $g(Y)$ will only depend on a finite prefix of
$R^{\prime}_{\mathsf{C}}$. A real execution is either finite—in which case
$f(X)$ only depends on a finite prefix of $R_{\mathsf{C}}$—or it is infinite.
If it is infinite the real execution (and $f$) outputs $\bot$, whereas the
ideal execution (and $g$) can never output $\bot$.

######  Lemma A.3 (Conditioning Lemma [Kasiviswanathan and Smith, 2014]).

Let $(A,B)$ and $(A^{\prime},B^{\prime})$ be pairs of random variables over
the same domain ${\mathcal{A}}\times{\mathcal{B}}$ such that $(A,B)\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
(A^{\prime},B^{\prime})$. Then for all $\delta^{\prime}>0$, with probability
at least $1-\gamma$ over $a\leftarrow A$, we have

$B|_{A=a}\
{\stackrel{{\scriptstyle{\tiny\epsilon^{\prime},\delta^{\prime}}}}{{\approx}}}\
B^{\prime}|_{A^{\prime}=a}\,,$

where $\epsilon^{\prime}=3\epsilon$ and
$\gamma=\frac{2\delta}{\delta^{\prime}}+\frac{2\delta}{1-\exp(-\epsilon)}$.

##  Appendix B Differential Privacy Preliminaries

A dataset $\mathbf{x}=(x_{1},\ldots,x_{n})\in\mathcal{X}^{n}$ is a vector of
elements from universe $\mathcal{X}$. Two datasets are neighbors if they
differ in at most one coordinate. Informally, differential privacy requires
that an algorithm’s output distributions are similar on all pairs of
neighboring datasets. We use two different variants of differential privacy.
The first one (and the main one used in this paper) is the standard definition
of differential privacy.

######  Definition B.1 (Differential Privacy [Dwork et al., 2016, 2006]).

A randomized algorithm $\mathcal{M}:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ is
$(\epsilon,\delta)$-differentially private if for every pair of neighboring
datasets $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}^{n}$ and for all
subsets $Y\subseteq\mathcal{Y}$,

$\Pr[\mathcal{M}(\mathbf{x})\in Y]\leq
e^{\epsilon}\cdot\Pr[\mathcal{M}(\mathbf{x}^{\prime})\in Y]+\delta.$

Notice that $\mathcal{M}$ is $(\epsilon,\delta)$-differentially private if and
only if for all pairs of neighboring datasets
$\mathbf{x},\mathbf{x}^{\prime}$, we have $\mathcal{M}(\mathbf{x})\
{\stackrel{{\scriptstyle{\tiny\epsilon,\delta}}}{{\approx}}}\
\mathcal{M}(\mathbf{x}^{\prime})$ as defined in Section 2.

Differential privacy protects the privacy of groups of individuals, and is
closed under post-processing. Moreover, it is closed under adaptive
composition. For a fixed dataset $\mathbf{x}$, adaptive composition states
that the results of a sequence of computations satisfies differential privacy
even when the chosen computation $\mathcal{M}_{t}(\cdot)$ at time $t$ depends
on the outcomes of previous computations
$\mathcal{M}_{1}(\mathbf{x}),\ldots,\mathcal{M}_{t-1}(\mathbf{x})$. Under
adaptive composition, the privacy parameters add up.

######  Lemma B.2 (Post-Processing).

If $\mathcal{M}:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ is
$(\epsilon,\delta)$-differentially private, and
$\mathcal{B}:\mathcal{Y}\rightarrow\mathcal{Z}$ is any randomized function,
then the algorithm $\mathcal{B}\circ\mathcal{M}$ is
$(\epsilon,\delta)$-differentially private.

######  Lemma B.3 (Group Privacy).

Every $(\epsilon,\delta)$-differentially private algorithm $\mathcal{M}$ is
$\left(k\epsilon,\delta\frac{e^{k\epsilon}-1}{e^{\epsilon}-1}\right)$-differentially
private for groups of size $k$. That is, for all datasets
$\mathbf{x},\mathbf{x}^{\prime}$ such that
$\|\mathbf{x}-\mathbf{x}^{\prime}\|_{0}\leq k$ and all subsets
$Y\subseteq\mathcal{Y}$,

$\Pr[\mathcal{M}(\mathbf{x})\in Y]\leq
e^{k\epsilon}\cdot\Pr[\mathcal{M}(\mathbf{x}^{\prime})\in
Y]+\delta\cdot\frac{e^{k\epsilon}-1}{e^{\epsilon}-1}.$

######  Definition B.4 (Composition of $(\epsilon,\delta)$-differential
privacy).

Suppose $\mathcal{M}$ is an adaptive composition of differentially private
algorithms $\mathcal{M}_{1},\ldots,\mathcal{M}_{T}$. If for each $t\in[T]$,
algorithm $\mathcal{M}_{t}$ is $(\epsilon_{t},\delta_{t})$-differentially
private, then $\mathcal{M}$ is
$\left(\sum_{t}\epsilon_{t},\sum_{t}\delta_{t}\right)$-differentially private.

##  Appendix C Strong History Independence and Deletion-as-control

We show that strong history independence implies deletion-as-control.
Throughout, we use SHI to mean $(0,0)$-SHI.

A foundational result in the study of history independent data structures
characterizes the behavior of SHI implementations of a large class of ADTs
called reversible ADTs.

######  Definition C.1 (Reversible ADT).

An ADT is _reversible_ if, for all logical states $A$ and $B$ reachable from
the initial state, there exists some finite sequence of operations $\sigma$
such that $\mathsf{ADT}(A,\sigma).\mathsf{state}=B$. That is, all reachable
states are _mutually reachable_.

######  Theorem C.2 (Hartline et al. [2005]).

A reversible data structure is SHI if and only if each logical state has a
single canonical memory representation for every setting of the
implementation’s randomness tape.

######  Claim C.3.

If an ADT supports logical deletion, then it is reversible. The converse is
not true.

###### Proof.

(Logical deletion $\implies$ reversible): To prove reversibility, it is
sufficient to give a sequence of operations that takes the ADT back to its
initial state. Fix a state $A$ that is reachable from the initial state. Pick
any sequence $\sigma$ that takes the initial state to $A$. Delete all of the
${id}$’s in $\sigma$ one by one. By logical deletion, the resulting state is
the initial state.

(Reversible $\centernot\implies$ logical deletion): Consider the ADT where the
set of (non-delete) operations is the space of IDs and the logical state
consists of the most recent ID. Suppose also that
$\mathsf{out}_{\mathsf{adt}}=\bot$ always. This ADT is reversible: for any IDs
$A$ and $B$, $\mathsf{ADT}((A,B)).\mathsf{state}=B$. (We note that this ADT
trivially admits a SHI implementation.)

Consider two sequences of IDs $(A,C)$ and $(B,C)$, where $A\neq B$. If this
ADT supports logical deletion, then we derive a contradiction:

$\displaystyle(A,\bot)=\mathsf{ADT}((A,C,{\text{\sf{delete}}}(C)))=\mathsf{ADT}((C,{\text{\sf{delete}}}_{C}))$
$\displaystyle=\mathsf{ADT}((B,C,{\text{\sf{delete}}}(C)))=(B,\bot),$

where the first and last equalities follow from logical deletion and the
second and third follow by construction. This counter example illustrates that
deletion may require the data controller to keep sufficient records of all
users to update the state. ∎

We now prove that SHI implies deletion-as-control. We restate the theorem for
convenience. See 4.7

###### Proof of Theorem 4.7.

Fix $\mathsf{C}$ and any $\mathsf{E}$ and $\mathsf{Y}$ in the deletion-as-
control game. By the definition of logical deletion, the sequence
$\vec{\mathsf{q}}$ in the real world and $\vec{\mathsf{q}}^{\prime}$ in the
ideal world are logically equivalent. Let $\mathsf{Sim}$ be the simulator that
always outputs $R^{\prime}_{\mathsf{C}}=R_{\mathsf{C}}$. By Theorem C.2, the
real-world and ideal-world states are identical (since the randomness and the
logical states are identical). So, we satisfy the first condition of deletion-
as-control. Furthermore, since the value of $R^{\prime}_{\mathsf{C}}$ equals
the value of $R_{\mathsf{C}}$, they are identically distributed. Thus, this
controller satisfies $(0,0)$-deletion-as-control. ∎