Practical Privacy-Preserving Machine Learning using Fully

Homomorphic Encryption
Michael Brand Gaëtan Pradel∗
School of Computing Technologies, RMIT University Royal Holloway, University of London
Melbourne, Vic, Australia Information Security Group
INCERT GIE Egham, United Kingdom
Leudelange, Luxembourg INCERT GIE
[Link]@[Link] Leudelange, Luxembourg
gpradel@[Link]

ABSTRACT financial data includes confidential transactional details that require

Machine learning is a widely-used tool for analysing large datasets, protection. In response, privacy-related regulations such as the
but increasing public demand for privacy preservation and the General Data Protection Regulation (GDPR) [22] in the European
corresponding introduction of privacy regulations have severely Union and the Health Insurance Portability and Accountability Act
limited what data can be analysed, even when this analysis is for (HIPAA) [12] in the United States of America have been enacted,
societal benefit. Homomorphic encryption, which allows compu- which require data holders to preserve the privacy of sensitive or
tation on encrypted data, is a natural solution to this dilemma, personally-identifiable data.
allowing data to be analysed without sacrificing privacy. Because Numerous techniques have been explored for enhancing privacy
homomorphic encryption is computationally expensive, however, in data processing and analysis. These include cryptography, differ-
current solutions are mainly restricted to use it for inference and ential privacy, federated learning, and the use of secure enclaves
not training. [36, 56], with many tasks requiring a combination of such tools
In this work, we present a practically viable approach to privacy- [39, 54].
preserving machine learning training using fully homomorphic In our work, we chose to tackle the privacy challenge using
encryption. Our method achieves fast training speeds, taking less homomorphic encryption (HE) [40]. Introduced in 1978 by Rivest et
than 45 seconds to train a binary classifier over thousands of sam- al. [52], HE enables computations to be performed on encrypted
ples on a single mid-range computer, significantly outperforming data without requiring decryption, so that the privacy of the data
state-of-the-art results. can be preserved throughout the entire analysis process, i.e. both
while the data is at rest and in use. Specifically, our goal was to use
KEYWORDS HE in order to enable privacy in Machine Learning, by introducing
practical tools that will allow the training of new Machine Learning
Privacy, Fully Homomorphic Encryption, Machine Learning Train-
models to be performed over encrypted data.
ing, Support Vector Machines
The idea of Privacy Preserving Machine Learning (PPML) is,
itself, not new [1]. However, despite numerous notable advance-
1 INTRODUCTION
ments made over the past two decades (see [36] for a survey), PPML
In recent years, Machine Learning (ML) techniques have become remains computationally challenging. As an example, consider re-
increasingly popular for analysing and extracting insights from cent results by Chillotti et al. [19] that presented PPML inference
large and complex datasets. With the rise of powerful computing using the Concrete library [18] which implements a fast variant
systems and the availability of vast amounts of data from various of the CGGI scheme [17], a fully homomorphic encryption (FHE)
domains, ML has found applications in numerous fields such as scheme. Despite great efforts by the designers to render FHE prac-
healthcare, finance, biometric recognition, surveillance and many tical, the private inference performed by their PPML models of
others. As examples, ML is used in the medical field to analyse various complexity still impose a significant computational burden.
patient data to help with disease diagnosis and treatment, while in On a standard personal computer, using 128-bit equivalent security,
finance, it is used for fraud detection, risk assessment, and trading the computation time required for even a single FHE-encrypted
strategies [2, 48]. inference ranged from over 100 seconds to almost 500 seconds,
However, the use of such techniques on sensitive data has raised representing a non-trivial computational expense. Furthermore,
significant concerns regarding data privacy [3, 36]. For example, their most complex algorithm for performing FHE-encrypted infer-
medical data contains highly sensitive personal information and ence still exhibits degradation of more than 10% in classification
∗ Corresponding author
accuracy, compared to inference on unencrypted data.
Moreover, similar to other related works, Chillotti et al. solely
This work is licensed under the Creative Commons Attribu- addresses the use of encrypted data for ML inference. Training is
tion 4.0 International License. To view a copy of this license
visit [Link] or send a
done exclusively in plaintext. This is because training ML models
letter to Creative Commons, PO Box 1866, Mountain View, CA 94042, USA. is a far more computationally-intensive task than inference, and
Proceedings on Privacy Enhancing Technologies YYYY(X), 1–15 performing it on encrypted data is unavoidably much slower and
© YYYY Copyright held by the owner/author(s).
[Link]
1
Proceedings on Privacy Enhancing Technologies YYYY(X) Brand and Pradel

more resource-intensive still, rendering it impractically slow under The patients themselves have access to their own information,
most current approaches. but while they may entrust their own health providers with han-
In this work, we focus exclusively on tackling the practicality of dling it, not all of them will wish to entrust the research institute
the much-heavier model training phase. We investigate training ML with the same data.
models on encrypted data using levelled FHE, which is a relatively One can imagine here three potential populations of patients. The
light flavour of FHE computation. (See Section 2.1 for an explanation first is the patients who do not want to assist the research institute
of levelled FHE and its relation to other types of HE computation.) in building its models. For them, privacy regulation ensures that
Levelled FHE can be used whenever the desired algorithm’s the data is theirs, and cannot be used without their consent. The
multiplicative depth can be bounded in advance. We show how second is the patients who feel free to provide their data (including
such bounding is always possible to do in the context of PPML both test results and final diagnosis) to the research institute, for the
training, and how we were able to design our algorithms so as to purpose of developing the model. This is the group that traditionally
minimise the computational depth required for such training. models were built on, and, in our scenario, can still be used, e.g., as
To demonstrate our technique in a simple ML context, we se- a verification group and to provide various types of sanity-checking
lected the Support Vector Machine (SVM) learning algorithm as our for the newly-developed model.
underlying ML model to be trained. We believe that this still leaves out, however, a large portion of
SVM is a widely used algorithm for classifying data in machine the population. This is namely the population of patients who do
learning due to its ability to handle complex datasets and produce wish to assist in the development of the new diagnosis tool, but do
robust predictions. not wish to expose for this their personal details. They wish their
Here, we show how to train a linear SVM, although the same details to remain private, and wish their participation in the model
basic technique can also be applied to more complex models.1 training population to remain anonymous.
In order to demonstrate practically feasible model training under It is this third group that our research results aim to cater for.
FHE, overcoming the computational challenges involved, we em- Our PPML paradigm allows these patients to contribute their data
ploy a well-established technique known as the client-assisted (CA) to potentially-life-saving research, without having to sacrifice for
computation model. The existing approaches for CA are reviewed this their privacy. Similar instances of this problem, which can be
in Section 1.3, and our own flavour of it is explained in Section 1.4. tackled with our methods, appear also beyond medical research,
In this paper, we show that CA computation can be used to both wherever data analysis is done with the ultimate goal of powering
significantly enhance the speed of PPML and to expand the scope societal benefits. Allowing this third group of participants into such
of what can be performed under levelled FHE, to the extent that models will enable models to be trained on larger training sets, and
training machine learning models over encrypted data becomes ones less biased by participant self-selection.
practical and scalable.
1.1.2 Privacy model. The motivating example above dictates the
1.1 Problem statement privacy model that our solution must work under. This privacy
model is somewhat more nuanced than typically used in cryp-
1.1.1 Motivating example. Consider the following scenario from
tography, in that parties are not simply considered “trusted” or
the medical world, in which a research institute wants to develop
“untrusted”. Rather, each of the actors in our model is considered
a new tool for diagnosing a particular condition, a tool which the
trusted in certain dimensions by certain other actors.
research institute then intends to sell to hospitals. The hospitals
To describe the privacy model explicitly, let us first introduce
are expected to perform various tests in order to measure multiple
the relevant actors.
patient attributes, and the tool will use the test results in order
to determine the likelihood that the patient is suffering from the Client: This is the research institute in our motivating example. It
condition in question. This will offer the hospitals better diagnoses, is the party building the new model.
and enable them to be more judicious in the choice of follow-up Model users: These are the hospitals in our example. They ulti-
tests, thus eliminating more invasive testing where it is superfluous mately receive the model and use it. In our example, hospitals
and improving patient care. use the model in order to diagnose their own new patients,
For this, the research institute wants to develop a new ML model after the model is fully developed.
that will drive the diagnosis tool. To train such a model, the research Data Owners: These are the patients in our motivating example.
institute would optimally need access to the widest possible patient They own their own data, which the model is then trained
population. For each patient, the research institute would need both on.
the patient’s initial test results and their final diagnosis. The test Cloud: This final actor is introduced here for the first time. It was
results will form the attributes fed into the model, and the final not mentioned in our motivating example because this actor
diagnosis will be the model’s target variable. is not part of our problem scenario. Instead, it is part of
Hospitals have access to all this information. However, due to our solution design. The Cloud performs the majority of the
privacy regulations, the hospitals cannot share it with the research processing in computing the new model. In our example, this
institute. role would presumably be taken by a cloud service provider
hired by the research institute for this purpose.
1 Duringresearch, we also trained our SVM with non-linear features, but these did not Because the data being processed in this problem scenario be-
improve overall accuracy, so we do not report the results here. longs to the Data Owners, they are the party that determines, for
2
Practical PPML using FHE Proceedings on Privacy Enhancing Technologies YYYY(X)

