Yulliwas Ameur
email: yulliwas.ameur@lecnam.net

Rezak Aziz

Vincent Audigier

Samia Bouzefrane

Secure and non-interactive k-NN classifier using symmetric fully homomorphic encryption

Keywords: k-nearest neighbors, homomorphic encryption, TFHE, data privacy, IoT, cloud computing, privacy-preserving

Machine learning as a service" (MLaaS) in the cloud accelerates the adoption of machine learning techniques. Nevertheless, the externalization of data on the cloud raises a serious vulnerability issue because it requires disclosing private data to the cloud provider. This paper deals with this problem and brings a solution for the K-nearest neighbors (k-NN) algorithm with a homomorphic encryption scheme (called TFHE) by operating on end-to-end encrypted data while preserving privacy. The proposed solution addresses all stages of k-NN algorithm with fully encrypted data, including the majority vote for the class-label assignment. Unlike existing techniques, our solution does not require intermediate interactions between the server and the client when executing the classification task. Our algorithm has been assessed with quantitative variables and has demonstrated its efficiency on large and relevant real-world data sets while scaling well across different parameters on simulated data.

INTRODUCTION

Cloud services have become central to data storage and data exploitation. Among these services, a machine-learning service is offered to train different models to predict for decision-making purposes. However, this raises the issue of data security because the data processed by the cloud may be sensitive and confidential while belonging to entities that do not trust the cloud provider.

The most commonly used cryptographic techniques are secret sharing, multiparty computation, and homomorphic encryption (HE) to achieve privacy-preserving for machine learning. Several techniques ensure strong privacy protection, often coming at the expense of reduced in terms of speed and communication.

homomorphic encryption is an encryption technique that allows computations directly on encrypted data. The results are encrypted and can be revealed/decrypted only by the owner of the secret key. This principle is very useful in many domains where data sharing and privacy preservation are required. For example, externalizing personal data considered as sensitive such as medical data or banking transactions [START_REF] Masters | Towards a homomorphic machine learning big data pipeline for the financial services sector[END_REF]. This paper considers a scenario where sensitive data are collected by IoT devices and outsourced on a resourceful cloud for Machine Learning (ML) processing. Considering that the cloud provider is not trustworthy, we propose using HE to preserve privacy.

ML over encrypted data has been particularly investigated in the domain of neural networks (NN). However, as state-of-the-art non-linear NN layers (pooling and activation) are too complex to be directly executed in the encrypted world, there is a strong need for approximating them. Much of the subsequent works have been proposed to address the limitation of implementing the nonlinear activation function by a polynomial approximation using Taylor series and Chebyshev polynomials, among others [START_REF] Chabanne | Privacy-preserving classification on deep neural network[END_REF][START_REF] Ehsan Hesamifard | Cryptodl: Deep neural networks over encrypted data[END_REF][START_REF] Al Badawi | Towards the alexnet moment for homomorphic encryption: Hcnn, the first homomorphic CNN on encrypted data with gpus[END_REF][START_REF] Brutzkus | Low latency privacy preserving inference[END_REF]. Due to the high cost of the HE systems, those methods do not scale well and are not appropriate for deep neural networks [START_REF] Pulido-Gaytan | Privacy-preserving neural networks with homomorphic encryption: Challenges and opportunities[END_REF], which are time-consuming due to the great depth of the network.

One way to solve the computational cost problem inherent to HE is to investigate less complex supervised methods. The k-nearest neighbors (k-NN) approach presents several advantages. Indeed, for a predefined number of neighbors k, the model does not require any training step, the value of the response variable for a given individual is obtained directly from the values observed on the neighbors without needing to estimate new parameters. In addition, the method can handle continuous, categorical, and mixed data. Furthermore, as a non-parametric method, k-NN can be relevant for many data structures as long as the number of observations is sufficiently large.

The prediction for a new observation is obtained by:

-Identifying the k nearest neighbors (according to a given distance) -Computing the majority class among them (for a classification problem) or by averaging values (for a regression problem).

HE has been recently investigated by various authors for k-NN [START_REF] Li | Exploring privacy preservation in outsourced k-nearest neighbors with multiple data owners[END_REF][START_REF] Bharath | k-nearest neighbor classification over semantically secure encrypted relational data[END_REF][START_REF] Wai | Secure knn computation on encrypted databases[END_REF][START_REF] Zuber | Efficient homomorphic evaluation of k-nn classifiers[END_REF].

