# Confidential Machine Learning on Untrusted Platforms: A Survey

Sagar Sharma
HP Inc.
<EMAIL_ADDRESS>Keke Chen
Computer Science Department
Marquette University
<EMAIL_ADDRESS>
###### Abstract

With ever-growing data and the need for developing powerful machine learning
models, data owners increasingly depend on untrusted platforms (e.g., public
clouds, edges, and machine learning service providers). However, sensitive
data and models become susceptible to unauthorized accesses, misuses, and
privacy compromises. Recently, a body of research has been developed to train
machine learning models on encrypted outsourced data with untrusted platforms.
In this survey, we summarize the studies in this emerging area with a unified
framework to highlight the major challenges and approaches. We will focus on
the cryptographic approaches for confidential machine learning (CML), while
also covering other directions such as perturbation-based approaches and CML
in the hardware-assisted confidential computing environment. The discussion
will take a holistic way to consider a rich context of the related threat
models, security assumptions, attacks, design philosophies, and associated
trade-offs amongst data utility, cost, and confidentiality.

##  I Introduction

Data-driven methods, e.g., machine learning and data mining, have become an
essential tool for numerous research and application domains. With abundant
data, data owners can build complex analytic models in areas ranging from
social networking, healthcare informatics, entertainment, and advanced science
and technology. However, due to the limited in-house resources and expertise,
data owners (e.g., parties that collect and analyze user-generated data) often
utilize somewhat untrusted platforms (e.g., cloud and edge service providers)
for elastic storage and data processing. As a result, cloud services for data
analytics, such as machine-learning-as-a-service (MLaaS), have been growing
rapidly during the past few years.

When outsourcing sensitive data (e.g., proprietary, human-related, or
confidential data), data owners have raised concerns in privacy,
confidentiality, and ownership [68, 24]. On one hand, cloud users cannot
verifiably prevent the cloud provider from getting access to their data.
Instead, using public clouds often means you have to fully trust your cloud
provider. On the other hand, public cloud providers are not immune to security
attacks, which may lead to breaches of sensitive data. The recent security
incidents including insider attacks [13, 24] as well as external security
breaches at the service providers [52, 75] have aggravated the situation.
Researchers and practitioners have developed solutions to protect the
confidentiality of cloud data at rest. For example, Google Cloud Platform has
allowed users to include an external key manager to store encrypted data on
the cloud with a third party (e.g., Fortanix) storing and managing keys off-
cloud. However, it remains a critical challenge for data owners and cloud
providers to protect confidential in computing, i.e., learning models on the
cloud while protecting the confidentiality of both the training data and the
learned models.

During the past few years, researchers have made some progress on novel
confidential machine learning (CML) approaches for learning from encrypted
outsourced data. Developing a successful CML approach is not straightforward.
Different from traditional machine learning approaches, a practical CML
framework struggles among security (confidentiality) guarantee, costs, model
quality, appropriate workload distributions between cloud and client. Direct
application of cryptographic and privacy-protection methods such as fully
homomorphic encryption (FHE) [28] and garbled circuits (GC) [78] in a
homogeneous fashion although theoretically may not meet the criteria for
practical CML approaches. Most efficient approaches have been using hybrid
methods that combines multiple primitives instead of a homogeneous
translation. Recent studies [56, 57, 21, 54, 69, 67] have followed this
direction to effectively reduce performance bottlenecks and other practicality
issues in developing CML solutions. However, various techniques have been
scattered among papers and the basic principles are unclear. The purpose of
this survey is to uncover the basic principles and nicely organize the
existing techniques under a unified framework, so that researchers and
practitioners can quickly grasp the development of this new area.

Scope and Related Work. Capturing a comprehensive view of a complex and new
topic like confidential machine learning is challenging. We primarily focus on
frameworks for _model training_ using cryptographic techniques that guarantee
strong (semantic) security with practical cost overburden. A complete machine
learning service may also include model application or inference, i.e.,
applying the learned model to generate prediction for new input data, which is
equivalent to secure function evaluation, normally much simpler and thus not
covered by this survey. Interested readers may refer to the related studies
about confidential inference with pre-trained models, such as Gilad-Bachrach
et al. [29], Bost et al. [10], and Hesamifard et al. [40].

We also exclude differentially private machine learning frameworks that hold a
distinct thread model aiming at sharing data and models. They assume that the
data consumer (i.e., model developer) is not trustable, who may try to reveal
private information in the training data shared by data owners or data
contributors. It does not protect the ownership of data and model as the
purpose is to share them without breaching individuals’ privacy in the
training data. Along with recent developments on differentially private deep
learning such as Abadi et al. [1] and Shokri et al. [71], Ji et al. [43] and
Sarwate and Chaudhari [63] also provide excellent surveys on this topic. Other
studies in privacy-preserving data mining (PPDM) [3, 53, 6, 62] also aim to
sharing the data (and the models) while preserving individual’s privacy, thus
excluded from our survey.

Shan et al. [65] focuses on techniques for practical secure outsourced
computation, using machine learning as a sample application. However, it does
not comprehensively cover the major approaches as we do. Attacks on machine
learning models have also raised serious concerns due to the wide applications
of machine learning in real life scenarios such as self-driving cars [35].
Papernot et al. [60] summarize different attack surfaces and focus on the
integrity of training data, training process, models, and model application.

Contributions and Organization Overview. This survey paper presents a unified
perspective on designing and implementing different types of CML model
learning methods with state-of-the-art cryptographic approaches. When studying
the related papers, we have observed a general framework has been implicitly
applied to design efficient hybrid approaches that combine different types of
cryptographic primitives - we call it the decomposition-mapping-composition
(DMC) process to optimize the solution. Specifically, the DMC process
involves: decomposing the target machine learning algorithm into several
components, mapping the components to their cryptographic constructions, and
final composing the CML solution with the confidential components. We develop
a systemization framework to summarize the compositional design principles,
strategies, cryptographic techniques, and optimization measures applied to
solve the challenging problems of machine learning over encrypted data in the
outsourced setting. The survey will be uniquely organized based on underlying
compositional principles rather than the machine learning problems being
solved. As part of the survey, we leverage the experiences and principles in
each category of CML topics as _insights_ and _gaps_.

In the following, we will present the necessary background knowledge,
notations, definitions, and the targeted threat model in Section II. Then, we
briefly discuss the homogeneous approaches that aim to provide a generalized
framework for translating any algorithm into a confidential one (Section III).
Then, we move to the main theme: the compositional hybrid approaches (Section
IV), which consists of the basic decomposition-mapping-composition (DMC)
process. We dissect the relevant research based on component-wise
cryptographic constructions and the challenges and principles for successful
compositions, especially focusing on cryptographic primitive switching and
design of crypto-friendly machine learning algorithms. Finally, we will also
cover several other approaches different from the cryptographic ones,
including the perturbation methods and hardware-assisted (e.g., SGX) methods.

##  II Overview of CML Approaches

In this section, we review the terms and concepts used in the literature.
First, we look at the representative system architectures considered in the
published confidential machine learning (CML) approaches that are based on
cryptographic protocols. Then, we present threat models, confidential assets,
and notable attacks along with the effect on the related design. Finally, we
briefly describe the common cryptographic and privacy primitives that serve as
the skeleton of most CML approaches.

###  II-A Representative System Architectures

The CML research is mostly motivated by the cloud computing paradigm and
extended to more scenarios, such as edge computing and services computing.
Thus, we use “Cloud” as the representative of untrusted platforms in CML
system architectures henceforth. Such as system may involve cloud providers,
optional cryptographic service providers, data owners or application service
providers, and data and model consumers depending on the outsourcing scenario.