the most part, who is trusted to what. Specifically, the trust mapping 1.2 General solution design
of the various actors is as follows. Homomorphic encryption typically involves the generation of a
key triplet. This key triplet is composed of a secret key used for
Client: The Data Owners are willing to have their data used for decryption, a public key for encryption, and an evaluation key for
the purpose of building a new ML model. The end model manipulating the encrypted data such as by performing on it arith-
will be visible to the Client, and the Data Owners are equally metic operations (but not enabling encryption or decryption).
willing to share with the Client also other non-identifiable In our general solution design, which addresses the above prob-
statistics for this purpose. As a general rule, if a value is the lem statement, it is the Client who generates the key triplet. While
sum of a particular statistic, computed symmetrically over the secret key is kept solely by the Client, the public key is made
the data of each Data Owner, it is usually considered non- public (and by this reaches any Data Owners who may wish to par-
identifiable, and permitted for the Client to see. The Client ticipate in the model build), and the evaluation key is shared with
must not be exposed to personal data, however, including the Cloud. This is the only case of direct communication between
both personal attributes (e.g., test results), and the value of the Client and the Data Owners.
the target variable for each participant. In particular, the Data Owners who wish to participate can now do so by encrypt-
Client does not know who is participating in their model ing their data and sending it directly to the Cloud for processing.
build. Because the Cloud has no access to the decryption key, their privacy
Model users: The Model Users receive the model only once it is is preserved.2
fully constructed. It is at this point no longer considered In principle, the Cloud could have at this point performed all
privacy sensitive from a Data Owner point of view. Model processing under homomorphic encryption, sending only the final
users use the derived model in plaintext: when a new patient output to the Client, for the Client to decrypt. In our solution,
is treated at a hospital, the treating doctors are expected to however, we show that far better results can be obtained by use
know both their test results and any diagnoses in order to of a client-assisted computation model. In this model, the Cloud
provide optimal treatment. (New patients will consent to can communicate information to and from the Client. We show
this, as is the case in any medical treatment.) that despite the fact that all such communication is required to be
Data Owners: Data Owners are clearly exposed to their own data. encrypted, privacy non-sensitive general statistics, it can still be
However, Data Owners have no trust relationship with any used effectively to speed up the work of the Cloud.
other Data Owner. Whether a person participates as a Data
Owner in the construction of any new diagnosis tool, and 1.3 Related work
what data they contribute, is entirely their own private in-
1.3.1 Privacy during inference. Cryptographic privacy-enhancing
formation.
technologies (PETS) are many, including, e.g., such tools as func-
Cloud: The trust model for the Cloud is the most nuanced. Data
tional encryption and garbled circuits [56]. The following is a review
Owners do not trust the Cloud with any of their personal
of literature related specifically to HE-powered PPML, which we
data, and not even with general statistics about their data.
use to introduce some of the techniques we have built upon. Within
However, for the Cloud to be able to process Data Owners’
this literature, it is notable that several works employ distributed
data, the Data Owners must trust the Cloud in two important
computation in conjunction with HE to maintain privacy.
ways. First, Data Owners (and by extension also the rest
We begin by presenting the research efforts that concentrate
of this data ecosystem) must trust the Cloud to truthfully
solely on the inference phase of PPML, which employ FHE for
process their data as per the instructions given to the Cloud
encryption without incorporating distributed computation.
by the Client. The Cloud is expected to not maliciously plant
A pioneering work in this field was Gilad-Baschrach et al.’s
bad data into the model. Second, Data Owners must trust
CryptoNets [24], from 2016. Here, a neural network model that
the Cloud not to collude with the Client against the wishes
was previously trained on clear data was shown to be usable for
of the Data Owners. In both cases, this is on a par with the
prediction over new encrypted inputs, by using FHE encryption for
trust that one normally extends to cloud hosting services,
the data and performing the prediction under this encryption. The
and underpins much of the viability of the Internet economy
solution was applied on the MNIST dataset [34], demonstrating a
at large.
99% accuracy for a throughput of 59, 000 predictions per hour.
One of the main challenges that Gilad-Baschrach et al. had to ad-
As can be seen, in this problem scenario it is only model training
dress in order to use HE in neural networks is that all homomorphic
that requires a privacy-preserving implementation. Once the model
operations that are enabled even by FHE are polynomial evalua-
is trained, it can be viewed in plaintext by the Client, which allows
tions on the encrypted inputs. This makes it difficult to compute in
the Client to package it as efficiently-running software for large-
the encrypted domain even such common functions as taking the
scale deployment. It will be run on plaintext data, and will return
square root of a number, comparing numbers, or even testing for
plaintext results. It is still possible that the Client, when packag-
equality. [11].
ing the model in software, may choose to use various software,
hardware and/or legal protections in order to protect the Client’s
2 Technologies that hide, e.g., Data Owners’ IP addresses when such data is uploaded
investment and prevent the model from being, e.g., exploited by
to the Cloud are beyond the scope of the present paper, but can certainly be used to
commercial competitors, but any such protection is beyond the ensure that Data Owners do not need to reveal any of their private identifiers to the
scope of our present work. Cloud for this purpose.
3
Proceedings on Privacy Enhancing Technologies YYYY(X) Brand and Pradel

Unfortunately, such functions form a fundamental part of neural security parameters for SVM prediction. The authors reached an
networks, e.g. appearing in typical neuron activation functions [44]. execution time of 1.25 seconds per prediction on a multi-core CPU
The solution used by CryptoNets was polynomial substitution. platform without accuracy degradation due to the use of FHE.
Namely, the (non-polynomial) sigmoid activation function of the tar- All solutions presented so far, despite tackling only the inference
get neural network was replaced by squaring, a simple-to-compute, phase on encrypted data, remain relatively slow. As discussed, one
low-degree polynomial function. option is to partner HE and distributed computation in order to
An alternative method to compute a non-polynomial function enhance the overall performance and get closer to real-world appli-
over encrypted data in HE-powered PPML is to prepare in advance cability. While this can be done via standard parallelisation methods,
a look-up table for the function over a discrete set of values. A other alternatives, with their own advantages and disadvantages,
solution of this type was presented by Crawford et al. [21]. exist.
Another commonly used technique, which is the one we applied An example is Secure Multi-Party Computation (MPC) [25]. MPC
in our work, is low-degree polynomial approximation. This has methods rely on the separation of computation in a way that each
been used, e.g., by Chabanne et al. [13] to extend CryptoNets. Their party individually is not exposed to private information, but a col-
neural network architecture was implemented with a ReLU activa- lusion of all parties breaks any privacy preservation. Such methods
tion function that was approximated using a polynomial function to are typically characterised by much lighter computations, as com-
support computation over encrypted data. In this paper, we present pared with FHE methods, but heavy communication loads.
a novel method that enabled us to approximate the ReLU function MPC methods were first typically restricted to only work under
significantly more accurately, however. partial homomorphic encryption (PHE) schemes. These are schemes
An important component in effective use of low-degree polyno- that support only one type of group operation on encrypted data,
mial approximations is batch normalisation, a technique that aligns are not universal in their computation capabilities, and have been
the distribution of inputs to the approximated function, thus guard- shown to not be resilient against quantum attacks [8]. PHE is dis-
ing against function evaluations outside the well-approximated cussed in greater detail in Section 2.
domain. This, too, is a technique employed by Chabanne et al. that The earliest works combining HE with MPC are Barni et al. [7]
our paper incorporates as well. and Orlandi et al. [45], who managed to execute the inference phase
The authors achieved a model with minimal accuracy degra- of a small neural network in around 10 seconds. These performance
dation between private and non-private inference. However, no results were obtained thanks to an interactive protocol involving a
timing results were reported. server and a client, and utilise an additive PHE scheme.
In 2019, Hesamifard et al. [28] presented another work based Even without MPC, the use of PHE instead of FHE has been
on the use of polynomial approximations of the ReLU function. A a popular avenue for obtaining speed increases, and this due to
range of approximation techniques was evaluated in the paper, the significantly more lightweight nature of PHE operations. So-
including the application of numerical approximation, the Taylor lutions such as MiniONN [37], Chameleon [51] and Gazelle [32]
series method, Chebyshev polynomials (in both a standard and a all introduced increasingly performant methods compared to their
modified form) and an approach based on the derivative of the ReLU predecessors. However, all were ultimately limited by their reliance
function. They found that the more successful approach is the latter, on PHE.
which is based on the observation that the derivative of the ReLU The use of FHE becomes necessary for computing more complex
function is a step function, and that the sigmoid function can be operations over encrypted data, or when quantum resilience is an
used as a smooth approximation to it. Thus, they approximated issue: most FHE schemes used in the literature are quantum-safe
the sigmoid function with a polynomial and then integrated it to [4].
obtain an approximation of the ReLU function. By contrast, our In 2020, Boemer et al. [9] presented a hybrid FHE-MPC frame-
method is based on approximating the “second derivative” of the work called MP2ML for ML inference in the encrypted domain
ReLU function using Chebyshev polynomials, and then integrating using the CKKS scheme, extending the nGraph-HE compiler [10].
it twice. Despite using only a low-degree polynomial approximation, They obtained similar results compared to state-of-the-art work
Hesamifard et al. achieved 99% accurary on the MNIST dataset, and but with stronger security properties.
were able to run at a throughput of 164, 000 predictions per hour,
outperforming CryptoNets, even with Chabanne et al.’s extensions. 1.3.2 Privacy during model training. All work presented so far
In 2022, Lee et al. [35] introduced privacy-preserving ML infer- addresses only the inference phase of ML on encrypted data and
ence that uses RNS-CKKS [15], a bootstrapped variant of the CKKS does not cover the training phase. The training of ML models poses
scheme [16]. CKKS was itself an important milestone in PPML, in greater computational challenges than the inference phase, and
that it was the first HE scheme that could perform floating point only few works have endeavoured to address it.
computation, thus being practically applicable for defining ML al- In 2019, Nandakumar et al. [43] showed that it is possible to train
gorithms. While the accuracy of the model on encrypted data was a neural network on encrypted data without any form of distributed
high, at three hours per classification it was still much too slow to be computation. They used the HElib library [27] to implement a Sto-
practically usable, highlighting the limitations of using unqualified, chastic Gradient Descent (SGD)-based training of a neural network,
non-levelled FHE schemes for ML. and demonstrated that the computational efficiency of encrypted
Similar to the works on neural networks, PPML inference using training can be improved using several techniques such as simplify-
FHE has also been implemented over SVM models [6, 30]. Most ing the network, selecting an appropriate data representation, and
recently, Badawi et al. [5] employed CKKS with 128-bit equivalent optimising data packing within the ciphertexts.
4
Practical PPML using FHE Proceedings on Privacy Enhancing Technologies YYYY(X)

