tcb@breakable

# Proof of Unlearning: Definitions and Instantiation

Jiasi Weng +Work was done when the author was a Postdoc with City University
of Hong Kong. College of Cyber Security, Jinan University  Department of
Computer Science, City University of Hong Kong  Shenglong Yao  Department of
Computer Science, City University of Hong Kong  Yuefeng Du  Department of
Computer Science, City University of Hong Kong  Junjie Huang  College of Cyber
Security, Jinan University  Jian Weng  College of Cyber Security, Jinan
University  Cong Wang  Department of Computer Science, City University of Hong
Kong

###### Abstract

The “Right to be Forgotten” rule in machine learning (ML) practice enables
some individual data to be deleted from a trained model, as pursued by
recently developed machine unlearning techniques. To truly comply with the
rule, a natural and necessary step is to verify if the individual data are
indeed deleted after unlearning. Yet, previous _parameter-space_ verification
metrics may be easily evaded by a distrustful model trainer. Thus, Thudi _et
al._ recently present a call to action on _algorithm-level_ verification in
USENIX Security’22.

We respond to the call, by reconsidering the unlearning problem in the
scenario of machine learning as a service (MLaaS), and proposing a new
definition framework for _Proof of Unlearning_ (PoUL) on algorithm level.
Specifically, our PoUL definitions (_i_) enforce correctness properties on
both the pre and post phases of unlearning, so as to prevent the state-of-the-
art forging attacks; (_ii_) highlight proper practicality requirements of both
the prover and verifier sides with minimal invasiveness to the off-the-shelf
service pipeline and computational workloads. Under the definition framework,
we subsequently present a trusted hardware-empowered instantiation using SGX
enclave, by logically incorporating an authentication layer for tracing the
data lineage with a proving layer for supporting the audit of learning. We
customize authenticated data structures to support large out-of-enclave
storage with simple operation logic, and meanwhile, enable proving complex
unlearning logic with affordable memory footprints in the enclave. We finally
validate the feasibility of the proposed instantiation with a proof-of-concept
implementation and multi-dimensional performance evaluation.

##  I Introduction

Machine learning (ML) models deployed for prediction services are usually
trained on user data, which can refer to the current machine learning as a
service (MLaaS) paradigm. Particularly, a data owner can authorize a service
provider to train an ML model over his/her data and later offer black-box
prediction services with the trained model. But at a later time, the data
owner might withdraw the authorization, _i.e._ , sending a request to delete
his/her data from the trained model, simply due to regret emotion [83, 69], or
deterred by privacy attacks on trained models [66, 77, 17, 50]. Such right of
data deletion can be legally protected by privacy regulations [79], namely
“Right to be Forgotten” (RTBF) which is explicitly stated by the European
Union’s General Data Protection Regulation (GDPR) [60] and the United States’s
California Consumer Privacy Act (CCPA) [4]. More specifically, the U.K.’s
Information Commissioner’s Office [1] and the Federal Trade Commission [23]
recently clarify that complying with the deletion request requires retraining
the model or deleting the model altogether.

Machine unlearning is a closely relevant concept, having a target model forget
partial training data, but previous unlearning approaches [16, 14, 32, 37, 34,
33, 52, 84] might fail to achieve the RTBF compliance in a distrustful
setting. First of all, the approaches often assume an honest server. However,
the powerful server side is likely to not delete user data in reality, which
is commonly reported [28, 5, 12], and is naturally wavering in users’ trust
[72, 46]. Furthermore, a dishonest server can also strategically evade the
verification metrics suggested by prior unlearning approaches, by launching
forging attacks [73, 67], and therefore, Thudi _et al._ [73] call for action
to audit unlearning, while leaving a blank space to be filled in. Last but not
least, the nature of a black-box service manner might motivate the server to
maliciously fork multiple models, which may invalidate previous unlearning
approaches as well as existing black-box verified methods [51, 40, 70]. For
instance, the server can fork an arbitrary model (not the target model in
question), and claim having deleted data from the forking model, while still
offering prediction services using the target model which never deletes data
at all.

In light of the dishonest server, which can arbitrarily deviate from prior
unlearning approaches, this work studies how to truly implement Proof of
Unlearning (PoUL) for pursuing the RTBF compliance with _end-to-end_
assurances, _i.e._ , closed-loop enforcement starting from pre-learning and
prediction to unlearning and post-prediction.

Unlearning problem. We clarify the unlearning problem specific for the off-
the-shelf ML pipeline in MLaaS. Starting from a trained _target model_
offering prediction services, when a data owner requests to delete a data
point, the server should execute an unlearning process on the target model,
yielding a newly predictive model which fully eliminates the effect of the
data point in accordance to the unlearning goal of previous efforts [16, 37,
19, 22, 14].

But the server may behave dishonestly, which may forge an incorrect target
model, or run an incorrect unlearning process or fork an inconsistent model
for new predictions. We next define our PoUL to prevent such misbehavior with
respect to a data point deletion.

Definitions of PoUL. Here involves two sequential phases aligned with the
black-box service nature: (_i_) Setup phase. the server proves that a target
model in question indeed learns the data point. (_ii_) Deletion phase. the
server proves that a newly predictive model is yielded by a correct unlearning
process which indeed removes the data point from the previous target model.
Within the definition scope, we require that the server should simultaneously
assure the correctness of the target model, the unlearning process and the
newly predictive model, such that the data owner (as a honest verifier) can be
convinced of the fulfillment of his/her unlearning problem.

PoUL is different from a recent excellent art [45], _proof-of-learning (PoL)_
, which facilitates proofs for a learning process based on the idea of re-
execution. Specifically, PoL offers a verifier a document on learning
trajectory for convincing him of the truth that the learning trajectory is
used to generate a particular model with overwhelming probability. While the
PoL is easy to understand and implement, it cannot be extended to implement
the PoUL, due to different problem statements and threat models, figured out
by Thudi _et al._ [73]. Recent attack examples [87] can efficiently forge
learning trajectory to generate a fake but valid PoL proof, which further
demonstrates the difficulty of implementing the PoUL. Lastly, our PoUL
especially emphasizes that subsequent prediction services should be offered by
an unlearned model as expected, which is not considered by the PoL.

To pursue practice-oriented solutions, we subsequently highlight practicality
requirements needed for our PoUL: (a) _Enabling generic models._ The
unlearning problem in MLaaS can happen in various models, which requires proof
techniques to support generic computations involved by various model
architectures. (b) _Limited invasiveness._ Proof techniques should be
maximally compatible with the underlying learning algorithms, so as to
maintain the original ML services quality. (c) _Minimal overhead._ Standing on
the already workload-intensive ML pipeline, additional proving workloads
should be as affordable as possible. Besides the server-side requirements,
PoUL should also meet the following verifier-side requirements, such that the
data owner can enjoy predictive services nearly as usual beyond verifying
unlearning. (d) _Concise proof._ Generated proofs should be short enough to
ease the storage cost of the data owner. (e) _Efficient verification._ Proofs
should also be cheaply verified considering a usually thin verifier.

###  I-A Solution Overview

We now present our solution roadmap to implement PoUL, towards complying with
the deletion obligation. We observe that PoUL relates to proof-based
verifiable computation (VC) [80], especially a line of “authenticate first and
prove later” proof systems. Simply speaking, a data owner can authorize her
data to the server, along with a data digest generated by authenticated data
structures (ADS) [71], and then keep track of particular zero-knowledge proofs
issued by the server, with respect to the correctness of a target model, an
unlearning process and a newly predictive model, which are not transparent to
the data owner. Yet, aware of the mentioned practicality requirements, the
line of pure crypto-assisted proof systems [80] are not the preferred choices
(see more in Appendix A).

From another perspective, trusted execution environments (TEEs) are quickly
becoming trusted computing services offered by dominant service providers,
_e.g._ , Alibaba Cloud [8], IBM Cloud [43] and Microsoft Azure [2], and many
application efforts [47, 26, 30] demonstrate that TEEs can assist the
providers in performing with obligation compliance, _e.g._ , enforcing data
usage with GDPR compliance [68, 61]. Therefore, we are naturally encouraged to
instantiate PoUL with the TEEs-backed offerings, and thereby enable native
implementation and practical deployment on the server side. Also, we admit
that recent TEEs-empowered ML works [75, 48, 38, 74, 54, 41, 42, 86, 88, 53,
39, 11] may help mitigate a certain issue within our PoUL, but we need new and
holistic designs tailored for proving end-to-end RTBF compliance in MLaaS.

Our unlearning setting. We begin with Bourtoule _et al._ ’s efficient
retraining-based unlearning framework [14], towards enabling complete deletion
[35]. Specifically, the server trains multiple chunked submodels in isolation
over disjoint shards of data, and meanwhile, each chunked submodel is
incrementally learned with non-overlapping slices of data points (named sliced
data hereafter); when one data point is deleted, _only particular submodels
exactly trained on or impacted by the data point need to be retrained_ , which
is therefore faster than retraining a complete model from scratch.

TEEs-capable PoUL implementation. Standing on the unlearning setting, we
incorporate ADS with Intel Software Guard Extensions (SGX) [3, 24] on the
server side, to issue proofs in the Setup and Deletion phases previously
described. Our incorporation implies (_i_) _an authentication layer_ for
tracing which sliced data are learned or unlearned, and which chunked
submodels are retrained or used to offer predictions; and (_ii_) _a proving
layer_ for attesting the execution correctness of the learning or prediction
processes that exactly use particular authenticated data or submodels.

However, it is challenging to implement the two-layer incorporation, due to
the incompatible features between our unlearning setting and Intel SGX.

_Challenge (i): Memory-Efficient Authentication._ In the authentication layer,
we require tracking which sliced data impact which chunked submodels, and
supporting authenticated updates on the impacted submodels when a data point
is deleted. But both data and submodels are often large-size and the
unlearning problem might cause a large number of submodels to be updated,
which inevitably incurs large memory footprints far beyond the original memory
limitation of SGX111It is about $94$ MB available to applications in a widely
adopted version, and a recent release [6] supports $188$ MB.. Hence, we
provide a memory-efficient authentication design tailored for the traceability
from the sliced data to the updatable submodels while protecting the
integrity.

_Challenge (ii): Proof of Stateful Computation and Fast Verification._ In the
proving layer, the computations involving a chain of incremental retraining
processes to update affected submodels, and subsequent prediction processes
using the newly retrained model should be attested, so that a verifier is
convinced of the fulfillment of data deletion. Yet, the computations are
stateful, since the incremental retraining and prediction processes require
previously generated states, _e.g._ , submodels, which is in conflict with the
SGX design of primarily protecting stateless computations. We extend the trust
outside the SGX’s protected memory to securely save previous states, by
typically letting the protected memory retain unique randomnesses (named seed)
respective to each submodel for subsequent integrity checking. To reduce
verification cost, we adopt a self-verification strategy. Concretely, we
enable the verifier to only assert that an appointed submodel (_i.e._ , a
final one) matching a newly produced digest yields new predictions on a given
test data, while the authenticity of all retrained submodels prior to the
appointed submodel is verified by the enclave itself. Furthermore, in light of
the need for monitoring the correctness of subsequent prediction services, an
additional SGX-enabled auditor is considered.

In summary, we make three-fold contributions as following:

  * •

We propose a new two-phase definition framework for achieving PoUL, which
adapts to Bourtoule _et al._ ’s generic unlearning algorithm (in IEEE S&P’21),
and meanwhile, prevents recent forging attacks (in USENIX Security’22).

  * •

Under the definition framework, we present an SGX-capable solution with newly
customized designs, by logically integrating an authenticated layer for
tracing the lineage of training data with a proving layer for auditing the
correctness of model training.

  * •