Figure 1 shows an architecture with a data owner outsourcing its data and
computation to a single cloud provider. The data owner must ensure the cloud
provider does not compromise any proprietary and privacy-sensitive data. A few
FHE-based frameworks, e.g., Graepel et al. [34] and Lu et al. [51], present
protocols for training machine learning models over encrypted data outsourced
to a cloud provider without almost any engagement of the data owner. However,
the associated cost makes these protocols unrealistic in real-life scenarios.
An alternate strategy would be to involve the data owner in minimal tasks
intermediately to simplify the single cloud architecture framework [69].

Figure 1: A data owner outsourcing to an untrusted cloud provider for learning
a model. The data contributors directly submit their encrypted data to the
cloud. The cloud carries out the major expensive computations over the
encrypted data and data owner can assist with some lightweight work.

As machine learning over encrypted data becomes more expensive for the data
owner assisted cloud-based learning, a data owner may choose to rely on two or
more cloud providers to reduce the overall expense of learning. The second
party may be as equally capable as the first party [54], or in case of a
cryptographic service provider (CSP), which manages keys and assists the cloud
with intermediate decryption operations and light-weight computations [56, 57,
67]. The two parties in such an architecture carry out secure two-party
computations without any of the parties learning the training data and the
trained model. This setting also assumes that the two parties do not collude
with each other, thus slightly more vulnerable than the first one. Figure 2
shows such a framework which uses garbled circuit.

Figure 2: A data owner outsources data storage and machine learning tasks to
the Cloud. The Cryptographic Service Provider (CSP) manages the keys, decrypts
intermediate results, and assists the Cloud with other relatively lightweight
computations.

###  II-B Threat Models

In this section, we examine the widely accepted threat models in the context
of CML. We focus on the following important aspects: the assumptions on the
adversaries and the confidential assets.

Assumptions on Adversaries. Most CML approaches [67, 54, 56, 57, 34] adopt the
honest-but-curious (semi-honest, or passive) adversary model to describe the
untrusted cloud provider. Honest-but-curious parties, by definition, perform
their share of tasks obediently, i.e., guarantee data and model integrity and
follow the pre-defined protocols exactly. However, they might clandestinely
snoop the storage, interactions, and computations for information. This
matches the purpose of preserving the confidentiality of data and models only,
to effectively reduce data owners and data contributors’ concerns about data
and model leakages, even when a reputable public platform incurs security
failures. In addition, if the cryptographic service provider is used, it’s
also considered honest-but-curious.

Some CML approaches additionally address an adversary which actively seeks to
compromise data and model confidentiality by performing additional probing
tasks, e.g., by inserting crafted records or secretively running the
algorithms on selected records offline. Sharma and Chen [67] address the
possibility of an adversary who may actively track identifiable training
records to the datasets and follow the computations to infer the information
about other training records. Nikolaenko et al. [57] considers an adversary
which selectively runs the machine learning protocol over an individual’s data
to draw personal inferences from the learned models. Nevertheless, with
passive or active adversaries, an important assumption of the CML approaches
is that the integrity of data and model is not compromised at the end of
training, which distinguish CML from other studies such as attacks on machine
learning by polluting training data or modifying learned models .

Moreover, the CML approaches often assume non-collusion between the involved
parties, for example, between the cloud provider and the CSP [56, 57, 67] or
the two cloud providers [54] in the two server architecture. A collusion
between the two parties in these frameworks directly compromise privacy of the
training data and learned models.

Most CML approaches assume that data and model consumers are trusted, which is
orthogonal to the applications of differential privacy [71, 1] that
specifically targets untrusted data and model consumers. Furthermore, CML
approaches assume properly secured infrastructures and communication channels
to exclude external attacks and focus on the CML-specific challenges.

Confidential Assets at Risk. An adversarial party may be interested in the
confidentiality of sensitive data and the generated models. Almost all CML
methods regard the training data feature vectors sensitive. Some methods for
supervised learning [34, 57] expose the training data labels to simplify their
secure modeling algorithms with the assumption that knowing the labels will
not bring significantly more information to adversaries, which might be
inappropriate for some applications. Some CML studies also expose unprotected
models [34, 57, 51]. However, recent studies [27, 26, 41, 72, 73] have shown
that an adversary may use crafted data to infer sensitive training data or use
the encoded advanced features in deep learning models for breaching privacy.
Furthermore, the intermediate results of outsourcing computations in the
setting of federated learning, for example, the intermediate representation in
a convolutional neural network learning, may reveal information about the
private training data [71]. Thus, it is necessary for CML to protect both data
and model confidentiality.

###  II-C Cryptographic Primitives

The cryptographic primitives are the fundamental building blocks for CML
approaches. Some of these primitives are more expressive – meaning they can
implement more types of functions or higher-level functions. Similarly, some
primitives are more cost-efficient than others. To make this survey self-
contained, this section briefly covers the most frequently used primitives in
existing CML approaches.

Additive Homomorphic Encryption (AHE). AHE schemes (e.g., Paillier encryption
[59]) allow the additive operation over encrypted messages without decryption.
Conceptually, with one of the operands unencrypted, a “pseudo-homomorphic”
multiplication between two messages can be expressed as a series of
additions111Some methods like Paillier encryption [59] allow more efficient
pseudo-homomorphic multiplication.. With homomorphic addition and pseudo-
homomorphic multiplication, one can derive pseudo-homomorphic dot-product of
vectors, matrix-vector multiplication, and matrix-matrix multiplication.
However, the unencrypted operands in these operations either need to be non-
sensitive information or protected with some masking and de-masking mechanism
[69, 67]. ElGamal, Goldwasser-Micali, Benaloh, and Okamoto-Uchiyama
cryptosystems are some additional examples of AHE schemes [2].

Somewhat Homomorphic Encryption (SHE). There are many encryption schemes in
this category (e.g., BV, BGV, NTRU, GSW, BFV, and BGN [2] and their variations
such as TFHE [17] and CKK [16]). SHE schemes allow both homomorphic additions
and multiplications over encrypted messages, while the number of consecutive
multiplications is limited to a few. A popular SHE scheme used in CML is the
ring learning-with-error (RLWE) scheme that relies on the intractability of
the learning-with-errors (LWE) problem on polynomial rings [11].
Theoretically, RLWE supports arbitrary levels of multiplications, therefore it
is considered to be fully homomorphic. However, due to associated high cost
for deeper levels of multiplications, RLWE is more suitable as a SHE scheme
only (i.e., 1-3 levels of multiplications). _Message packing_ [11] enables
packing multiple ciphertexts into one polynomial, which considerably reduces
RLWE’s ciphertext size and optimizes linear algebra operations [37]. HELib
library [37] is a popular implementation of the RLWE scheme.

Garbled Circuits (GC). Garbled Circuits (GC) [78] allow two parties, each
holding an input to a function, to securely evaluate a function without
revealing any information about the respective inputs. GC can express
arbitrary functions using several basic gates such as AND and XOR gates in a
secure two-party computation setting (usually with a Cryptographic Service
Provider (CSP)). One party constructs the circuit, whereas the other evaluates
it. Despite several GC cost optimization techniques, such as Free XOR gates
[46], Half AND gates [79], and OTExtensions [7], GC still incurs high
communication costs. Therefore, one must carefully examine its use in
composing CML frameworks. FastGC [42] and ObliVM [49] are two popular GC
libraries.

Randomized Secret Sharing (SecSh). The randomized secret sharing method [21]
protects data by splitting it into two (or multiple) random additive shares
outsourced to two (or more) non-colluding untrusted parties. The two parties
compute on the respective shares and return the results also as random shares.
Addition is straightforward. Multiplication, however, is expensive as it
depends on the beaver triplet generation method [21, 54], which further
depends on expensive AHE or Oblivious Transfer (OT) schemes to exchange the
intermediate results securely.