[9] suggested a Homomorphic additive encryption scheme [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. They investigated the privacy preservation in an outsourced k-NN system with various data owners. The untrusted entity securely computes the computations of distances by using HE. However, the comparison and classification phases require interactions. Given that the computational and communication difficulties scale linearly, they admit that the method may not be practical for massive data volumes. The cost of communications between the entities is also a limitation in the deployment of this work [START_REF] Bharath | k-nearest neighbor classification over semantically secure encrypted relational data[END_REF].

[14], used an "asymmetric scalar-product-preserving encryption"(ASPE). However, the client has the ciphertext, and the server can decrypt it. The proposed solution is vulnerable to Chosen Plaintext Attacks as stated by [START_REF] Xiao | Secure nearest neighbor revisited[END_REF].

Recently, [START_REF] Zuber | Efficient homomorphic evaluation of k-nn classifiers[END_REF] proposed a secure k-NN algorithm in quadratic complexity concerning the size of the database completely non-interactively by using a fully homomorphic encryption [START_REF] Chillotti | TFHE: Fast fully homomorphic encryption library[END_REF]. However, they assume that the majority vote is done on a clear-text domain, which is a significant security flaw that we will address here. Doing a majority vote on a clear-text domain imposes interaction between entities, which causes information leakage.

Unlike other existing works, in this paper, we propose a new methodology to apply k-NN on encrypted data by using fully homomorphic encryption avoiding interaction between entities.

We consider a client/service provider architecture that supports scenarios described here. The service provider is a company that owns a labeled training dataset D composed of sensitive data allowing predict for novel observation by k-NN. This model is offered as a service.

We assume a context that is concerned by some privacy issues as in the following:

-Because the training data are sensitive, they cannot be shared with a third party such as a client. -The model is an intellectual property of the service provider. Hence, the service provider does not want to share the used model with his clients. -A client who needs to perform classification on the service-provider platform does not trust the service provider.

This work aims to do a classification using k-NN algorithm on sensitive data using HE. Our solution assumes that the service provider, which is the dataset owner, has all the necessary resources to perform the data classification and storage. This assumption ensures that encrypting the training dataset is not necessary since these data are kept with the data owner. Only the client will need to encrypt his query that includes his data by using a private key and by sending it to the data owner for classification. The goal is to protect the training dataset, the query, and the model parameter k. Our solution meets the following privacy requirement as in the following:

-The contents of D are known only by the data owner since they are not sent to other parties. -The client's query is not revealed to the data owner.

-The client knows only the predicted class.

-The index of the k nearest neighbors is unknown from the data owner or the client.

Our solution has a greater added value than the existing literature solutions. First, it guarantees that no information leakage occurs during the process: the only things known by the data owner are the dataset and the model used. The only things that the client knows are the query and the class. All intermediate results are encrypted. In addition, our solution is fully non-interactive since prediction is performed by the data owner and do not need any decryption during the process. Finally, it supports multi-label classification.

The rest of this paper is organized as follows: Section 2 presents the background of HE before highlighting the principle of Fast Fully homomorphic encryption over the Torus (TFHE). Our proposed solution is then described in Section 3. A simulation study is presented in Section 4 to assess our methodology based on real datasets. Finally, Section 5 concludes the paper.

BACKGROUND

2.1 homomorphic encryption HE allows a third party (a service provider in our scenario) to compute functions on ciphertexts to preserve the confidentiality of the data. An encryption scheme is called homomorphic over an operation * if it supports the following property:

E(m 1 ) * E(m 2 ) = E(m 1 * m 2 )
where E is the encryption algorithm and m 1 , m 2 belong to M the set of all possible messages. An additional algorithm is needed for homomorphic encryption schemes, called the Eval algorithm. This algorithm is defined as follows:

Eval(f, C 1 , C 2 ) = f (m 1 , m 2 )
where Dec(C 1 ) = m 1 and Dec(C 2 ) = m 2 and f is a function that determines the type of the HE scheme. In case f supports the evaluation of arbitrary functions for an unlimited number of times, the HE is called Fully homomorphic encryption (FHE).

This paper uses "TFHE: Fast Fully homomorphic encryption over the Torus" as an RLWE-based scheme in his fully homomorphic setting, especially in gate bootstrapping mode. The bootstrapping procedure is the homomorphic evaluation of a decryption circuit on the encryption of a secret key.

Functional Bootstrap in TFHE

TFHE defines three types of ciphertexts, TLWE Sample, TRLWE Sample and TRGSW Sample.

There are two bootstraps algorithms in TFHE. Gate Bootstrap was introduced to implement logic gates, and the Circuit Bootstrap, which converts TLWE samples to TRGSW samples. In our work, we use Functional Bootstrap. By "Functional" we mean that the bootstrap can evaluate functions using a BlindRotate algorithm to perform a lookup table (Lut) evaluation. LUTs are a simple, efficient way of evaluating discretized functions. For instance the sign function was used in [START_REF] Bourse | Fast Homomorphic Evaluation of Deep Discretized Neural Networks[END_REF] and [START_REF] Izabachène | Practical Fully Homomorphic Encryption for Fully Masked Neural Networks[END_REF].

OUR CONTRIBUTION

3.1

The System Model

Our system uses the client-server architecture (see Figure 1). The client is the querier, and the server is the data owner.

1. The data owner: owns the data and can do heavy calculations. For example, it receives the query in an encrypted way, performs an encrypted k-NN algorithm then sends the result to the querier for decryption. 2. The querier: generates the keys, encrypts the query that contains its data and sends it to the data owner for computations before decrypting the result. The querier can be an ordinary computer or any IoT device that collects data.

Fig. 1: The system model: the client is the querier, and the server is the data owner: the data owner receives the query in an encrypted way, performs an encrypted k-NN algorithm then sends the result to the querier for decryption.

Encrypted k-NN Challenges

In order to propose an encrypted version of k-NN, we should substitute the challenging operations used in the standard k-NN with equivalent operations in encrypted domains. As seen before, k-NN is composed of three parts: the distance calculation, the distance sorting, the selection of the k nearest neighbors, and the majority vote. This subsection will introduce the equivalent operations as integrated with our solution.

Distance Calculation The euclidean distance calculation between the dataset entries x i as well as the query q are necessary in order to find the k nearest neighbors to the query. We can use the standard formula of the distance as in (1).

d 2 (x i , q) = p j=0 x 2 ij + p j=0 q 2 j -2 * p j=0 x ij q j (1)
What is relevant in our case is the difference between two distances to compare them. So, we get the formula (2) as follows:

d 2 (x i , q) -d 2 (x i ′ , q) = p j=0 (x 2 ij -x 2 i ′ j ) -2 * p j=0 (x i ′ j -x ij )q j (2)
Since the dataset is a clear text, we can easily calculate formula (2) using the TFHE scheme. However, we need to adapt it. Using TFHE, the difference between the distances should be in the range of [-1 2 , 1 2 ]. Another constraint is that the multiplication is done between a clear-text integer and a ciphertext. Two rescaling values are required to resolve these constraints. Let v be the first one. It is used to have values of the differences between [-1 2 , 1 2 ]. Let p be the second one. It indicates the precision of the differences. Each attribute of the dataset as well as the query are rescaled using v. p is used when calculating the product

(x i ′ j -x ij )q j .
Sorting Sorting computed distances is a crucial step in k-NN. The standard algorithm for sorting, like the bubble sort, can be used while considering encrypted data. However, these algorithms are time-consuming in an encrypted world because the worst case is computed every time. The authors [START_REF] Gizem S C ¸etin | Depth optimized efficient homomorphic sorting[END_REF] propose two methods to sort an array of values. The method of the direct sort is used in [START_REF] Zuber | Efficient homomorphic evaluation of k-nn classifiers[END_REF]. It is based on a matrix of comparison called delta matrix:

     m 1,1 m 1,2 • • • m 1,n m 2,1 m 2,2 • • • m 2,n . . . . . . . . . . . . m n,1 m n,2 • • • m n,n      with m i,j = sign(X i -X j ) = 1 if X i < X j 0 else.
When summing columns of this matrix, we will have a sorting index of the distances.

Majority Vote

The majority vote can cause a problem because the operation requires comparison to detect the class. To determine the predicted class, we need to know k nearest neighbors' classes. This step is challenging in two ways: first, we need to avoid information leakage, unlike the solutions in the literature. Second, the majority vote requires comparison in order to predict the class.

To the best of our knowledge, no solution in the literature studied this point in an encrypted way without information leakage. Therefore, in the following subsection, we will demonstrate a solution to process k-NN with the majority vote in an encrypted way while supporting a multi-label classification.

Our proposed k-NN algorithm

Our proposed algorithm, called "HE-kNN-V", is composed of three steps: the construction of the delta matrix, the selection of k-nearest neighbors, and the majority vote. The two first steps are similar to the solution of [START_REF] Zuber | Efficient homomorphic evaluation of k-nn classifiers[END_REF] even if we adapt the existing formulas in order to eliminate unnecessary calculations. [START_REF] Zuber | Efficient homomorphic evaluation of k-nn classifiers[END_REF] use polynomials to define the formulas, while what interests us is just one term of those polynomials to eliminate un-necessary calculations. The majority vote is our added value and is specific to our solution. We will discuss in this subsection the design of our solution, including each building block.

Building the delta matrix To build the delta matrix, we need to know the sign of the differences between the distances to sort. Since we defined a method to calculate the differences in the last subsection, the sign can easily be achieved using the standard bootstrapping sign function in TFHE. However, the standard bootstrapping function returns +1 if the phase is greater than 0 and -1 if the phase is lower than 0. Therefore, since we need to have 0 or 1 in the matrix, we need to adapt the bootstrapping operation to return 1 2 and -1 2 then by adding 1 2 to the result we will have 0 or 1. Even if building this matrix is time-consuming, it is highly parallelizable.

Selecting the k-nearest neighbors To select the k-nearest neighbors, we use the scoring operation proposed by Zuber [START_REF] Zuber | Efficient homomorphic evaluation of k-nn classifiers[END_REF]. By using the delta matrix, the principle is as follows:

1. Sum m values in each column with m the number of possible operations without bootstrapping. 2. If there are still values to sum: do a bootstrapping operation using the modified sign bootstrapping function (See Algorithm 1 in [START_REF] Zuber | Efficient homomorphic evaluation of k-nn classifiers[END_REF]) and go to Step 1. 3. Otherwise, execute the modified sign bootstrapping and return the last sign returned by this operation.

Finally, we obtain an encrypted vector where the position i equals the cipher of 1 if the individual with index i is among the k-nearest neighbors, the cipher of 0 otherwise. We call this vector the "mask" (See Figure 2 for more clarity).

Majority vote

The majority vote is the most important added value in our work. We propose to do the majority vote without any leakage of information, unlike existing works like that of [START_REF] Zuber | Efficient homomorphic evaluation of k-nn classifiers[END_REF] in which the majority value is done in clear text or by using other alternative solutions proposed in the literature.

First, we illustrate the issue with the method of [START_REF] Zuber | Efficient homomorphic evaluation of k-nn classifiers[END_REF]. We consider the scenario where the querier does the calculations. The majority vote is done in clear text, but we need to decrypt the vector of indexes of the nearest neighbor. The data owner does the decryption. Significant information leakage occurs if the data owner knows the vector of indexes. Then, he will know the classification of the query, and by doing some triangulation, he can approximate the query. In addition, the solution will be interactive. If we consider the scenario where the data owner does the calculation, the decryption of the vector is done by the querier. However, to do the classification, the querier should know the labels of the dataset, which is also a critical leakage of information. In addition, the querier will know the size of the dataset and the k parameter of nearest neighbors considered. This information is considered as internal information of the model used, and it should be protected.

In our solution, the majority vote is done by the data owner in an encrypted way. First, the data owner encodes the labels using one hot encoding. Having the mask and the matrix of labels in one hot form, it is easy to do an AND operation between the mask and each column of the labels, as in Figure 2. We get a matrix A (for affectation) with A ij equal to 1 if the individual i is among the k-nearest neighbors and its class is j. Using this matrix, it is possible to sum the columns and obtain the probability of each class. We can now return only the class and guarantee no information leakage and no interactivity.

PERFORMANCE EVALUATION

In this section, we discuss the experiments of our solution. First, we describe the technical and the setup of the environment. Then, we will evaluate the performances of our solution according to different criteria: execution time, accuracy, bandwidth consumption.

Test Environment

Setup Our solution is implemented using the TFHE scheme in C/C++ and Python for training k-NN in clear text and for tests. To test the effect of parallelism, we used OpenMP to do some parallelization. The source code is available in the following github "https://github.com/Yulliwas/HE-kNN-V". Our solution is tested on Linux Ubuntu 64-bit machine with i7-8700 CPU 3.20GHz.

Table 1 shows the parameters used to setup TFHE scheme.

λ N σ 110 1024 10 -9

Table 1: TFHE Parameters: λ for the overall security, N for the size of the polynomials,σ for the Gaussian noise parameter. Table 3: Datasets: number of individuals(n), the size of the model (d) and number of classes Simulation procedure First, we preprocess the data by rescaling each attributes to a value between 0 and 1. Our dataset and the query should be rescaled by a factor of v as seen above. We must also multiply the dataset vectors by the precision factor τ and then rounded. In the other hand, the query vector is divided by this same factor. To obtain the classification rate, first we need to divide our dataset to a training set and a test set. We choose to use 20% of our dataset as a test set and the rest as a training set. Among the training set, we select a certain number of points that represent as well as possible our dataset. The process for choosing the best points that represent our training set is as follows:

1. choose n individuals randomly ; 2. calculate the classification rate ; 3. Repeat the previous Step 1 and Step 2 a certain amount of time and keep the best accuracy and the best individuals.

To select the k parameter, we use the same procedure as in the clear domain. In our case, we tested different values of k and we keep the best k value that gives the best results.

Performance results

To position our approach according to existing works, and especially regarding the voting step that is performed without information leakage, we compare in Table 4 our solution with Zuber's solution and with a clear-text version based on the Iris dataset and a fixed k=3. The comparison is done in terms of complexity (C), Information Leakage (L), accuracy (A), interactivity (I) and execution time (T). The accuracy and the prediction time are indicated only when it is possible.

Empirical study

Classification rate To evaluate the classification rate, we have chosen the accuracy instead of other metrics like: recall or F1-score. We studied the accuracy according to two parameters: the number of data sampled from the dataset and the number k of neighbors. The goal is to choose the best points that represent the datasets and the best k parameters for each dataset. We chose real-world datasets in order to see the evolution of the accuracy and compared it to clear-text accuracy.

In one hand, we know that the accuracy depends on the k parameter and we can confirm it easily in the graphs. On the other hand, the assumption that the accuracy depends on the number of data used is not complete. For the dataset where the data is well separated (like Iris), having a lot of data is not necessary, the best accuracy can be achieved using only few data. But, in the case where data is not well separated (like in Heart dataset), the accuracy seems to depend on the number of data. According to our different simulations illustrated in Figure 3 and Figure 4, we do not lose accuracy when we apply our HE-kNN-V method on the encrypted data compared to the application of the kNN on the plain data. This is possible by varying the number of individuals and by fixing k to 3.

We also notice that by setting the number of individuals to 40 and varying k, (see Figure 5 and Figure 6) the accuracy behaves in the same way between the application of the kNN on the plain data and the application of our method HE-kNN-V on the encrypted data.

Execution time In our solution, the execution time is independent of the content of the dataset, it does not depend on the values, but does depend on the content, since it depends on the number of tuples . We can use either simulated dataset or real world dataset. To visualize the evolution of the execution time according to k, n and d, we choose to use the Breast Cancer dataset instead of simulating a new dataset. We change n, k, d and we see the evolution of the execution time. Our simulations, as depicted in Figure 7, illustrate that HE-kNN-V is parallelizable, and also that the number of individuals strongly impacts the execution time unlike the two simulations of Figure 8 and Figure 9 where the variation of respectively d the number of attributes and k does not impact the execution time.

Bandwidth In our solution, the only thing that is communicated is the query in the ciphertext and the response in the ciphertext. The size of the query is proportional to the number of attributes d. Each attribute is a TLWE Sample with the size of 4 KB and the size of the response (number of classes)*4 KB. The bandwidth according to each dataset is illustrated in Table 5. Discussion According to our experiments, we can say that the accuracy in our case depends on three factors: the number of individuals, the representativity of these individuals and the k parameter. To have a better model that fits our dataset, we must select the individuals that are more representative of our dataset and the best k parameter. We also should take care of the number of individuals because most of the execution time depends on that number.

CONCLUSION

We proposed HE-kNN-V a method for performing k-NN on encrypted data that includes a majority vote for class-label assignment. The proposed solution addresses all stages of k-NN algorithm with fully encrypted data. It guarantees that no information leakage occurs during the process. Unlike other techniques, our solution eliminates the need for intermediate interactions between the server and the client when performing classification tasks. Our algorithm has been evaluated using quantitative variables and demonstrated its efficiency on large and relevant real-world data sets. As a perspective, it would be interesting to see how a hardware acceleration of the TFHE scheme could improve the computation time of our proposed solution HE-kNN-V.

Fig. 2 :

 2 Fig. 2: Majority Vote illustration by using the mask

  -V O(n 2 ) N N 0.97 1.72s HE-kNN-VP O(n 2 ) N N 0.97 0.46s Zuber O(n 2 ) Y Y 0.98 1.74s Clear k-NN O(n) Y N 0.95 1.8msTable 4: Comparison between solutions for Iris Dataset: complexity (C), Information Leakage (L), accuracy (A), interactivity (I) and execution time (T).

Fig. 3 :Fig. 4 :Fig. 5 :Fig. 6 :

 3456 Fig. 3: Encrypted Accuracy vs number of individuals

Fig. 7 : 8 :Fig. 9 :

 789 Fig. 7: Execution time vs number of individuals Fig. 8: Execution time vs number of attributes

Table 2 :

 2 Datasets To test our solution, we choose to use 6 datasets: Iris, Breast Cancer, Wine, Heart, Glass and MNIST as in Table3. The goal is to test the performances of our algorithm in different distributions of data, so that to confirm that our solution works with any dataset and that has performances that are equivalent to those of clear-text domains.

	HE-kNN Parameters:
	the number of operations m
	without needing a
	bootstrapping, the
	bootstrapping base b, and the
	rescaling factors v and p

Table 5 :

 5 Bandwidth

	Dataset	Bandwidth (KB)
	Iris	28
	Wine	64
	Heart	64
	Breast Cancer	128
	Glass	60
	MNIST	296


Yulliwas Ameur

Samia Bouzefrane

Vincent Audigier

Book chapter: Application of Homomorphic Encryption in Machine Learning

Big data technologies, such as machine learning, have increased data utility exponentially. At the same time, the cloud has made the deployment of these technologies more accessible. However, computations of unencrypted sensitive data in a cloud environment may expose threats and Cybersecurity attacks. We consider a class of innovative cryptographic techniques called Privacy-Preserving Technologies (PPTs) to address this problem. That might help increase utility by taking more significant advantage of the cloud and machine learning technologies while preserving privacy.

The first section provides a brief introduction to the so-called Homomorphic Encryption "HE" by giving an overview of the most promising schemes and then giving the current state of the art of HE tools such as Libraries and Compilers. This section aims to help non-cryptographer developers propose HE solutions by explaining what makes developing HE applications challenging.

Then, we address the Privacy-Preserving in Machine Learning (PPML), an approach that allows to train and deploy ML models without exposing their private data. After exploring state-of-the-art for the most used ML models in PPML, we will overview applications of Homomorphic Encryption in Machine Learning.

1

Introduction to Homomorphic Encryption

This new encryption paradigm allows any entity (for example, the cloud provider) to operate on private data in encrypted form without ever decrypting it. The goal of HE is to perform operations on the plain text while manipulating only ciphertexts. Usually, we must decrypt them and then apply the desired processing to manipulate encrypted data. For example, one widespread use case is outsourcing healthcare data to cloud computing services for medical studies (Figure 1). Figure 1: "diagram showing how to manipulate encrypted data on a cloud. On the left, the user encrypts the data before sending it to the cloud, on the right, the cloud service has to decrypt the data in order to process it."

For some cryptosystems with algebraic structures, some operations are possible. For example, two RSA ciphertexts can be multiplied to obtain the multiplication of the two corresponding plain texts. We call this property the multiplicative homomorphic property of the "textbook RSA" cryptosystem. Another operation can also be performed on ciphertexts. For example, in the Paillier cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] , we can add two ciphertexts to obtain the addition of the two corresponding plain texts. We call this property the additive property of the "Paillier" cryptosystem. For example, this can be useful when we are interested in e-voting applications to add encrypted votes without knowing the initial vote.