The results of Vizitiu et al. [59] are presently the best in class The method reaches practical speeds in running privacy-preser-
in terms of speed. They performed both training and inference of ving model training: less than 45 seconds were necessary to train a
deep learning-based applications on encrypted data also without binary classifier on 8, 000 samples, each with 30 numerical features,
relying on either MPC or CA. A customized version of the MORE when running on a single computer (we used a Dell XPS 15 laptop
encryption scheme [33] was employed by the authors, which was and an Ubuntu workstation), without any use of parallelisation or
specifically designed to operate on floating-point data in order GPU acceleration. Training complexity is linear in the number of
to accommodate ML applications. In this way, they were able to features and the number of ciphertexts necessary to hold all samples.
obtain the same accuracy as in the unencrypted domain at the In our design, one ciphertext vector can hold 8,192 samples, so only
cost of a 30-fold increase in training time (which is a remarkably a single vector was required for each feature.
small factor). However, their solution comes with some caveats: When training on a public medical dataset, the WBC dataset,
the MORE encryption scheme is subject to some security concerns we show that such training on encrypted data yields a model with
[57, 58] which do not apply to the CKKS scheme, the algorithm we 99% accuracy. (As per our problem statement, actually running the
use in this work. classification under encryption was not a goal of this project, so
Nevertheless, most works in the field use either MPC or CA, and this 99% was evaluated in plaintext on a held out set.)
attain by this results that are an order of magnitude faster than To obtain our results, we incorporated a set of carefully chosen
those of Nandakumar et al.. techniques and design considerations that prioritise pragmatic con-
One such work is SecureML by Mohassel and Zhang [41]. They cerns related to computational efficiency and processing capacity:
showed how to perform ML training and inference in a privacy-
State-of-the-art cryptography: We opted for the levelled version
preserving way in a two-party computation model, i.e. one where
of the CKKS FHE scheme. CKKS competes with state-of-the-
Data Owners share their sensitive data in encrypted form among
art time-performance [31] and is able to process floating-
two non-colluding servers that share the computational work. In
point data directly.
their study, the authors achieved model training times on the or-
Vectorised computations: CKKS operates in a SIMD architecture,
der of several thousand seconds in offline settings, and hundreds
allowing for the processing of multiple operands in a single
of seconds online. The difference between their work and our ap-
instruction. Our algorithm has been optimised with SIMD
proach is two-fold. First, they did not use FHE, as we do, but rather
operations in mind, further improving overall performance.
a combination of garbled circuits and PHE. Second, they use MPC
Client-assisted computational model: We carefully partitioned
rather than the CA model.
the computation so that all “heavy lifting” is done by the
In 2018, Hesamifard et al. [29] presented CryptoDL, a solution
Cloud, which mass-processes data under encryption. Flow
for both PPML training and inference, using FHE. This solution
control and the computation of run-state parameters, how-
is much closer to our approach in that it employs levelled FHE, is
ever, are all relegated to the Client. In this way, not only
built over CA computation instead of MPC, only uses client-server
does each party in the computation lean on its strengths, the
communication when necessary (rather than at each operation, as
overall communication between them is also minimised.
SecureML does), and relies on polynomial approximations. They
Frugality in the polynomial approximations: We used only
used a more sophisticated neural network than us, which they tested
low-degree polynomial approximations of the non-linear
on three small datasets. However, they used only 80-bit equivalent
functions necessary for the machine learning training. This
security, which enabled them to utilise much faster homomorphic
allowed us to work with low CKKS parameters that support
operations, and they parallelised model training over the cores of
only a small multiplication-depth but translate to fast FHE
a twelve-cores machine, allowing them significantly more CPU
operations and small-sized ciphertexts, without compromis-
power. Even so, our 128-bit equivalent results obtained on a dataset
ing on security strength. (Our parameters were set for 128-bit
with almost double the number of features were still 55% faster
equivalent security.) A novel approximation technique us-
(when accounting for the dataset size differences), and showed
ing Chebyshev polynomials allowed us to obtain sufficiently
better accuracy.
accurate approximations even under the degree constraint.
Park et al. [47] presented for the first time SVM training using
Normalisation: Polynomial approximations might only be valid
FHE. (See also [46].) They used the CKKS scheme and its SIMD
on a certain interval. To keep the data within the target
architecture in their implementation, and performed PPML training
interval and mitigate precision issues and overflows, we
on various datasets, including the Wisconsin Breast Cancer (WBC)
used a batch normalisation technique on the data.
dataset [60], which we also trained on. Although their approach
Application of rapid convergence methods: We used a re-
was similar to ours, we were able to achieve significantly better
stricted version of Newton iterations to speed-up the conver-
performance, reducing per-iteration times by a factor of 4.6 and
gence of our training algorithm, in order to be able to work
reaching convergence in 40% less iterations, despite working on
with less algorithm iterations and obtain an overall-faster
more features and attaining better model accuracy.
implementation. This is as opposed to gradient descent or
SGD methods.
The selection and use of these techniques and methods serve
1.4 Contributions as the principal contributions of this paper, providing a blueprint
We present a practically viable PPML training method that uses for developing practical PPML training through FHE within the
FHE in the CA computational model. client-assisted computational model.
5
Proceedings on Privacy Enhancing Technologies YYYY(X) Brand and Pradel

1.5 Outline of the paper based on the hardness of the Ring variant of the Learning With Er-
The rest of this paper is organised as follows. rors (RLWE) problem [38, 50]. RLWE has been proven to be at least
Section 2 introduces the necessary notions in homomorphic as hard as certain worst-case lattice problems. These problems are
encryption and machine learning. Section 3 presents the technical considered to be computationally hard problems for both classical
details of our approach. Section 4 describes our experimental setup and quantum computers.
and results. Lastly, a short conclusions section follows. Unlike its predecessors, CKKS is suited for non-integer compu-
tation, supporting approximate arithmetic over encrypted real and
2 PRELIMINARIES complex numbers: its arithmetic is performed on block floating
point [42] numbers. This crucial property makes CKKS a highly
2.1 Homomorphic encryption suitable option for implementing ML algorithms, which typically
Homomorphic encryption is a type of encryption that enables com- work with floating-point data.
putations over encrypted data without ever decrypting it. It has In addition to its natural compatibility with the floating-point
been considered since 1978 [52] as the Holy Grail of cryptography domain, the CKKS scheme incorporates a SIMD architecture. This
[26]. allows the scheme to perform computations on multiple data points
The first HE schemes, such as RSA [53], allowed only a single at once, greatly enhancing its processing speed and efficiency for
type of operation, typically either addition or multiplication, to be computations that can be formulated as vectorised operations.
computed on encrypted data. Such systems are known as partially
homomorphic encryption (PHE) schemes. While holding the promise
for enabling practical computation on encrypted data [49], PHE 2.2 Machine learning
schemes are inherently limited. A PHE scheme that only supports Supervised learning is a process in which ML models are trained to
addition and subtraction, for example, can only ever compute linear map vectors of input features into output labels based on a training
functions over its inputs, which is insufficient for general-purpose set that contains examples of features-label pairs, known as samples.
computing, or even for the training of the simplest of ML models. During training, the ML algorithm learns from the labelled samples
To address the limitations of PHE schemes and support Turing- a model that can predict the output label for new, unseen input
complete computation over encrypted data, HE schemes have been feature vectors. The process of training ML models involves finding
developed that support full ring operations (i.e., both additions and a set of parameters that optimises (in some sense) the performance
multiplications) over encrypted data. Such schemes are called fully of the model on the training data. Once the model has been trained,
homomorphic encryption (FHE) schemes. it can be applied to new, unseen data to make predictions about the
Many FHE schemes support any number of additions but only output label.
computations of up to a predefined multiplication depth. These are Training such an ML model typically involves defining a loss
known as levelled FHE schemes. Despite this apparent restriction, function that measures the difference between the predicted output
levelled FHE schemes demonstrate great performance, particularly of the model and the true output, and then using an optimisation
when compared to unqualified FHE schemes that support unlimited algorithm to minimise this loss. Such a loss function may also
computations over encrypted data. encapsulate other factors. For example, it may include penalties,
Such unlimited FHE schemes were pioneered by Gentry [23] in known as regularisation terms, that are meant to keep the model
2009, through a technique known as bootstrapping. The fundamental from overfitting its training data (thus reducing its usefulness on
concept behind bootstrapping is that the decryption algorithm for a new data), e.g. by penalising models for their complexity.
given ciphertext can be executed as an algorithm under levelled FHE. To test the usefulness of the model on new data and validate
This enables the ciphertext to be “refreshed”, effectively removing that it did not overfit its training data, the labelled dataset available
the limitation on what can be computed over encrypted data, but at is commonly separated into a training set and a test set. The main
the cost of transforming each homomorphic operation into a heavy idea is then to minimise the ML model’s loss over the training set
bootstrapping process. and then evaluate how well it performs on the test set.
For the most part, the availability of an unlimited number of Even though classification accuracy can be a simple binary “cor-
multiplication operations is not necessary: if one knows in advance rect” or “incorrect”, the loss functions used in ML training are
what computation one is attempting, one only needs to set the usually smooth, or at least differentiable, functions. This allows for
levelled-FHE parameters so as to allow the desired number of mul- efficient optimisation using gradient-based methods, such as gradi-
tiplications, and this usually results in order-of-magnitude time ent descent. In the absence of local optima, gradient-based methods
savings. can be used to find the optimal model parameters, even for general
In our implementation, we broke up the computation of Newton models.
iterations so that each homomorphic computation only needs to Viewed in this context, our work can be seen as an exploration
calculate one step of the iteration. As a result, the total needed into efficient methods to perform function optimisation under HE,
computation depth is known in advance, regardless of the number with general applicability across many ML model types.
of iterations. We were consequently able to utilise fast, levelled- The specific classifier that we use in this paper as an example is
homomorphic operations. the linear binary classifier. This can be viewed as a linear Support
Specifically, we use the CKKS FHE scheme in its levelled version. Vector Machine (SVM) [20], although it can also be viewed as the
CKKS is a new type of FHE scheme, considered as the precursor of training of a perceptron, which is the simplest example of a neural
the “fourth-generation” [40] of FHE. The security of this scheme is network.
6
Practical PPML using FHE Proceedings on Privacy Enhancing Technologies YYYY(X)

In all cases, the purpose of training is to find a vector of weights, If a computation involves no brackets at all, and therefore no
(𝑤 1, · · · , 𝑤𝑛 ), and a bias, 𝑏, such that given a vector of inputs communication, it can refer to a standalone computation either by
(𝑥 1, · · · , 𝑥𝑛 ), the sign of the Cloud or by the Client. The two can be distinguished based on
𝑛
∑︁ whether or not the result features a hat notation. As an example, if
𝑥𝑖 𝑤 𝑖 + 𝑏 Algorithm 1 itself was written in this notation (rather than merely
𝑖=1 acting to explain the SUM() operator), all variables in it would
best predicts the class label associated with the input vector. have had hats in their names, because it is an algorithm only run
In vector notation, the equation for the separating hyperplane by the Cloud.
can be written as The only other values used in our system are those that are
pre-computed by the Data Owners prior to being uploaded to the
x · w + 𝑏 = 0, (1)
Cloud. Each Data Owner 𝑖 sends to the Cloud the following, each
where w is the normal to the hyperplane. number encrypted in its own ciphertext:

3 PPML TRAINING • −𝑦𝑖 , and

• For each 𝑗 ∈ [1, ℓ]:
Let 𝑥𝑖 𝑗 ∈ R, with 𝑖 ∈ [1, 𝑚] and 𝑗 ∈ [1, ℓ], be the value of feature 𝑗
◦ 𝑥𝑖 𝑗 ,
of the 𝑖 th training sample. These values will be arranged in a matrix
◦ 𝑥𝑖2𝑗 , and
x, such that x𝑖∗ is a row vector of the entire 𝑖 th sample and x∗𝑗 is a
◦ 𝑥𝑖 𝑗 𝑦𝑖 .
column vector of the 𝑗 th feature. Let y, a column vector of length 𝑚,
be the target variable, encoding for each sample a class designation Where these values which were communicated by the Data Owners
as either 1 or −1. are used in a formula, they are enclosed in braces (“{}”).
We use the following notation to describe the algorithm’s execu- Unlike communications from the Client, when a Data Owner
tion in the CA model: values that are computed by the Client and sends a ciphetext vector to the Cloud, this vector includes the en-
sent to the Cloud will be denoted in double brackets (“⟦𝑥⟧”). All crypted value in only its first element. When the Cloud uploads
such communication will be in ciphertext, each value transmitted these, it uses cyclic shifting to map each Data Owner’s information
in its own, separate ciphertext, and each such ciphertext storing to its own unique position, then sums together vectors that under-
the communicated value across every one of its elements. went different shifts into a single vector, packing as many values as
When elements of ciphertext vectors that are stored by the Cloud possible, from different Data Owners, that are all of the same value
are summed together by the Cloud and sent to the Client, this will type.
be denoted by the function “SUM()”. Such summation is performed We refer to this as column-oriented storage. It enables efficient use
by Algorithm 1. In the algorithm, “|𝑣 |” indicates the element length of CKKS’s SIMD architecture for both intra-vector and inter-vector
of the vector 𝑣, and “𝑠 ≪ 𝑖” indicates cyclic shift. operations.

Algorithm 1: Vector summation algorithm. 3.1 Normalisation

Input : A ciphertext vector, 𝑣. Because the vast majority of the computation in this algorithm is
Output : Ciphertext vector 𝑠, where each element contains done over encrypted data, it is important throughout the algorithm
Í
𝑖 𝑣𝑖 . to keep information from becoming too large (and susceptible to
𝑠 ←𝑣 overflows) or too small (and susceptible to loss of precision). We
𝑖←1 account for this in the algorithm in two places. First, when the
while 𝑖 < |𝑣 | do Data Owners upload their data, they do so in units of measure-
𝑠 ← 𝑠 + (𝑠 ≪ 𝑖) ment that are appropriate, so that data values come at a consistent
𝑖 ← 2𝑖 order of magnitude. This order of magnitude does not need to be
return 𝑠
too precisely prescribed, because all such values are immediately
standardised when uploaded to the Cloud, so as to have zero mean
In our computing model, this is the only type of information and unit variance. Second, at each iteration of the algorithm, the
that is allowed to be communicated from the Cloud to the Client. Client communicates to the Cloud a scaling factor, 𝛾, such that
If the number of training samples exceeds what can be packed computations are effectively done on 𝛾𝑥, rather than on 𝑥.
into a single vector, all vectors are first summed together, and then The first thing the algorithm needs to compute is therefore the
Algorithm 1 is run on the result. The output value, 𝑠, is returned mean and the variance for each feature, in order to remove them
to the Client as a ciphertext vector, and the Client decrypts it and from the data. This is done as described in Algorithm 2. This al-
extracts its value (from any element). gorithm removes the mean from the data in the Cloud, but only
Operations outside brackets, meaning that they are executed computes the standard deviation at the Client. It would have been
by the Cloud, can only be linear operations. In order to visually possible to completely standardise the data by multiplying it by 1/𝜎,
distinguish variables that are stored by the Cloud, we use for these but this would have cost us an extra multiplication. Instead, the
names that feature a hat notation (e.g., “𝑥”).ˆ The values 𝑚 and ℓ, multiplicative factor 𝛾, which is applied on the data each iteration,
which are the only values known to the Cloud in plaintext, do not already incorporates the 𝜎 factor when communicated from the
receive a hat notation. Client to the Cloud.
7
Proceedings on Privacy Enhancing Technologies YYYY(X) Brand and Pradel

Algorithm 2: Calculate the variance and remove the mean. of optimisation the optimising algorithm would steer to avoid such
Input : A feature vector, x∗𝑗 . cases.
Output : Mean-removed x̂∗𝑗 and standard deviation 𝜎.


𝜇 ← SUM {x∗𝑗 } /𝑚 3.2 The training algorithm
√︂
We use an iterative training algorithm whose purpose is to find the
 
SUM {x2∗𝑗 } /𝑚−⟦𝜇 2 ⟧
𝜎← 𝑚−1 classifier parameters (w, 𝑏) that minimise the loss function
x̂∗𝑗 ← {x∗𝑗 } − ⟦𝜇⟧  
return x̂∗𝑗 , 𝜎 ˜
𝐿(w, 𝑏) = SUM𝑖 ℎ({−𝑦 𝑖 }(x𝑖∗ · ⟦w⟧ + ⟦𝑏⟧)) . (2)

This is an approximated form of hinge loss, which is a common loss

The purpose of multiplying by a factor 𝛾 at each iteration, beyond function for training the perceptron algorithm. In our case, because
the issue of maintaining the integrity of the encrypted value as the approximation is least accurate around zero, and smoothes over
described above, is to allow us to apply on the data a non-linear the function’s transition to zero, it also introduces a built-in margin,
function. In order to compute, for example, ℎ(𝑥), where ℎ is the so this loss can equally be thought of as the minimisation of slack
hinge function, ℎ(𝑥) = max(𝑥, 0), we replace ℎ by a polynomial variables in SVM optimisation.
approximation, ℎ, ˜ but any such polynomial approximation is only This optimisation is subject to ∥w∥ = 1, meaning that the w
valid within a specific range. We have designed all our polynomial is a unit vector indicating the normal to the decision boundary
approximations to be accurate within the range −1 ≤ 𝑥 ≤ 1. As a hyperplane. Without this constraint, it would have been possible
result, we continuously rescale our data to make sure that all of it to improve the loss simply by scaling w.
is exactly within this range. We note that the entire loss function 𝐿(w, 𝑏) can be computed
We try to maximise the spread of 𝑥 values within the allowed with a multiplication depth of only 2 plus the multiplication depth
range, because our approximations are also most effective away ˜ In our implementation, we use a ℎ˜ polynomial of degree 14,
of ℎ.
from zero. However, because within a single optimisation iteration which we compute using a multiplicative depth of 4.
values are modified incrementally, we actually scale to within the Because hinge loss is a convex loss function (when not constrain-
range [−(1−𝜂), 1−𝜂], keeping a margin of 𝜂 so as to allow breathing ing the size of w), it is well suited for iterative, gradient-based
room for this. The value of 𝜂 was set in our experiments at 0.2. algorithms. Two such popular algorithms are gradient descent and
The calculation of the maximum |𝑥 | value, in order to allow for Newton iterations. Gradient descent shifts the parameters in the di-
the scaling, is also approximate, and is described in Algorithm 3. rection of maximal improvement, but requires one to set a learning
We use 𝑘 = 3, which allows fairly accurate estimation of the maxi- rate, 𝛼, for it. The iterations then become
mum without running the risk of overflows, and is well within our
multiplication budget. (w𝑡 +1, 𝑏𝑡 +1 ) ← (w𝑡 , 𝑏𝑡 ) − 𝛼∇𝐿(w, 𝑏).

A too-small choice for 𝛼 would lead to slow convergence, whereas

Algorithm 3: Calculate the approximate maximum, a choice that is too large would cause the algorithm to overshoot
softmax(x∗𝑗 ). the optimum and potentially lose stability.
Input : A feature vector, x∗𝑗 . Newton iterations, on the other hand, do not require such a
Output : The approximate max𝑖 |x𝑖 𝑗 |. manually set learning rate parameter, but do so at significant com-
𝑡ˆ ← x2∗𝑗 putational cost. A Newton iteration locally approximates the target
for 𝑖 ← 2 to 𝑘 do function as a hyperboloid and sets the next iteration to the opti-
𝑡ˆ ← 𝑡ˆ2 mal point on the hyperboloid. It has been shown that when such

2−𝑘 iterations are within their basin of convergence, convergence is
softmax ← SUM 𝑡ˆ
exponentially fast. However, computing the parameters of the hy-
return softmax
perboloid requires a second derivative, i.e. a Hessian, which is an
ℓ ×ℓ matrix, so requires an amount of effort quadratic in the number
The initial choice of 𝛾 is done before the Client can have enough of features.
information from the Cloud in order to make sure that softmax We opted to use a third method, combining the best of both
can be calculated safely, so instead of Algorithm 3 we scale using gradient descent and Newton iterations. Namely, at each iteration,
the previously calculated standard deviation, 𝜎, so that the range we first compute the gradient, and then perform a Newton optimi-
[−(1 − 𝜂), 1 − 𝜂] covers 𝑠 standard deviations, for a predefined sation iteration just in the direction of the gradient. In other words,
𝑠, dependent only on 𝑚. We chose 𝑠 to be 3 in our experiments, we approximate the loss function along the line of the gradient as a
because, given our 𝑚, if the features are normally distributed, this parabola, and set our new values to the optimum of that parabola.
scaling ensures that less than one sample in expectation will exceed This algorithm, one-dimensional Newton iterations, can be thought
the designated range. of as a form of gradient descent where the 𝛼 parameter is computed
There is still a risk that some samples will slightly exceed the automatically. The complete algorithm is shown in Algorithm 4.
range, but not enough to cause problematic overflows, and slight In Algorithm 4, “·” indicates matrix multiplication, “×” indicates
deviations are handled by the use of an even-degree approximating element by element multiplication, and function application on a
polynomial for our loss function, which ensures that in the process vector works also element by element. For the purposes of matrix
8
Practical PPML using FHE Proceedings on Privacy Enhancing Technologies YYYY(X)

Algorithm 4: A Newton iteration. 3.3 Initialisation