We give a proof-of-concept implementation for the SGX-capable PoUL, and
evaluate the multifaceted performance in terms of storage cost, deletion time,
learning/unlearning time and trained accuracy. The implementation code is
available in https://github.com/James-yaoshenglong/unlearning-TEE.

##  II Background

###  II-A Machine Unlearning

Machine unlearning starts from a concept of removing a/some training data from
an already trained model [16]. According to the different understanding of the
concept, existing approaches can be roughly classified into two groups,
including _approximate unlearning_ achieving data deletion from parameter
level [34, 33, 32, 63] and _exact unlearning_ achieving data deletion from
algorithm level [16, 14, 37, 19, 22]. The essential difference between the two
groups is clarified by the Definition 1.

###### Definition 1

Let $D=\\{d_{i}\\}\cup d_{u},i\in\\{1,\dots,N\\}\backslash u$ be a collection
of $N$ training samples. Let $D_{-u}$ denote a collection of $N-1$ training
samples, namely $D\backslash d_{u}$. Let $\mathcal{D}_{M}$ be the distribution
of a model that has ever been trained over $D$ and then unlearned $d_{u}$ via
a machine unlearning algorithm R. Let $\mathcal{D}_{M}^{{}^{\prime}}$ be the
distribution of a model trained over $D_{-u}$. Then denote R as an approximate
unlearning algorithm, if the distribution $\mathcal{D}_{M}$ is approximately
equal to $\mathcal{D}_{M}^{{}^{\prime}}$. Otherwise, denote R as an exact
unlearning algorithm, if the distribution $\mathcal{D}_{M}$ is exactly equal
to $\mathcal{D}_{M}^{{}^{\prime}}$.

Recently, _the SISA framework_ [14] provides an exact unlearning method
towards generic ML models, which fully erases the effect of deleted data. It
is faster than retraining from scratch by trading storage for efficiency, and
is followed by many promising unlearning work [37, 19, 22].

We next introduce a server-side ML pipeline under the SISA framework, as shown
in Fig. 1. Suppose the server-side pipeline runs over the dataset authorized
by a data owner and generates learned models, along with model checkpoints. At
a later time, it complies with a deletion request of the data owner via
unlearning. We introduce the pipeline with two parts: A) pre-learning and
prediction stages, as well as B) unlearning and post-prediction stages. We
denote $N=\\{1,\dots,n\\}$ and $S=\\{1,\dots,s\\}$.

Figure 1: The server-side ML pipeline under the SISA framework. Multiple
dashed rectangles represent that different _Shards_ of data are used for
incrementally training constituent models in an _Isolated_ manner. Within one
shard, the training data is further _Sliced_ into disjoint data slices, where
the data slice in grey (_i.e._ , $d_{s-1}$) influences or impacts the
intermediate submodels in grey (_i.e._ , $m_{s-1}$ and $m_{s}$). All
constituent models (the last submodels) of individual shards produce
predictions that are _Aggregated_ into final predictions.

A. Pre-learning and Prediction Stages There are four major operations. (a)
_Shard._ In the first place, the data owner’s dataset is divided into $n$ non-
overlapping data shards, denoted as $D_{j\in[N]}$; (b) _Isolation._
Subsequently, stochastic gradient descent (SGD)-based training algorithm is
applied to train a constituent model on each shard of data in isolation; (c)
_Slice._ Inside each shard, the data $D_{j}$ is further sliced into $s$
disjoint data slices, represented by $D_{j}=\\{d_{j,i}\\}_{i\in[S],j\in[N]}$,
such that data slices are incrementally added for learning, and the produced
submodels $\\{m_{i}\\}_{i\in[S]}$ are saved during learning; (d)
_Aggregation._ The final prediction is obtained by aggregating the predictions
provided by the constituent models $m_{s,j},j\in[N]$ of all shards. Herein, a
data slice can contain a small set of _non-overlapping_ data points. Note that
the impact of each data point is restricted on relatively small-size
submodels, rather than an entire model.

B. Unlearning and Post-prediction Stages On receiving the data owner’s request
of deleting one data point $d_{u}\in D$, the following steps are executed: (a)
find which shards this data point $d_{u}$ belongs to and which submodels it
influences; (b) locate the shard and the slice associated to $d_{u}$, and
delete the $d_{u}$ from the slice and the submodels influenced by $d_{u}$
within the shard; (c) re-execute the incremental training processes with the
remaining data slices as pre-training.

Now we show a concrete example. We suppose the $d_{u}$ that will be deleted
falls in the last but one slice $d_{s-1}$ of Fig. 1 and the submodels
$m_{s-1}$ and $m_{s}$ are influenced by the $d_{u}$. Guided by the above
steps, the $m_{s-1}$ and $m_{s}$ will be deleted, and subsequently, new
$m_{s-1}$ and $m_{s}$ are relearned over the remaining data
$\\{d_{1},\cdots,d_{s-2},d_{s-1}\backslash d_{u}\\}$ and $\\{d_{1},\cdots,$
$d_{s-2},d_{s-1}\backslash d_{u},d_{s}\\}$, respectively, in the same
incremental manner. Finally, new predictions are produced by newly updated
models and aggregated without any effect of the deleted data point. Notice,
the server only needs to re-compute the relatively small-scale submodels
affected by the $d_{u}$, without the need to retrieve or relearn the entire
model. As a result, this framework can be faster than retraining from scratch,
varying from $2.45\times$ to $4.63\times$ [14].

###  II-B Trusted Execution Environments

Trusted Execution Environments (TEEs) provide a hardware-protected memory
environment for sealed data and shielded execution of applications in an
untrusted platform. Many off-the-shelf TEEs technologies, _e.g._ , Intel SGX
[3, 24], ARM TrustZone [9], become promising to implement secure applications
with minimal performance compromise, in which Intel SGX is widely adopted, and
thus our work adopts SGX.

Intel SGX Enclave Intel SGX allows creating a secure memory region, named as
_enclave_ , to execute application codes with confidentiality and integrity
guarantees, _isolated_ from the outside platform which can be untrusted. It
also provides a _remote attestation_ mechanism by issuing a signature-based
proof (Enhanced Privacy ID signature scheme [15]) on a requested _quote_ ,
containing the measurement of the enclave’s code and data. With the proof, a
remote client can assert the authenticity of the enclave identity and the
truthfulness of code execution, after it subscribes to the Intel’s Attestation
Service.

Formal Functionality Modeling Shi _et al._ [58] formalize the functionality of
an SGX enclave, involving enclave initialization, enclave operations and
attestation. With the functionality, Tramèr _et al._ [76] introduce an
enclave-empowered “commit-and-prove” functionality executed by a prover
equipped with a _transparent_ enclave and a verifier. The transparent enclave
is considered with integrity property, but with minimal confidentiality
assumptions, _e.g._ , random number generators and the signing key, not
including the programs running in the enclave. More detailed description
refers to Appendix B.

Attack Threats on SGX Enclave Integrity violation attacks on the SGX enclave,
such as forking, replacing, relocation and rollback attacks will be mitigated
by our designs (see Section V-B). However, we do not address existing side-
channel attacks breaking integrity by stealing secret keys [20, 78], aware of
recent countermeasures protecting secret-dependent memory accesses against
such side-channel attacks. Control flow attacks [7, 25] are also outside of
our scope, since the attacks escape from the off-the-shelf static remote
attestation mechanisms. In addition, Denial-of-Service attacks [44], _e.g._ ,
shutting down the enclave applications, are not our concern.

###  II-C Data Structure for Fast Membership Testing

We elaborate here a space-optimized and high-speed data structure, namely,
cuckoo filter [27], designed for membership query from a usually large data
set with low and controllable false positive rates. Different from Bloom
filters, it supports $O(1)$ element deletion, not merely addition. Compared
with cuckoo hash tables, it only stores short and constant-size fingerprints
of elements.

Concretely, a cuckoo filter consists of an array of buckets, in which each
bucket contains multiple entries, _e.g._ , $4$ or $8$. A fingerprint of an
element can be filled in two possible buckets. This is determined by two hash
functions derived from standard cuckoo hashing [57] as introduced in the
following. For example, given a new element $e$ to be inserted and its
fingerprint $f_{e}$ (_e.g._ , truncated PRESENT ciphertext with $16$ bits as
[65] applied), an alternative location $h_{1}$ of bucket $B$ is found by
calculating a $64$-bit hash value $h_{1}=\text{Hash}(e)$. The hash functions
can adopt the CityHash [27]. If it is empty, the fingerprint of this element
is inserted into $B[h_{1}]$. Otherwise, another location $h_{2}$ is found by
calculating $h_{2}=h_{1}\oplus\text{Hash}(f_{e})$, where the original element
$e$ is not needed to be retrieved. Next, a location displacement method is
called, if $B[h_{2}]$ is also not empty. Specifically, the element at $h_{2}$
would be replaced with $f_{e}$, and the element is placed in its alternative
location. This displacement process is repeated until an empty bucket is found
or a displacement threshold (_e.g._ , 500) is reached.

##  III Problem Statement

We observe that a dishonest sever can arbitrarily deviate from fulfilling a
data deletion request of a data owner during unlearning. Also, there not
exists an approach to enforcing the behavior of the server during unlearning.
The observation motivates us to establish trust for the data owner. This
section will clarify the threats and deletion assumptions we are concerned
about, for ease of understanding our definitions of PoUL in the next section.

###  III-A Threat Scenario

Figure 2: Three threats to the server-side ML pipeline.

On top of the ML pipeline previously described, we consider the server can
misbehave arbitrarily, by forking multiple models due to the non-transparent
nature of the black-box service manner, or forging unlearned models with off-
the-shelf forging attacks [73, 67]. We note prior auditing methods [51, 40,
70, 31] are not concerned about the misbehaviors. Concretely, we summarize the
following three cases of misbehaviors in the pipeline assisted with Fig. 2:

  * •

At the prediction stage, the server might substitute a _correct target model_
and avoid deleting data from the target model. The so-called correct target
model is denoted as the model which was ever trained using the data to be
deleted.

  * •

At the unlearning stage, the server might not correctly execute an unlearning
process.

  * •

At the post-prediction stage, the server might not deploy a correct unlearned
model for subsequent service.

For data owner, we consider he/she is honest throughout the process, only
having a black-box access to the models. His/Her data collected by the server
for learning and test data for predictions are also considered benign. Data
confidentiality against the server is not considered. Lastly, we let the the
data owner communicate with the server via an authenticated point-to-point
communication channel.

###  III-B Deletion Assumptions

We focus on the problem of deleting training data from a target model on the
server site. We note that data deletion from memory on physical medium
addressed by previous arts [59, 55] is outside of our consideration. We are
not concerned about data or model copy, simply due to monetary storage costs,
and do not consider deleting copied data or model. We assume the training data
is non-overlapping similar to the SISA framework. We focus on a single data
deletion request, but our design can be extended to delete multiple data
pieces (see Appendix C). Relying on the SISA framework’s technical
characteristic, multiple data deletion requests should be assumed irrespective
of the actual models (_e.g._ , a never unlearned model or an unlearned model)
in question [14], and adaptive deletion [37] is out of our scope.
Additionally, recent inference attacks [21, 29] on unlearned models are out of
consideration.

##  IV Definitions on Proof of Unlearning

We are ready to describe the definitions on PoUL, along with three correctness
properties and five practicality goals. Intuitively, we require the server to
generate proofs of correct unlearning, and given the proofs, the data owner
has confidence in asserting if the server complies with his/her deletion
request or not.

To begin with, we denote some notations. We let an indexed collection of
learning data $D=\\{d_{i}\\}_{i\in[N]}$, including a data point $d_{u}$ that
will be deleted. We denote $\textsf{M}_{0}$ as a public model with initial
weights, and F/G as public learning/prediction algorithms. We let a test data
$t$ and a prediction $p$. We mark $[m_{u}]$ as the affected part of a model by
its learning data $d_{u}$. We use SR and DO to denote the server and the data
owner, respectively. We also use $\pi$ to define a proof component generated
by the SR.