Rivest, Adelman and Dertouzos first introduced the notion of homomorphic encryption in [START_REF] Rivest | On Data Banks and Privacy Homomorphisms[END_REF]. Building a cryptosystem with both multiplicative and additive properties was a significant problem in cryptography, until the work of Gentry [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]. Gentry proposed a first Fully homomorphic encryption based on ideal lattices. The HE is categorized depending on the number of mathematical operations performed on the encrypted message as following: Partially Homomorphic Encryption (PHE), Somewhat Homomorphic Encryption (SHE), and Fully Homomorphic Encryption (FHE). Over encrypted data, FHE allows arbitrary addition and multiplication. Because any functions may be expressed as Boolean circuits, an encryption scheme capable of performing addition and multiplication can theoretically evaluate any polynomial function [START_REF][END_REF]. When operations are performed on ciphertexts, the noise increases and too much noise disables accurate decryption. The bootstrapping approach is used by FHE systems to get around this as stated in [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]. Bootstrapping decreases the collected noise, allowing further computation. This procedure can be done as many times as necessary to analyze any particular circuit. However, bootstrapping is computationally costly, so many solutions do not employ it in reality. Therefore, we recommend the reader to refer to [START_REF] Acar | A Survey on Homomorphic Encryption Schemes: Theory and Implementation[END_REF] for more detailed information on the different homomorphic encryption schemes. We have chosen not to describe the entire functioning of cryptosystems due to the lack of space. Also, selecting secure and efficient instantiations of the underlying cryptographic problem is hard for most of encryption and homomorphic schemes. Therefore, we have chosen to list the most studied schemes by the community of researchers and developers interested in advancing homomorphic encryption.