Input : Input parameters (w𝑡 , 𝑏𝑡 ). Before algorithm iterations can commence, we must choose an
Output : Next iteration parameters (w𝑡 +1, 𝑏𝑡 +1 ). initial parameter set to start with. There are many ways to do this.
ĉ ← {−y} × ( x̂ · ⟦w𝑡 ⟧ + ⟦𝑏𝑡 ⟧) We have opted to set the bias 𝑏 to zero and the initial weights 𝑤 𝑗 to
d̂ ← ℎ˜ ′ (ĉ) be proportional to the covariance between the target labels and the
for 𝑗 ← 1 to ℓ do  𝑗 th feature. If the feature noise is independent between features,

 this initialisation produces predictions that are least affected by
Δ𝑤 𝑗 ← SUM𝑖 𝑑ˆ𝑖 {−𝑦𝑖 }𝑥ˆ𝑖 𝑗
  noise.
Δ𝑏 ← SUM𝑖 𝑑ˆ𝑖 {−𝑦𝑖 } The covariance is computed using the Data Owner-precalculated
𝑥𝑖 𝑗 𝑦𝑖 values. The specifics are almost identical to the way feature
𝑝 ← ∆w𝑇 · w𝑡
variance was computed in Algorithm 2. We do not repeat the de-
∆w ← ∆w − 𝑝w𝑡
scription here.
𝐷 ← (Δ𝑏) 2 + ∥∆w∥ 2 
𝐻 ← SUM𝑖 ℎ˜ ′′ (𝑐ˆ𝑖 )(𝑥ˆ𝑖∗ · ⟦∆w⟧ + ⟦Δ𝑏⟧) 2
3.4 Approximating ℎ
𝛼 ← 𝐷/𝐻
The final part of the algorithm, which we have not discussed yet,
(w𝑡 +1, 𝑏𝑡 +1 ) ← (w𝑡 , 𝑏𝑡 ) − 𝛼 (∆w, Δ𝑏)
is how to approximate the hinge function using a polynomial ap-
w𝑡 +1 ← w𝑡 +1 /∥w𝑡 +1 ∥
proximation with a small multiplication depth. In fact, instead of
return (w𝑡 +1, 𝑏𝑡 +1 )
computing ℎ˜ directly, we chose to approximate ℎ˜ ′′ , or a function
proportional to ℎ˜ ′′ , instead, and compute ℎ˜ by doubly integrating
multiplication, the vectors w𝑡 , w𝑡 +1 and ∆w are all taken to be the result, scaling, and adding an affine function (this affine function
column vectors. They are all of length ℓ. being a degree of freedom in the integration). The scaling factor
𝜕𝐿 (w,𝑏 ) and the linear component of the affine function were chosen so that
In the algorithm, Δ𝑤 𝑗 acts as the partial derivative 𝜕𝑤𝑗 while
the negative portion of the function will be as flat as possible while
𝜕𝐿 (w,𝑏 )
Δ𝑏 acts as 𝜕𝑏 . We remove from ∆w, however, its component the positive part will have a slope of 1. The optimisation algorithm
parallel to the w𝑡 vector, in order for small steps in this direction itself is invariant to the choice of the additive constant, so in the
to not change the size of the weight vector, thus improving the actual implementation we used for it zero. This choice made it
stability of the algorithm. easier to ignore unused vector positions when summing function
The polynomials ℎ˜ ′ and ℎ˜ ′′ are the first and second derivatives output values across an entire ciphertext vector. However, in order
˜ our approximation for the hinge function, and were computed
of ℎ, to demonstrate of the quality of the approximation, it is possible to
analytically from ℎ. ˜ The computation of all 3 functions was done substitute this zero by the additive constant that minimises the Root
ahead of time, and involves no communication. Mean Square Error (RMSE) in approximating the hinge function.
The values 𝐷 and 𝐻 are the first and second derivatives in the Figure 1 shows the plots of the hinge function ℎ, the raw result
direction of the gradient, so setting 𝛼 as 𝐷/𝐻 is simply a standard of doubly integrating ℎ˜ ′′ and scaling, 𝐼 , and our final polynomial
Newton iteration in one dimension. approximation of ℎ˜ after adding the appropriate affine function,
Newton iterations, because of their ability to perform large steps, including the additive constant that minimises its RMSE. The num-
are at risk of diverging when not near an optimum, for which reason bers in Table 2, which showcase the significant improvement in
in our implementation following this step the Client checks whether approximation accuracy afforded by our method, were computed
there is an improvement in the loss function. A deterioration in the using this same constant.
loss function leads to halving 𝛼. However, this condition was never
triggered in our training, and the algorithm converged after only
6–7 iterations even from a random initialisation. (And even faster 1
when using the initialisation recommended in Section 3.3.) I(x)
We note that throughout this entire process the Cloud at no point h̃(x)
needed to perform a computation with a multiplicative depth of h(x) 0.5
more than 3 plus the depth of the polynomial. (Two multiplications
are needed in order to compute ĉ, the input to the polynomial, and
one more in order to multiply the polynomial’s output with any
additional factors in a final multiplication step.) Scaling, in partic- −1 −0.5 0.5 1
ular, does not increase the multiplicative depth of the algorithm:
when scaling {−𝑦𝑖 }( x̂𝑖∗ · ⟦w𝑡 ⟧ + ⟦𝑏𝑡 ⟧) by a factor 𝛾 in order to −0.5
use the result as an input to a function, we do this simply by hav-
ing the Client scale the values w𝑡 and 𝑏𝑡 prior to communicating
them. Where the output of the function needs to be scaled as well, −1
this is done after the summation by the Cloud, by the Client, in
plaintext, so once again does not incur any additional ciphertext
Figure 1: Plot of 𝐼 , ℎ˜ and ℎ.
multiplications.
9
Proceedings on Privacy Enhancing Technologies YYYY(X) Brand and Pradel

We note that while the additive constant used in the approx- the Wisconsin Breast Cancer (WBC) dataset [60], a public medical
imation is arbitrary, a good choice of the linear coefficient and dataset, to generate our PPML model. This dataset contains real data
scaling factor is critical. Hinge loss penalises the model when the on breast cancer tumours for 569 patients. The dataset is composed
predicted score is on the wrong side of the decision boundary of 30 numerical features that describe measured attributes of each
(i.e., 𝑦𝑖 (xi · w + 𝑏) < 0). When the predicted score is correct (i.e., tumour, and one binary attribute indicating the final diagnosis of
𝑦𝑖 (xi · w + 𝑏) > 0), the loss is 0. Thus, correct classifications do whether the tumour was subsequently designated ‘malignant’ or
not impact the optimisation algorithm which is merely trying to ‘benign’. The final diagnosis, being our target variable, was mapped
improve the incorrect classifications (i.e., to minimise the slack to 1 for ‘benign’ and −1 for ‘malignant’.
variables). As optimisation progresses, there should be more and Although WBC is a relatively small dataset, it was suitable for our
more correctly classified pairs, and the misclassified pairs become a proof-of-concept implementation. Our purpose was to demonstrate
small minority. As a result, it is important for the correctly classified the feasibility of our approach, not to create a production system.3
majority to not bias the optimisation and by this prevent proper In fact, because of the small number of samples in WBC, the vast
handling of the remaining incorrectly classified samples. This was majority of our ciphertext vectors remains unused when learning
done by considering the smallest and largest positive zeros of the WBC in its native form, so at first glance our timing results may
original (unscaled) 𝐼 polynomial, and scaling the function so that appear suboptimal. However, in follow-up experiments, we have
the slope between them is exactly 1/2. A linear coefficient of 1/2 supplemented WBC with synthetic repetitions of the same training
then aligns the corresponding negative zeroes to the same height samples, and our results show that even learning on 8, 000 samples
in the final ℎ˜ ′′ , while adjusting the positive slope to 1. does not increase run-times. Furthermore, the algorithmic complex-
It remains to show how to approximate ℎ˜ ′′ . In the case of the ity of our homomorphic operations is invariant to the number of
original hinge function ℎ, the first derivative is a Heaviside step samples, so increasing the training set size has no effect on our
function and the second derivative is a Dirac 𝛿 function. To approx- choice of encryption parameters.
imate this, we wanted to choose a polynomial that in the range For a CKKS implementation, we used the SEAL open-source
𝜖 ≤ |𝑥 | ≤ 1 never exceeds some absolute value 𝛼, but at 𝑥 = 0 library [55] by Microsoft implemented in C/C++, which we accessed
reaches 1. through the Python wrapper SEAL-Python [14].
A well-known family of polynomials whose absolute values We chose our parameters so as to provide 128-bit equivalent
are bounded within the range [−1, 1] is the family of Chebyshev security and to allow a multiplicative depth of at least 7 (being 4 for
polynomials. These are easy-to-compute polynomials, all of whose the polynomial calculation and 3 for the Newton iterations). The
roots lie within the [−1, 1] range, and all of whose maxima and minimal choice of such parameters, which led to the fastest exe-
minima reach a height of 1 and −1, respectively. At −1 and 1, the cution times and smallest ciphertexts, allowed for a multiplicative
polynomials also reach the same height. depth of 8, thereby providing ample computational headroom for
Consider now, for the Chebyshev polynomial 𝑇𝑛 of some even employing more complex algorithms. However, we did not use the
degree 𝑛, the polynomial extra headroom for the results presented here. The resulting cipher-
  text vectors when using our chosen parameters possessed a length
𝑄 (𝑥) = 𝛼𝑇𝑛 𝑠 − (𝑠 + 1)𝑥 2 , of 8, 192 ciphertext elements, which is why training execution time
remains invariant even with the inclusion of additional samples.
where 𝑠 = 1 + 𝜖 2 / 1 − 𝜖 2 . This polynomial stays within [−𝛼, 𝛼]