###  IV-A Definition Framework

There are two phases composing the definition framework for PoUL. In a setup
phase, the SR offers a proof attesting that the currently predictive model is
a true target model responding to a test challenge from the DO. In a later
deletion phase, the SR retains a proof of truth that the newly predictive
model is a truly unlearned model from the above target model excluding the
deleted data piece $d_{u}$, responding to a new test challenge. Particularly,
the two phases involve a chain of interactive procedures as following.

Setup Phase ($\textsf{S}_{1}$-Initialize) The DO uploads his/her data $D$
along with an authentic data digest to the SR; The DO specifies a learning
algorithm F and an initial model $\textsf{M}_{0}$ with the SR; The SR then
learns a model $\textsf{M}_{1}$ from $\textsf{M}_{0}$ with F taking the data
$D$ as input. Notice, the learned $\textsf{M}_{1}$ now is the target model we
describe before, and its digest $\textsf{H}(\textsf{M}_{1})$ is published.
($\textsf{S}_{2}$-Challenge) The DO sends a test data $t$ to the currently
predictive model for prediction query. ($\textsf{S}_{3}$-Prove) The SR
responses to the query with a prediction $p$ and a proof component $\pi$.
($\textsf{S}_{4}$-Verify) With the proof $\pi$ and prediction $p$, and the
above model digest $\textsf{H}(\textsf{M}_{1})$, the DO verifies the
correctness of the prediction. Specifically, he/she would reject it with high
probability, if the prediction is not yielded by the target model
$\textsf{M}_{1}$, denoted as a statement
$p\leftarrow\textsf{G}(\textsf{M}_{1},t)\wedge\textsf{M}_{1}\leftarrow\textsf{F}(\textsf{M}_{0},D)$.

Deletion Phase ($\textsf{D}_{1}$-Unlearning) The DO sends a request of
deleting the data $d_{u}$ from the target model $\textsf{M}_{1}$; the SR
executes an unlearning process of F on the $\textsf{M}_{1}$ and $D\backslash
d_{u}$, yielding an unlearned model $\textsf{M}_{2}$ whose digest
$\textsf{H}(\textsf{M}_{2})$ is public. ($\textsf{D}_{2}$-Challenge) At a
later time, the DO challenges the newly predictive model with a new test data
$t^{\prime}$. ($\textsf{D}_{3}$-Prove) The SR returns a prediction
$p^{\prime}$, along with a new proof component $\pi^{\prime}$.
($\textsf{D}_{4}$-Verify) With the proof $\pi^{\prime}$ and prediction
$p^{\prime}$, and the digests $\textsf{H}(\textsf{M}_{1})$ plus
$\textsf{H}(\textsf{M}_{2})$, the DO verifies the prediction correctness, and
rejects it with high probability, if the prediction $p^{\prime}$ is not
offered by a correctly unlearned model, denoted as a statement
$p^{\prime}\leftarrow\textsf{G}(\textsf{M}_{2},t^{\prime})\wedge\textsf{M}_{2}\leftarrow\textsf{F}(\textsf{M}_{1}\backslash[m_{u}],D\backslash
d_{u})$.

Logical Components Essentially, there are two-layer components to be realized
for supporting the setup and the deletion phases in our scoped PoUL: _(1)
Authentication layer_ : The data owner authenticates his/her data (_e.g._ ,
data digest) in the first place and delegates the data to the server, along
with the authenticated result for tracking operations on the data in a future
time, _e.g._ , using or not using the data for training. Relying on the
authentication layer, the intermediate models and the final model yielded by a
learning process, should also be authentically saved (and updated), such that
a later unlearning process or a prediction process is ensured to use the
previously authenticated models. _(2) Proving layer_ : This layer works
jointly with the authentication layer. Particularly, the server convinces the
data owner that a learning process, either in the $\textsf{S}_{1}$-Initialize
or the $\textsf{D}_{1}$-Unlearning procedure, is executed as expected, with
the learning data matching the previously authenticated data. Besides
learning, the server also assures the correctness of a predictive model, which
exactly means that a prediction process in the $\textsf{S}_{3}$-Prove
procedure (resp. $\textsf{D}_{3}$-Prove) uses a most recent model yielded by
the $\textsf{S}_{1}$-Initialize procedure (resp. $\textsf{D}_{1}$-Unlearning).

###  IV-B Correctness Properties

We define three correctness properties that should be satisfied by PoUL.

$\bullet$ _Target Model Correctness._ A currently predictive model
$\textsf{M}_{1}^{{}^{\prime}}$ yielding a prediction $p$ respective to a test
data $t$, is a correct target model $\textsf{M}_{1}$, if the statement
$p\leftarrow\textsf{G}(\textsf{M}_{1}^{{}^{\prime}},t)\wedge\textsf{M}_{1}^{{}^{\prime}}=\textsf{H}^{-1}(\textsf{M}_{1})\wedge\textsf{M}_{1}\leftarrow\textsf{F}(\textsf{M}_{0},D)$
is true, where $\textsf{G},\textsf{F}$ and $\textsf{M}_{0}$ are publicly
known.

$\bullet$ _Unlearning Correctness._ The unlearning process for deleting the
$d_{u}$ from the target model $\textsf{M}_{1}$ is correct, if
$\textsf{M}_{2}\leftarrow\textsf{F}(\textsf{M}_{1}\backslash[m_{u}],D\backslash
d_{u})$ is true, where $[m_{u}]$ included in $\textsf{M}_{1}$ is the part
exactly impacted by the $d_{u}$.

$\bullet$ _New Model Correctness._ A newly predictive model
$\textsf{M}_{2}^{{}^{\prime}}$ yielding a new prediction $p^{\prime}$ for a
new test data $t^{\prime}$, is a correct new model with respect to the deleted
$d_{u}$, if the statement $p^{\prime}\leftarrow
G(\textsf{M}_{2}^{{}^{\prime}},t^{\prime})\wedge\textsf{M}_{2}^{{}^{\prime}}=\textsf{H}^{-1}(\textsf{M}_{2})$
is true.

Specifically, in the setup phase, we require guaranteeing the target model
correctness, such that the server cannot fake a target model that never learns
the data owner’s data, and claim unlearning from it in the later deletion
phase. In the deletion phase, unlearning correctness and new model correctness
should be ensured, such that the server cannot execute an incorrect unlearning
process, and cannot fork an arbitrary model for subsequent predictions while
claiming the fulfillment of unlearning. If the above correctness properties
are satisfied, the data owner can be convinced that his/her deletion request
is truly addressed by the server.

###  IV-C Practicality Goals

$\bullet$ _Generic Model Supports._ Data deletion requests can occur in
generic ML model scenarios, as previous unlearning approaches [14] supported.
The definition of PoUL should cover generic ML models.

$\bullet$ _Limited Invasiveness._ We desire that proof generation has little
modification effect on the underlying learning and unlearning pipelines, and
should not compromise model accuracy222Our paper considers single data
deletion, which generally makes no obvious effect on model accuracy [79].

$\bullet$ _Minimal Overhead._ Proof generation should not incur additional
unaffordable overhead to the already intensive workloads.

$\bullet$ _Concise Proof._ Proof size should be short, compared to giving a
PoL document on training trajectory [45].

$\bullet$ _Efficient Verification._ Verification cost is expected to be small
and constant, faster than re-executing and validating partial training
trajectory as [45].

##  V Our Designs

We present our SGX-protected designs for the PoUL on top of the SISA
unlearning framework, with a partition of an authentication layer and a
proving layer. We mainly place the large authenticated storage with simple
operation logic outside the enclave, and preserve complex provable execution
logic but minimal storage costs in the enclave. This section begins with two
challenges of implementing PoUL, considering the server equipped with an SGX
enclave. In Section V-B, we customize data structures for authenticating
learning data and intermediate submodels. In Section V-C, we integrate the
customized data structures with a proof protocol for realizing PoUL.

###  V-A Challenges and Solutions

Although Intel SGX provides the integrity property that is important to our
scenario problem, its inherent limitations make us encounter challenges in
order to efficiently implement PoUL. We next introduce two main challenges,
with respect to the authentication layer and the proving layer we need.

(1) _Authentication layer : How to efficiently track the lineage from
authenticated learning data to learned intermediate submodels while supporting
authenticated deletion?_

It is challenging due to the incompatibility of memory-constrained SGX enclave
and memory-intensive workloads. Combining with the SISA training process in
Section II-A, one possibility of implementing the authentication layer is to
move data and submodels outside the enclave (_e.g._ , persistent memory or
disks), and meanwhile, adopt appropriate compact ADS to authenticate them as
well as keep the lineage from the data to the corresponding submodels. In
particular, we may leverage two same-size Merkle hash trees (MHTs) to
separately package data and the corresponding intermediate submodels, aligning
with sliced indices in SISA. Their lineage is preserved, by making the
location of a data slice in one MHT consistent with that of the _earliest_
intermediate submodel influenced by the data slice within another MHT. Lastly,
the two entire MHTs reside out of the enclave and their constant-size roots
are stored in the enclave for integrity check. Such adoption, however, is not
efficient, in light of the costs to update the two MHTs at worst-case
unlearning of SISA. That is, ($\textsf{op}_{1}$) deleting a data piece from
the first data slice of a shard, and simultaneously, ($\textsf{op}_{2}$)
updating a sequential of submodels affected by the data piece. We suppose
$n_{d}$ and $n_{m}$ leaves in the two MHTs. Then, $\textsf{op}_{1}$ consumes
$n_{d}\times\text{log}~{}n_{d}+\text{log}~{}n_{d}$ hash evaluations for
checking the integrity of $n_{d}$ data slices and updating the first data
slice. $\textsf{op}_{2}$ needs $2\times n_{m}\times\text{log}~{}n_{m}$ hash
evaluations for integrity check and update on the $n_{m}$ submodels. To assure
correctness, both $\textsf{op}_{1}$ and $\textsf{op}_{2}$ also need to be
operated in the secure enclave, and thus unfortunately it is not cost-
efficient.

_Solution._ We reconsider that the necessity of adopting the above ADS is
aimed to track the data lineage correlated with the intermediate submodels
while supporting dynamic updates. To relieve the strict configuration on the
ADS and avoid tree traversals, we let the enclave itself achieve the data
lineage tracking with correctness guarantees, by designing highly memory-
efficient data structures (_i.e._ , compact index list and filter) and cheap
pointers interlinking data slices with correlated submodels out of the
enclave. Besides, data and submodels are authentically saved outside the
enclave, and are protected against potential integrity attacks, with our
strategical data structure designs in the enclave.

(2) _Proving layer : How to enable efficient verifiability on the correctness
of predictive models and incremental learning which involve stateful
computations, using previously authenticated submodels and learning data?_

This challenge is caused by the conflict between our essential requirements on
attesting stateful computations, _e.g._ , multiple incremental learning
processes, and the SGX’s protection primarily on stateless in-memory
computations, which cannot allow a low and constant verification cost. To be
specific, we require the enclave to execute each incremental learning process,
taking as input a most recent submodel and newly incremental learning data,
and finally yield a new submodel. A verifier then can assert the correctness
of the new submodel by verifying a signature. Due to the incremental nature,
the verifier who asserts the correctness of a predictive model (_i.e._ , the
final submodel) needs to assert that all submodels learned prior to this final
submodel are correct. For example, when the data owner wants to verify if a
newly predictive model is not trained on her data piece originally falling in
the most beginning data slice, she needs to verify the correctness starting
from the most beginning submodel till the final one. Such verification
overhead linearly depends on the number of submodels affected by the data
slice.