As usual, new cryptographic proposals need a few years before widespread adoption in the industry, as was the case of Elliptic Curve Cryptography, postquantum encryption and many other standardization projects.

We are waiting for the standardization results and recommendations of the workshops, which include representatives from industry, government organizations and academia.

This brief review aims to guide readers fast enough, even if they are not cryptography specialists, to the appropriate HE scheme by directing them to the library(ies) where HE is implementable.

HE Schemes

Research in the field of FHE may be classified into four major groups. The first family represents the difficulty based on the lattice reduction problem, which mainly comes from Gentry's seminal work [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]. The second category consists of integer-based methods [START_REF] Van Dijk | Fully Homomorphic Encryption over the Integers[END_REF], the hardness of which is based on the Approximate of Greatest Common Divisor (A-GCD) problem [START_REF] Gentry | Computing Arbitrary Functions of Encrypted Data[END_REF]. Schemes based on Learning with Error (LWE) [START_REF] Regev | On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[END_REF] and Ring Learning with Error (RLWE) [START_REF] Lyubashevsky | On Ideal Lattices and Learning with Errors over Rings[END_REF], both reducible to lattice problems, constitute the third family. Finally, the Nth-Degree Truncated Polynomial Ring Unit (NTRU) family [START_REF] Rohloff | A Scalable Implementation of Fully Homomorphic Encryption Built on NTRU[END_REF].

All HE schemes have common steps: key generation, encryption, decryption and homomorphic operations on the ciphertexts.

Table 1 summarizes the most implemented and studied schemes by the cryptographic community, and the figure 2 give an overvieww of the Homomorphic Encryption timeline.

Operation SCHEMES BFV BGV CKKS FHEW TFHE Native Add/Sub ✓ ✓ ✓ ✗ ✗ Native Mult ✓ ✓ ✓ ✗ ✗ Boolean Logic ✗ ✗ ✗ ✓ ✓ SIMD ✓ ✓ ✓ ✓ ✓
The choice of encryption scheme has a multitude of implications:

• It specifies which operations are possible and, as a result, which types of activation and architectures may be employed.

• It can determine the plaintext space. Messages should be encoded before they may be sent in plaintext. The majority of schemes, including BGV, BFV, only support integers. CKKS can handle real numbers, but TFHE can only handle individual bits.

HE Librairies

There exist several open-source libraries for the implementation of the HE scheme. They provide key generation, encryption, decryption, and homomorphic operations for each scheme; library APIs frequently include additional features for maintaining and manipulating ciphertexts. Even though there is a lack of technical interoperability, but also a lack of conceptual interoperability; for

Rust ✗ ✗ ✗ ✗ ✓ FHEW C++ ✗ ✗ ✗ ✓ ✗ FV-NFlib C++ ✓ ✗ ✗ ✗ ✗ HEAAN C++ ✗ ✗ ✓ ✗ ✗ HElib C++ ✓ ✓ ✓ ✗ ✗ lattigo Go ✓ ✗ ✓ ✗ ✗ PALISADE C++ ✓ ✓ ✓ ✓ ✓ SEAL C++, .NET ✓ ✓ ✓ ✗ ✗ TFHE C++ ✗ ✗ ✗ ✗ ✓ HE-GPU-TARGETING cuFHE C++, Python ✗ ✗ ✗ ✗ ✓ nuFHE C++, Python ✗ ✗ ✗ ✗ ✓
example, even libraries that use the same scheme can provide surprisingly different results. The ongoing standardization efforts attempt to develop a unified view of the most popular schemes.

FHE Restrictions

Current HE methods have a significant restriction. They cannot support division operations and comparisons easily, such as the equality/inequality test. Number comparison and sign determination are critical processes for MLaaS 2 Privacy-Preserving in Machine Learning (PPML):HEsolutions

Using a third-party infrastructure reduces the problems of resources and complexity but introduces privacy issues of sensitive information. To construct a privacy-preserving framework for machine learning techniques, it must first identify the most important privacy requirements:

• Input privacy: Only the real data owner should have access to the input.

• Output privacy: The output/result of the ML methods' assessment is not permitted to be known by the cloud server.

• Model privacy: A private machine learning model that is also an asset should not be shared with anyone except its owner.

Another approach is to look if the privacy-preserving framework targets the learning phase or the inference phase of the machine learning algorithm.

Depending on the framework we want to design, we have to use privacypreserving technologies. The leading privacy Preserving Machine Learning techniques are

• Multi-party Computation: These methods involve one or more trusted parties that can be used to outsource specific computations by the algorithm owner.

• Differential Privacy: These methods rely on data randomization and perturbation. Because it affects the information, this method has the drawback of negatively influencing the model's performance.

• Federated Learning: Federated learning is a machine learning setting where many clients collaboratively train a model under the administration of a central server while keeping the training data local.

• Garbled Circruit: Garbled Circuit, also known as Yao's garbled circuit, is an underlying technology of secure two-party computation initially proposed by Andrew Yao. GC provides an interactive protocol for two parties (a garbler and an evaluator) obliviously evaluate an arbitrary function represented as a Boolean circuit.

• Homomorphic Encryption: An encryption that allows performing operations over encrypted data. See section 1 for more detail.

• Hybrid PPML Techniques: In addition to the above-mentioned singleprotocol PPML, some commonly used frameworks typically use hybrid protocols, which combine two or more protocols by making use of the advantages and avoiding the problems of each. For example, the basic idea behind the mixed protocol that combines HE and GC is to calculate operations that have an efficient representation as Arithmetic circuits (e.g., additions and multiplications) using HE and operations that have an efficient representation as Boolean circuits (e.g., comparisons) using GC. However, converting between share systems is not simple, and the charges are very high. Furthermore, various frameworks integrate MPC with Differential Privacy.

We are interested therein Machine Learning Research Using Homomorphic Encryption "HEML". According to this Bibliometrics [START_REF] Chen | Bibliometrics of Machine Learning Research Using Homomorphic Encryption[END_REF], the number of papers on HEML has constantly been rising since 2009. Each year from 2005 to 2015, fewer than 100 HEML papers were published. However, the number of publications per year increased significantly after 2015, reaching between 200 and 500 in recent years. This section summarizes recent works and gives many practical applications of homomorphic encryption for privacy-preserving purposes for each machine learning algorithm. We end the section with a summary of the work to ease the reading of this synthesis.

Logistic Regression

Logistic regression is a powerful machine-learning approach that uses a logistic function to model two or more variables. Logistic models are commonly used in the medical community to predict binary outcomes, such as whether a patient requires treatment or whether a disease appears [START_REF] Hastie | Unsupervised learning[END_REF]. It has been utilized in applications such as evaluating diabetes patients' medications [START_REF] Bender | Ordinal logistic regression in medical research[END_REF], and social sciences [START_REF] Gayle | Logistic regression models in sociological research[END_REF].

iDASH is an annual competition that attempts to deploy novel cryptographic methods in a biological environment. Since 2014, genomics and biomedical privacy have been incorporated into iDASH. Both the third track of the 2017 iDASH competition [START_REF] Wang | iDASH secure genome analysis competition[END_REF] and the second track of the 2018 iDASH competition driven the development of homomorphic encryption-based solutions for building a Logistic regression model over encrypted data. The performance of LR training based on homomorphic encryption (HE) has improved significantly as a result of these two competitions.

Homomorphic encryption has been used in much research on training logistic regression models.

[16] trained a privacy-preserving logistic regression model using HE; however, the time complexity of linear HE increases exponentially with the number of parameters.

[17] used an additive HE scheme and delegated particular challenging HE computations to a trusted client, the authors in this work introduced an approximation to convert the likelihood function into a low-degree polynomial.

The issue of doing LR training in an encrypted environment was discussed by [START_REF] Kim | Secure logistic regression based on homomorphic encryption: Design and evaluation[END_REF]. They used complete batch gradient descent in the training phase, using the least-squares approach to approximate the logistic regression. They also employed the CKKS scheme, which allows for a homomorphic approximation of the sigmoid function.

There is no closed-form solution to logistic regressions, so we must use nonlinear optimization methods to find the maximum likelihood estimators of the regression parameters. During training, gradient descent and Newton-Raphson are the most commonly used methods. The Newton-Raphson method requires matrix inversion, and most HE schemes do not natively support division and matrix inversion. On the other hand, Gradient descent does not require the division operation and so is a better candidate for homomorphic logistic regression.

Although the gradient descent approach appears to be better suited for homomorphic evaluation than other training methods, some technical issues remain for implementation. The sigmoid function is the most challenging to evaluate since existing homomorphic encryption techniques only allow the evaluation of polynomial functions, so Taylor polynomials have been widely employed for sigmoid function approximation [START_REF] Joppe W Bos | Private predictive analysis on encrypted medical data[END_REF][START_REF] Mohassel | Secureml: A system for scalable privacy-preserving machine learning[END_REF] For implementation and performance of Private Logistic Regression (Hebased solutions), see the table 3

Naive Bayes and Decision Trees