2
√︁ the entire range where −1 ≤ 𝑠 − (𝑠 + 1)𝑥 ≤ 1, i.e. where
in 4.2 Results
(𝑠 − 1)/(𝑠 + 1) ≤ |𝑥 | ≤ 1 holds. This is exactly the desired range 4.2.1 Execution times. We separated our PPML training process
𝜖 ≤ |𝑥 | ≤ 1. For each 𝜖, there is an 𝛼 for which 𝑄 (0) = 1. This into three phases:
presents a trade-off between our choice of 𝜖 (the range of the ap- Encryption: Encryption of the samples,
proximation) and 𝛼 (the accuracy of the approximation). In our Data Ingest: Uploading the encrypted samples to the Cloud, and
implementation we used 𝛼 = 1/4. the samples’ subsequent preprocessing and scaling, and
In the literature, polynomial approximations for non-linear func- Training: Initialisation and iterations of the Newton-based algo-
tions are computed using either Taylor coefficients or Chebyshev rithm.
coefficients, the latter of which is meant to reduce inaccuracies
near the edges of the approximation range, this effect being known As is common practice, we partitioned the full WBC dataset into
as Runge’s Phenomenon. Our approximation method, however, training and testing sets, with the former comprising 80% and the
using Chebyshev polynomials to directly constrain the maximal latter 20% of the data.
divergence of the approximation, has allowed us to reach superior Three types of actors participate in the training phase: the Data
results. Owners, the Client, and the Cloud. Encryption of the samples is
performed by the Data Owners, and is, in a real-world application,
a massively parallelised process in which each Data Owner only
4 EXPERIMENTAL IMPLEMENTATION
encrypts their own data. The other steps are performed jointly by
4.1 Parameters
3We acknowledge that a linear SVM, even supplemented with non-linear features,
The results presented here are based on executions on a single
is unable to handle more complex datasets such as the MNIST dataset. In follow-up
machine with 32 GBs RAM, running an Intel(R) Core(TM) i7-8700 work, we expand our solution to enable the learning of general models, which allow
CPU at 3.20GHz, under the Ubuntu 21.10 operating system. We used classification on full-sized, high-complexity datasets.
10
Practical PPML using FHE Proceedings on Privacy Enhancing Technologies YYYY(X)

200 60 20 80
Encryption Data Ingest Data Ingest Training
Training
Time per Data Owner (ms)

150 15 60
40

Time (s)

Time (s)

Time (s)
100 10 40

20
50 5 20

0 0 0 0
0 2,000 4,000 6,000 8,000 0 2,000 4,000 6,000 8,000 0 15 30 45 60 0 15 30 45 60
Number of samples Number of samples Number of features Number of features

(a) Encryption execution time per (b) Data Ingest and Training ex- (a) Data Ingest execution time by (b) Training execution time by
Data Owner by number of sam- ecution time by number of sam- number of features. number of features.
ples. ples.
Figure 3: Execution time as a function of feature count.
Figure 2: Execution time as a function of sample count.

with respect to the number of samples up to the point of saturating

the Client and the Cloud, and Data Owners do not participate in
the ciphertext vector. However, any increase in the number of
them at all. The computational load for performing this algorithm
samples beyond the prescribed limit of 8, 192 (as determined by our
should therefore be analysed from the perspective of the Data
SEAL parameters) results in additional ciphertext vectors i.e. in a
Owners and the Client separately (noting that the Client, in a real-
linear growth of the Training phase, and is fully parallelisable.
world setting, is likely to be paying for the computational load
The results also show a linear growth in the length of the Data
of the Cloud as well). From the perspective of the Data Owners,
Ingest phase. This growth is only due to the uploading of the en-
only the time it takes to encrypt each Data Owner’s own data is
crypted data by the Cloud. Once data is uploaded and packed into
important, and we analyse this in terms of the time it takes to
ciphertext vectors, its total processing time depends only on the
encrypt a single new sample. From the perspective of the Client,
number of ciphertext vectors, and therefore, as before, remains
encryption time is immaterial, but the entirety of the rest of the
constant up to 8, 192 samples.
process should be measured; we therefore analyse this portion of
Figure 3 illustrates the execution times in the Data Ingest and
the training seperately to encryption. For completeness, we also
Training phases for a varying number of features.
include in Table 1 the full summed-up processing times, where
As previously described, in our implementation we chose a
total encryption time is given. In this view, encryption takes up the
column-oriented arrangement: we used the entire length of our
majority of our CPU time, although in practice this is unlikely to
ciphertext vectors to store as many data samples as we have, each
be a concern. Without encryption, our PPML training algorithm
vector housing the values of only a single feature, in order to effec-
completes in under 45 seconds.
tively exploit the SIMD architecture inherent in the CKKS algorithm.
As a result, execution times of the training phase exhibit a linear
Table 1: PPML training execution times. Total execution time
growth with the number of features, as depicted in Figure 3(b).
is given without (“w/o”) and with (“w”) encryption.
The Data Ingest phase grows linearly in both the number of fea-
tures and the number of samples. The contribution of each feature
Phase Execution time (s) to the computation time is approximately 250 milliseconds in the
Encryption 56.70 Data Ingest phase (for the total sample size of the WBC dataset)
Data Ingest 6.448 and approximately 1.2 seconds in the Training phase.
Model initialisation 2.194 4.2.2 Accuracy. The efficacy of our PPML model is inherently de-
Model optimisation 34.99 pendent on the effectiveness of our polynomial approximation
Total time (w/o) 43.632 technique, which we utilise in order to compute the hinge function
Total time (w) 100.333 over encrypted data. Table 2 compares the quality of our polyno-
mial approximation to related works and confirms the effectiveness
We investigated the scalability of our PPML training algorithm of our approach. The results are due both to our approximation
in relation to variations in the number of samples and features. For method and to the fact that our efficient use of multiplications else-
this, we executed the complete algorithm, including data encryption, where in the PPML training algorithm enabled us to incorporate
with up to 8, 000 samples and 60 features. here a full multiplicative-depth 4 polynomial approximation.
Figure 2 displays execution times as a function of the number of Using our polynomial approximation, we obtained an accuracy
samples. This is separated by actor. Figure 2(a) displays the average of 99.1% on our (decrypted) trained model over held-out data. For
execution time for a single Data Owner; Figure 2(b) shows combined comparison, we trained the same model on clear data using common
execution times for the Client and Cloud. methods and obtained exactly the same accuracy results, proving
These results demonstrate that, regardless of the number of Data the viability of our methods.
Owners involved, computation time for each Data Owner remains Figure 4 presents a confusion matrix of the results of our PPML-
constant at around 150 milliseconds. Training remains invariant trained model, when applied over clear data.
11
Proceedings on Privacy Enhancing Technologies YYYY(X) Brand and Pradel

Table 2: Comparison between related works and ours on We propose that our techniques and methods can serve as a
polynomial approximation in the [−1, 1] domain. blueprint for real-world training of machine-learning models under
the constraint of privacy-preservation, in settings where a client-
Work Method Function Multiplicative-depth RMSE
Final model assisted computation model can be used.
accuracy (%)
In ongoing research, we are expanding our solution to support
[13] Taylor series ReLU 3 0.056 97.91
Orthogonal systems
generic algorithms, applicable for significantly larger datasets.
[29] Sigmoid 1 N/A 96.3
of polynomials
Derivative and
[28]
Chebyshev
ReLU 1 0.13 98.52 ACKNOWLEDGMENTS
Second derivative The authors acknowledge INCERT for the funding of the project.
Ours ReLU/hinge 4 0.0050 99.1
and Chebyshev

REFERENCES
[1] Rakesh Agrawal and Ramakrishnan Srikant. 2000. Privacy-Preserving Data
Mining. In Proceedings of the 2000 ACM SIGMOD International Conference on
60 Management of Data, May 16-18, 2000, Dallas, Texas, USA, Weidong Chen, Jeffrey F.
Malignant 23% 0.9% Naughton, and Philip A. Bernstein (Eds.). ACM, 439–450. [Link]
1145/342009.335438
[2] Shamima Ahmed, Muneer M. Alshater, Anis El Ammari, and Helmi Hammami.
Predicted

2022. Artificial intelligence and machine learning in finance: A bibliometric

40 review. Research in International Business and Finance 61 (2022), 101646. https:
//[Link]/10.1016/[Link].2022.101646
[3] Mohammad Al-Rubaie and J. Morris Chang. 2019. Privacy-Preserving Machine
Learning: Threats and Solutions. IEEE Secur. Priv. 17, 2 (2019), 49–58. https:
Benign 0% 76.1% 20 //[Link]/10.1109/MSEC.2018.2888775
[4] Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey
Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam,
Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod
0 Vaikuntanathan. 2018. Homomorphic Encryption Security Standard. Technical
Malignant Benign Report. [Link], Toronto, Canada.
Actual [5] Ahmad Al Badawi, Ling Chen, and Saru Vig. 2022. Fast homomorphic SVM
inference on encrypted data. Neural Comput. Appl. 34, 18 (2022), 15555–15573.
[Link]
Figure 4: Confusion matrix of our PPML model. [6] Jean-Claude Bajard, Paulo Martins, Leonel Sousa, and Vincent Zucca. 2020. Im-
proving the Efficiency of SVM Classification With FHE. IEEE Trans. Inf. Forensics
Secur. 15 (2020), 1709–1722. [Link]
[7] Mauro Barni, Claudio Orlandi, and Alessandro Piva. 2006. A privacy-preserving
4.2.3 Comparison with related work. Park et al.’s [47] is the work protocol for neural-network-based computation. In Proceedings of the 8th work-
most comparable to ours and warrants a comprehensive comparison. shop on Multimedia & Security, MM&Sec 2006, Geneva, Switzerland, September
26-27, 2006, Sviatoslav Voloshynovskiy, Jana Dittmann, and Jessica J. Fridrich
This is given in Table 3. (Eds.). ACM, 146–151. [Link]
[8] Daniel J. Bernstein and Tanja Lange. 2017. Post-quantum cryptography. Nat. 549,
7671 (2017), 188–194. [Link]
Table 3: Comparison between Park et al. and our work. [9] Fabian Boemer, Rosario Cammarota, Daniel Demmler, Thomas Schneider, and
Hossein Yalame. 2020. MP2ML: a mixed-protocol machine learning frame-
work for private inference. In ARES 2020: The 15th International Conference
Number Time per
Number of Model final on Availability, Reliability and Security, Virtual Event, Ireland, August 25-28,
Work of used iteration Training (s)
iterations accuracy (%) 2020, Melanie Volkamer and Christian Wressnegger (Eds.). ACM, 14:1–14:10.
features (s) [Link]
Park et al. [47] 9 10 33.545 335.45 97–98 [10] Fabian Boemer, Yixing Lao, Rosario Cammarota, and Casimir Wierzynski. 2019.
Ours 30 6 7.272 43.632 99.1 nGraph-HE: a graph compiler for deep learning on homomorphically encrypted
data. In Proceedings of the 16th ACM International Conference on Computing
Frontiers, CF 2019, Alghero, Italy, April 30 - May 2, 2019, Francesca Palumbo,
Michela Becchi, Martin Schulz, and Kento Sato (Eds.). ACM, 3–13. [Link]
5 CONCLUSION AND FUTURE WORK org/10.1145/3310273.3323047
[11] Florian Bourse, Olivier Sanders, and Jacques Traoré. 2020. Improved Secure
In this paper, we presented a novel PPML training method using Integer Comparison via Homomorphic Encryption. In Topics in Cryptology - CT-
RSA 2020 - The Cryptographers’ Track at the RSA Conference 2020, San Francisco,
FHE, which achieves state-of-the-art processing speeds without CA, USA, February 24-28, 2020, Proceedings (Lecture Notes in Computer Science,
sacrificing accuracy. Specifically, we trained a linear SVM classifier Vol. 12006), Stanislaw Jarecki (Ed.). Springer, 391–416. [Link]
on 8, 000 samples, each containing 30 numerical features in under 45 3-030-40186-3_17
[12] Centers for Medicare & Medicaid Services. 1996. The Health Insur-
seconds (not including the initial encryption) on a single computer, ance Portability and Accountability Act of 1996 (HIPAA). Online at
without any GPU acceleration, and attained 99% accuracy, which is [Link]
a state-of-the-art result for the dataset used. [13] Hervé Chabanne, Amaury de Wargny, Jonathan Milgram, Constance Morel,
and Emmanuel Prouff. 2017. Privacy-Preserving Classification on Deep Neural
To achieve these results, we applied a collection of carefully Network. IACR Cryptol. ePrint Arch. (2017), 35. [Link]
selected techniques and design considerations that prioritise prag- [14] Zhigang Chen. 2022. SEAL-Python (release 4.0). [Link]
Python.
matic concerns relating to computational efficiency and processing [15] Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim, and Yongsoo Song.
capacity. These include FHE over floating-point data, vectorised and 2018. A Full RNS Variant of Approximate Homomorphic Encryption. In Selected
parallelised computations, the client-assisted computation model, Areas in Cryptography - SAC 2018 - 25th International Conference, Calgary, AB,
Canada, August 15-17, 2018, Revised Selected Papers (Lecture Notes in Computer
minimal communication between the client and the cloud, frugal Science, Vol. 11349), Carlos Cid and Michael J. Jacobson Jr. (Eds.). Springer, 347–368.
polynomial approximations, and rapid convergence methods. [Link]
12
Practical PPML using FHE Proceedings on Privacy Enhancing Technologies YYYY(X)