_Solution._ We enable a constant verification cost by letting the verifier
only assert the correctness of the final submodel, but it in turn requires
extending the SGX’s protection to stateful computations. Therefore, we
consider a self-verification method. That is, before verifying the final
model, the authenticity of all prior submodels is verified by the enclave
itself, by securely retaining unique randomnesses (named seed) respective to
each submodel. To further assert the correctness of subsequent predictions, we
additionally introduce a trusted enclave, serving as an _auditing enclave_.
The auditing enclave is responsible to send challenges to the previous enclave
for execution, checkpoint the attestation proofs with regard to prediction
correctness, and verify the proofs. Once the auditing enclave catches an
incorrect execution, it can generate an alert report, along with an
attestation proof. Resorting to the auditing enclave, the data owner only
needs to verify the auditing enclave’s attestation proof to determine whether
subsequent predictions are offered by a correct model. It is also noteworthy
that the introduction of the auditing enclave can support third-party
auditing.

###  V-B Designing Data Structures for Authentication Layer

Figure 3: Overview of integrating four data structures.

To overcome the first challenge, we customize data structures inside and
outside the enclave for our logical authentication layer, as Fig. 3 shown. We
specifically adopt highly memory-efficient index list and cuckoo filter in the
enclave, and use cheap pointers to interlink data slices with correlated
submodels out of the enclave. With the data structures, we are aimed to (_a_)
authentically store learning data and submodels out of the enclave, (_b_)
efficiently track the lineage from data slices to learned submodels, (_c_)
support fast deletion and update on the submodels upon receiving a request of
deleting a data point, while maintaining the traceable lineage.

Data Structures There are two out-enclave structures and two compact in-
enclave data structures.

$\bullet$ data_store: a list for storing sliced learning data and the
integrity MACs. Its basic unit is respective to a single data point. We note
that multiple disjoint data points compose one data slice, as the form of a
rounded rectangle in Fig. 3.

$\bullet$ model_link: a linked list for storing submodels and the integrity
MACs. Its basic unit is for one submodel which is learned over the learning
data added with one new data slice. The linkability between two neighboring
submodels is enforced by the key_list introduced later.

$\bullet$ key_list: a list for storing the keys respective to each data point.
Its purpose is to efficiently fetch data and submodels and let data slices and
submodels store in a correct order outside the enclave.

$\bullet$ filter: a succinct structure for packaging data points while
supporting deletion and membership query. It is operated in the enclave at the
very beginning to authenticate data. It supports fast deletion on a data
point, and tells a learning program that this data point is not allowed to be
used.

Detailed Field Description We now correspondingly describe concrete fields of
the filter, key_list, data_store and model_link. We note that each data point
is represented as a form of $<$kid, data$>$, where kid is an identifier of the
data with a consensual hash function, _e.g._ , non-cryptographic xxHash
function.

filter: it is a stateful cuckoo filter residing within the enclave, filled
with the fingerprints of the data points. The fingerprints are generated as
the form of $\textsf{Enc}(\textsf{kid}||\textsf{data}||\textsf{eid})$, where
Enc can be a lightweight encryption algorithm used by [65], and eid is the
identity of an initialized enclave. The fingerprints can further be truncated
by selecting optimized parameters. For example, we use $8$ bits per data point
for the Purchase dataset. When a request of deleting a data point is raised,
the data fingerprint is removed from the cuckoo filter. Moreover, the filter
helps the enclave in checking if a loaded data point is matched with the
respective kid, besides checking its MAC.

key_list: it maintains a list (or skip list) of keys about the data points,
where each key entry has five fields as following. (1) kid serves as the data
index. The orders of the indices enable us to determine the orders of storing
and restoring data points (and data slices) plus submodels out of the enclave,
and fast fetch them into the enclave in learning and unlearning via pointers.
We can see two pointer fields *data and *model later. (2) tag is a binary
field for indicating whether the data point is inserted into or deleted from
the cuckoo filter. With the tag, we can avoid repeatedly querying and
inserting data points in the filter from scratch, especially in case of
deleting a data point from one data slice and relearning over the remaining
data. More importantly, we can use the tag to mitigate _false positives_
caused by the existence of certain data point that just shares the same
fingerprint with the deleted data point, when looking up the deleted data
point later. (3) *data is used to find the corresponding data point. (4)
*model is used to connect a data slice with the corresponding submodel which
is just trained over the training data that just recently adds this data
slice. Note that one data slice can contain multiple data points, and we let
its last data point’s key be responsible for linking the corresponding
submodel. (5) seed is prepared for storing the submodels with freshness
guarantees. This seed is generated when a new submodel is built within the
enclave, which is filled with a unique and unpredictable randomness. We assign
the fresh seed to the key of the last data point within a data slice for ease
of retrieval, resorting to the fact that the key is responsible for linking
with the submodel we describe before.

data_store and model_link: each entry of the data_store stores a data point
and its MAC dmac, and similarly, each entry of the model_link stores a
submodel and the integrity MAC m_s_mac. We can check a data point’s integrity
by verifying its MAC and then querying filter with
$\textsf{Enc}(\textsf{kid}||\textsf{data}||\textsf{eid})$. When resorting a
submodel, we check the integrity by retrieving the respective seed and
rebuilding its MAC m_s_mac, so as to verify the authenticity of the submodel.
We note that the submodels and the integrity MACs can be stored in disks or
persistent memory, while during learning certain submodel, its previous
submodel can reside in DRAM memories.

Mitigating Integrity Violation Attacks We consider potential threats violating
the integrity of out-enclave data and submodels. We include the enclave
identity within each fingerprint to protect against _forking attacks_ , so as
to prevent the server from scheduling multiple enclave instances to conduct
the same unlearning task. We also use the in-enclave filter to protect each
data point against _replacing attacks_ , _e.g._ , replacing a data point with
one not matching a particular kid. As for model checkpoints, we generate
trustful and fresh seeds respective to each newly generated submodel, and
associate the in-enclave seeds to their integrity MACs. With the enforcement,
_relocation attacks_ and _rollback attacks_ , _e.g._ , using a valid submodel
from a different or stale address to replace the real stored one, are
mitigated.

###  V-C Designs on Proving Layer

We are ready to implement the proving layer, by integrating the previous data
structures with SGX enclaves to address the second challenge. We start by
using the data structures to make the data and submodels operate in an
authenticated manner, and meanwhile, scheduling an execution enclave to
enforce the correctness of the learning and prediction computations associated
with the data and submodels. It enables a data owner to assert the correctness
of the associated computations on deleting a specific data point, by
challenging a newly predictive model and verifying attestation proofs. Later,
we introduce an auditing enclave to monitor the subsequent correctness of
prediction services, aiming to relieve the data owner’s verification cost.