Random Masking. A data owner may generate a random mask to hide the sensitive
data, which she strips off at a certain step in the CML protocol to recover
the desired result. It frequently serves as an auxiliary tool for a complex
protocol, for instance, in CML for spectral clustering [69], boosting [67],
and matrix factorization [56].

###  II-D Systematization Framework

We organize several representative approaches for CML on outsourced data in a
systematic way, as shown by Figure 3. They may use one crypto primitive in a
homogeneous fashion or multiple primitives in a hybrid composition. The
homogeneous approaches mostly rely on either fully homomorphic encryption
(FHE) schemes or garbled circuits. The hybrid composition of CML frameworks
involves the DMC steps: the decomposition of the target algorithm into
different subcomponents, the mapping of the sub-components to different
crypto-primitives, and the final composition of the CML framework with the
confidential sub-components. The hybrid composition generally is a manual
process and involves several heuristic assessments. However, a few frameworks
have started exploring the automatic optimization of the composition process.

The perturbation-based CML approaches are typically more efficient. They do
not follow the cryptographic composition framework, but employ secrete data
transformations to protect data and models. As a result, they do not provide
strong security guarantees as the cryptographic approaches do, e.g., most of
them provide a resilience level equivalent to ciphertext-only attacks.
However, their high efficiency feature is still appealing for many
applications that seek solutions better than plaintext-based unprotected
approaches. Thus, we will also cover this category of methods in our survey.

Figure 3: The systematization framework for confidential machine learning
(CML) approaches.

##  III Homogeneous Cryptographic Approaches

Homogeneous approaches rely on single primitive to construct the framework
protocols, typically, AHE, SHE, FHE, or GC. Since FHE implements homomorphic
addition and multiplication, and GC implements the boolean gates, in theory,
they can individually construct all CML algorithms. However, they are too
expensive to be practical when used in training CML for complex models.

Graepel et al. [34] present an FHE-based framework for learning Fisher’s
linear discriminant analysis and Linear Means Classifier models on encrypted
data. However, the resulting models are trivial and limited to linearly
separable datasets. Similarly, Liu et al. [49] present a GC-based KMeans
learning framework that involves two untrusted servers. The associated cost
overburden, however, is far from practical in real-world settings. For
example, the KMeans implementation required over 2,000 million AND gates and
more than 200 GB communication for clustering just 6,000 data points.

On the other side, due to the limited expressiveness of AHE and SHE schemes,
they are limited to constructing homogeneous solutions with a few
multiplications, including the basic statistical aggregation functions, such
as average, sum, and variance, which, however, are sufficient for many
applications. Lu et al. [51] apply SHE for more sophisticated principal
component analysis and linear regression [38]. However, due to the limited
message space of the selected SHE implementation (60-bits in HELib) and the
limited use of multiplications, only low-dimensional data (about 20) and a few
iterations are used to achieve practical costs, which, however, gives only
sub-optimal models. Researchers also aim to provide libraries for learning
based on Garbled Circuits (GC). However, their practical uses are also
restricted due to the huge costs [49].

_Insight. Homogeneous solutions are often limited to simple functions
involving only additions (for AHE), a few multiplications (SHE), or a few
comparisons (GC). Individually, these crypto primitives are unable to
construct complex CML algorithms. However, they can be valuable components for
hybrid solutions, as we will see later._

##  IV Hybrid Composition Approaches

As we discussed above, depending on one cryptographic primitive to compose a
sophisticated CML algorithm is almost impractical. However, ßeach primitive
has unique strengths (e.g., performance advantage) in attaining certain
operations only. This leads to an interesting strategy: can we combine
different primitives to get secure and more optimized protocols? The idea of
hybrid composition is thus: mix and switch amongst different primitives to
avoid the associated cost bottlenecks and restrictions. Next, we show this
primitive-level performance difference and explore the general framework for
the decomposition-mapping-composition (DMC) process. The DMC process
decomposes the target machine learning algorithm into its sub-components and
maps those sub-components to different cryptographic and privacy primitives
before composing the overall CML frameworks. Figure 4 depicts the DMC process.
First, we systematically examine the cryptographic versions of common machine
learning algorithms’ sub-components and operations, the switching and mixing
strategies in practice, including the automated strategies, and finally, the
complicated issue of designing crypto-friendly algorithms for cost-efficient
and practical CML solutions.

Figure 4: The decomposition-mapping-composition (DMC) process for constructing
hybrid CML solutions.

###  IV-A Cryptographic Implementations of Basic Operations

We devote this subsection in inspecting the mapping of the foundational sub-
components of the target machine learning algorithms to their confidential
versions. We observe that some of these mappings are practical or crypto-
friendly, whereas some may face cost bottlenecks and other limitations. The
discussions around the crypto-friendliness of the algorithms and their sub-
components will eventually determine the actual optimized composition of a CML
solution.

Comparison. Comparison is essential in sorting vectors, building binary trees,
training perceptrons and k-nearest neighbors, and applying activation
functions such as ReLU, Sigmoid, and Tanh, which are crucial to neural
networks. Unfortunately, comparing two encrypted or protected integers is not
trivial. Graepel et al. [34] pose the complexity of comparison as the reason
to avoid algorithms like perceptrons and logistic regression in their SHE-
based confidential ML framework. Veugen [76] presents a client-server
interactive comparison protocol for two encrypted integers based on the AHE
scheme, which involves computation and transfer of $b$ many AHE encrypted
bits. Each comparison incurs $O(b)$ homomorphic multiplications for both
client and server. Lu et al. [51] use the technique of “greater than” protocol
[32] optimized with the message packing of the RLWE scheme for comparing two
encrypted messages, in a two-party setting. However, the associated complexity
is an astonishing cost $O(2^{b}/h)$ of homomorphic additions when comparing
two $b$-bit integers, while packing $h$ messages in a ciphertext. With GC, a
comparison between two $b$-bit integers is possible with $O(b)$ AND gates and
$O(b)$ communication, encryption, and decryption by two parties. Since GC-
based comparison for full integers is expensive, one may use an efficient one-
bit sign checking protocol [54, 67] by encoding negative integers as two’s
complement, making the comparison cost is constant to the number of bits. Note
that the GMW protocol of Goldreich, Micali, and Wigderson [30] can perform
comparisons just as garbled circuits but with $O(b)$ rounds. Similar sign-
checking protocol might be used for GMW. However, the GC-based comparison
seems the popular choice in current solutions.

Division. Division can be important to some analytics algorithms, e.g., from
the computation of mean to the implementation of complex algorithms such as
K-means [12] and Levenshtein distance [61]. Despite its prevalence and
importance, translating division to its confidential version is expensive and
often a performance bottleneck [47]. Veugen [76] presents a protocol for exact
division in a client-server scenario, using the AHE scheme and additive noise
masking. However, the protocol requires the divisor to be public knowledge. On
top of that, the protocol requires $O(b)$ homomorphic comparisons and $O(b)$
encrypted communication for division between two $b$-bit integers. Dahl, Chao,
and Tomas [20] present two AHE-based division schemes that rely on Taylor
approximation, in a secure multi-party setting. The schemes brought expensive
$O(b)$ encrypted communication. It is possible to perform integer divisions
with GC when the two parties hold the numerator and denominator respectively
in a 2-party setting [47, 57]. However, even with several optimizations, this
involves the construction and evaluation of a circuit with $O(b)$ non-XOR
gates [47] for division between two $b$-bit integers. A more practical
solution is to decrypt the operands on a crypto-service provider and conduct
division on plaintext and then encrypt the result, if this intermediate step
does not reveal additional valuable information.

Linear Algebra Operations. Linear algebra operations, such as vector products,
matrix-vector multiplication, and matrix-matrix multiplications, are the core
operations for many machine learning algorithms. They can be simply extensions
of the arithmetic operations based on the cryptographic primitives. Among all
available methods, the AHE and SHE based implementations are the most
efficient ones.