Naive Bayesian classification is a simple probabilistic Bayesian classification based on Bayes' theorem. It uses a naive Bayesian classifier, or naive Bayes classifier, belonging to the family of linear classifiers. [START_REF] Bost | Machine Learning Classification over Encrypted Data[END_REF] propose a privacypreserving Naive Bayes classification algorithm. A client learns the classification of her data point X in their model without knowing the classification model or disclosing any information about her input. The model's estimated parameters are encrypted and transferred to a cloud server. The authors use two partially homomorphic encryption schemes, Quadratic Reciprocity [START_REF] Goldwasser | Probabilistic Encryption & How to Play Mental Poker Keeping Secret All Partial Information[END_REF] and Paillier [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF], in the same work [START_REF] Bost | Machine Learning Classification over Encrypted Data[END_REF] implements a privacy-preserving strategy for three algorithms, and one of those is decision trees. This work has shown that polynomials may be utilized to express decision trees. The decision tree node values must be compared to the evaluation data, and the outputs must be used to construct the polynomial, yielding the evaluation results.

For implementation and performance of Private Naive Bayes and Decision tree (He-based solutions), see the table 4

K-nearest neighbors

The k-Nearest Neighbors (k-NN) a simple method that can handle continuous, categorical, and mixed data. Furthermore, as a non-parametric method, k-NN can be relevant for many data structures as long as the number of observations is sufficiently large. In addition, for a predefined number of neighbors k, the model does not require any training step since the prediction for a new observation is obtained by: • Computing the majority class among them (for a classification problem) or by averaging values (for a regression problem).

Homomorphic encryption has already been investigated by various authors for k-NN [START_REF] Li | Exploring Privacy Preservation in Outsourced K-Nearest Neighbors with Multiple Data Owners[END_REF][START_REF] Bharath | k-Nearest Neighbor Classification over Semantically Secure Encrypted Relational Data[END_REF][START_REF] Wai | Secure KNN Computation on Encrypted Databases[END_REF][START_REF] Zuber | Efficient homomorphic evaluation of k-NN classifiers[END_REF].

The authors of [START_REF] Li | Exploring Privacy Preservation in Outsourced K-Nearest Neighbors with Multiple Data Owners[END_REF] suggested a Homomorphic additive encryption scheme [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. They investigated the privacy preservation in an outsourced k-NN system with various data owners. The untrusted entity securely computes the computations of distances by using HE. However, the comparison and classification phases require interactions. Given that the computational and communication difficulties scale linearly, they admit that the method may not be practical for massive data volumes. The cost of communications between the entities is also a limitation in the deployment of this work [START_REF] Bharath | k-Nearest Neighbor Classification over Semantically Secure Encrypted Relational Data[END_REF].

Recently, [START_REF] Zuber | Efficient homomorphic evaluation of k-NN classifiers[END_REF] proposed a secure k-NN algorithm in quadratic complexity concerning the size of the database completely non-interactively by using a fully homomorphic encryption [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF]. However, they assume that the majority vote is done on a clear-text domain, which is a significant security flaw that we will address here. Doing a majority vote on a clear-text domain imposes interaction between entities, which causes information leakage. For implementation and performance of Private k nearest neighbors (He-based solutions), see the table 5

Neural Networks and Deep Learning

Deep learning is one of the most sophisticated techniques in machine learning, and it has received a lot of attention in recent years. It is presently employed in a variety of areas and applications, including pattern recognition, medical prediction, and speech recognition. Deep learning experiences are enhanced significantly by utilizing strong infrastructures such as clouds and implementing collaborative learning for model training. However, this compromises privacy, particularly when sensitive data is processed during the training and prediction stages, as well as when the training model is disseminated. In this section, we discuss known privacy-preserving deep learning algorithms based on homomorphic encryption, we present recent challenges concerning the intersection of HE cryptosystems and Neural Networks models, as well as methods to overcome limitations.

HE cannot be used naively in neural networks algorithms. There are a lot of challenges and restrictions that must be overcome. The constraints differ according to the scheme, however, several common issues emerge in most systems. The learning and inference phases of the deep learning algorithm can be distinguished.

Privacy preserving deep learning: Private training

Several techniques have been proposed; they consider collaborative training, in which the training is performed collaboratively between different participants, or individual training, in which the training is performed by a single participant, such as a client who wants to use a cloud to train its model. [START_REF] Aono | Privacy-preserving deep learning via additively homomorphic encryption[END_REF] proposed a solution in collaborative learning mode, where participants send the calculated encrypted local gradients to the cloud after each iteration of local training, starting with the initial weights obtained from the cloud. To ensure homomorphic ciphertext integrity, each participant uses a unique TLS/SSL secure channel. The cloud then updates the encrypted global weights vector, which the participants download. The approach theoretically achieves the same accuracy as standard asynchronous SGD, whereas evaluations show that MLP and CNN reach 97 percent and 99 percent accuracy, respectively. In terms of efficiency, an overhead in communication and calculation was seen; however, the authors considered it negligible. However, the accuracy/privacy trade-off might be adjusted to efficiency/Privacy, allowing the precision to be preserved while maintaining Privacy.

The privacy-preserving back-propagation technique described in [START_REF] Bu | Privacy preserving back-propagation based on BGV on cloud[END_REF] is based on BGV fully homomorphic encryption and Maclaulin polynomial approximation of the sigmoid activation function. The client encrypts input data and configured parameters before uploading them to the cloud, which executes one loop. The client downloads and decrypts the findings before updating its local model. It then encrypts and sends the updated parameters back to the cloud, which repeats the process. This method is repeated until the maximum error threshold or number of iterations is achieved. Although BGV encryption provides for the protection of private data throughout the learning process, it does need the approximation of the activation function. This might lead to a drop in accuracy. In terms of efficiency, while the solution achieved a two times greater efficiency, i.e., 45 percent of the training time of the standard model, it experienced compute and communication costs due to the encryption-related overhead.

[30] employs the Taylor theorem to estimate the sigmoid activation function polynomially. The evaluation findings revealed a reduction in accuracy for both classification and prediction tasks. However, the authors proposed adding additional Taylor series terms to decrease classification loss, raising the BGV encryption level, resulting in poor performance. The method could achieve 2.5 times greater classification efficiency and two times higher overall efficiency in learning time.

[31] described a more recent solution based on encryption. A client who wants to participate to the model's training transmits its data encrypted using the Paillier scheme [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] to the server, which performs all possible neural network calculations except non-linear activation functions. To continue execution, the encrypted weighted sums before each activation function are provided to the client, who will be in charge of performing the calculation. The result is then encrypted again and sent back to the server.

privacy preserving deep learning: Private inference

Fully homomorphic encryption is deployed in a line of research that performs private classification of encrypted data using a neural network that has been trained using plain data. [START_REF] Gilad-Bachrach | Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy[END_REF] is the first solution for Privacy-preserving deep learning for inference, developed by Microsoft Research. The approach is based on the YASHE a (Leveled Homomorphic Encryption) LHE scheme was proposed. The user encrypts their data and sends it to the cloud, which runs the model and returns an encrypted prediction. It has since been demonstrated that the YASHE scheme is vulnerable to subfield lattice attack [START_REF] Albrecht | A Subfield Lattice Attack on Overstretched NTRU Assumptions[END_REF]. To make the network compatible with homomorphic encryption, max-pooling is replaced by a scaled-mean pool function, and activation functions are approximated by the square function, which is the lowest-degree non-linear polynomial function. According to the authors, these adjustments should preferably be considered during training on unencrypted data. For example, the solution could achieve 99% accuracy and 59000 predictions per hour on a single PC for the MNIST dataset.

[34] To overcome the heavy computation cost of HE, a dual cloud model was proposed, in which two clouds, A and B, collaborate to generate classification results in a secure environment. Cloud A operates the neural network on private data encrypted by the client with Paillier cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF], but delegates activation function computations to the cloud B since they share a key. The technique is repeated until the final layer is reached. Client A then protects the final output with a random salt from cloud B, which uses the softmax function and sends the final encrypted result to the client. A theoretical scenarios-based security and accuracy study demonstrated how the approach successfully defends against potential threats.