[16] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. 2017. Homo- [35] Joon-Woo Lee, HyungChul Kang, Yongwoo Lee, Woosuk Choi, Jieun Eom, Maxim
morphic Encryption for Arithmetic of Approximate Numbers. In Advances in Deryabin, Eunsang Lee, Junghyun Lee, Donghoon Yoo, Young-Sik Kim, and Jong-
Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Ap- Seon No. 2022. Privacy-Preserving Machine Learning With Fully Homomorphic
plications of Cryptology and Information Security, Hong Kong, China, December 3-7, Encryption for Deep Neural Network. IEEE Access 10 (2022), 30039–30054. https:
2017, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 10624), Tsuyoshi //[Link]/10.1109/ACCESS.2022.3159694
Takagi and Thomas Peyrin (Eds.). Springer, 409–437. [Link] [36] Bo Liu, Ming Ding, Sina Shaham, Wenny Rahayu, Farhad Farokhi, and Zihuai
3-319-70694-8_15 Lin. 2022. When Machine Learning Meets Privacy: A Survey and Outlook. ACM
[17] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2020. Comput. Surv. 54, 2 (2022), 31:1–31:36. [Link]
TFHE: Fast Fully Homomorphic Encryption Over the Torus. J. Cryptol. 33, 1 [37] Jian Liu, Mika Juuti, Yao Lu, and N. Asokan. 2017. Oblivious Neural Network Pre-
(2020), 34–91. [Link] dictions via MiniONN Transformations. In Proceedings of the 2017 ACM SIGSAC
[18] Ilaria Chillotti, Marc Joye, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA,
2020. CONCRETE: Concrete Operates oN Ciphertexts Rapidly by Extending TfhE. October 30 - November 03, 2017, Bhavani Thuraisingham, David Evans, Tal Malkin,
In WAHC 2020–8th Workshop on Encrypted Computing & Applied Homomorphic and Dongyan Xu (Eds.). ACM, 619–631. [Link]
Cryptography, Vol. 15. [38] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2010. On Ideal Lattices
[19] Ilaria Chillotti, Marc Joye, and Pascal Paillier. 2021. Programmable Bootstrapping and Learning with Errors over Rings. In EUROCRYPT (Lecture Notes in Computer
Enables Efficient Homomorphic Inference of Deep Neural Networks. In Cyber Science, Vol. 6110). Springer, 1–23.
Security Cryptography and Machine Learning - 5th International Symposium, [39] Mohamad Mansouri, Melek Önen, Wafa Ben Jaballah, and Mauro Conti. 2023. SoK:
CSCML 2021, Be’er Sheva, Israel, July 8-9, 2021, Proceedings (Lecture Notes in Secure Aggregation Based on Cryptographic Schemes for Federated Learning.
Computer Science, Vol. 12716), Shlomi Dolev, Oded Margalit, Benny Pinkas, and Proc. Priv. Enhancing Technol. 2023, 1 (2023), 140–157. [Link]
Alexander A. Schwarzmann (Eds.). Springer, 1–19. [Link] popets-2023-0009
3-030-78086-9_1 [40] Chiara Marcolla, Victor Sucasas, Marc Manzano, Riccardo Bassoli, Frank H. P.
[20] Corinna Cortes and Vladimir Vapnik. 1995. Support-Vector Networks. Mach. Fitzek, and Najwa Aaraj. 2022. Survey on Fully Homomorphic Encryption,
Learn. 20, 3 (1995), 273–297. [Link] Theory, and Applications. Proc. IEEE 110, 10 (2022), 1572–1609. [Link]
[21] Jack L. H. Crawford, Craig Gentry, Shai Halevi, Daniel Platt, and Victor Shoup. 10.1109/JPROC.2022.3205665
2018. Doing Real Work with FHE: The Case of Logistic Regression. In Proceedings [41] Payman Mohassel and Yupeng Zhang. 2017. SecureML: A System for Scalable
of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptogra- Privacy-Preserving Machine Learning. In 2017 IEEE Symposium on Security and
phy, WAHC@CCS 2018, Toronto, ON, Canada, October 19, 2018, Michael Brenner Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017. IEEE Computer Society,
and Kurt Rohloff (Eds.). ACM, 1–12. [Link] 19–38. [Link]
[22] European Commission. 2016. Regulation (EU) 2016/679 of the European Parlia- [42] Jean-Michel Muller, Nicolas Brunie, Florent de Dinechin, Claude-Pierre Jeannerod,
ment and of the Council of 27 April 2016 on the protection of natural persons Mioara Joldes, Vincent Lefèvre, Guillaume Melquiond, Nathalie Revol, and Serge
with regard to the processing of personal data and on the free movement of Torres. 2018. Handbook of Floating-Point Arithmetic (2nd Ed.). Springer. https:
such data, and repealing Directive 95/46/EC (General Data Protection Regulation) //[Link]/10.1007/978-3-319-76526-6
(Text with EEA relevance). [Link] [43] Karthik Nandakumar, Nalini K. Ratha, Sharath Pankanti, and Shai Halevi. 2019.
[23] Craig Gentry. 2009. A fully homomorphic encryption scheme. Ph. D. Dissertation. Towards Deep Neural Network Training on Encrypted Data. In IEEE Conference
Stanford University. [Link]/craig. on Computer Vision and Pattern Recognition Workshops, CVPR Workshops 2019,
[24] Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin E. Lauter, Michael Long Beach, CA, USA, June 16-20, 2019. Computer Vision Foundation / IEEE,
Naehrig, and John Wernsing. 2016. CryptoNets: Applying Neural Networks 40–48. [Link]
to Encrypted Data with High Throughput and Accuracy. In Proceedings of [44] Srinath Obla, Xinghan Gong, Asma Aloufi, Peizhao Hu, and Daniel Takabi. 2020.
the 33nd International Conference on Machine Learning, ICML 2016, New York Effective Activation Functions for Homomorphic Evaluation of Deep Neural
City, NY, USA, June 19-24, 2016 (JMLR Workshop and Conference Proceedings, Networks. IEEE Access 8 (2020), 153098–153112. [Link]
Vol. 48), Maria-Florina Balcan and Kilian Q. Weinberger (Eds.). [Link], 201– 2020.3017436
210. [Link] [45] Claudio Orlandi, Alessandro Piva, and Mauro Barni. 2007. Oblivious Neural
[25] Oded Goldreich. 2004. The Foundations of Cryptography - Volume 2: Basic Appli- Network Computing via Homomorphic Encryption. EURASIP J. Inf. Secur. 2007
cations. Cambridge University Press. (2007). [Link]
[26] Shai Halevi. 2017. Homomorphic Encryption. In Tutorials on the Foundations of [46] Saerom Park, Junyoung Byun, and Joohee Lee. 2022. Privacy-Preserving Fair
Cryptography., Yehuda Lindell (Ed.). Springer International Publishing, 219–276. Learning of Support Vector Machine with Homomorphic Encryption. In WWW
[Link] ’22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022,
[27] Shai Halevi and Victor Shoup. 2014. Algorithms in HElib. In Advances in Cryptol- Frédérique Laforest, Raphaël Troncy, Elena Simperl, Deepak Agarwal, Aristides
ogy - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, Gionis, Ivan Herman, and Lionel Médini (Eds.). ACM, 3572–3583. [Link]
USA, August 17-21, 2014, Proceedings, Part I (Lecture Notes in Computer Sci- org/10.1145/3485447.3512252
ence, Vol. 8616), Juan A. Garay and Rosario Gennaro (Eds.). Springer, 554–571. [47] Saerom Park, Junyoung Byun, Joohee Lee, Jung Hee Cheon, and Jaewook Lee.
[Link] 2020. HE-Friendly Algorithm for Privacy-Preserving SVM Training. IEEE Access
[28] Ehsan Hesamifard, Hassan Takabi, and Mehdi Ghasemi. 2019. Deep Neu- 8 (2020), 57414–57425. [Link]
ral Networks Classification over Encrypted Data. In Proceedings of the Ninth [48] Adnan Qayyum, Junaid Qadir, Muhammad Bilal, and Ala Al-Fuqaha. 2021. Secure
ACM Conference on Data and Application Security and Privacy, CODASPY 2019, and Robust Machine Learning for Healthcare: A Survey. IEEE Reviews in Biomed-
Richardson, TX, USA, March 25-27, 2019, Gail-Joon Ahn, Bhavani Thuraising- ical Engineering 14 (2021), 156–180. [Link]
ham, Murat Kantarcioglu, and Ram Krishnan (Eds.). ACM, 97–108. https: [49] Jean Louis Raisaro, Jeffrey G Klann, Kavishwar B Wagholikar, Hossein Estiri,
//[Link]/10.1145/3292006.3300044 Jean-Pierre Hubaux, and Shawn N Murphy. 2018. Feasibility of Homomorphic
[29] Ehsan Hesamifard, Hassan Takabi, Mehdi Ghasemi, and Rebecca N. Wright. 2018. Encryption for Sharing I2B2 Aggregate-Level Data in the Cloud. AMIA Summits
Privacy-preserving Machine Learning as a Service. Proc. Priv. Enhancing Technol. on Translational Science Proceedings 2017 (may 2018), 176–185. [Link]
2018, 3 (2018), 123–142. [Link] [Link]/pmc/articles/PMC5961814/
[30] Hai Huang, Yongjian Wang, and Haoran Zong. 2022. Support vector machine [50] Oded Regev. 2005. On lattices, learning with errors, random linear codes, and
classification over encrypted data. Appl. Intell. 52, 6 (2022), 5938–5948. https: cryptography. In Proceedings of the 37th Annual ACM Symposium on Theory of
//[Link]/10.1007/s10489-021-02727-2 Computing, Baltimore, MD, USA, May 22-24, 2005, Harold N. Gabow and Ronald
[31] Lei Jiang and Lei Ju. 2022. FHEBench: Benchmarking Fully Homomorphic En- Fagin (Eds.). ACM, 84–93. [Link]
cryption Schemes. CoRR abs/2203.00728 (2022). [Link] [51] M. Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M. Songhori,
2203.00728 arXiv:2203.00728 Thomas Schneider, and Farinaz Koushanfar. 2018. Chameleon: A Hybrid Secure
[32] Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha P. Chandrakasan. 2018. Computation Framework for Machine Learning Applications. In Proceedings of
GAZELLE: A Low Latency Framework for Secure Neural Network Inference. In the 2018 on Asia Conference on Computer and Communications Security, AsiaCCS
27th USENIX Security Symposium, USENIX Security 2018, Baltimore, MD, USA, 2018, Incheon, Republic of Korea, June 04-08, 2018, Jong Kim, Gail-Joon Ahn,
August 15-17, 2018, William Enck and Adrienne Porter Felt (Eds.). USENIX As- Seungjoo Kim, Yongdae Kim, Javier López, and Taesoo Kim (Eds.). ACM, 707–721.
sociation, 1651–1669. [Link] [Link]
presentation/juvekar [52] Ronald L. Rivest, M. L. Dertouzos, and Leonard M. Adleman. 1978. On data banks
[33] Aviad Kipnis and Eliphaz Hibshoosh. 2012. Efficient Methods for Practical Fully and privacy homomorphisms. Fondations of Secure Computation, Academia Press
Homomorphic Symmetric-key Encrypton, Randomization and Verification. IACR (1978), 169–179.
Cryptol. ePrint Arch. (2012), 637. [Link] [53] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. 1978. A Method for
[34] Yann LeCun, Corinna Cortes, and Christopher J.C. Burges. 1998. MNIST hand- Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM 21,
written digit database. [Link] (1998). 2 (1978), 120–126.
13
Proceedings on Privacy Enhancing Technologies YYYY(X) Brand and Pradel