A dot product $x_{k}^{T}y_{k}$ involves $O(k)$ element-wise homomorphic
multiplications and additions. Similarly, a matrix-vector multiplication
$A_{n\times k}x_{k}$ involves $O(nk)$ homomorphic multiplications and
additions, and a matrix-matrix multiplication $A_{n\times k}B_{k\times m}$
involves $O(nkm)$ multiplications and additions. With the AHE scheme, one of
the operands must remain unencrypted for these multiplicative operations, and
thus this unencrypted operand needs some level of protection, e.g., novel
randomized masking [69] with a minimized cost. With the message packing
feature for the RLWE-like SHE scheme, one can easily vectorize the vector and
matrix operations with message packing to gain more efficiency [37]. With such
facilities, Jiang et al. [44] can optimize matrix-matrix multiplication with
only $O(k)$ complexity for symmetric matrices of $k$ dimensions.

Randomized secret sharing enables linear algebraic operations with the
multiplicative triplet generation approach in a multi-party setting. However,
this involves the expensive AHE or OT based multiplicative triplet generation
schemes as used in [54, 21]. In computing a matrix-vector multiplication $Ab$,
each party is responsible for $O(n+k)$ encryptions and upload, $O(nk)$
homomorphic multiplications, $O(nk+n)$ homomorphic additions, and $O(n)$
decryptions.

One can easily map the Linear algebra operations to garbled circuits. GC-based
vector and matrix addition/subtraction require $O(kb)$ and $O(nkb)$ AND gates
where $b$ is the number of bits in the vector and matrix elements. This
results in $O(kb)$ and $O(nkb)$ communication, encryption, and decryption
operations, respectively. GC-based dot product for two $b$ bit vectors with
$k$ dimensions is a collection of sub-circuits for multiplication and
additions, which consist of $O(kb^{2})$ AND gates. This involves $O(b^{2})$
encryption and decryption, and $O(b^{2})$ encrypted communication. The GC-
based dot product can be straightforwardly extended to matrix-vector and
matrix-matrix multiplication. However, GC-based linear algebra solutions are
more expensive than HE based ones.

TABLE I: Real cost comparison for confidential arithmetic operations at 112-bit security Operations | AHE (Paillier) | SHE (RLWE) | Garbled Circuits | Secret Sharing
---|---|---|---|---
Comp | Comp | Comp | Comm | Comp | Comm
Addition/Subtraction | 0.01 ms | 0.2 ms | 37 ms | 2 KB | 0.0 ms | 0.0 KB
Multiplication | 0.05 ms | 39 ms | 138 ms | 40 KB | 1 s | 2 KB
Comparison | 429 h | $10^{5}h$ | 37 ms | 2 KB | - | -
Division | - | - | 208 ms | 46 KB | - | -
TABLE II: Real cost comparison for confidential linear algebra operations at 112-bit security. $v_{100\times 1}$ and $M_{100\times 100}$.  Operations | AHE (Paillier) | SHE (RLWE) | Garbled Circuits | Secret Sharing
---|---|---|---|---
Comp | Comp | Comp | Comm | Comp | Comm
Vector Addition | 0.6 ms | 0.2 ms | 36 ms | 192 KB | 0.0 ms | 0.0 KB
Dot Product | 6 ms | 39 ms | 5 s | 4 MB | 7 s | 195 KB
Matrix-vector Multiplication | 1 s | 3 m | 8 m | 396 MB | 7 s | 290 KB

To have a better idea how the cost differences look like, we prepare the
tables I and II. Since this comparison is done with a specific hardware
configuration and software implementation, readers should only focus on the
relative differences rather than the actual numbers. After a careful study of
available AHE and SHE implementations, we choose the most efficient one for
each category: we use the HELib library [36] for the RLWE encryption scheme
and implement the Paillier cryptosystem [59] for the AHE encryption scheme.
The ObliVM (oblivm.com) library is adopted for the garbled circuits. We also
take the AHE scheme for the multiplicative triplet generation when using the
randomized secret sharing (SecSh) method. We pick cryptographic
parameters222The Paillier cryptosystem uses 2048-bit key-size. The degree of
the corresponding cyclotomic polynomial in RLWE scheme is set to $\phi(m)$ =
12, 000 and c = 7 modulus switching matrices, which gives us h = 600 slots for
message packing.corresponding to $112$-bit security. All schemes allow at
least 32-bit messages-space overall. Moreover, the RLWE parameters allow one
full vector replication and at least two levels of multiplication. Note again
that the GC and SecSh costs are for the two-party setting and thus also
involve the communication between the two parties. Thus, we also include the
bytes for communication for these methods. We run the experiments on Intel
i7-4790K CPU running at 4.0 GHz using 32 GB RAM with Ubuntu 18.04.

Table I compares the related cost of arithmetic operations over integers. We
observe that the AHE scheme has the most efficient arithmetic additions and
multiplications. However, for comparison and division, the 2-party garbled
circuits are the only viable option. Table II shows the costs for the linear
algebraic operations. The observation is consistent with the simpler
arithmetic operation of additions and multiplications. As we can fit multiple
messages in a ciphertext when using the RLWE scheme, the vectorized additions
and multiplications are much more efficient than the non-vectorized additions
and multiplications. The RLWE with message packing realizes homomorphic
additions more efficiently when compared to the Paillier scheme. The RLWE
costs for dot product and matrix-vector multiplication involve the ciphertext
replication costs. Although better than without message packing, the RLWE
scheme with the vectorized linear algebraic operation is still slower than the
Paillier solutions. Randomized secret sharing is almost free for vector
addition but involves higher computation and communication costs for the dot
product and matrix-vector multiplication. Garbled circuits appear to be the
worst solution for the confidential versions of the linear algebraic operation
with higher computation and communication costs between the two parties.
Although the Paillier implementation for AHE shows performance advantages over
RLWE on arithmetic operations, it does require one operand to be plaintext and
its encryption and decryption costs are actually higher than RLWE [69]. When
CSP is involved in a solution, encryption and decryption costs will become a
critical performance factor. These cost comparisons on the basic operations
will be useful for readers to analyze and compare a pair of CML protocols,
especially when not all CML methods are open sourced.

_Insight. The most efficient constructions for comparison are GC-based. SHE
and AHE are the better candidates for confidential linear algebra operations.
Since most division schemes are very expensive, one should rather transform
the functions/algorithms with divisions to the equivalent (often
approximately) ones that involve no division. _

###  IV-B Switching Costs and Composing Strategies

TABLE III: Examples for primitive switching strategies in hybrid composition of CML frameworks.  Framework | Primitive Switch |  Operation Switch |  Justification
---|---|---|---
Sharma and Chen [67] |  SHE $\rightarrow$ GC |  Matrix vector multiplication $\rightarrow$ Sign Check |  Sign checking is impractically expensive with SHE whereas tolerable with GC.
Nikolaenko et al. [57] |  AHE $\rightarrow$ GC |  Matrix Additions $\rightarrow$ Cholesky’s decomposition |  The operations of division and square root in Cholesky’s decomposition were not feasible with the AHE scheme.
Nikolaenko et al. [56] |  AHE $\rightarrow$ GC |  Matrix Additions $\rightarrow$ Gradient Descent |  Gradient descent involved multiplications, additions, and subtractions not entirely feasible with the AHE scheme.
Mohassel et al. [54] |  SecSh $\rightarrow$ GC |  Matrix-vector multiplication $\rightarrow$ Comparison |  Comparison is impossible over randomly shared secrets leading the switch to the garbled circuits.
Mohassel et al. [54] |  GC $\rightarrow$ SecSh |  Comparison $\rightarrow$ Vector Subtraction |  Use of garbled circuits for comparison was unavoidable however continuing GC on to vector subtraction would result in excessive cost overhead.
Demmler et al. [21] |  SecSh $\rightarrow$ AHE/OT |  Data at rest $\rightarrow$ Multiplication |  Multiplication with random shares required switching to either AHE or OT protocol involving the two parties in the frameworks.