[35] suggested a method for classification problems over the CNN model based on BGV an FHE scheme. The combination of polynomial approximation and batch normalization is the major technological breakthrough. During the training phase, a batch normalization layer is introduced before each ReLU layer to avoid excessive accuracy deterioration, and max-pooling is replaced by average-pooling, which is more FHE-friendly and has a small overhead.

Prior to each ReLU, a batch normalization layer is introduced with a lowdegree (2) polynomial approximation. When the model is complete, the user encrypts its private data and sends it to the model, carrying out the specified analysis. The evaluation findings revealed that the solution has a short running time, with comparable performance, as if there was no privacy.

[36] Attempt to use HE for deep learning problems. They provide methods by using low degree polynomials to approximate the most generally used neural network activation functions (ReLU, Sigmoid, and Tanh). This is a critical step in the development of effective homomorphic encryption methods. They then train convolutional neural networks using those approximation polynomial functions before implementing the models over encrypted data and evaluating its performance.

[37] suggest a recent homomorphic encryption-based approach. The user encrypts their personal information and transmits it to the server for prediction. The Paillier scheme accelerates linear, convolutional, and pooling transformations. The authors chose ReLU as the activation function and suggested, rather than utilizing polynomial approximation, an interactive protocol between the client and the server for its computation. The user gets the ReLU input data, decrypts it, and communicates the positivity or negativity of this input to the server, enabling the server to calculate the output. The evaluation findings revealed that the solution could reach near model accuracy in plain text and was similar to Cryptonet [START_REF] Gilad-Bachrach | Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy[END_REF]. In terms of efficiency, the approach saves a significant amount of time.

Recently, authors in [START_REF] Chillotti | Programmable Bootstrapping Enables Efficient Homomorphic Inference of Deep Neural Networks[END_REF] have resulted in considerable improvements by using the scheme TFHE [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF]. FHE methods permit unrestricted encrypted operations and give accurate polynomial approximations to non-polynomial activation functions using a programmable bootstrapping technique, an extension of the bootstrapping technique that allows resetting the noise in ciphertext to a fixed level while-at the same time-evaluating a function for free.

Clustering

Clustering is an unsupervised machine learning problem that automatically identifies natural grouping (clusters) in data.

A clustering algorithm can be collaborative or individual. In both cases, a model can be based on a server, and the calculations are exclusively performed on the server or assisted by a server. In this case, some calculations are delegated to the server.

Individual clustering

A clustering is individual if only one person has data and he wants to have the results of the clustering of this data. Most of the works interested in this kind of clustering require an intermediate decryption step.

The authors [START_REF] Theodouli | Implementing private k-means clustering using a LWE-based cryptosystem[END_REF] demonstrate a solution to perform k-means using a collaboration between the client and a server. They used the BV scheme [START_REF] Brakerski | Fully homomorphic encryption without bootstrapping[END_REF]. In this work, they proposed three variant solutions. Each solution takes as input a dataset of dimension nxd, an integer k wich denotes a the number of clusters and a threshold of iterations. The algorithm returns a matrix of dimension kxd that indicates the cluster centers. In the first variant, the computation of the centers and the assignment are done at the client level, which implies that the client performs a lot of computations (only the distances are computed at the server level). In the second variant, the client performs the comparisons and the division. At the same time, the server calculates the distances and the assignment of the points, then the sum to calculate the new centers. This variant induces an information leakage on how the points are distributed on the clusters. Finally, a third variant tries to solve the information leakage problem by returning an encrypted assignment vector of a point instead of the clear assignment. The authors [START_REF] Almutairi | K-Means Clustering Using Homomorphic Encryption and an Updatable Distance Matrix: Secure Third Party Data Clustering with Limited Data Owner Interaction[END_REF] propose a method for k-means that limits interaction with the data owner using the concept of "Updatable Distance Matrix (UDM)". The latter is a 3D matrix whose first two dimensions equal the number of data in the dataset, and the third dimension equals the number of attributes. Each cell in the matrix is initialized to the difference between the attributes of the data vectors. The idea is to save the encrypted data and the UDM matrix to a third party. This matrix is updated at each iteration of k-means using an offset matrix obtained by calculating the difference between the new and current centers. This method is expensive in terms of time and memory to store the UDM matrix.

The authors [START_REF] Jäschke | Unsupervised Machine Learning on Encrypted Data[END_REF] have tried an exact implementation of k-means that requires no intermediate decryption. Instead, the method relies on building a logic circuit to perform k-means using TFHE. From a theoretical point of view, the method gives equivalent results to the plaintext version. However, this method is not feasible; with two dimensions and 400 points, the execution time has been estimated at 25 days.

The authors [START_REF] Sakellariou | Homomorphically Encrypted K-Means on Cloud-Hosted Servers with Low Client-Side Load[END_REF] also propose a solution that focuses on k-means. In this solution, the BGV scheme [START_REF] Brakerski | Leveled) Fully Homomorphic Encryption without Bootstrapping[END_REF] is used. The authors remark that deciphering the intermediate steps at the client level is a costly operation. The proposed solution relies on using a third party as a trusted entity to decrypt the intermediate results. A private key equivalent (but different) to the owner's and a switch matrix are generated to be used by the trusted server. The proposed solution is considered secure in a semi-honest model but not in the malicious case.

Discussion and challenges

Many challenges need to be tackled to apply privacy-preserving machine learning in real-world applications. Although the HE standards, platforms, and implementations described in this chapter contribute to the advancement of HEML, there are still specific remaining challenges to be tackled, including overhead, performance, interoperability, bootstrapping bottlenecks, sign determination, and common frameworks:

• Overhead: Compared to its unencrypted counterpart, HEML has significant overhead, making it unsuitable for many applications. However, for non-HE models, the training phase of ML comprises a computationally intensive effort. However, even with modern techniques, it becomes increasingly difficult with HE. A recent trend is to bypass the training step by employing pre-trained models to find a balance between complexity and accuracy.

• Parallelization: Incorporating well-known and new leading to many algorithms is one approach to deal with the computational overhead. Highperformance computers, distributed systems, and specialized resources can all be used in HEML models. Multi-core processing units (GPUs, FPGAs, etc.) and customized chips (ASICs) provide more friendly and efficient HEML environments. Another approach to improving overall efficiency is batching and parallelizing numerous bootstrapping operations.

• Comparison and min/max function: We need new methods to compare numbers which are encrypted by Homomorphic Encryption (HE). Actually, comparison and min/max functions are evaluated using Boolean functions where input numbers are encrypted bit-wise. However, the bitwise encryption methods require relatively expensive computations for basic arithmetic operations such as addition and multiplication.