The $\textsf{Prot}_{\text{SGX}}^{\text{PUL}}$ protocol Enclave initialization:
1.
Init($1^{k}$)$\rightarrow(\textsf{eid},\textsf{pk}_{\text{sgx}},\textsf{sk}_{\text{sgx}})$
and publicize $\textsf{pk}_{\text{sgx}}$ 2. install the programs
$\textsf{prog}_{k}$, $\textsf{prog}_{c}$, $\textsf{prog}_{t}$ and
$\textsf{prog}_{p}$ Server: 3. On input (‘commit’, $sid$, eid, msg, $d$):
//$sid$ is the session identifier 4. generate the key of $d$ as kid via
$\textsf{prog}_{k}$ 5. if msg=’add’: //$\textsf{S}_{1}$-Initialize procedure
in Setup Phase 6. link the kid with $d$ in data_store 7. insert $d$ into the
cuckoo filter $c$, and set $\textsf{tag}=1$ 8. if msg=’del’:
//$\textsf{D}_{1}$-Initialize procedure in Deletion Phase 9. unlink the kid
with $d$ 10. delete model linked with kid and the follow-up models 11. delete
the seeds of the keys behind the kid in key_list 12. delete $d$ from cuckoo
filter $c$ and set $\textsf{tag}=0$ 13.
$\sigma_{d}:=\Sigma.\textsf{Sign}(\textsf{sk}_{\text{sgx}},(c,\textsf{prog}_{c},\textsf{prog}_{k}))$
14. send (‘receipt’, $sid$, eid, $\sigma_{d}$, $c$) to a verifier 15. On input
(‘prove’, $sid$, eid, $c$)://proving learning on committed data 16. fetch
bathes of data, and check data integrity with MACs and filter 17. restore and
check the integrity of the previous model model’ or halt 18. let
model:=$\textsf{prog}_{t}(\textsf{model'},\textsf{data})$ 19. generate a
random seed using the current state, and assign it to kid’s seed 20. generate
$h_{\textsf{model}}=\textsf{H}(\textsf{model}||\textsf{seed})$, and assign it
to m_s_mac 21. store the model and $h_{\textsf{model}}$ outside the enclave
22. let the kid’s *model link to the storage location 23.
$\sigma_{m}:=\Sigma.\textsf{Sign}(\textsf{sk}_{\text{sgx}},(c,h_{\textsf{model}},\textsf{prog}_{t}))$
24. send (‘proof’, $sid$, eid, $\sigma_{m}$, $c$, $h_{\textsf{model}}$) to a
verifier 25. On input (‘prove’, $sid$, eid, $t$,
$h_{\textsf{model}}$)://proving prediction on committed model 26. find model
linked with the kid respective to the last data point 27. check if model
matches the $h_{\textsf{model}}$ 28. let
$p$:=$\textsf{prog}_{p}(\textsf{model},t)$//one test data for simplicity 29.
$\sigma_{p}:=\Sigma.\textsf{Sign}(\textsf{sk}_{\text{sgx}},(p,t,h_{\textsf{model}},\textsf{prog}_{p}))$
30. send (‘proof’, $sid$, eid, $\sigma_{p}$, $p$, $t$) to a verifier Verifier:
//$\textsf{S}_{4}$-Verify and $\textsf{D}_{4}$-Verify procedures 31. On
receive (‘receipt’, $sid$, eid, $\sigma_{d},c$) from the server: 32. assert
$\Sigma.{\textsf{Verify}}(\textsf{pk}_{\text{sgx}},\sigma_{d},c,\textsf{prog}_{c},\textsf{prog}_{k})$
33. On receive (‘proof’, $sid$, eid, $\sigma_{m},c,h_{\textsf{model}}$) from
the server: 34. assert
$\Sigma.{\textsf{Verify}}(\textsf{pk}_{\text{sgx}},\sigma_{m},c,h_{\textsf{model}},\textsf{prog}_{t})$
35. On receive (‘proof’, $sid$, eid, $\sigma_{p},p,t$) from the server: 36.
assert
$\Sigma.{\textsf{Verify}}(\textsf{pk}_{\text{sgx}},\sigma_{p},p,t,h_{\textsf{model}},\textsf{prog}_{p})$

Figure 4: The $\textsf{Prot}_{\text{SGX}}^{\text{PUL}}$ protocol.

The $\textsf{Prot}_{\text{SGX}}^{\text{PUL}}$ Protocol From a commit-and-prove
perspective, we leverage an enclave to ensure that learning processes are fed
with the learning data consistent with pre-committed data as a form of in-
enclave filter. Similarly, we enforce that the later prediction process uses a
newly yielded submodel matching the lastly committed submodel in model_link.
Next, in Fig. 4, we elaborate the protocol based on Tramèr _et al._ ’s
“commit-and-prove” functionality [76], which involves both the learning and
prediction processes, deducing an implementation for our PoUL defined in
Section IV.

To start with, the enclave initializes a pair of public verification key and
signing key $(\textsf{pk}_{\text{sgx}},\textsf{sk}_{\text{sgx}})$, and
installs the public and correct programs, including $\textsf{prog}_{k}$,
$\textsf{prog}_{c}$, $\textsf{prog}_{t}$ and $\textsf{prog}_{p}$. We note that
$\textsf{prog}_{k}$ specifies how to store the keys of the incrementally
feeding data in key_list. $\textsf{prog}_{c}$ defines how to insert the
feeding data into a cuckoo filter $c$. $\textsf{prog}_{t}$ specifies how to
incrementally train intermediate model checkpoints while $\textsf{prog}_{p}$
defines a model prediction process on given test data. We also note that the
data points in the data_store are fed into the enclave in an incremental
manner.

_(1) Setup Phase._ With a collection of data points $D$, the server packs the
data into a filter $c$ and build a key list, as shown in line 3-7. After that,
the data points are unloaded to release the in-enclave memory. For executing a
learning process (see line 15-24), $\textsf{prog}_{t}$ can appoint batches of
data via their keys, and fetch them into the enclave with integrity checking.
The yielded submodels are stored orderly with integrity and freshness
guarantees in model_link, and the last one will be a predictive model, say
$h_{\text{model}}$. Later, the data owner can enjoy the model prediction by
offering test data, refer to line 25-30.

_(2) Deletion Phase_. Upon deleting one data point $d_{u}\in D$, the enclave
executes the deletion operations on the filter to delete the data point, and
meanwhile, invalidates the affected submodels, as demonstrated in line 8-14.
Later, a sequential of new submodels are relearned on the remaining data by
executing the steps in line 15-24, and the last submodel is queried by new
test data. The execution processes are similar to that in the setup phase,
with the main difference that the new model $h_{\textsf{model}}^{{}^{\prime}}$
does not use the data point $d_{u}$.

Verifying Correctness Properties With the
$\textsf{Prot}_{\text{SGX}}^{\text{PUL}}$ protocol, the data owner can assert
whether the server offers a fake target model, or executes an incorrect
unlearning process, or uses an incorrect unlearned model for new predictions,
with respect to the deletion on $d_{u}\in D$. The correctness properties are
verified based on some necessary assumptions: the SGX enclave guarantees
integrity and partial confidentiality (_i.e._ , sealing randomness and secret
keys); the associated signature scheme $\Sigma$ satisfies unforgeable under
chosen message attacks (EU-CMA) security; the hash functions used for
generating the enclave identity and integrity MACs are collision-resistant;
lastly, all programs running inside the enclave are bug-free.

_(1) Verifying target model correctness._ The data owner can verify that the
predictive model is indeed the incrementally learned model $h_{\text{model}}$
over the data $D$, with the following three steps. _First_ , the data owner
can verify the authenticity of the filter $c$ and the key list, namely,
correctly packing her data, by asserting the validity of $\sigma_{d}$ and
querying the data point membership $d_{u}$ with the filter, see line 32.
_Second_ , the data owner can assert that the last submodel $h_{\text{model}}$
is incrementally learned over the data existing in the filter $c$, on the
promise of the validity of $\sigma_{d}$, the integrity of on-the-fly batches
of data and the previous submodels, and the confidentiality of randomly
generated seed. This step relies on the attestation proof $\sigma_{m}$ and be
verified in line 34. _Finally_ , the data owner asserts that the predictive
model is the above submodel $h_{\text{model}}$, by verifying $\sigma_{p}$ in
line 36.

_(2) Verifying unlearning correctness._ The data owner firstly can verify the
validity of a new attestation proof $\sigma_{d}^{{}^{\prime}}$ on the updated
filter and key list after the deletion operations. Particularly, the deletion
operations on the key list are two-fold: for the $d_{u}$’s key entry, the
changes include tag$=0$, *data unlinked to $d_{u}$, *model unlinked to the
affected submodel, and seed$=$NULL; for other key entries after the $d_{u}$’s
key entry in the key_list, the *model fields are unlinked to the submodels,
and the seed fields are set null. Next, all affected submodels are relearned
on the remaining data until the last submodel $h_{\text{model}}^{{}^{\prime}}$
is obtained, which is enforced by the updated filter and the key_list. The
data owner secondly verifies that the new last submodel
$h_{\text{model}}^{{}^{\prime}}$ is incrementally relearned over the data
exactly excluding $d_{u}$, by asserting the corresponding signature-based
proof $\sigma_{m}^{{}^{\prime}}$ against the updated filter $c^{{}^{\prime}}$.
Note that the correctness of all affected submodels prior to
$h_{\text{model}}^{{}^{\prime}}$ are enforced and verified by the enclave
itself, with help of our authentication layer.

_(3) Verifying new model correctness._ With the last submodel
$h_{\text{model}}^{{}^{\prime}}$ which is newly generated, the data owner can
determine whether it is used for prediction on her given test data, by
verifying the new signature $\sigma_{p}^{{}^{\prime}}$ on given new test data
$t^{{}^{\prime}}$ and $h_{\text{model}}^{{}^{\prime}}$.

Introducing an Auditing Enclave We introduce an additional enclave as a
trusted auditor to monitor the correctness of the execution enclave and offer
the evidences of incorrect execution for post verification. It derives from
our considerations that making the data owner always assert the correctness of
each prediction is impractical. Besides, the previous designs might not be
scalable to support third-party regulators to audit unlearning, if they have
no access to the data owners’ data. We note that the auditing enclave can work
in a centralized or decentralized manner, inspired by Paccagnella _et al._ ’s
work [56].

The auditing enclave can be setup on the server’s machine and configured with
auditing programs, after the interactions between the data owner and the
server. The auditing programs define the auditing logic, including (1) reading
the inputs and outputs of ECALL functions invoked by the execution enclave,
(2) interacting with Intel’s verification server, (3) logging the verification
results, and (4) generating reports in the case of verification failure. At
the beginning, the auditing enclave can run a key exchange protocol with the
execution enclave, so as to build a secure communication channel [10]. The
auditing enclave then is stably scheduled when using models for predictions.
Specifically, upon receiving a data owner’s test challenge, the auditing
enclave can also load the test data due to the defined logic (1), and then
monitor the execution of another execution enclave, and lastly assert whether
the final prediction output is yielded by the model as expected, according to
the logic (2). From the view of the data owner (and third-party regulators)
can retrieve the verification reports returned by the auditing enclave,
resorting to the logging history in logic (3) and (4).

##  VI Implementation and Evaluation

We implement our SGX-capable PoUL instantiation with the logically
authentication layer and proving layer. Based on the implementation, our
evaluation answers the questions as follows: ($\textsf{Q}_{1}$) how is the
additional storage cost for PoUL, standing on the already storage workloads of
the SISA framework? ($\textsf{Q}_{2}$) how does our authentication layer
perform, compared against an MHT-based implementation? ($\textsf{Q}_{3}$) how
are the learning/unlearning time complexity and trained accuracy in the SGX-
capable PoUL?

###  VI-A Implementation and Setup

We begin with the implementation idea of the SISA framework, and run the
training process over a single shard of data in an SGX enclave. We omit other
shards’ training processes, since they can be securely executed in the same
manner, and thus we measure prediction accuracy of a single-shard model.

SGX enclave. We install SGX SDK of version Linux 2.16 to initialize the SGX
enclave environment. We also utilize the Intel’s SGX DNNL Library with version
1.1.1 to bootstrap our training tasks. All codes are run in hardware mode.

In-enclave programs. As we described in Section V-C, the programs are
implemented in C++ majorly including (1) $\textsf{prog}_{c}$ for building a
cuckoo filter by using Fan _et al._ ’s public
library333https://github.com/efficient/cuckoofilter, (2) $\textsf{prog}_{k}$
for generating a list for data keys, (3) $\textsf{prog}_{t}$ for implementing
learning and unlearning a specific model guided by the SISA framework
444https://github.com/cleverhans-lab/machine-unlearning, and (4)
$\textsf{prog}_{p}$ for implementing a specific prediction process by
restoring a newly trained model via $\textsf{prog}_{t}$.

Model and dataset. Following the SISA framework’s open source library, we
adopt a model with two fully connected (FC) layers and re-implement it in C++.
Each FC layer is followed with an activation layer, and the output layer uses
one-hot encoding for two classes. The model is trained with a mini-batch
stochastic gradient descent (SGD) algorithm, and evaluated over the Purchase
[62] dataset. The Purchase dataset is divided into a training set with
$280367$ data points and a test set with $31152$ data points.

Setup configuration. We configure the setup information about training the
model on the Purchase dataset using the SISA framework. Concretely, we divide
the Purchase dataset into $5$ shards, and each shard contains $56073$ data
points. We then further slice one-shard data points with a range of slice size
in $\\{1,3,6,12\\}$ (see Appendix D). For a training case with a fixed slice
size, we adaptively select the training parameters, such as the batch size,
epoch number and learning rate, leading to a trained model with best accuracy.

Besides, our experiments are carried out on an Ubuntu 20.04 server equipped
with Intel@ Xeon(R) CPU E3-1505M v5 @ 2.80GHz $\times 8$ CPU and 14.6 GiB of
RAM.

###  VI-B Evaluation

TABLE I: Storage size of customized data structures. Dataset | filter | key_list | data_store | model_link
---|---|---|---|---
Purchase |  $192$ KB |  $2.85$ MB |  $133.17$ MB |  $1.81$ MB

Firstly, we measure the storage costs of our customized data structures, when
building the SISA training framework over the Purchase dataset. We select
appropriate parameters, such as the size of each item in the filter and the
size of each hidden layer in a model, which are the main impact factors for
the storage costs. On the Purchase dataset with $56073$ data points in one
shard, we let the filter have $2^{16}$ buckets and the fingerprint size of
each item be $12$ bits, such that the false positive rate (FPR) for membership
query is low enough, nearly $0.003$. As a result, the filter filled with the
one-shard data leads to $192$ KB, as presented in Table I. We can also lower
the fingerprint size till $8$ bits to obtain a smaller-size filter, but we
suffer from a higher FPR value, about $0.041$. Next, the key_list is in about
$2.85$ MB size, in which each entry needs $416$ bits. The last two storage
sizes are majorly dominated by the data scale (_i.e._ , $600$ nodes in the
input layer) and the number of nodes in the FC layer (_i.e._ , $128$ nodes),
on the case of using precision training with $32$-bit floating point numbers.
They are the storage workloads already needed by the SISA training. Therefore,
our authentication layer additionally incurs around $3.00$ MB storage
workloads for training on the Purchase dataset, answering the $\textsf{Q}_{1}$
question.

TABLE II: Performance comparison with an MHT (µs). Structures | Insertion | Query | Deletion
---|---|---|---
Cuckoo filter | 0.034 | 0.035 | 0.037
MHT | 6.300 | 12.600 | 12.600

Secondly, we make a further effort to evaluate the run-time performance of our
authenticated layer, compared to a baseline implementation based on an MHT. As
we introduced before, we setup a cuckoo filter inside the enclave for
authenticating one shard of data points and later authentically deleting data
points. Here, we compare the performance of insertion, query and deletion
operations with that of an MHT using the SHA-256 hash function, over the
Purchase dataset. For demonstrating a best-case comparison, we let the
fingerprint size be only $8$ bits. To the end, we deduce the time consumption
for inserting, querying and deleting one data point in average over the cuckoo
filter and MHT, as summarized in Table II. To respond to the $\textsf{Q}_{2}$
question, our implementation with respect to one data point can achieve about
$185$, $360$ and $340$ times time savings in insertion, query and deletion,
respectively.

Figure 5: Impact of unlearning one data point.

We are ready to evaluate the learning/unlearning time and accuracy in the SGX-
capable setting for answering the $\textsf{Q}_{3}$ question. On top of our
setup configuration with six sequential slices, we measure the unlearning time
respective to the positions of the deleted data point, _i.e._ , the slice it
falls in. We also evaluate the individual learning time of each slice before
unlearning for comparison. It is easy to observe from Fig. 5(a) that learning
time turns longer as the number of slices increases, due to that more data
need to be trained. As for unlearning, it consumes more time when the deleted
data point falls in the slice with smaller indices, since more impacted
submodels need to be retrained. During the training processes, we notice that
model checkpoint and restoring in such an SGX setting take negligible time,
compared to the learning/unlearning time, as shown in Fig. 5(b). Besides the
time consumption, we also compare the corresponding trained accuracy in Fig.
5(c). We use the trained accuracy $95.14\%$ before unlearning as a baseline
(shorten as BL in the figure). We discover from the results that the case of
single data point deletion may not influence the original trained accuracy,
which might be aligned with a recent study’s conclusion [79]. It is noteworthy
that due to the memory restriction of the SGX enclave, the trained accuracy
mentioned before is obtained by carefully tuning hyperparameters during the
SGD training. Fig. 6 demonstrates the improvement of trained accuracy when (a)
the batch size is fixed with $1000$ while the epoch number increases till
$22$; and (b) the epoch number is fixed with $20$ while the batch size
decreases to $1000$. As a result, we obtain the baseline accuracy in $95.14\%$
by training with $22$ epochs and a batch size of $1000$.

(a) Varying training epochs with fixed batch size

(b) Varying batch sizes with fixed epochs

Figure 6: Accuracy improvement via training parameter tuning.

##  VII Analysis of Related Work

###  VII-A Auditing Unlearning

Auditing unlearning implies that a data owner or third-party regulators can
examine if the revoked training data indeed do not exist in an unlearned model
residing on a server. That may relate to a long line of work in auditing the
integrity of remotely stored data [82, 81, 18], but the focuses here are
placed on the model derived from data. Existing methods [51, 40, 70, 31] to
audit unlearning essentially examine the existence or absence of _certain
fingerprint of deleted data_ left on an unlearned model, independent of
unlearning techniques. The fingerprint effect either merely relies on original
training data [51, 40], or is strengthened via backdoored triggers [70] and
recent watermarking and fingerprinting strategies [31]. The examination is
generally performed by means of black-box querying [51, 40, 70], aligned with
the MLaaS paradigm that offers black-box APIs to users for querying server-
side models. Although the SISA unlearning method can also be audited by
letting an auditor re-execute the unlearning process with the submodel
checkpoints and the corresponding dataset, the auditing manner cannot protect
the intellectual property of the submodels, and may not support efficient
verification as mentioned in Section IV-C.

Different from prior efforts, our work opens a new auditing perspective, in
light of a dishonest server who can conduct forging and forking attacks. For
example, the server can forge a model which has an indistinguishable model
distribution with that of the target model in question (consider deep neural
network models), but the model is never trained on requested data that will be
deleted [73, 67]. Then, the server forks the target model in question using
the forging model, by resorting to the black-box service manner, and claim
having deleted data from the forging model while still offering prediction
services with the target model. In such case, neither previous verification
metrics via comparing model distribution, nor the above auditing methods via
probing fingerprint, can faithfully tell if the requested data is indeed
deleted.

###  VII-B TEEs-based Verifiable ML

In outsourced ML scenarios, TEEs become a practical tool to enforce
computation correctness, either in the training process [54, 41, 42, 86, 88,
53, 39, 11] or the inference process [75, 48, 38, 74]. Our work departs from
prior implementations merely for inference, but closely relates to the arts,
namely [41, 86, 88, 39, 11] for implementing an integrity-protected training
(and prediction) pipeline. Among these arts, very few of them immediately
support authentically tracking, storing and updating the lineage of training
data in intermediate models, which are particularly required to realize our
PoUL.

_Comparison_ TrustFL [88] and Plinius [86] are potential to meet our
requirements, but they are still not satisfactory. TrustFL is a TEE+GPUs
solution for integrity-preserving federated learning, with the main ideas
including (1) individual participants conduct all training iterations on a GPU
processor and authentically stores all training intermediate models in
alignment with authenticated batches of data; (2) a co-located TEE verifier
can randomly re-execute several successive iterations of training for
correctness checking after training. To authentically store models outside the
TEE, it adopts an MHT by packing each intermediate model as a leaf, while
preserving the tree root inside the enclave for verification (suppose $n$
leaves in the tree). When the TEE restores an intermediate model, it needs to
compute $O(\text{log}~{}n)$ hashes along the path from the leaf with respect
to this intermediate model to the root, so as to verify the integrity. Such
design is not suitable to realize the PoUL, since we require updating a large
number of intermediate models upon receiving a single deletion request, which
needs verifying their hashes and computing new hashes in the memory-limited
TEE. As for Plinius [86], it focuses on storing models in the processor-
accessible persistent memory (PM) colocated with a TEE. The authors study how
to efficiently copy model checkpoints from the secondary storage to the
persistent memory, with the eventual aim of making the TEE fast restore the
model checkpoints. Although it does not demand designing efficient data
structures to store model checkpoints with dynamic deletion supports, the idea
of incorporating efficiently accessible PM is complementary to our work.

_Challenging issues of realizing PoUL by combining GPUs with TEEs_ To make our
TEEs-based PoUL instantiation salable to real-life deep neural networks, a
suggestive direction is to remove workloads from CPUs-embedded TEEs to GPUs,
as promoted by existing works on the training phase [53, 39, 88, 11]; Yet, it
is challenging and to be answered by more ongoing rigorous efforts with the
previous lessons. This line of works usually provides probabilistic
verification on the integrity of computations delegated to distrustful GPUs by
leveraging additional integrity-enhancing algorithms, either delegating all
training iterations, _e.g._ , TrustFL [88] and GINN [11] or solely partial
linear computations, _e.g._ , Goten [53] and DarKnight [39]. In addition to
integrity-enhancing algorithms, GINN also creatively uses gradient clipping to
defend against a fine-gained tampering attack on a single SGD-update step.
Despite the inspiring efforts, following their lessons to realize PoUL needs
more exploration, in order to guarantee integrity and practical performance
like accuracy, storage overhead and communication complexity caused by
frequent system calls. One big issue is simultaneously ensuring unlearning
accuracy and integrity, considering the following two lessons: First,
Freivalds’ algorithm for integrity checking [75, 53, 11] requires carefully
mapping the original floating-point numbers into fixed-point ones for
maintaining accuracy. Second, the adoption of gradient clipping demands
appropriately adjusting hyperparameters like clipping rate and learning rate
for retaining performance, as evaluated by GINN. Thus, combining GPUs with
TEEs for implementing PoUL requires exploring the answer to how the above
defences against integrity violation impact unlearning accuracy in the SISA
setting.

##  VIII Conclusion and Future Work

We respond to the need for auditing unlearning in light of the latest attacks
on unlearning. We define the new problem on Proof of Unlearning from the
perspective of VC, which is allowed to be realized using various VC
techniques. As an initial effort to push forward auditable unlearning, we
propose a native implementation based on Intel SGX. Standing on top of the
initial effort, we collate future work directions as following: (_i_) _Scaling
to specialized hardware accelerators._ We pursue more efficient auditing in
the TEEs setting empowered with specialized hardware accelerators, by
incorporating the available optimizing compilers or adapting to the
accelerators with the TEEs capability. (_ii_) _Enabling flexible deletion._ We
seek to explore auditing the compliance of deleting inappropriate sensitive
attributes, _e.g._ , race or gender, which can be included in a group of data
points, rather than individual data points. To support deleting the group of
data is necessary, as the ML fairness problems become increasingly noticeable
(_e.g._ , in face recognition system). (_iii_) _Protecting data content and
privacy._ To fully respect privacy regulations, auditing unlearning may should
stand on the privacy-preserving machine learning/unlearning pipeline, in which
data content and data privacy are protected. Towards this direction, extending
our SGX-capable PoUL to work jointly with data-oblivious implementations and
differential privacy mechanisms will be explored.

## References

  * [1] Guidance on the ai auditing framework (draft consultation).  https://ico.org.uk/about-the-ico/ico-and-stakeholder-consultations/ico-consultation-on-the-draft-ai-auditing-framework-guidance-for-organisations/, Last access on 2020-02-19.
  * [2] Microsoft azure machine learning (azure ml).  https://studio.azureml.net.
  * [3] Intel(r) software guard extensions (intel sgx).  https://software.intel.com/sites/default/files/332680-002.pdf, 2015\.
  * [4] California consumer privacy act (ccpa).  https://oag.ca.gov/privacy/ccpa, 2018.
  * [5] Facebook blames a bug for not deleting your deleted videos.  https://newyork.cbslocal.com/2018/04/03/facebook-deleted-videos-bug/, 2018\.
  * [6] 10th generation intel core processor families data sheet.  https://www.intel.com/content/dam/www/public/us/en/documents/datasheets/10th-gen-core-families-datasheet-vol-1-datasheet.pdf, 2020\.
  * [7] Tigist Abera, N Asokan, Lucas Davi, Jan-Erik Ekberg, Thomas Nyman, Andrew Paverd, Ahmad-Reza Sadeghi, and Gene Tsudik.  C-flat: control-flow attestation for embedded systems software.  In Proc. of ACM CCS, 2016.
  * [8] Alibaba.  Alibaba cloud.  https://www.alibabacloud.com/product/ebm.
  * [9] Tiago Alves and Don Felton.  Trustzone: Integrated hardware and software security.  In ARM white paper 3, volume 4, 2004.
  * [10] Ittai Anati, Shay Gueron, Simon Johnson, and Vincent Scarlata.  Innovative technology for cpu based attestation and sealing.  In Proc. of HASP, volume 13, 2013.
  * [11] Aref Asvadishirehjini, Murat Kantarcioglu, and Bradley Malin.  Ginn: Fast gpu-tee based integrity for neural network training.  In Proc. of ACM CODASPY, 2022.
  * [12] Dyslexic Atheist.  Instead of deleting account, new york times appends ‘1000’ to username and email address.  https://news.ycombinator.com/item?id=23005060, 2020.
  * [13] Dan Boneh, Benedikt Bünz, and Ben Fisch.  Batching techniques for accumulators with applications to iops and stateless blockchains.  In CRYPTO, 2019.
  * [14] Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot.  Machine unlearning.  In Proc. of IEEE S&P, 2021.
  * [15] Ernie Brickell and Jiangtao Li.  Enhanced privacy id from bilinear pairing for hardware authentication and attestation.  International Journal of Information Privacy, Security and Integrity 2, 1(1):3–33, 2011.
  * [16] Yinzhi Cao and Junfeng Yang.  Towards making systems forget with machine unlearning.  In Proc. of IEEE S&P, 2015.
  * [17] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song.  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In Proc. of USENIX Security, 2019.
  * [18] Bo Chen and Reza Curtmola.  Robust dynamic provable data possession.  In Proc. of IEEE ICDCSW, 2012.
  * [19] Chong Chen, Fei Sun, Min Zhang, and Bolin Ding.  Recommendation unlearning.  In Proc. of ACM WWW, 2022.
  * [20] Guoxing Chen, Sanchuan Chen, Yuan Xiao, Yinqian Zhang, Zhiqiang Lin, and Ten H Lai.  Sgxpectre: Stealing intel secrets from sgx enclaves via speculative execution.  In Proc. of EuroS&P, 2019.
  * [21] Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang.  When machine unlearning jeopardizes privacy.  In Proc. of ACM CCS, 2021.
  * [22] Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang.  Graph unlearning.  In Proc. of ACM CCS, 2022.
  * [23] Federal Trade Commission.  California company settles ftc allegations it deceived consumers about use of facial recognition in photo storage app, 2021.
  * [24] Victor Costan and Srinivas Devadas.  Intel sgx explained.  https://eprint.iacr.org/2016/086.pdf, 2016.
  * [25] Ghada Dessouky, Shaza Zeitouni, Thomas Nyman, Andrew Paverd, Lucas Davi, Patrick Koeberl, N Asokan, and Ahmad-Reza Sadeghi.  Lo-fat: Low-overhead control flow attestation in hardware.  In Proc. of DAC, 2017.
  * [26] Huayi Duan, Cong Wang, Xingliang Yuan, Yajin Zhou, Qian Wang, and Kui Ren.  Lightbox: Full-stack protected stateful middlebox at lightning speed.  In Proc. of ACM CCS, 2019.
  * [27] Bin Fan, Dave G Andersen, Michael Kaminsky, and Michael D Mitzenmacher.  Cuckoo filter: Practically better than bloom.  In Proc. of ACM CoNEXT, 2014.
  * [28] Conner Forrest.  Dropbox bug sends years-old deleted files back to user accounts.  https://www.techrepublic.com/article/dropbox-bug-sends-years-old-deleted-files\\\\-back-to-user-accounts/, 2017\.
  * [29] Ji Gao, Sanjam Garg, Mohammad Mahmoody, and Prashant Nalini Vasudevan.  Deletion inference, reconstruction, and compliance in machine (un) learning.  In Proc. of PETS, 2022.
  * [30] Mingyuan Gao, Hung Dang, and Ee-Chien Chang.  Teekap: Self-expiring data capsule using trusted execution environment.  In Proc. of IEEE ACSAC, pages 235–247, 2021.
  * [31] Xiangshan Gao, Xingjun Ma, Jingyi Wang, Youcheng Sun, Bo Li, Shouling Ji, Peng Cheng, and Jiming Chen.  Verifi: Towards verifiable federated unlearning.  https://arxiv.org/abs/2205.12709v1, 2022.
  * [32] Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou.  Making ai forget you: Data deletion in machine learning.  In Proc. of NIPS, 2019.
  * [33] Aditya Golatkar, Alessandro Achille, et al.  Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations.  In Proc. of ECCV, 2020.
  * [34] Aditya Golatkar, Alessandro Achille, and Stefano Soatto.  Eternal sunshine of the spotless net: Selective forgetting in deep networks.  In Proc. of IEEE/CVF CVPR, 2020.
  * [35] Samuel Greengard.  Can ai learn to forget?  Communications of the ACM, 65(4):9–11, 2022.
  * [36] Jens Groth.  Short pairing-based non-interactive zero-knowledge arguments.  In ASIACRYPT, 2010.
  * [37] Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Chris Waites.  Adaptive machine unlearning.  In Proc. of NIPS, 2021.
  * [38] Lucjan Hanzlik, Yang Zhang, et al.  Mlcapsule: Guarded offline deployment of machine learning as a service.  In Proc. of IEEE/CVF CVPR, 2021.
  * [39] Hanieh Hashemi, Yongqin Wang, and Murali Annavaram.  Darknight: An accelerated framework for privacy and integrity preserving deep learning using trusted hardware.  In Proc. of IEEE/ACM MICRO, 2021.
  * [40] Yangsibo Huang, Xiaoxiao Li, and Kai Li.  Ema: Auditing data removal from trained models.  In Proc. of MICCAI, 2021.
  * [41] Tyler Hunt, Congzheng Song, Reza Shokri, et al.  Chiron: Privacy-preserving machine learning as a service.  https://arxiv.org/abs/1803.05961, 2018.
  * [42] Nick Hynes, Raymond Cheng, and Dawn Song.  Efficient deep learning on multi-source private data.  https://arxiv.org/pdf/1807.06689, 2018.
  * [43] IBM.  Ibm cloud data shield.  https://www.ibm.com/cloud/data-shield.
  * [44] Yeongjin Jang, Jaehyuk Lee, Sangho Lee, and Taesoo Kim.  Sgx-bomb: Locking down the processor via rowhammer attack.  In Proc. of SysTEX, 2017.
  * [45] Hengrui Jia, Mohammad Yaghini, Christopher A Choquette-Choo, Natalie Dullerud, Anvith Thudi, Varun Chandrasekaran, and Nicolas Papernot.  Proof-of-learning: Definitions and practice.  In Proc. of IEEE S&P, 2021.
  * [46] Nicole Karlis.  You just deleted facebook. can you trust facebook to delete your data?  https://www.salon.com/2019/02/10/you-just-deleted-facebook-can-you-trust-facebook-to-delete-your-data/.
  * [47] Do Le Quoc, Franz Gregor, Jatinder Singh, and Christof Fetzer.  Sgx-pyspark: Secure distributed data analytics.  In Proc. of ACM WWW, 2019.
  * [48] Taegyeong Lee, Zhiqi Lin, et al.  Occlumency: Privacy-preserving remote deep-learning inference using sgx.  In Proc. of ACM MobiCom, 2019.
  * [49] Jiangtao Li, Ninghui Li, and Rui Xue.  Universal accumulators with efficient nonmembership proofs.  In Proc. of ACNS, 2007.
  * [50] Zheng Li and Yang Zhang.  Membership leakage in label-only exposures.  In Proc. of ACM CCS, 2021.
  * [51] Xiao Liu and Sotirios A Tsaftaris.  Have you forgotten? a method to assess if machine learning models have forgotten data.  In Proc. of MICCAI, 2020.
  * [52] Yi Liu, Lei Xu, Xingliang Yuan, Cong Wang, and Bo Li.  The right to be forgotten in federated learning: An efficient realization with rapid retraining.  In Proc. of IEEE INFOCOM, 2022.
  * [53] Lucien KL Ng, Sherman SM Chow, et al.  Goten: Gpu-outsourcing trusted execution of neural network training.  In Proc. of AAAI, 2021.
  * [54] Olga Ohrimenko, Felix Schuster, Cédric Fournet, Aastha Mehta, Sebastian Nowozin, Kapil Vaswani, and Manuel Costa.  Oblivious $\\{$Multi-Party$\\}$ machine learning on trusted processors.  In Proc. of USENIX Security, 2016.
  * [55] Kaan Onarlioglu, William Robertson, and Engin Kirda.  Eraser: Your data won’t be back.  In Proc. of IEEE EuroS&P, 2018.
  * [56] Riccardo Paccagnella, Pubali Datta, Wajih Ul Hassan, Adam Bates, Christopher Fletcher, Andrew Miller, and Dave Tian.  Custos: Practical tamper-evident auditing of operating systems using trusted execution.  In Proc. of NDSS, 2020.
  * [57] Rasmus Pagh and Flemming Friche Rodler.  Cuckoo hashing.  Journal of Algorithms, 51(2):122–144, 2004.
  * [58] Rafael Pass, Elaine Shi, and Florian Tramèr.  Formal abstractions for attested execution secure processors.  In EUROCRYPT, 2017.
  * [59] Joel Reardon, David Basin, and Srdjan Capkun.  Sok: Secure data deletion.  In Proc. of IEEE S&P, 2013.
  * [60] G. D. P. Regulation.  Regulation (eu) 2016/679 of the european parliament and of the council of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing directive 95/46.  Official Journal of the European Union, 59(1-88):294, 2016.
  * [61] Mark Russinovich, Manuel Costa, Cédric Fournet, David Chisnall, Antoine Delignat-Lavaud, Sylvan Clebsch, Kapil Vaswani, and Vikas Bhatia.  Toward confidential cloud computing.  Communications of the ACM, 64(6):54–61, 2021.
  * [62] C Okan Sakar, S Olcay Polat, Mete Katircioglu, and Yomi Kastro.  Real-time prediction of online shoppers’ purchasing intention using multilayer perceptron and lstm recurrent neural networks.  Neural Computing and Applications, 31(10):6893–6908, 2019.
  * [63] Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh.  Remember what you want to forget: Algorithms for machine unlearning.  In Proc. of NIPS, 2021.
  * [64] Srinath Setty.  Spartan: Efficient and general-purpose zksnarks without trusted setup.  In CRYPTO, 2020.
  * [65] Omais Shafi and Janibul Bashir.  Secsched: Flexible scheduling in secure processors.  In Proc. of ACM PACT, 2020.
  * [66] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models.  In Proc. of IEEE S&P, 2017.
  * [67] Ilia Shumailov, Zakhar Shumaylov, Dmitry Kazhdan, Yiren Zhao, Nicolas Papernot, Murat A Erdogdu, and Ross Anderson.  Manipulating sgd with data ordering attacks.  In Proc. of NIPS, 2021.
  * [68] Jatinder Singh, Jennifer Cobbe, Do Le Quoc, and Zahra Tarkhani.  Enclaves in the clouds.  Communications of the ACM, 64(5):42–51, 2021.
  * [69] Manya Sleeper, Justin Cranshaw, Patrick Gage Kelley, Blase Ur, Alessandro Acquisti, Lorrie Faith Cranor, and Norman Sadeh.  ” i read my twitter the next morning and was astonished” a conversational perspective on twitter regrets.  In Proc. of ACM SIGCHI, 2013.
  * [70] David Marco Sommer, Liwei Song, et al.  Towards probabilistic verification of machine unlearning.  https://arxiv.org/abs/2003.04247, 2020.
  * [71] Roberto Tamassia.  Authenticated data structures.  In Proc. of ESA, 2003.
  * [72] Daniel Terdiman.  Why deleting personal information on the internet is a fool’s errand.  https://www.fastcompany.com/3048871/why-deleting-personal-information-on-the-internet-is-a-fools-errand.
  * [73] Anvith Thudi, Hengrui Jia, Ilia Shumailov, and Nicolas Papernot.  On the necessity of auditable algorithmic definitions for machine unlearning.  In Proc. of USENIX Security, 2022.
  * [74] Shruti Tople, Karan Grover, Shweta Shinde, Ranjita Bhagwan, and Ramachandran Ramjee.  Privado: Practical and secure dnn inference.  https://arxiv.org/abs/1810.00602, 2018.
  * [75] Florian Tramèr and Dan Boneh.  Slalom: Fast, verifiable and private execution of neural networks in trusted hardware.  In Proc. of ICML, 2018.
  * [76] Florian Tramèr, Fan Zhang, et al.  Sealed-glass proofs: Using transparent enclaves to prove and sell knowledge.  In Proc. of IEEE EuroS&P, 2017.
  * [77] Florian Tramèr, Fan Zhang, Ari Juels, Michael K Reiter, and Thomas Ristenpart.  Stealing machine learning models via prediction $\\{$APIs$\\}$.  In Proc. of USENIX Security, 2016.
  * [78] Stephan van Schaik, Andrew Kwong, Daniel Genkin, and Yuval Yarom.  Sgaxe: How sgx fails in practice.  https://sgaxe.com/files/SGAxe.pdf, 2020.
  * [79] Eduard Fosch Villaronga, Peter Kieseberg, and Tiffany Li.  Humans forget, machines remember: Artificial intelligence and the right to be forgotten.  Computer Law & Security Review, 34(2):304–313, 2018.
  * [80] Michael Walfish and Andrew J Blumberg.  Verifying computations without reexecuting them.  Communications of the ACM, 58(2):74–84, 2015.
  * [81] Cong Wang, Qian Wang, Kui Ren, and Wenjing Lou.  Ensuring data storage security in cloud computing.  In Proc. of IEEE/ACM IWQoS, 2009.
  * [82] Cong Wang, Qian Wang, Kui Ren, and Wenjing Lou.  Privacy-preserving public auditing for data storage security in cloud computing.  In Proc. of IEEE INFOCOM, 2010.
  * [83] Yang Wang, Gregory Norcie, Saranga Komanduri, Alessandro Acquisti, Pedro Giovanni Leon, and Lorrie Faith Cranor.  ” i regretted the minute i pressed share” a qualitative study of regrets on facebook.  In Proc. of SOUPS, 2011.
  * [84] Alexander Warnecke, Lukas Pirch, Christian Wressnegger, and Konrad Rieck.  Machine unlearning of features and labels.  https://arxiv.org/abs/2108.11577, 2021.
  * [85] Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang.  Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits.  In Proc. of IEEE S&P, 2021.
  * [86] Peterson Yuhala, Pascal Felber, et al.  Plinius: Secure and persistent machine learning model training.  In Proc. of IEEE/IFIP DSN, 2021.
  * [87] Rui Zhang, Jian Liu, Yuan Ding, Qingbiao Wu, and Kui Ren.  “adversarial examples” for proof-of-learning.  In Proc. of IEEE S&P, 2022.
  * [88] Xiaoli Zhang, Fengting Li, Zeyu Zhang, Qi Li, Cong Wang, and Jianping Wu.  Enabling execution assurance of federated learning at untrusted participants.  In Proc. of IEEE INFOCOM, 2020.
  * [89] Lingchen Zhao, Qian Wang, Cong Wang, Qi Li, Chao Shen, and Bo Feng.  Veriml: Enabling integrity assurances and fair payments for machine learning as a service.  IEEE Transactions on Parallel and Distributed Systems, 32(10):2524–2540, 2021.
  * [90] Wenting Zheng, Raluca Ada Popa, et al.  Helen: Maliciously secure coopetitive learning for linear models.  In Proc. of IEEE S&P, 2019.

##  Appendix A Motivations for our TEEs-Based Solution

We logically combine an authentication layer and a proving layer, and we might
implement them by incorporating dynamic ADS with proof-based verifiable
computation, to obtain a conceptual solution. To be specific, ADS enables a
user holding the digest of her data, to outsource the data and potential
operations on the data to a server, while tracking the integrity of the data.
Proof-based verifiable computation on the ADS can further allow the user to
verify the truth of some server-side statement like “a specific computation is
executed on this data matching the ADS, yielding that output”, which is faster
than reexecution by herself. Towards the solution, one possibility is
combining general-purpose and concise proof systems, such as succinct non-
interactive argument of knowledge (SNARK) [36], with dynamic accumulators [49,
13], such as RSA-based, pairing-based or Merkle tree-like to initialize the
proving layer and the authentication layer, respectively.

But the above incorporation may not be able to handle extensive ML workloads
yet, while respecting the underlying computations. The incorporation might
suit the problems with simple computation logic, _e.g._ , linear regression
models with dozens of training iterations, but it can become unafforable to
handle complex neural network models. For example, the latest SNARK-based
system [64] takes 86GB memory to prove knowledge of $512\times 512$ matrix
multiplication, despite allowing concise proof. Other memory-efficient proof
systems from interactive oracle proofs, “MPC-in-the-head” paradigm, garbled
circuits and subfield Vector Oblivious Linear Evaluation (sVOLE), have to
sacrifice communication efficiency or verification time, as summarized by a
recent work [85]. Furthermore, the off-the-shelf proof systems are not
designed tailored for training algorithm and usually need modification for
adapting to inherent crypto operations [89], _e.g._ , arithmetic operations on
finite fields via model quantization. Recent efforts [90] also require some
changes on the underlying linear model learning algorithms.

Since the above crypto-assisted solutions are not scalable to generic models,
or not compatible to the underlying learning algorithms, or not cost-tolerant
yet, our practicality goals cannot be supported. Therefore, we explore a
trusted hardware-based verifiable computation to realize PoUL at as native
speed as possible while supporting concise proof and fast verification.

##  Appendix B Functionality Modeling for SGX Enclave

As depicted in Fig. 7, there starts with a pair of public verification key and
signing key $(\textsf{pk}_{\text{sgx}},\textsf{sk}_{\text{sgx}})$ at most one
time by the Intel’s EPID group signature scheme $\Sigma$ on an host
$\mathcal{H}$. Herein, $\textsf{sk}_{\text{sgx}}$ is shielded inside the
enclave while $\textsf{pk}_{\text{sgx}}$ is publicly known. On the activation
point install, an enclave can be installed with the program
$\textsf{prog}_{\text{sgx}}$, yielding a unique enclave identity eid (a
SHA-256 hashsum of the at-launch pages added to the encalve). Upon receiving a
call on the resume activation point with input inp, the program runs on the
input and outputs a result. The result is subsequently attested by the
signature scheme, yielding the attestation result $\sigma$. As a result, the
resume result including the output and the attestation result are returned.
The authenticity of attestation results relies on that the EPID signature
scheme is existentially unforgeable under chosen message attacks (EU-CMA).

The $\mathcal{F}_{\text{SGX}}$ Functionality Initialize:
$(\textsf{pk}_{\text{sgx}},\textsf{sk}_{\text{sgx}}):=\Sigma.\textsf{KeyGen}(1^{\lambda})$
//$\textsf{sk}_{\text{sgx}}$ is hardcoded and $\textsf{pk}_{\text{sgx}}$ is
published. Install: On receive(‘install’, $\textsf{prog}_{\text{sgx}}$) from
$\mathcal{H}$: let eid $\in\\{0,1\\}^{\lambda}$; store
$\textsf{prog}_{\text{sgx}}$ in enclave memory mem; return eid to
$\mathcal{H}$. Resume: On receive(‘resume’, eid, inp) from $\mathcal{H}$: find
$\textsf{prog}_{\text{sgx}}$ from mem; let
$\textsf{outp}:=\textsf{prog}_{\text{sgx}}(\textsf{eid},\textsf{inp})$; let
$\sigma:=\Sigma.\textsf{Sign}(\textsf{sk}_{\text{sgx}},\textsf{eid},\textsf{prog}_{\text{sgx}},\textsf{outp})$;
return outp and $\sigma$ to $\mathcal{H}$.

Figure 7: The $\mathcal{F}_{\text{SGX}}$ functionality.

With the $\mathcal{F}_{\text{SGX}}$, Tramèr _et al._ [76] define the “commit-
and-prove” functionality in Fig. 8. Specifically, the prover is required to
firstly commit to an input in the enclave memory. Upon receiving an unseen
challenge from a verifier, the prover executes a previously installed program
on the committed input and the verifier’s challenge, and yields an attestation
proof for the execution correctness. At a later time, the verifier can also
attest the authenticity of the opening of the committed input.

We emphasize that our PoUL problem meets a nature of _knowledge asymmetry_ in
the above “commit-and-prove” functionality. For instance, a server can commit
to a trained model at first before receiving a data owner’s test data as a
challenge, and then prove a prediction yielded by a correctly generated model
on the test data. Notice that we do not require protecting the confidentiality
of both the model and data. Standing on top of the functionality, we need a
new design tailored for PoUL satisfying correctness properties and
practicality goals as required.

The “commit-and-prove” Functionality $\mathcal{F}_{\text{SGX}}^{\text{CP}}$
Commit: On receive(‘commit’,eid, $\textsf{inp}_{\mathcal{P}}$) from
$\mathcal{P}$: send (‘resume’, (‘commit’,eid, $\textsf{inp}_{\mathcal{P}}$))
to $\mathcal{F}_{\text{SGX}}$; store $\textsf{inp}_{\mathcal{P}}$ in the
enclave memory mem; receive (‘receipt’, eid, $\sigma_{c}$) from
$\mathcal{F}_{\text{SGX}}$; return (‘receipt’, eid, $\sigma_{c}$) to
$\mathcal{V}$. Challenge: On receive(‘challenge’,eid,
$\textsf{inp}_{\mathcal{V}}$) from $\mathcal{V}$: let
$\textsf{inp}_{\mathcal{V}}$ store in the enclave memory mem. Prove: On
receive(‘prove’,eid) from $\mathcal{P}$: find
$(\textsf{inp}_{\mathcal{P}},\textsf{inp}_{\mathcal{V}})$ in mem; send
(‘resume’, (‘prove’,eid,
$\textsf{inp}_{\mathcal{P}},\textsf{inp}_{\mathcal{V}}$)) to
$\mathcal{F}_{\text{SGX}}$; //run
$\textsf{outp}:=\textsf{prog}(\textsf{inp}_{\mathcal{P}},\textsf{inp}_{\mathcal{V}})$
//run
$\sigma_{p}=\Sigma.\textsf{Sign}(\textsf{sk}_{\text{sgx}},\textsf{outp})$
receive (‘proof’, eid, outp, $\sigma_{p}$) from $\mathcal{F}_{\text{SGX}}$;
return (‘proof’, eid, outp, $\sigma_{p}$) to $\mathcal{V}$. Open: On
receive(‘open’,eid) from $\mathcal{P}$: find $\textsf{inp}_{\mathcal{P}}$ in
mem; send (‘open’, eid, $\textsf{inp}_{\mathcal{P}},\sigma_{o}$) to
$\mathcal{V}$.

Figure 8: The “commit-and-prove” functionality based on the SGX enclave. We
describe the activation points on the side of the prover, and omit that on the
verifier side, majorly for verifying attestation reports.

##  Appendix C Discussions

Supporting Multiple Data Owners We consider that the data used to train a
predictive model can come from multiple data owners. In such a scenario, data
owners cannot mutually access the data of others, and all of them do not trust
the server who trains the model. To implement PoUL, we start by sequentially
authenticating the data owners’ data with a unique in-enclave filter in the
$\textsf{S}_{1}$-Initialize procedure. Suppose the first data owner, with her
identity $\textsf{ow}_{1}$, uploads her data to the server’s execution
enclave. The enclave generates the fingerprint of each data point in the form
of $\textsf{Enc}(\textsf{kid}||\textsf{data}||\textsf{eid}||\textsf{ow}_{1})$.
Herein, kid is generated by $\textsf{xxHash}(\textsf{ow}_{1}||\textsf{data})$.
After traversing her data, the second data owner who prepares for uploading
data asserts the current states of the execution enclave, by verifying
$(\sigma_{d},h_{c},\textsf{prog}_{c},\textsf{prog}_{k})$, where $h_{c}$ is the
digest of the current filter in the enclave. The above processes repeat until
the last data owner’s data is traversed, and the filter at the current time
packs all data owners’ data. Next, suppose a Deletion phase is invoked for
complying with one data owner’s deletion request which contains the
corresponding kids of the data point to be deleted. The execution enclave can
retrieve $\textsf{kid}=\textsf{xxHash}(\textsf{ow}_{1}||\textsf{data})$, and
delete the associated data and submodels. Notice, we consider that the
training data points are likely to be _overlapping_ in the multi-owner
scenario. Therefore, both keys and fingerprints should include the unique
identity information of data owners for identifiability, as described above.

Enabling Batch Data Deletion To delete data in a batch fashion can be
necessary, since proving the desired correctness properties with respect to
one data point deletion is already cost-consuming for a service provider. With
the concern, the server might wait for deletion requests from the data owners,
and record the corresponding kid, and after a waiting period, he executes a
Deletion phase in batch, starting from the kid at the foremost location. We
argue such a processing is reasonable, since there often allows a time period
to comply with the deletion requests, _e.g._ , one month regulated by the
U.K.’s Information Commissioner’s Office555https://ico.org.uk/for-
organisations/guide-to-data-protection/.

##  Appendix D Complementary Experimental Results

Figure 9: Impact on learning time and accuracy with varying number of slices.

Recall that we fix the number of slices for our previous evaluation; we now
vary the number of slices in one shard, and observe if it impacts the training
time and accuracy. We divide the one-shard training data into $1,3,6$ and $12$
slices, and correspondingly execute the incrementally training processes over
them. As Fig. 9 demonstrated, the number of slices makes a really little
effect on both the accuracy and the training time.