When composing the operations implemented with different primitives, there is
an important step: switching between the primitives. This switching often
requires a second party in the CML frameworks, i.e., either the data owner,
the second non-colluding cloud, or a CSP.

HE to GC. Switching from a HE component to a GC component involves a second
server (e.g., a CSP) in the framework. A straightforward approach is to
include a data decryption circuit inside a garbled circuit, however, this is
super-expensive [56]. A more practical strategy [56, 57, 67] is to have the
party holding the encrypted data, denoted $P_{A}$, to mask it homomorphically
and send it to the second party, $P_{B}$ for decryption. The second party
constructs the desired garbled circuit, where the first step of the garbled
circuit is de-masking the data with inputs: the decrypted masked data from
$P_{B}$ and the mask from $P_{A}$.

SecSh to GC. Switching from a SecSh component to a GC component is
straightforward in a two-party architecture. The two random shares in
possession of the two parties can be their respective private inputs to the
desired garbled circuits [54, 67].

SecSh to/from HE. A switch from randomized secret sharing to a HE component
needs two involved parties to encrypt their respective shares. Then, one of
the parties homomorphically reconstructs the protected value from the shares.
Similarly, a switch from a HE component to a randomized secret sharing
protocol includes a masking mechanism (homomorphic noise addition) similar to
the HE-to-GC switch. These two switches are relevant in the AHE-based
multiplicative triplet generation protocol for randomized secret sharing [54,
21].

Table III provides some examples of switching between cryptographic primitives
in well-known CML approaches. These switchings lead to simplification of the
CML framework and cost optimizations as explained in the “Justification”
column of the table. The ABY framework [21] covers different adapter-like
switching protocols for the multi-party computation settings, where two
servers hold the training data as arithmetic, boolean, or Yao’s garbled
shares. This work, however, does not include the switch from and to the
homomorphic encryption schemes.

Manual vs. Automated Composition. Most existing CML approaches that embrace
the hybrid composition strategy [54, 67, 69, 57] are manually composed as
there are myriads of problem-specific details to address. A line of research
explores the possibility of automatically composing the CML frameworks [22,
39]. Although promising, the automatic composition strategy of Dreier and
Kerschbaum [22] depends on the availability of an extensive performance matrix
for the different confidential versions of the target algorithms’ components.
Henecka et al. [39] propose the TASTY compiler that automatically compiles a
given machine learning problem as a mixture of garbled circuits and
homomorphic encryption in a secure two-party computation framework. However,
the process is still not fully automated - it requires a privacy expert to
design and specify the components together with the recommended mappings.

_Gap. Due to the high complexity of formulating the component-wise costs and
profiling the switching costs, the automated composition approaches are not
fully mature yet. More importantly, as we will see in the next section, the
construction of a practical CML solution involves one more crucial step that
automated composition methods cannot help much. One must establish an in-depth
understanding and analysis of the target ML algorithm to redesign a “crypto-
friendly” algorithm. _

###  IV-C Designing Crypto-friendly ML Algorithms

TABLE IV: Example CML methods that replace the expensive algorithmic components with their crypto-friendly versions. Framework |  ML Algorithm |  Original Component |  Crypto-friendly Component |  Benefits
---|---|---|---|---
Mohassel et al. [54] |  Logistic Regression, Neural Networks |  Sigmoid, Softmax |  ReLu |  Avoids inversion and limits expensive confidential divisions to one.
Graepel et al. [34] |  LMC, Fisher’s LDA |  Divisions |  Multiplications with incorporated division factors |  Avoids division costs and simplifies the protocol.
Nikolaenko et al. [57] |  Ridge Linear Regression |  LU decomposition |  Cholesky’s decomposition |  Reduces the cost complexity by half.
Nikolaenko et al. [56] |  Matrix Factorization |  Cholesky’s Decomposition |  Sorting based matrix factorization |  Reduces the overall complexity from quadratic to within a polylogarithmic factor of the complexity in the plaintext
Sharma and Chen [67] |  Boosting |  Decision Stumps |  Random Linear Classifiers |  Reduced number of comparisons and simplicity in learning.
Naehrig et al. [55] |  Logistic Regression |  Exponentiation |  Taylor Expansion |  Avoids costs involved in multiple levels of multiplications.
Sharma et al. [69] |  Spectral Clustering |  Eigen decomposition |  Eigen-approximation by Lanczos and Nystrom |  Reduces complexity of the problem from $O(N^{3})$ to $O(N^{2})$.

So far, the DMC framework seems quite straightforward: once one decomposes the
target machine learning algorithm to its sub-components and maps them to
cryptographic constructions, the final composition becomes almost trivial.
With enough experimentation, one can find an optimal composition set. However,
this straightforward strategy may only work for some problems. Despite the
best optimization of mapping and composition, one may still end up with a
highly expensive protocol - better than the homogeneous constructions or other
suboptimal compositions, but still impractically expensive. The fundamental
reason is that the original machine learning algorithm, when it was designed,
does not account for confidential computation. They are optimized to achieve
the best model prediction power rather than to be crypto-friendly for being
translated to a confidential version. On the other hand, a less-known
slightly-under-performing ML algorithm that achieves the same learning goal,
but possibly slightly less performing in terms of prediction power, might be
more cost effective to translate to its confidential version. Thus, an
advanced design step beyond the DMC framework is to replace or redesign some
components or even the entire ML algorithm to find the most efficient
protocols.

Table IV summarizes some example CML frameworks that incorporate strategies to
make their protocols crypto-friendly and hence more cost-effective. Mohassel
et al. [54], in their SecureML work, substitute the expensive softmax
operation involving inverses with a ReLU-based function involving only one
division. This way, the framework significantly reduces the cost bottlenecks
in their protocol. Graepel et al. [34] cleverly avoid the division of
encrypted data in their framework for learning confidential linear means
classifier and Fisher’s linear discriminant analysis by replacing the division
component with a multiplicative factor. Nikolaenko et al. [57] use the more
efficient Cholesky’s decomposition instead of the expensive LU decomposition
in solving a system of linear equations in their linear regression framework.
Similarly, Nikolaenko et al. [56] adopt the sorting based matrix factorization
solution to reduce overall complexity of computing gradient descent with
Cholesky’s decomposition based matrix factorization. Sharma and Chen [67]
propose to train a boosting classifier over encrypted data with an ensemble of
random linear classifiers (RLC) instead of decision stumps. An RLC takes mere
$N$ encrypted comparisons, whereas a decision stump takes far too many
comparisons. Naehrig et al. [55] replace the exponential function (the
sigmoid) in their logistic regression protocol with the Taylor approximation
of exponentiation. Computing the exact exponential function would have led to
the computation of several levels of multiplications over the encrypted
message – which would have been intolerably expensive with SHE schemes.
Similarly, Sharma et al. [69] replace the inherently expensive eigen-
decomposition $O(N^{3})$ with cheaper eigen-approximations $O(N^{2})$
algorithms of Lancozs and Nystrom in their spectral clustering framework. Data
reduction techniques such as subsampling and preserving the sparsity of matrix
are also critical to performance. Nikolaenko et al. [56], in their matrix
factorization framework, use a sorting network that optimizes the garbled
circuit based gradient descent algorithm by only updating it for the user
ratings that are present in the training dataset. Similarly, Sharma et al.
[69] propose a differential privacy based graph submission mechanism that
reduced total storage by over 15 times and costs involving encryptions and the
associated homomorphic operations by over 20 times on the graph drastically
when running the secure Nystrom method for spectral clustering. To sum up,
although the approximate algorithms introduce some degradation to the learned
models, they deliver desired cost practicality justifying the tolerable
quality sacrifice.