• PPML tools For the deployment of these technologies,it is practically difficult to design a high-performing and secure PPML solution without a thorough HE understanding. However, PPML developers must be knowledgeable in both machine learning and security. PPML, which uses HE, has not been extensively accepted by the ML community due to HE's high barrier to entry and the absence of user-friendly tools.

• Hybrid protocols Adopting hybrid protocols, which combine two or more protocols to use the advantages and avoid the disadvantages of each, is a promising direction for performance improvements.

Figure 2 :

 2 Figure 2: Homomorphic Encryption timeline

Figure 3 :

 3 Figure 3: HEML scenario

Table

Table 2

 2

	: Overview of existing FHE librairies: CPU-targeting (top)
		and GPU-targeting (bottom)
	Name	Input language	Supported schemes BFV BGV CKKS FHEW TFHE
		HE-CPU-TARGETING
	Concrete

Table 3 :

 3 Summary of main works on Private Prediction for Logistic Regression

	REF	HE scheme / Type	Plateform	Evaluation Time	Accuracy	Datasets
			Logistic Regression
	[16]	[1] /LHE	-	-	82.89%	Dataset SPECT -267 instances -23 features
	[17]	[1] /LHE	2.60 GHz x 2 CPU, 128 GB RAM.	-	73.7%	SPECTF heart dataset -267 instances -44 features)
	[17]	[1] /LHE	2.60 GHz x 2 CPU, 128 GB RAM.	-	80.7%	Pima diabetes dataset -768 instances -8 features
	[18]	CKKS / LHE	intel Xeon 2.3 GHz processor with 16 cores and 64GB of RAM,	131min	86.03%	Edinburgh -1253 instances -10 features
	[18]	CKKS / LHE	intel Xeon 2.3 GHz processor with 16 cores and 64GB of RAM,	101min	69.30%	Lbw -189 instances -10 features
	[18]	CKKS / LHE	intel Xeon 2.3 GHz processor with 16 cores and 64GB of RAM,	265min	79.23%	Nhanes3 -15649 instances -16 features
	[18]	CKKS / LHE	intel Xeon 2.3 GHz processor with 16 cores and 64GB of RAM,	119min	68.85%	Pcs -379 instances -10 features
	[18]	CKKS / LHE	intel Xeon 2.3 GHz processor with 16 cores and 64GB of RAM,	109min	74.43%	Uis -575 instances, -9 features
	[19]	YASHE / LHE	Intel Core i7-3520M at 2893.484 MHz	-	-	Heart Disease Framingham -4,000 instances -15 features
			Amazon EC2
	[20]	linearly homomorphic encryption	c4.8xlarge machines running Linux, with	149.7sec	98.62%	MNIST dataset -60 000 instances -784 features
			60GB of RAM each.

Table 4 :

 4 Summary of main works on Private Prediction for Naive Bayes and Decision Tree

	REF	HE scheme / Type	Plateform	Evaluation Time	Accuracy	Datasets
			Naive Bayes
			two Intel Core
	[21]	[1] + [22] /LHE	i7 (64 bit) processors for a total 4 cores running at 2.66 GHz	479 ms	-	Breast Cancer -2 classes -9 features
			and 8 GB RAM.
			two Intel Core
	[21]	[1] + [22] /LHE	i7 (64 bit) processors for a total 4 cores running at 2.66 GHz	1415 ms	-	Nursery -9 classes -5 features
			and 8 GB RAM.
			two Intel Core
	[21]	[1] + [22] /LHE	i7 (64 bit) processors for a total 4 cores running at 2.66 GHz	3810 ms	-	Audiology -14 classes -70 features
			and 8 GB RAM.
			Decision tree
			two Intel Core
			i7 (64 bit)
	[21]	[1] + [22] /LHE	processors for a total 4 cores	239 ms	-	Nursery
			running at 2.66 GHz
			and 8 GB RAM.
			two Intel Core
			i7 (64 bit)
	[21]	[1] + [22] /LHE	processors for a total 4 cores	899 ms	-	ECG
			running at 2.66 GHz
			and 8 GB RAM.

Table 5 :

 5 Summary of main works on Private K-nearest neighbors

	REF	HE scheme / Type	Plateform	Evaluation Time	Accuracy	Datasets
			K-nearest neighbors
	[23]	[1] /LHE	-	-	97.85%	Cancer 1 (9 features)
	[23]	[1] /LHE	-	-	96.49%	Cancer 2 -569 instances, -30 features)
	[23]	[1] /LHE	-	-	81.82%	Diabetes
						MNIST
	[23]	[1] /LHE	-	-	97%	dataset -60 000 instances
						-784 features
	[26]	[27] /FHE	Intel Core i7-6600U CPU	11.6 min	94.8	MNIST dataset -60 000 instances -784 features

• Identifying the k nearest neighbors (according to a given distance)

Three models can be found in the literature:

1. data comes from several parties, and these parties collaborate to train a clustering model.

2. single party that holds the data but not the computational resources needed to perform the calculations. The data is outsourced to perform clustering.

3. data comes from multiple parties and is paired to build a shared database.

Then the data is outsourced to perform clustering.

Cases 2 and 3 are similar; this case is called "outsourced clustering". The first case is called "distributed clustering". Plenty of clustering algorithms have been seen in the privacy-preserving framework: k-means, k-medoids, GMM, Meanshift, DBSCAN, baseline agglomerative HC BIRCH and Affinity Propagation. Among them, k-means has been intensively studied. In what follows, we focus on works that use homomorphic encryption.

Collaborative clustering

In the case of collaborative clustering, several parties own data and want to collaborate to get good quality clustering without disclosing the information contained in the data. This case has been extensively studied in two parts. [START_REF] Liu | Outsourcing Two-Party Privacy Preserving K-Means Clustering Protocol in Wireless Sensor Networks[END_REF] interested in the case where two parties with limited computational resources would like to run k-means by outsourcing the computations to the cloud. Both parties will have a result based on both datasets. In this case, one party's data should be kept confidential from the cloud and the other party. The authors based two schemes to propose a solution: the Liu encryption and the Pallier encryption. Each party encrypts the data and sends it to the cloud. The cloud performs calculations and comparisons based on additional information about both parties. To recalculate the centers, the cloud sends the sum of all vectors to both parties, and the parties use a protocol to calculate the new centers. The authors [START_REF] Jiang | Efficient two-party privacy-preserving collaborative k-means clustering protocol supporting both storage and computation outsourcing[END_REF] propose a protocol to perform secure k-means in the semi-honest model. In this work, the Pallier scheme has been used. The computation of the Euclidean distance requires interaction with the data owner to perform the multiplications. The comparison is performed using bit-by-bit encryption.

The authors [START_REF] Spathoulas | Using homomorphic encryption for privacy-preserving clustering of intrusion detection alerts[END_REF] studied clustering using the k-medoids algorithm applied to intrusion detection. Multiple organizations collaborate to perform clustering and have better results without sharing the content of this information in the clear. In addition, the system relies on a semi-honest party to perform clustering using Pallier encryption. The k-medoid algorithm requires more complex operations than addition. This requires interactions between collaborators to decrypt this data at runtime and thus perform the operations.