[54] Sinem Sav, Apostolos Pyrgelis, Juan Ramón Troncoso-Pastoriza, David Froelicher, Algorithm 7: Function seek_beta
Jean-Philippe Bossuat, Joao Sa Sousa, and Jean-Pierre Hubaux. 2021. POSEIDON:
Privacy-Preserving Federated Neural Network Learning. In 28th Annual Network Input : A polynomial 𝑃 (𝑥) of degree 𝑛 and 𝛽 ∈ R
and Distributed System Security Symposium, NDSS 2021, virtually, February 21- Output :𝑠 ∈ R such that 𝑃 (𝑠) = 𝛽
25, 2021. The Internet Society. [Link]
poseidon-privacy-preserving-federated-neural-network-learning/
if 𝛽 ≤ 1 then
[55] SEAL 2022. Microsoft SEAL (release 4.0). [Link] Stop
Microsoft Research, Redmond, WA.. 𝜖 ← 10 −14
[56] Harry Chandra Tanuwidjaja, Rakyong Choi, Seunggeun Baek, and Kwangjo Kim.
2020. Privacy-Preserving Deep Learning on Machine Learning as a Service - a 𝑥𝑚𝑖𝑛 ← 1.0
Comprehensive Survey. IEEE Access 8 (2020), 167425–167447. [Link] 𝑥𝑚𝑎𝑥 ← 1.1
1109/ACCESS.2020.3023084
[57] Boaz Tsaban and Noam Lifshitz. 2015. Cryptanalysis of the MORE symmetric
while 𝑃 (𝑥𝑚𝑎𝑥 ) < 𝛽 do
key fully homomorphic encryption scheme. J. Math. Cryptol. 9, 2 (2015), 75–78. 𝑥𝑚𝑎𝑥 ← 2𝑥𝑚𝑎𝑥 − 1.0
[Link] while 𝑥𝑚𝑎𝑥 − 𝑥𝑚𝑖𝑛 > 𝜖 do
[58] Serge Vaudenay and Damian Vizár. 2015. Cryptanalysis of chosen symmetric ho- 𝑥𝑚𝑖𝑑 ← (𝑥𝑚𝑎𝑥 + 𝑥𝑚𝑖𝑛 ) ∗ 0.5
momorphic schemes. STUDIA SCIENTIARUM MATHEMATICARUM HUNGARICA
52, 2 (2015), 288–306. [Link] 𝑦𝑚𝑖𝑑 ← 𝑃 (𝑥𝑚𝑖𝑑 )
[59] Anamaria Vizitiu, Cosmin Ioan Nita, Andrei Puiu, Constantin Suciu, and Lu- if 𝑦𝑚𝑖𝑑 > 𝛽 then
cian Mihai Itu. 2020. Applying Deep Neural Networks over Homomorphic 𝑥𝑚𝑎𝑥 ← 𝑥𝑚𝑖𝑑
Encrypted Medical Data. Comput. Math. Methods Medicine 2020 (2020), 3910250:1–
3910250:26. [Link] else
[60] William Wolberg, Nick Street, and Olvi Mangasarian. 1995. Breast Cancer Wiscon- 𝑥𝑚𝑖𝑛 ← 𝑥𝑚𝑖𝑑
sin (Diagnostic). UCI Machine Learning Repository. [Link] return 𝑥𝑚𝑎𝑥
[Link]

A ALGORITHMS Algorithm 8: Function approx_hinge that approximates

We used Algorithm 5 to generate the Chebyshev polynomial of the hinge loss
degree 𝑛. Input : A degree 𝑛 and 𝛼 ∈ R
Output : A polynomial approximation ℎ˜ of the hinge loss
Algorithm 5: Function chebyshev that computes Cheby- (𝑄 (𝑥), −1
∬𝑠) ← approx_dirac(𝑛 − 2, 𝛼 )
shev 𝑇𝑛 ℎ˜ ← 𝑄 (𝑥)
Input : Degree 𝑛 𝑚 ← 𝑛−2 2
Output : Chebyshev polynomial 𝑇𝑛 of degree 𝑛 𝑘𝑚𝑖𝑛 ← 0
𝑇0 ← 1 𝑘𝑚𝑎𝑥 ← √︂ 𝑚−1
𝑇1 ← 𝑥
 
0.5𝜋 +𝜋𝑘𝑚𝑖𝑛
cos 𝑚
for 𝑖 ← 2 to 𝑛 do 𝑥𝑚𝑖𝑛 ← 𝑠− 𝑠+1.0
𝑇𝑖 ← 2𝑥𝑇𝑖 −1 − 𝑇𝑖 −2 √︂ 
0.5𝜋 +𝜋𝑘𝑚𝑎𝑥

cos
return 𝑇𝑛 𝑥𝑚𝑎𝑥 ← 𝑠 −
𝑚
1+1.0
𝑦𝑚𝑖𝑛 ← ℎ(𝑥˜ 𝑚𝑖𝑛 )
The algorithm for computing ℎ˜ ′′ is given in Algorithm 6. 𝑦𝑚𝑎𝑥 ← ℎ(𝑥 ˜ 𝑚𝑎𝑥 )
𝑦𝑚𝑎𝑥 −𝑦𝑚𝑖𝑛
𝑎 ← 𝑥𝑚𝑎𝑥 −𝑥𝑚𝑖𝑛
Algorithm 6: Function approx_dirac that approximates ℎ˜ ← ℎ˜ × 𝑎2
the Dirac function
ℎ˜ ← ℎ˜ + 𝑥2
Input : A degree 𝑛 and 𝛽 ∈ R
Output : A polynomial 𝑄 (𝑥) ≈ ℎ ′′ and 𝑠 ∈ R return ℎ˜
if 𝑛 . 0 mod 2 then
Stop: the degree must be even.
actors during the training of the PPML model based on FHE, using
𝑇𝑛/2 ← chebyshev(𝑛/2) the terminology of our motivating example in Section 1.1.1.
𝑠 ← seek_beta(𝑇𝑛/2, 𝛽)
𝑄 (𝑥) ← 𝛽 −1𝑇𝑛/2 (𝑠 − (𝑠 + 1.0)𝑥 2 )
return (𝑄 (𝑥), 𝑠)

The solution to the equation 𝑇𝑛/2 (𝑠) = 𝛽, used in Algorithm 6, is

generated using the function seek𝛽 defined by Algorithm 7, which
is essentially a binary search.
The algorithm for approximating of the hinge loss is given in
Algorithm 8.

B SOLUTION ILLUSTRATION
Figure 5 presents a design overview of our solution described in
Section 1.2 including the various tasks achieved by the various
14
Practical PPML using FHE Proceedings on Privacy Enhancing Technologies YYYY(X)

Figure 5: Illustration of our solution design.

15