_Insight. For the same learning problem, there are numerous learning
algorithms; Even for the same learning algorithm, there are many variants
[38]. The search space for optimal composition is quite large. More
difficultly, most well-known ML algorithms are best known for model quality or
learning efficiency. None of the ML algorithms is specially designed for
optimal CML. Even worse, some crypto-friendly alternatives might have been
forgotten in history due to their suboptimal quality or efficiency. The design
of a good CML solution heavily depends on the designer’s deep understanding of
the ML algorithms and even the history of ML algorithm development. _

_Gap. There is no systematic way to explore crypto-friendly alternative ML
algorithms. The current practice is to design a problem/algorithm specific
crypto-friendly solution. Although the experiences can be used for designing a
new solution, there are no well-known rules or general frameworks for
exploring such alternative ML algorithms yet. _

##  V Discussion on Other CML Approaches

So far, we have focused on the cryptographic methods based on the well-known
primitives. To cover a panoramic view of the development in this growing area,
we will briefly discuss two closely related approaches: the perturbation based
approach and the hardware-assisted approach.

###  V-A Perturbation Methods

Most practical CML solutions that carefully follow the DMC process with some
innovative uses of crypto-friendly ML algorithms still cost magnitudes more
than the original plaintext algorithms. Especially if the learning algorithm
is intrinsically expensive or relies on a massive-scale training dataset, the
cryptographic primitives that provide semantic security may become
impractically expensive, discouraging users from adopting the outsourcing
paradigm. Another category of work: the perturbation-based approach offers
much more efficient solutions with some weaker security notions. Often, they
do not guarantee semantic security and may only be resilient to ciphertext-
only attacks. Nevertheless, they can be interesting for users who are willing
to make a practical trade-off between efficiency and the level of protection.
We briefly discuss this body of work to extend readers’ interests to this
unique domain.

The basic idea of perturbation is injecting random noises into the outsourced
data while (approximately) preserving some specific properties that machine
learning models are built on. Most well-known properties are geometric and
topological structures in the multidimensional space. Therefore, a model can
still be learned from the perturbed data on the untrusted platform with
preserved confidentiality of both data and model. Typical perturbation methods
include randomized response [25, 23], additive perturbation [4], geometric
perturbation [15], random projection perturbation [50], and random space
perturbation [77]. They have been applied to decision tree learning [23, 4],
clustering [15, 50], kNN classifier [15], support vector machines [15], linear
classifier [15, 14], and boosting [14]. These perturbation mechanisms can also
be adapted to disguise the training images in deep learning frameworks [66] to
achieve much lower training costs than cryptographic protocols [54].
Furthermore, as the perturbation methods often do not involve expensive
cryptographic primitives, significant cost savings can be observed in the
entire life cycle of data analytics, including data submission, computation,
and communication amongst the involved parties.

_Insight. The key idea of perturbation approaches is to identify a certain
high-level utility and preserve it in secure randomized transformations.
Similar ideas have also been explored in the cryptographic domain, such as
order-preserving encryption [9, 8, 45] and encrypted keyword search [33, 19]_.

_Gap. Despite their efficiency, perturbation-approaches face two critical
weaknesses. First, perturbation methods may cause some degradation to the data
quality and thus reduce model quality. Second, there is no systematic
framework for analyzing the protection level guaranteed by a perturbation
method. Some of them are known not to provide provable semantic security [15,
77]. However, under a clear, rigorous threat model definition and thorough
analysis, these methods will have high practical values in the venues where
users can accept the specific threat model. _

###  V-B Hardware-Assisted Approaches

During the past few years, hardware-assisted trustworthy computing has made a
significant breakthrough. In particular, the trusted execution environment
(TEE) has been implemented by multiple CPU manufactures, among which the most
popular one is Intel’s Software Guard Extensions (SGX) [18]. We will take SGX
as an example in the following. SGX defines a specific memory area (e.g., the
_enclave_). Only the authorized owner can run programs and access data in the
enclave via special instructions. Owners and users gain the access right via
an _attestation_ protocol. SGX minimized the trust boundary to the enclave,
which means even though the entire operating system is compromised,
adversaries cannot access the enclave. The physical enclave memory is limited
(less than 100MB are usable by users). When the enclave memory pages are
swapped out/in by the virtual memory management subsystem of the OS333The
enclave virtual memory management is only enabled on the Linux system for
early versions of SGX, which might be changed in newer versions of SGX, they
are encrypted/decrypted by the SGX library functions implicitly. SGX uses AES
encryption, and thus the encryption and decryption costs are much lower than
the primitives we have discussed so far. Besides, since the enclave program
works on decrypted data, there is no need to develop special CML algorithms
for running inside the enclave, making SGX an appealing platform for
developing CML solutions for complex algorithms working with large data.

However, there are a few challenges for migrating algorithms to the SGX
environment. First, users need to learn the whole SGX working mechanism and
learn to use special instructions and APIs, which can be inconvenient. A few
efforts have been made to simplify the migration of applications to SGX, among
which the Graphene-SGX library OS [74] is the most well-known. With a tool
like Graphene-SGX, developing CML solutions becomes more straightforward. Lee
et al. [48] try to migrate machine learning algorithms to SGX based on
Graphene-SGX.

Second, side-channel attacks are considered the primary threat to SGX-based
applications. Among many mentioned side-channel attacks [64, 5], the two
attacks are most prominent: the access patterns on the untrusted memory area
[64, 5] and the page fault attack [70] that happens when accessing a new page
that is not in the enclave. As the encrypted data have to be loaded from the
file to the untrusted area first and then accessed by the enclave, the access
pattern attacks seem inevitable for data-intensive applications like CML. The
well-known approach addressing this problem is the Oblivious RAM technique
[31], which has been applied to SGX by ZeroTrace [64] and Obliviate [5].
Ohrimenko et al. [58] also used oblivious access techniques for multi-party
machine learning with SGX. More studies are to be done to explore unique
problems with SGX-based CML.

_Insight. The TEE, e.g., SGX, techniques can significantly boost CML’s
performance on untrusted platforms, as the solutions do not involve expensive
crypto primitives or protocols. We consider the SGX based CML as a promising
direction because it achieves strong confidentiality guarantee with
significant performance benefits compared to other approaches. _

_Gap. The most important challenge is to address the side-channel attacks,
especially the access pattern attacks. Also, machine learning algorithms have
unique features distinct from other applications’, which may lead to specific
attacks that have not been fully explored yet. Another practical concern is
that most recent Intel server CPUs still have not had SGX enabled. While a few
cloud platforms such as Microsoft Azure and IBM Cloud have started offering
SGX-enabled instances, we consider this gap will be filled up soon. _

##  VI Conclusion

Despite the potential risk of data and model leakages, many resource-
constrained data owners use untrusted platforms (e.g., clouds and edges) for
training machine learning models. Researchers have been designing and
developing confidential machine learning (CML) approaches for outsourced data
using cryptographic primitives and various composition strategies. CML’s
overall goal is to protect the confidentiality of data, model, and
intermediate results from the untrusted platforms while also preserving the
trained model quality within acceptable costs.

We have reviewed the recent significant developments on CML under a
systemization framework focusing on the cryptographic approaches. We have
included the cryptographic primitives that are the backbone of the CML
approaches and compared the costs for basic operations. While the homogeneous
methods that rely on a single cryptographic primitive are straightforward,
their solutions are costly. Thus, we focus on the primary design trend of the
hybrid composition of multiple primitives under the decomposition-mapping-
composition (DMC) process and describe the critical issues such as the
switching between primitives and the crypto-friendly machine learning
algorithms. Finally, we also include a brief discussion of related approaches
and new directions, including the perturbation and hardware-assisted methods.
At the end of most sections, we have also included a concise summary area
labeled with _Insight_ and _Gap_ for readers to get the gist conveniently. We
believe this survey can be a useful resource for both researchers and
practitioners to build more complex and practical CML solutions in the future.

## References

  * [1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, pages 308–318, New York, NY, USA, 2016. ACM.
  * [2] A. Acar, H. Aksu, A. S. Uluagac, and M. Conti.  A survey on homomorphic encryption schemes: Theory and implementation.  ACM COMPUTING SURVEYS, 51(4), 2018.
  * [3] C. C. Aggarwal and P. S. Yu.  Privacy-Preserving Data Mining: Models and Algorithms.  Springer, 2010.
  * [4] R. Agrawal and R. Srikant.  Privacy-preserving data mining.  In Proceedings of ACM SIGMOD Conference, pages 439–450, Dallas, Texas, 2000. ACM.
  * [5] A. Ahmad, K. Kim, M. I. Sarfaraz, and B. Lee.  Obliviate: A data oblivious file system for intel sgx.  In the Network and Distributed System Security Symposium, 2018.
  * [6] Y. A. A. S. Aldeen, M. Salleh, and M. A. Razzaque.  A comprehensive review on privacy preserving data mining.  SpringerPlus, 4(1):694, Nov 2015.
  * [7] G. Asharov, Y. Lindell, T. Schneider, and M. Zohner.  More efficient oblivious transfer and extensions for faster secure computation.  In 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, Berlin, Germany, November 4-8, 2013, pages 535–548, 2013.
  * [8] A. Boldyreva, N. Chenette, Y. Lee, and A. O’Neill.  Order preserving symmetric encryption.  In Proceedings of EUROCRYPT conference, 2009.
  * [9] A. Boldyreva, N. Chenette, and A. O’Neill.  Order-preserving encryption revisited:improved security analysisand alternative solutions.  In CRYPTO, 2011.
  * [10] R. Bost, R. A. Popa, S. Tu, and S. Goldwasser.  Machine learning classification over encrypted data.  In Annual Network and Distributed System Security Symposium (NDSS), 2015.
  * [11] Z. Brakerski, C. Gentry, and V. Vaikuntanathan.  (leveled) fully homomorphic encryption without bootstrapping.  In Innovations in Theoretical Computer Science Conference (ITSC), pages 309–325, 2012.
  * [12] P. Bunn and R. Ostrovsky.  Secure two-party k-means clustering.  In Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS ’07, pages 486–497, New York, NY, USA, 2007. ACM.
  * [13] A. Chen.  Gcreep: Google engineer stalked teens, spied on chats.  Gawker, http://gawker.com/5637234/, 2010.
  * [14] K. Chen and S. Guo.  Rasp-boost: Confidential boosting-model learning with perturbed data in the cloud.  IEEE Trans. on Cloud Computing, 6(2), 2018.
  * [15] K. Chen and L. Liu.  Geometric data perturbation for outsourced data mining.  Knowledge and Information Systems, 29(3), 2011.
  * [16] J. H. Cheon, A. Kim, M. Kim, and Y. Song.  Homomorphic encryption for arithmetic of approximate numbers.  In T. Takagi and T. Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, pages 409–437, Cham, 2017. Springer International Publishing.
  * [17] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène.  TFHE: fast fully homomorphic encryption over the torus.  J. Cryptology, 33(1):34–91, 2020.
  * [18] V. Costan and S. Devadas.  Intel sgx explained.  IACR Cryptology ePrint Archive, 2016:86, 2016.
  * [19] R. Curtmola, J. Garay, S. Kamara, and R. Ostrovsky.  Searchable symmetric encryption: improved definitions and efficient constructions.  In ACM CCS, pages 79–88, 2006.
  * [20] M. Dahl, C. Ning, and T. Toft.  On secure two-party integer division.  In A. D. Keromytis, editor, Financial Cryptography and Data Security, pages 164–178, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
  * [21] D. Demmler, T. Schneider, and M. Zohner.  ABY - A framework for efficient mixed-protocol secure two-party computation.  In 22nd Annual Network and Distributed System Security Symposium, NDSS 2015, San Diego, California, USA, February 8-11, 2015, 2015\.
  * [22] J. Dreier and F. Kerschbaum.  Practical privacy-preserving multiparty linear programming based on problem transformation.  In Proceedings of the third IEEE Conference on Social Computing, pages 916–924, 2011.
  * [23] W. Du and Z. Zhan.  Using randomized response techniques for privacy-preserving data mining.  In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 505–510. ACM, 2003.
  * [24] A. J. Duncan, S. Creese, and M. Goldsmith.  Insider attacks in cloud computing.  In 2012 IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications, 2012.
  * [25] U. Erlingsson, V. Pihur, and A. Korolova.  Rappor: Randomized aggregatable privacy-preserving ordinal response.  In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS ’14, pages 1054–1067, New York, NY, USA, 2014. ACM.
  * [26] M. Fredrikson, S. Jha, and T. Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In ACM Conference on Computer and Communications Security, 2015\.
  * [27] M. Fredrikson, E. Lantz, S. Jha, S. Lin, D. Page, and T. Ristenpart.  Privacy in pharmacogenetics: An end-to-end case study of personalized warfarin dosing.  In 23rd USENIX Security Symposium USENIX Security, pages 17–32, San Diego, CA, 2014. USENIX Association.
  * [28] C. Gentry.  Fully homomorphic encryption using ideal lattices.  In Annual ACM Symposium on Theory of Computing, pages 169–178, New York, NY, USA, 2009. ACM.
  * [29] R. Gilad-Bachrach, N. Dowlin, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing.  Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy.  In M. F. Balcan and K. Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 201–210, 2016.
  * [30] O. Goldreich, S. Micali, and A. Wigderson.  How to play any mental game.  In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, pages 218–229, New York, NY, USA, 1987. ACM.
  * [31] O. Goldreich and R. Ostrovsky.  Software protection and simulation on oblivious ram.  Journal of the ACM, 43:431–473, 1996.
  * [32] P. Golle.  A private stable matching algorithm.  In International Conference on Financial Cryptography and Data Security, pages 65–80. Springer, 2006.
  * [33] P. Golle, J. Staddon, and B. Waters.  Secure conjunctive keyword search over encrypted data.  In ACNS 04: 2nd International Conference on Applied Cryptography and Network Security, pages 31–45. Springer-Verlag, 2004.
  * [34] T. Graepel, K. Lauter, and M. Naehrig.  Ml confidential: Machine learning on encrypted data.  In International Conference on Information Security and Cryptology, pages 1–21, 2013.
  * [35] S. Grigorescu, B. Trasnea, T. Cocias, and G. Macesanu.  A survey of deep learning techniques for autonomous driving.  Journal of Field Robotics, 37(3), 2019.
  * [36] S. Halevi and V. Shoup.  Design and implementation of a homomorphic-encryption library.  2013\.
  * [37] S. Halevi and V. Shoup.  Algorithms in HELib.  In International Cryptology Conference, pages 554–571. Springer, 2014.
  * [38] T. Hastie, R. Tibshirani, and J. Friedman.  The Elements of Statistical Learning.  Springer-Verlag, 2001.
  * [39] W. Henecka, S. K ögl, A.-R. Sadeghi, T. Schneider, and I. Wehrenberg.  Tasty: Tool for automating secure two-party computations.  In Proceedings of the 17th ACM Conference on Computer and Communications Security, CCS ’10, pages 451–462, New York, NY, USA, 2010. ACM.
  * [40] E. Hesamifard, H. Takabi, and M. Ghasemi.  Cryptodl: Deep neural networks over encrypted data.  CoRR, abs/1711.05189, 2017.
  * [41] B. Hitaj, G. Ateniese, and F. Perez-Cruz.  Deep models under the gan: Information leakage from collaborative deep learning.  In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, pages 603–618, New York, NY, USA, 2017. ACM.
  * [42] Y. Huang, D. Evans, J. Katz, and L. Malka.  Faster secure two-party computation using garbled circuits.  In USENIX Conference on Security, pages 35–35, 2011.
  * [43] Z. Ji, Z. C. Lipton, and C. Elkan.  Differential privacy and machine learning: a survey and review.  CoRR, abs/1412.7584, 2014.
  * [44] X. Jiang, M. Kim, K. Lauter, and Y. Song.  Secure outsourced matrix computation and application to neural networks.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS ’18, pages 1209–1222, New York, NY, USA, 2018. ACM.
  * [45] F. Kerschbaum.  Frequency-hiding order-preserving encryption.  In Proceedings of ACM Conference on Computer and Communication Security, 2015.
  * [46] V. Kolesnikov and T. Schneider.  Improved garbled circuit: Free xor gates and applications.  In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Part II, pages 486–498, Berlin, Heidelberg, 2008\. Springer-Verlag.
  * [47] R. Lazzeretti and M. Barni.  Division between encrypted integers by means of garbled circuits.  In 2011 IEEE International Workshop on Information Forensics and Security, pages 1–6, Nov 2011.
  * [48] D. Lee, D. Kuvaiskii, A. Vahldiek-Oberwagner, and M. Vij.  Privacy-preserving machine learning in untrusted clouds made simple.  CoRR, abs/2009.04390, 2020.
  * [49] C. Liu, X. S. Wang, K. Nayak, Y. Huang, and E. Shi.  Oblivm: A programming framework for secure computation.  In 2015 IEEE Symposium on Security and Privacy, pages 359–376, May 2015.
  * [50] K. Liu, H. Kargupta, and J. Ryan.  Random projection-based multiplicative data perturbation for privacy preserving distributed data mining.  IEEE Transactions on Knowledge and Data Engineering (TKDE), 18(1):92–106, 2006.
  * [51] W. Lu, S. Kawasaki, and J. Sakuma.  Using fully homomorphic encryption for statistical analysis of categorical, ordinal and numerical data.  In The Network and Distributed System Security Symposium, 2017.
  * [52] S. Mansfield-Devine.  The Ashley Madison affair.  Network Security, 2015(9):8 – 16, 2015.
  * [53] S. Matwin.  Privacy-Preserving Data Mining Techniques: Survey and Challenges, pages 209–221.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2013.
  * [54] P. Mohassel and Y. Zhang.  Secureml: A system for scalable privacy-preserving machine learning.  In 2017 IEEE Symposium on Security and Privacy (SP), pages 19–38, 2017.
  * [55] M. Naehrig, K. Lauter, and V. Vaikuntanathan.  Can homomorphic encryption be practical?  In Proceedings of cloud computing security workshop, pages 113–124, New York, NY, USA, 2011. ACM.
  * [56] V. Nikolaenko, S. Ioannidis, U. Weinsberg, M. Joye, N. Taft, and D. Boneh.  Privacy-preserving matrix factorization.  In ACM SIGSAC conference on Computer and communications security, pages 801–812. ACM, 2013.
  * [57] V. Nikolaenko, U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, and N. Taft.  Privacy-preserving ridge regression on hundreds of millions of records.  In IEEE Symposium on Security and Privacy, pages 334–348, 2013\.
  * [58] O. Ohrimenko, F. Schuster, C. Fournet, A. Mehta, S. Nowozin, K. Vaswani, and M. Costa.  Oblivious multi-party machine learning on trusted processors.  In T. Holz and S. Savage, editors, 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016, pages 619–636. USENIX Association, 2016.
  * [59] P. Paillier.  Public-key cryptosystems based on composite degree residuosity classes.  In EUROCRYPT, pages 223–238. Springer-Verlag, 1999.
  * [60] N. Papernot, P. McDaniel, A. Sinha, and M. P. Wellman.  Sok: Security and privacy in machine learning.  In 2018 IEEE European Symposium on Security and Privacy (EuroS P), pages 399–414, 2018.
  * [61] S. Rane and W. Sun.  Privacy preserving string comparisons based on levenshtein distance.  In 2010 IEEE International Workshop on Information Forensics and Security, pages 1–6, Dec 2010.
  * [62] A. Sachan, D. Roy, and P. V. Arun.  An analysis of privacy preservation techniques in data mining.  In N. Meghanathan, D. Nagamalai, and N. Chaki, editors, Advances in Computing and Information Technology, pages 119–128, Berlin, Heidelberg, 2013\. Springer Berlin Heidelberg.
  * [63] A. D. Sarwate and K. Chaudhuri.  Signal processing and machine learning with differential privacy: Algorithms and challenges for continuous data.  IEEE Signal Processing Magazine, 30(5):86–94, Sep. 2013.
  * [64] S. Sasy, S. Gorbunov, and C. W. Fletcher.  Zerotrace : Oblivious memory primitives from intel SGX.  In 25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-21, 2018, 2018\.
  * [65] Z. Shan, K. Ren, M. Blanton, and C. Wang.  Practical secure computation outsourcing: A survey.  ACM COMPUTING SURVEYS, 51(2), n.d.
  * [66] S. Sharma and K. Chen.  Image disguising for privacy-preserving outsourced deep learning.  In Poster Session of ACM CCS, 2018.
  * [67] S. Sharma and K. Chen.  Confidential boosting with random linear classifiers for outsourced user-generated data.  In Computer Security - ESORICS 2019 - 24th European Symposium on Research in Computer Security, Luxembourg, September 23-27, 2019, Proceedings, Part I, pages 41–65, 2019.
  * [68] S. Sharma, K. Chen, and A. Sheth.  Toward practical privacy-preserving analytics for iot and cloud-based healthcare systems.  IEEE Internet Computing, 22(2):42–51, Mar./Apr. 2018.
  * [69] S. Sharma, J. Powers, and K. Chen.  Privategraph: Privacy-preserving spectral analysis of encrypted graphs in the cloud.  IEEE Transactions on Knowledge and Data Engineering, 2018.
  * [70] S. Shinde, Z. L. Chua, V. Narayanan, and P. Saxena.  Preventing page faults from telling your secrets.  In Proceedings of the 11th ACM on Asia Conference on Computer and Communications Security, ASIACCS16, page 317–328, New York, NY, USA, 2016\. Association for Computing Machinery.
  * [71] R. Shokri and V. Shmatikov.  Privacy-preserving deep learning.  In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, 2015.
  * [72] R. Shokri, M. Stronati, C. Song, and V. Shmatikov.  Membership inference attacks against machine learning models.  2016\.
  * [73] C. Song and V. Shmatikov.  Overlearning reveals sensitive attributes.  In International Conference on Learning Representations, 2020.
  * [74] C. Tsai, D. E. Porter, and M. Vij.  Graphene-sgx: A practical library OS for unmodified applications on SGX.  In D. D. Silva and B. Ford, editors, 2017 USENIX Annual Technical Conference, USENIX ATC 2017, Santa Clara, CA, USA, July 12-14, 2017, pages 645–658. USENIX Association, 2017.
  * [75] L. Unger.  Breaches to customer account data.  Computer and Internet Lawyer, 32(2):14 – 20, 2015.
  * [76] T. Veugen.  Encrypted integer division and secure comparison.  International Journal of Applied Cryptography, 3(2):166, 2014.
  * [77] H. Xu, S. Guo, and K. Chen.  Building confidential and efficient query services in the cloud with rasp data perturbation.  IEEE Transactions on Knowledge and Data Engineering, 26(2), 2014\.
  * [78] A. C. Yao.  How to generate and exhange secrets.  In IEEE Symposium on Foundations of Computer Science, pages 162–167, 1986.
  * [79] S. Zahur, M. Rosulek, and D. Evans.  Two Halves Make a Whole, pages 220–250.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2015.