# Privacy-Preserving Outsourcing Scheme for SVM on Vertically Partitioned Data

Authors: Guowei Qiu; Hua Huo; Xiaolin Gui; Huijun Dai
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Support vector machine (SVM) is an important technique for data classification. Traditional SVM assumes free access to data. If the data are split and held by different users, for privacy reasons, users are likely unwilling to submit their data to a third party for classification. In this paper, by using additive homomorphic encryption and random transformations (matrix transformation and vector decomposition), we design a privacy-preserving outsourcing scheme for conducting Least Squares SVM (LS-SVM) classification on vertically partitioned data. In our system, multiple data owners (users) submit their encrypted data to two non-colluding service providers, which conduct SVM algorithm on it. During the execution of our algorithm, neither service provider learns anything about the input data, the intermediate results, or the predicted result. In other words, our algorithm is encrypted in the whole process. Extensive theoretical analysis and experimental evaluation demonstrate the correctness, security, and efficiency of the method.


---

## Body

## 1. Introduction

### 1.1. Background

SVM [1] is a powerful machine learning algorithm. It uses some given data points to learn a model which separates the feature space into two parts. All data in each part are considered to belong to one category. Then, the model could be used to predict the category of a new data point. Thus far, SVM classification has been successfully used in many fields, such as pattern recognition [2], diagnosis and classification of diseases [3, 4], and financial forecast [5]. Traditional SVM supposes that data are centralized and can be freely accessed. However, there is a widespread practice in today’s cloud computing environment; that is, the data for learning are split and held by multiple users, and the learning process is outsourced to some cloud service providers. For example, multiple financial institutions (banks, insurance companies, etc.) want to construct a model used for assessing personal credit. Clearly, the more the data used for learning are, the more accurate the model will be. To obtain a more accurate model, these institutions should contribute their data to a service provider for learning a SVM model. However, in this procedure, the traditional SVM will expose their data to the service providers. This is not permitted because of legal and moral constraints. The key to solving this problem is to develop a privacy-preserving SVM (PP-SVM) algorithm which obtains valid results without disclosing the users’ data.PP-SVM is a privacy-preserving machine learning (PPML) algorithm [6]. Generally speaking, a PPML algorithm modifies the original machine learning algorithm from two aspects: changing the system architecture and combining different security techniques with the original algorithm. For the first aspect, some architectures used by people include one client and one server [7, 8], multiclient and one server [9, 10], and multiclient and multiserver [11] architecture. Thus far, it is still difficult to design a highly efficient algorithm for one server architecture. In contrast, multiserver provides more possibilities for designing a highly efficient algorithm, but it also increases communication costs. For the second aspect, the security techniques often used in PPML include fully homomorphic encryption [7, 12], additive homomorphic encryption [11, 13–15], secret sharing [15–17], garbled circuits [17, 18], and differential privacy [19]. In this paper, we mainly use additive homomorphic encryption to construct our PP-SVM on a multiclient/two-server architecture.


### 1.2. Related Work

In the last two decades, some attention has been given to PP-SVM algorithm.Laur et al. [8] designed a cryptographically private SVM with additive homomorphic encryption [20], linear secret sharing [21], and conditional oblivious transfer [22]. Their algorithm only works on a system consisting of one server and one client, where the server owns the input data points and the client owns the corresponding class labels. Their system is not suitable for multiclient situation.Yu et al. [23] proposed an algorithm for PP-SVM based on secure set intersection cardinality [9] and commutative public-key encryption. Vaidya et al. [14] constructed three PP-SVM methods using secure addition, secure scalar product, and homomorphic encryption for vertically, horizontally, and arbitrarily partitioned data. The algorithms proposed by Yu et al. and Vaidya et al. are secure multiparty computing system. Omer et al. [13] proposed a PP-SVM algorithm based on additive homomorphic encryption, which is suitable for multiclient and one server systems. In above three algorithms, the input data points are concealed, but the corresponding class labels and kernel matrix are exposed to other participants. Exposing these messages to others can sometimes reveal some privacy about the input data (see the appendix in [24]). Therefore, we want to hide all this information in our algorithm.Liu et al. [12] proposed their PP-SVM algorithm based on fully homomorphic encryption [25, 26] and secure addition method. In their algorithm, each user communicates with the server many times, and each user performs a lot of computation by itself. These operations increase the workload of users and make their system look more like a collaborative rather than an outsourcing computing system.Park et al. [7] used CKKS [27] scheme, a fully homomorphic encryption, to construct a training algorithm based on Least Squares SVM [28]. Their method is suitable for the case of one client and one server, not directly for the case of multiple users.Thus far, all known methods of fully homomorphic encryption are still not efficient enough for practical use. We hope to design a sufficiently effective algorithm, which should reduce the work of users as much as possible.Wang et al. [11] first built a secure computation system and then designed a PP-SVM algorithm on it. Their computation system consists of eight secure operations, including secure integer multiplication, secure inner product, and secure floating-point addition/subtraction. They use a distributed two-trapdoor public-key cryptosystem [29] to set up this computation system, which ensures that their algorithm has better performance. This method can work on a multiclient/multiserver architecture. Compared with their methods, our method in this paper is simple and easy to understand.In addition, because our algorithm is based on LS-SVM, the service providers need to solve a linear system of equations. To ensure the data security, our algorithm employs random transformations to hide the coefficients of the equations. Similar data masking techniques have been used by some researchers. Lei et al. [30] proposed a secure outsourcing method to compute the inverse matrix. They use a sparse matrix to mask the original matrix, and then send it to the cloud for computing the inverse matrix. Chen et al. [31] proposed a secure outsourcing scheme for solving large-scale systems of linear equations based on matrix transformation in the fully malicious model. Chen et al. [32] designed two protocols for secure outsourcing of linear regression. They use random orthogonal matrix to mask the original equations and then outsource the equation solving process to the cloud. However, all their methods only work in one client and one server architecture. In this paper, we combine homomorphic encryption and random transformation technique to tackle the problem under multiclient/two-server framework.


### 1.3. The Target Problem, Architecture, and Security Model

#### 1.3.1. Target Problem

In this paper, we focus on the data privacy issues when multiple users submit their data to some cloud servers for SVM classification.Specifically, suppose there arem data pairs x1,y1,…,xm,ym for training and a new data point x for predicting, where each yi is the class label corresponding to the data point xi and is shared by all users. Each vector xi (including x) is vertically partitioned among r users as shown in Figure 1, where(1)xi=x1i,x2i,…,xni=xi1,xi2,…,xir.Figure 1
The problem model.Thexik=xnk−1+1i,xnk−1+2i,…,xnki∈ℝnk−nk−1 is the private data of userk who is unwilling to share it with others. Meanwhile, all users do not want to reveal yi to any server.We want to design a PP-SVM algorithm that enables the cloud server to perform SVM algorithm using all user data without learning any input data or prediction results.


#### 1.3.2. Our System Architecture

Our system architecture consists of useruserA, multiple users, and two service providers (SP1 and SP2), as shown in Figure 2. They each undertake the following tasks.(1)
userA: It sends a service request to all data owners (users). Then, all users and service providers perform PP-SVM algorithm. userA may or may not be one of the data owners.(2)
Users: Each user provides different attribute values of the same set of objects to a service provider in an encrypted form. The data can be used for training or prediction.(3)
SP1, SP2: They collaboratively learn a SVM model and predict the category of a new data point. In the training process, SP1 plays the role of Evaluator and SP2 plays the role of Crypto Service Provider (CSP). In the predicting process, SP1 and SP2 switch their roles. These two roles have the following responsibilities.(1)
CSP generates a key pairpk,sk of the Paillier cryptosystem [20] and then sends the public key pk to all other participators. It also performs some computations to help Evaluator execute our algorithm.(2)
Evaluator executes our training and predicting algorithms by collaborating with CSP. It performs all homomorphic computations in our protocols.Figure 2
The system architecture.Figure2 shows that the training and predicting procedure can be divided into the following steps as a whole.(1)
CSP sends the public key to other participators.(2)
All users send encrypted data to Evaluator.(3)
Evaluator and CSP collaboratively perform the privacy-preserving training or predicting protocols.(4)
Evaluator sends the predicted result touserA.


#### 1.3.3. Security Model

Each party in our system is semi-honest. This means that each service provider or user performs our protocols faithfully but hopes to learn some privacy of others by observing the execution of the protocols.Meanwhile, we suppose the two service providers are non-colluding. Service providers are generally large companies that are heavily regulated; we believe this condition is not difficult to achieve.In addition, we found that our protocol for computing RBF kernel (Protocol 3) may be inefficient. Therefore, we designed a new protocol (Protocol 4) as an alternative. However, the new protocol requires that there is no collusion between any two participants.


### 1.4. Our Contributions

In this paper, we propose a privacy-preserving outsourcing scheme for SVM classification on vertically partitioned data. Our algorithm is based on LS-SVM. Paillier encryption and random transformation are the main techniques in this work. Our algorithm has the following features.


#### 1.4.1. Secure Outsourced SVM Training

Our algorithm enables two service providers to solve LS-SVM equation in an encrypted state. In this procedure, the two service providers cannot learn the input data (allxi and yi), the solution of LS-SVM equation, and the training parameters.


#### 1.4.2. Secure Outsourced SVM Prediction

Our algorithm enables two service providers to make prediction for a new data point in an encrypted state. In this procedure, the two service providers learn nothing about the input data or the value of the decision function. The encrypted outcome will be sent to useruserA, and then userA can use it to compute the value of the decision function by himself.


#### 1.4.3. Concealing Important Intermediate Results

In our algorithm, the kernel matrix and decision function are hidden, which makes it more difficult for the service provider to infer some information about the input data.In addition, we conduct a comprehensive security analysis of the protocol and prove its security under various collusion scenarios. Experiments show that our algorithm has good accuracy and performance.


## 1.1. Background

SVM [1] is a powerful machine learning algorithm. It uses some given data points to learn a model which separates the feature space into two parts. All data in each part are considered to belong to one category. Then, the model could be used to predict the category of a new data point. Thus far, SVM classification has been successfully used in many fields, such as pattern recognition [2], diagnosis and classification of diseases [3, 4], and financial forecast [5]. Traditional SVM supposes that data are centralized and can be freely accessed. However, there is a widespread practice in today’s cloud computing environment; that is, the data for learning are split and held by multiple users, and the learning process is outsourced to some cloud service providers. For example, multiple financial institutions (banks, insurance companies, etc.) want to construct a model used for assessing personal credit. Clearly, the more the data used for learning are, the more accurate the model will be. To obtain a more accurate model, these institutions should contribute their data to a service provider for learning a SVM model. However, in this procedure, the traditional SVM will expose their data to the service providers. This is not permitted because of legal and moral constraints. The key to solving this problem is to develop a privacy-preserving SVM (PP-SVM) algorithm which obtains valid results without disclosing the users’ data.PP-SVM is a privacy-preserving machine learning (PPML) algorithm [6]. Generally speaking, a PPML algorithm modifies the original machine learning algorithm from two aspects: changing the system architecture and combining different security techniques with the original algorithm. For the first aspect, some architectures used by people include one client and one server [7, 8], multiclient and one server [9, 10], and multiclient and multiserver [11] architecture. Thus far, it is still difficult to design a highly efficient algorithm for one server architecture. In contrast, multiserver provides more possibilities for designing a highly efficient algorithm, but it also increases communication costs. For the second aspect, the security techniques often used in PPML include fully homomorphic encryption [7, 12], additive homomorphic encryption [11, 13–15], secret sharing [15–17], garbled circuits [17, 18], and differential privacy [19]. In this paper, we mainly use additive homomorphic encryption to construct our PP-SVM on a multiclient/two-server architecture.


## 1.2. Related Work

In the last two decades, some attention has been given to PP-SVM algorithm.Laur et al. [8] designed a cryptographically private SVM with additive homomorphic encryption [20], linear secret sharing [21], and conditional oblivious transfer [22]. Their algorithm only works on a system consisting of one server and one client, where the server owns the input data points and the client owns the corresponding class labels. Their system is not suitable for multiclient situation.Yu et al. [23] proposed an algorithm for PP-SVM based on secure set intersection cardinality [9] and commutative public-key encryption. Vaidya et al. [14] constructed three PP-SVM methods using secure addition, secure scalar product, and homomorphic encryption for vertically, horizontally, and arbitrarily partitioned data. The algorithms proposed by Yu et al. and Vaidya et al. are secure multiparty computing system. Omer et al. [13] proposed a PP-SVM algorithm based on additive homomorphic encryption, which is suitable for multiclient and one server systems. In above three algorithms, the input data points are concealed, but the corresponding class labels and kernel matrix are exposed to other participants. Exposing these messages to others can sometimes reveal some privacy about the input data (see the appendix in [24]). Therefore, we want to hide all this information in our algorithm.Liu et al. [12] proposed their PP-SVM algorithm based on fully homomorphic encryption [25, 26] and secure addition method. In their algorithm, each user communicates with the server many times, and each user performs a lot of computation by itself. These operations increase the workload of users and make their system look more like a collaborative rather than an outsourcing computing system.Park et al. [7] used CKKS [27] scheme, a fully homomorphic encryption, to construct a training algorithm based on Least Squares SVM [28]. Their method is suitable for the case of one client and one server, not directly for the case of multiple users.Thus far, all known methods of fully homomorphic encryption are still not efficient enough for practical use. We hope to design a sufficiently effective algorithm, which should reduce the work of users as much as possible.Wang et al. [11] first built a secure computation system and then designed a PP-SVM algorithm on it. Their computation system consists of eight secure operations, including secure integer multiplication, secure inner product, and secure floating-point addition/subtraction. They use a distributed two-trapdoor public-key cryptosystem [29] to set up this computation system, which ensures that their algorithm has better performance. This method can work on a multiclient/multiserver architecture. Compared with their methods, our method in this paper is simple and easy to understand.In addition, because our algorithm is based on LS-SVM, the service providers need to solve a linear system of equations. To ensure the data security, our algorithm employs random transformations to hide the coefficients of the equations. Similar data masking techniques have been used by some researchers. Lei et al. [30] proposed a secure outsourcing method to compute the inverse matrix. They use a sparse matrix to mask the original matrix, and then send it to the cloud for computing the inverse matrix. Chen et al. [31] proposed a secure outsourcing scheme for solving large-scale systems of linear equations based on matrix transformation in the fully malicious model. Chen et al. [32] designed two protocols for secure outsourcing of linear regression. They use random orthogonal matrix to mask the original equations and then outsource the equation solving process to the cloud. However, all their methods only work in one client and one server architecture. In this paper, we combine homomorphic encryption and random transformation technique to tackle the problem under multiclient/two-server framework.


## 1.3. The Target Problem, Architecture, and Security Model

### 1.3.1. Target Problem

In this paper, we focus on the data privacy issues when multiple users submit their data to some cloud servers for SVM classification.Specifically, suppose there arem data pairs x1,y1,…,xm,ym for training and a new data point x for predicting, where each yi is the class label corresponding to the data point xi and is shared by all users. Each vector xi (including x) is vertically partitioned among r users as shown in Figure 1, where(1)xi=x1i,x2i,…,xni=xi1,xi2,…,xir.Figure 1
The problem model.Thexik=xnk−1+1i,xnk−1+2i,…,xnki∈ℝnk−nk−1 is the private data of userk who is unwilling to share it with others. Meanwhile, all users do not want to reveal yi to any server.We want to design a PP-SVM algorithm that enables the cloud server to perform SVM algorithm using all user data without learning any input data or prediction results.


### 1.3.2. Our System Architecture

Our system architecture consists of useruserA, multiple users, and two service providers (SP1 and SP2), as shown in Figure 2. They each undertake the following tasks.(1)
userA: It sends a service request to all data owners (users). Then, all users and service providers perform PP-SVM algorithm. userA may or may not be one of the data owners.(2)
Users: Each user provides different attribute values of the same set of objects to a service provider in an encrypted form. The data can be used for training or prediction.(3)
SP1, SP2: They collaboratively learn a SVM model and predict the category of a new data point. In the training process, SP1 plays the role of Evaluator and SP2 plays the role of Crypto Service Provider (CSP). In the predicting process, SP1 and SP2 switch their roles. These two roles have the following responsibilities.(1)
CSP generates a key pairpk,sk of the Paillier cryptosystem [20] and then sends the public key pk to all other participators. It also performs some computations to help Evaluator execute our algorithm.(2)
Evaluator executes our training and predicting algorithms by collaborating with CSP. It performs all homomorphic computations in our protocols.Figure 2
The system architecture.Figure2 shows that the training and predicting procedure can be divided into the following steps as a whole.(1)
CSP sends the public key to other participators.(2)
All users send encrypted data to Evaluator.(3)
Evaluator and CSP collaboratively perform the privacy-preserving training or predicting protocols.(4)
Evaluator sends the predicted result touserA.


### 1.3.3. Security Model

Each party in our system is semi-honest. This means that each service provider or user performs our protocols faithfully but hopes to learn some privacy of others by observing the execution of the protocols.Meanwhile, we suppose the two service providers are non-colluding. Service providers are generally large companies that are heavily regulated; we believe this condition is not difficult to achieve.In addition, we found that our protocol for computing RBF kernel (Protocol 3) may be inefficient. Therefore, we designed a new protocol (Protocol 4) as an alternative. However, the new protocol requires that there is no collusion between any two participants.


## 1.3.1. Target Problem

In this paper, we focus on the data privacy issues when multiple users submit their data to some cloud servers for SVM classification.Specifically, suppose there arem data pairs x1,y1,…,xm,ym for training and a new data point x for predicting, where each yi is the class label corresponding to the data point xi and is shared by all users. Each vector xi (including x) is vertically partitioned among r users as shown in Figure 1, where(1)xi=x1i,x2i,…,xni=xi1,xi2,…,xir.Figure 1
The problem model.Thexik=xnk−1+1i,xnk−1+2i,…,xnki∈ℝnk−nk−1 is the private data of userk who is unwilling to share it with others. Meanwhile, all users do not want to reveal yi to any server.We want to design a PP-SVM algorithm that enables the cloud server to perform SVM algorithm using all user data without learning any input data or prediction results.


## 1.3.2. Our System Architecture

Our system architecture consists of useruserA, multiple users, and two service providers (SP1 and SP2), as shown in Figure 2. They each undertake the following tasks.(1)
userA: It sends a service request to all data owners (users). Then, all users and service providers perform PP-SVM algorithm. userA may or may not be one of the data owners.(2)
Users: Each user provides different attribute values of the same set of objects to a service provider in an encrypted form. The data can be used for training or prediction.(3)
SP1, SP2: They collaboratively learn a SVM model and predict the category of a new data point. In the training process, SP1 plays the role of Evaluator and SP2 plays the role of Crypto Service Provider (CSP). In the predicting process, SP1 and SP2 switch their roles. These two roles have the following responsibilities.(1)
CSP generates a key pairpk,sk of the Paillier cryptosystem [20] and then sends the public key pk to all other participators. It also performs some computations to help Evaluator execute our algorithm.(2)
Evaluator executes our training and predicting algorithms by collaborating with CSP. It performs all homomorphic computations in our protocols.Figure 2
The system architecture.Figure2 shows that the training and predicting procedure can be divided into the following steps as a whole.(1)
CSP sends the public key to other participators.(2)
All users send encrypted data to Evaluator.(3)
Evaluator and CSP collaboratively perform the privacy-preserving training or predicting protocols.(4)
Evaluator sends the predicted result touserA.


## 1.3.3. Security Model

Each party in our system is semi-honest. This means that each service provider or user performs our protocols faithfully but hopes to learn some privacy of others by observing the execution of the protocols.Meanwhile, we suppose the two service providers are non-colluding. Service providers are generally large companies that are heavily regulated; we believe this condition is not difficult to achieve.In addition, we found that our protocol for computing RBF kernel (Protocol 3) may be inefficient. Therefore, we designed a new protocol (Protocol 4) as an alternative. However, the new protocol requires that there is no collusion between any two participants.


## 1.4. Our Contributions

In this paper, we propose a privacy-preserving outsourcing scheme for SVM classification on vertically partitioned data. Our algorithm is based on LS-SVM. Paillier encryption and random transformation are the main techniques in this work. Our algorithm has the following features.


### 1.4.1. Secure Outsourced SVM Training

Our algorithm enables two service providers to solve LS-SVM equation in an encrypted state. In this procedure, the two service providers cannot learn the input data (allxi and yi), the solution of LS-SVM equation, and the training parameters.


### 1.4.2. Secure Outsourced SVM Prediction

Our algorithm enables two service providers to make prediction for a new data point in an encrypted state. In this procedure, the two service providers learn nothing about the input data or the value of the decision function. The encrypted outcome will be sent to useruserA, and then userA can use it to compute the value of the decision function by himself.


### 1.4.3. Concealing Important Intermediate Results

In our algorithm, the kernel matrix and decision function are hidden, which makes it more difficult for the service provider to infer some information about the input data.In addition, we conduct a comprehensive security analysis of the protocol and prove its security under various collusion scenarios. Experiments show that our algorithm has good accuracy and performance.


## 1.4.1. Secure Outsourced SVM Training

Our algorithm enables two service providers to solve LS-SVM equation in an encrypted state. In this procedure, the two service providers cannot learn the input data (allxi and yi), the solution of LS-SVM equation, and the training parameters.


## 1.4.2. Secure Outsourced SVM Prediction

Our algorithm enables two service providers to make prediction for a new data point in an encrypted state. In this procedure, the two service providers learn nothing about the input data or the value of the decision function. The encrypted outcome will be sent to useruserA, and then userA can use it to compute the value of the decision function by himself.


## 1.4.3. Concealing Important Intermediate Results

In our algorithm, the kernel matrix and decision function are hidden, which makes it more difficult for the service provider to infer some information about the input data.In addition, we conduct a comprehensive security analysis of the protocol and prove its security under various collusion scenarios. Experiments show that our algorithm has good accuracy and performance.


## 2. Preliminaries

In general, we use lowercase letters to indicate numbers (e.g.,xi, yi, a, αi), lowercase boldface letters (e.g., xi, e, α) for vectors, and uppercase boldface letters (e.g., Q, A) for matrices.


### 2.1. SVM and LS-SVM Overview

SVM algorithm consists of two phases: training and predicting. In SVM training phase, it uses all training data to learn a linear or nonlinear model represented by a decision functionfx. Then, in SVM prediction phase, it computes fx at a given x. The function value is used to predict the category of the given data.The SVM model is actually a hyperplane called decision boundary, which separates the training data into two categories. The training process finds the hyperplane by maximizing the margin between two categories of data; Figure 3 shows a two-dimensional case. It can be described as follows. Suppose there are m data pairs x1,y1,…,xm,ym for SVM training, where xi∈ℝn is a vector in the feature space and yi∈−1,+1 is the class label of xi. The SVM learns a decision boundary fx=w,x+b=0 by solving the following optimization problem:(2)minw,b,ξ12w2+C∑i=1mξis.t.yiw,xi+b≥1−ξi,ξi>0,fori=1,…,m,where ξ=ξ1,…,ξm is the slack variables that allow some data points to lie within the margin. Figure 2 is a two-dimensional example. The classification rule induced by fx is sgnfx. The problem equation (2) is usually solved in its dual form, which often combines with the kernel trick to deal with the nonlinear decision boundary. Finally, the form of its dual problem is(3)minα12∑i,j=1mαiαjyiyjKxi,xj−∑i=1mαis.t.∑i=1mαiyi=0,0≤αi≤Ci=1,…,m,where Kxi,xj=ϕxi,ϕxj is a kernel function, and ϕx:ℝn⟶ℝl is a basis function. The decision function is(4)fx=∑i=1mαiyiKxi,x+b,where αi0≤i≤m are the solutions to the dual problem equation (3). b can be obtained as follows: select αj that satisfies 1≤αj≤C; compute b=yj−∑i=1mαiyiKxi,xj.Figure 3
The SVM maximizes the margin between two classes of data (points in squares are support vectors).Three popular choices for kernel functionKxi,xj are(5)Linear kernel:xi,xjPolynomial kernel:axi,xj+cpRBF kernel:exp−σxi−xj2.The matrixK=Kxi,xjm×m is the kernel matrix.Although problem equation (3) is only quadratic programming, it is still difficult to solve in the encrypted state, because the inequality constraints are difficult to deal with. The algorithm in this paper is based on the following LS-SVM.(6)minw,b,e12w2+γ2∑i=1mei2s.t.yiw,ϕxi+b=1−ei,fori=1,…,m.We can also transform this problem to its dual form with Lagrange multiplier method. Likewise, we can apply the kernel trick to its dual problem. The kernel functions (5) can also be used in LS-SVM. Most important of all, we can obtain the coefficients of its decision function by solving LS-SVM equation as follows:(7)Qβ=e,where(8)Q=0y1⋯ymy1⋮ymΩ+γ−1Iβ=bα1⋮αme=01⋮1,and ωij=yiyjKxi,xj is the i,jth entry of Ω. In this paper, we will solve this linear equation in an encrypted form and then secretly compute fx for a new data point x. For more details about SVM, see [1, 28].


### 2.2. The Paillier Cryptosystem

The Paillier cryptosystem is an additive homomorphic encryption scheme which satisfies semantic security [33]. Semantic security makes it impossible for any polynomial algorithm to gain extra information about a plaintext when given only its ciphertext and public key. As an asymmetric encryption, Paillier cryptosystem has a key pair pk,sk, where pk is the public key and sk is the private key.LetE⋅ be the encryption algorithm and D⋅ be the decryption algorithm. Given a,b∈ℤn, the Paillier encryption satisfies the following properties:(9)Ea+b=Ea⋅Ebmodn2,Eka=Eakmodn2∀k∈ℤn.For more details, see chapter 13 of [34].In our system, CSP generates the key pairpk,sk and sends pk to other parties. To simplify the description, for any A=aijm×n or b=bim, we use EA or Eb to denote a matrix or vector whose each entry is Eaij or Ebi.


### 2.3. Data Representation

We use fixed-point representation in our system. More precisely, we represent a real number with a fixed-point integer. For a fixed-point real numbera which dedicates q bits to the fractional part, we use the integer a⋅2q to represent it. Supposing a and b are fixed-point numbers in our system, we perform the arithmetic operations as follows:(10)a±bfixed=a±b,abfixed=ab2q,abfixed=ab⋅2qfora,b>=0,where the operation ⋅ rounds a real number down to the nearest integer.Because the cryptosystem works only for nonnegative integers, we use 2’s complement in our system to ensure all numbers are positive. However, this causes another problem, the operationa/bfixed listed above is not correct for the complement of a negative number. Therefore, when performing a division operation, we first transform the 2’s complement to its true form and then perform division on it, and the result of division will be transformed back to the complement for subsequent computation.


### 2.4. The ProtocolEncMulEa,Eb⟶Eab

The protocol EncMul⋅,⋅ is a two-party protocol that accomplishes the following task: Evaluator provides Ea,Eb; CSP keeps the private key; finally, Evaluator obtains Eab, and the two servers cannot learn anything about a or b.Elmehdwi et al. [35] proposed this protocol and Liu et al. [29] gave a similar one which used multiple keys. This protocol is used in our methods to compute the polynomial or RBF kernel functions. The description of the EncMul protocol is as follows:(1)
Evaluator chooses two random positive integersr1 and r2; computes Ea+r1=Ea⋅Er1, Eb+r2=Eb⋅Er2; and then sends Ea+r1, Eb+r2 to CSP.(2)
CSP obtainsa+r1=DEa+r1, b+r2=DEb+r2; then computes(11)T=Eab+ar2+br1+r1r2=Ea+r1b+r2;and returnsT to Evaluator.(3)
Evaluator computes(12)Eab=T⋅Ear2−1⋅Ebr1−1⋅Er1r2−1.In this protocol,Ex−1 is the modular inverse of Ex. This protocol is based on the equation ab=a+r1b+r2−ar2−br1−r1r2.


## 2.1. SVM and LS-SVM Overview

SVM algorithm consists of two phases: training and predicting. In SVM training phase, it uses all training data to learn a linear or nonlinear model represented by a decision functionfx. Then, in SVM prediction phase, it computes fx at a given x. The function value is used to predict the category of the given data.The SVM model is actually a hyperplane called decision boundary, which separates the training data into two categories. The training process finds the hyperplane by maximizing the margin between two categories of data; Figure 3 shows a two-dimensional case. It can be described as follows. Suppose there are m data pairs x1,y1,…,xm,ym for SVM training, where xi∈ℝn is a vector in the feature space and yi∈−1,+1 is the class label of xi. The SVM learns a decision boundary fx=w,x+b=0 by solving the following optimization problem:(2)minw,b,ξ12w2+C∑i=1mξis.t.yiw,xi+b≥1−ξi,ξi>0,fori=1,…,m,where ξ=ξ1,…,ξm is the slack variables that allow some data points to lie within the margin. Figure 2 is a two-dimensional example. The classification rule induced by fx is sgnfx. The problem equation (2) is usually solved in its dual form, which often combines with the kernel trick to deal with the nonlinear decision boundary. Finally, the form of its dual problem is(3)minα12∑i,j=1mαiαjyiyjKxi,xj−∑i=1mαis.t.∑i=1mαiyi=0,0≤αi≤Ci=1,…,m,where Kxi,xj=ϕxi,ϕxj is a kernel function, and ϕx:ℝn⟶ℝl is a basis function. The decision function is(4)fx=∑i=1mαiyiKxi,x+b,where αi0≤i≤m are the solutions to the dual problem equation (3). b can be obtained as follows: select αj that satisfies 1≤αj≤C; compute b=yj−∑i=1mαiyiKxi,xj.Figure 3
The SVM maximizes the margin between two classes of data (points in squares are support vectors).Three popular choices for kernel functionKxi,xj are(5)Linear kernel:xi,xjPolynomial kernel:axi,xj+cpRBF kernel:exp−σxi−xj2.The matrixK=Kxi,xjm×m is the kernel matrix.Although problem equation (3) is only quadratic programming, it is still difficult to solve in the encrypted state, because the inequality constraints are difficult to deal with. The algorithm in this paper is based on the following LS-SVM.(6)minw,b,e12w2+γ2∑i=1mei2s.t.yiw,ϕxi+b=1−ei,fori=1,…,m.We can also transform this problem to its dual form with Lagrange multiplier method. Likewise, we can apply the kernel trick to its dual problem. The kernel functions (5) can also be used in LS-SVM. Most important of all, we can obtain the coefficients of its decision function by solving LS-SVM equation as follows:(7)Qβ=e,where(8)Q=0y1⋯ymy1⋮ymΩ+γ−1Iβ=bα1⋮αme=01⋮1,and ωij=yiyjKxi,xj is the i,jth entry of Ω. In this paper, we will solve this linear equation in an encrypted form and then secretly compute fx for a new data point x. For more details about SVM, see [1, 28].


## 2.2. The Paillier Cryptosystem

The Paillier cryptosystem is an additive homomorphic encryption scheme which satisfies semantic security [33]. Semantic security makes it impossible for any polynomial algorithm to gain extra information about a plaintext when given only its ciphertext and public key. As an asymmetric encryption, Paillier cryptosystem has a key pair pk,sk, where pk is the public key and sk is the private key.LetE⋅ be the encryption algorithm and D⋅ be the decryption algorithm. Given a,b∈ℤn, the Paillier encryption satisfies the following properties:(9)Ea+b=Ea⋅Ebmodn2,Eka=Eakmodn2∀k∈ℤn.For more details, see chapter 13 of [34].In our system, CSP generates the key pairpk,sk and sends pk to other parties. To simplify the description, for any A=aijm×n or b=bim, we use EA or Eb to denote a matrix or vector whose each entry is Eaij or Ebi.


## 2.3. Data Representation

We use fixed-point representation in our system. More precisely, we represent a real number with a fixed-point integer. For a fixed-point real numbera which dedicates q bits to the fractional part, we use the integer a⋅2q to represent it. Supposing a and b are fixed-point numbers in our system, we perform the arithmetic operations as follows:(10)a±bfixed=a±b,abfixed=ab2q,abfixed=ab⋅2qfora,b>=0,where the operation ⋅ rounds a real number down to the nearest integer.Because the cryptosystem works only for nonnegative integers, we use 2’s complement in our system to ensure all numbers are positive. However, this causes another problem, the operationa/bfixed listed above is not correct for the complement of a negative number. Therefore, when performing a division operation, we first transform the 2’s complement to its true form and then perform division on it, and the result of division will be transformed back to the complement for subsequent computation.


## 2.4. The ProtocolEncMulEa,Eb⟶Eab

The protocol EncMul⋅,⋅ is a two-party protocol that accomplishes the following task: Evaluator provides Ea,Eb; CSP keeps the private key; finally, Evaluator obtains Eab, and the two servers cannot learn anything about a or b.Elmehdwi et al. [35] proposed this protocol and Liu et al. [29] gave a similar one which used multiple keys. This protocol is used in our methods to compute the polynomial or RBF kernel functions. The description of the EncMul protocol is as follows:(1)
Evaluator chooses two random positive integersr1 and r2; computes Ea+r1=Ea⋅Er1, Eb+r2=Eb⋅Er2; and then sends Ea+r1, Eb+r2 to CSP.(2)
CSP obtainsa+r1=DEa+r1, b+r2=DEb+r2; then computes(11)T=Eab+ar2+br1+r1r2=Ea+r1b+r2;and returnsT to Evaluator.(3)
Evaluator computes(12)Eab=T⋅Ear2−1⋅Ebr1−1⋅Er1r2−1.In this protocol,Ex−1 is the modular inverse of Ex. This protocol is based on the equation ab=a+r1b+r2−ar2−br1−r1r2.


## 3. Our PP-SVM Training Algorithm

In the training phase, SP1 is Evaluator and SP2 is CSP.


### 3.1. Main Steps of Our PP-SVM Training Algorithm

The key of our training algorithm is to solve the LS-SVM equationQβ=e securely. Figure 4 shows the procedure of PP-SVM training, which includes several steps as follows:(1)
SP2 sendspk2 to other participators.(2)
All users send encrypted data to SP1.(3)
SP1 computesEQ and EC=EQR and then sends EC to SP2 (R is used for masking Q).(4)
SP2 decryptsEC, solves Cδ=e, decomposes δ into δ=t1δ1+t2δ2, and then sends δ1,δ2 to SP1 (t1,t2∈ℝ and δ1,δ2∈ℝm+1).(5)
SP1 computesζ=Rδ1, η=Rδ2 (removing perturbation).Figure 4
The procedure of our PP-SVM training.Finally, the SP1 has random vectorsζ, η; SP2 has random numbers t1,t2. These data satisfy β=t1ζ+t2η, where β is the solution of LS-SVM equation. Because the two service providers do not collude, neither of them knows β.Furthermore, during the training procedure, SP1 and SP2 should not learn anything aboutQ. The reason for this is that someone can learn the kernel matrix from Q, because the difference between them is small, and thus can learn some information about xi from the kernel matrix, especially when the kernel function is simple (see the appendix in [24]).We use the notationsSP1E and SP2C instead of SP1 and SP2 in this section to make their roles easy to identify.


### 3.2. Securely Computing MatricesEΩ and EQ

#### 3.2.1. Case 1: PP-SVM with Linear Kernel

For a linear-kernel matrix, itsi,jth entry Kxi,xj=xi,xj=∑k=1rxik,xjk. For Ω=ωijm×n, we have(13)Eωij=EyiyjKxi,xj=E∑k=1ryixik,yjxjk=∏k=1rEyixik,yjxjk.Based on (13), we design Protocol 1.Protocol 1.
ComputeEQ for linear-kernel PP-SVM.Input:userk provides xik; each yi is shared by all users, where 1≤i≤m and 1≤k≤r.Output: SP1 obtains EQ.(1)
Eachuserk computes Eyixik,yjxjk locally and sends them to SP1, where 1≤i,j≤m, 1≤k≤r.(2)
For any1​≤​i,j​≤​m, SP1 computes EΩ as follows:Eωij=∏k=1r​Eyixik,yjxjk.(3)
User sendsEγ−1 and all Eyi to SP1, who computes each Eωii+γ−1=Eωii⋅Eγ−1. Then, SP1 obtains EQ (γ is the parameter in (7)).


#### 3.2.2. Case 2: PP-SVM with Polynomial Kernel

For a polynomial kernel matrix, itsi,jth entry Kxi,xj=axi,xj+cp=∑k=1raxik,xjk+cp. Hence,(14)Eωij=EyiyjKxi,xj=Eyiyj∑k=1raxik,xjk+cp.Based on (14), we design Protocol 2.Protocol 2.
ComputeEQ for polynomial kernel PP-SVM.Input: userk provides xik all yi, and a,c,p in the kernel function are shared by all users 1≤i≤m,1≤k≤r.Output: SP1E obtains EQ.(1)
user1 computes Eyiyj, Ec, and Eaxi1,xj1; other users compute Eaxik,xjk1≤i,j≤m,2≤k≤r. Then, all users send these data to SP1E.(2)
For1≤i,j≤m, SP1E computes(15)Tij=E∑k=1raxik,xjk+c=∏k=1rEaxik,xjk⋅Ec.(3)
user1 sends p to SP1E. For 1≤i,j≤m, let Sij=Tij. SP1E and SP2C repeatedly execute(16)Sij=EncMulSij,Tijp−1 times. Then, SP1E obtains(17)EKxi,xj=Sij=E∑k=1raxik,xjk+cp.(4)
SP1E and SP2C compute(18)Eωij=EncMulSij,Eyiyj1≤i,j≤m.Then,SP1E obtains EΩ.(5)
user1 sends Eγ−1 and all Eyi to SP1E, who computes Eωii+γ−1=Eωii⋅Eγ−1. Then, SP1E obtains EQ.Remark 1.
Becauseyi cannot be disclosed to service provider, two service providers must execute EncMul to generate Eωij, as shown in step 4. Another method is that SP1 sends all EKxi,xj to one user, who computes Eωij=EKxi,xjyiyj and returns it to SP1. In this way, two service providers can reduce the execution of EncMul once.
In addition, the degreep is the only parameter sent directly to SP1.


#### 3.2.3. Case 3: PP-SVM with RBF Kernel

For a RBF kernel matrix, itsi,jth entry(19)Kxi,xj=exp−σxi−xj2=exp−σxi,xi−2xi,xj+xj,xj=exp−σ∑k=1rxik,xik−2xik,xjk+xjk,xjk=∏k=1rexp−σxik,xik−2xik,xjk+xjk,xjk.LetΔkij=exp−σxik,xik−2xik,xjk+xjk,xjk; we have(20)Eωij=EyiyjKxi,xj=Eyiyj∏k=1rΔkij.According to (9), we can design the following two methods for computing EΩ:(A)
SP1E collects EΔkij and EyiyjΔ1ij from users. Then, two servers use EncMul to compute Eωij.(B)
user1 chooses some random hij; all users try to compute Tij=hij∏k=1rΔkij. SP1E collects Eyiyj/hij and Tij; then, it can compute Eωij with them.Protocol 3 is designed based on method A.Protocol 3.
(method A)ComputeEQ for PP-SVM with RBF kernel.Input:userk provides xik, and each yi is shared by all users, where 1≤i≤m and 1≤k≤r.Output:SP1E obtains EQ.(1)
For any1≤i,j≤m, userk2≤k≤r computes EΔkij and user1 computes EyiyjΔ1ij. Then, all users send these data to SP1E.(2)
LetTij=EyiyjΔ1ij. SP1E and SP2C repeatedly execute(21)Tij=EncMulEΔkij,Tij,fork=2,3,…,r. Then, SP1E obtains(22)Eωij=Tij=Eyiyj∏k=1rΔkij1≤i,j≤m.(3)
user1 sends Eγ−1 and all Eyi to SP1E, who computes Eωii+γ−1=Eωii⋅Eγ−1. Then, SP1E obtains EQ.Remark 2.
Protocol 3 will call EncMul r−1 times. This leads to inefficiency because EncMul is a time-consuming protocol.
Protocol 4 is designed based on the method B.Protocol 4.
(method B) ComputeEQ for PP-SVM with RBF kernel.Input: userk provides xik, and each yi is shared by all users, where 1≤i≤m and 1≤k≤r.Output: SP1E obtains EQ.(1)
user1 chooses random real numbers hij>11≤i,j≤m and a random integer f>0, where f/hij>2g,g>10. Then, user1 computes Tij=hijΔ1ij for 1≤i,j≤m.(2)
user1 sends each Tij to user2, and user2 computes Tij=TijΔ2ij and then sends Tij to user3. One by one, other users do the same thing until userr computes Tij=TijΔrij and sends these data to SP1E.(3)
user1 computes Efyiyj/hij for 1≤i,j≤m; sends Efyiyj/hij to SP1E; and sends f to SP1E and SP2C.(4)
SP1E computes EΩ as follows:(23)Ef2ωij=Ef2yiyjhij∏k=1rΔkij≈EfyiyjhijfTij,where1≤i,j≤m.(5)
user1 sends Ef2γ−1 and all Ef2yi to SP1E, who computes Ef2ωii+f2γ−1=Ef2ωii⋅Ef2γ−1. Then, SP1E obtains Ef2Q.Remark 3.
The datayiyj/hij<1. To improve the accuracy, we multiply yiyj/hij by f and use the integer part of fyiyj/hij in subsequent computations. Proposition 1 will illustrate why it require f/hij>2g and g>10.
In this paper, we use Linear-SVM, Poly-SVM, RBF-SVM(A), and RBF-SVM(B) to denote the PP-SVM methods which useProtocols 1–4, respectively.
The RBF-SVM(B) is far more efficient than RBF-SVM(A), but it requires that any two participants do not collude with each other (see Section3.5.2).


### 3.3. Securely Computingβ and Splitting It between Two Service Providers

The decision function, which we call SVM model, can be written as follows:(24)fx=∑i=1mαiyiKxi,x+b=β⋅kx,where(25)β=b,α1,α2,…,αm,kx=1,y1Kx1,x,…,ymKxm,x.In this section, the two service providers will securely computeβ. Because β discloses the relationship between the input points and the hyperplane fx to some extent, we do not reveal β to service provider. To this end, we will randomly decompose β into a linear combination, then split this combination into two parts, and provide different parts to Evaluator and CSP. This ensures that both of the service providers learn nothing about β.In a word, we require that none of the service providers can learn anything aboutxi,yi,β, or Kxi,x when executing our algorithm.Protocol 5.
Computeβ and split it between two servers.Input: SP1E inputs EQ; CSP has the private key.Output: SP1E obtains vectors ζ, η; SP2C obtains real numbers t1, t2. These data satisfy β=t1ζ+t2η.(1)
SP1E chooses an invertible random R∈ℤ+m+1×m+1. For Linear-SVM, Poly-SVM, and RBF-SVM(A), let C=QR; SP1E computes each entry of EC as follows:(26)ECij=E∑k=1m+1QikRkj=∏k=1m+1EQikRkj.For RBF-SVM(B), letC=f2QR; SP1E computes(27)ECij=∏k=1m+1Ef2QikRkj,whereCij, Qik, Rkj are the elements of C, Q, R. Then, SP1E sends EC to SP2C.(2)
SP2C obtains C=DEC. Especially for method RBF-SVM(B), SP2 computes C=C/f2. Then, SP2 solves Cδ=e and obtains δ.(3)
Then,SP2C randomly divides δ into a linear combination as follows:(28)δ=t1δ1+t2δ2t1,t2∈ℝ,δ1,δ2∈ℝm+1.Then,SP2C sends vectors δ1,δ2 to SP1E.(4)
SP1E computes ζ=Rδ1 and η=Rδ2.Remark 4.
Step 1 uses an invertible matrixR to mask Q in an encrypted state. Step 3 decomposes δ into a linear combination. These random transformations prevent SP1 and SP2 from learning anything about Q or δ.
It is worth noting that keepingQ confidential is a key step to ensure the security of β. If someone obtains Q, they can compute β=Q−1e, where e=0,1,…,1 is the right-hand side of (6).
SP1 and SP2 will useζ, η, t1, and t2 to compute fx in prediction phase.


### 3.4. Correctness of Our Training Algorithm

It is easy to verify the correctness ofProtocols 1–3 by using the properties of Paillier encryption.InProtocol 4, we use secure multiplication which uses hij to conceal each user’s Δkij. The integers fyiyj/hij and fTij are used instead of fyiyj/hij and fTij in this protocol, which introduces error into system. Fortunately, the following proposition proves that the error is small.Proposition 1.
(precision)InProtocol 4, the use of fyiyj/hij and fTij introduces errors into the system, but the actual effect on each element in Q is less than 1/2g−1.
Proof: InProtocol 4, SP1 computes(29)Ef2ωij=EfyiyjhijfTij≈EfyiyjhijfTij.We usefyiyj/hijfTij instead of fyiyj/hijfTij. Let Q′ be a matrix and its i,jth entry be fyiyj/hijfTij.(30)Err=fyiyjhijfTij−fyiyjhijfTij=fhijfTij−fhijfTijyiyj=1or−1≤fhijfTij−fhijfTij+fhijfTij−fhijfTij<fhij+fhij∏k=1rΔkij<fhij+fhij0<Δkij<1.In step 2, SP2 computesC=C/f2=Q′/f2R. Clearly, it is equivalent to replacing Q with Q′/f2. This means the error for each entry in the matrix Q is Err/f2. We have(31)Errf2<1fhij+hijf<12ghij2+12g<12g−1f>2g.For example, if theg=11, the error is less than 10−3. The following proposition proves that the output of Protocol 5 is a linear combination of β.Proposition 2.
(correctness)InProtocol 5, SP1 has ζ and η; SP2 has t1 and t2. These data satisfy β=t1ζ+t2η, where β is the solution of LS-SVM equation.Proof: .
(32)t1ζ+t2η=Rt1δ1+t2δ2=Rδ=RR−1Q−1e=β.


### 3.5. Security of Our Training Algorithm

#### 3.5.1. Security of the Protocol Itself

Protocols 1–4 only use Paillier encryption and protocol EncMul. Paillier encryption is semantically secure, and the security of EncMul has been confirmed by previous studies. Therefore, Protocols 1–4 do not disclose input data. The following proposition proves the security of Protocol 5.Proposition 3.
(security) InProtocol 5, two semi-honest and non-colluding service providers learn nothing about Q and β of the LS-SVM equation.Proof:SP1E only has the plaintext ζ and η. These data have nothing to do with Q; hence, SP1 cannot learn anything about Q. In addition, SP1 probably knows t1ζ+t2η=β. This gives it m+1 equations but m+3 unknowns t1,t2,β. Therefore, SP1 cannot also learn anything about β.SP2C only knows the matrix C. Even if it knows C=QR, it still cannot obtain anything about Q or R, because C=QR gives it m+12 equations but 2m+12 unknowns in Q and R. Meanwhile, CSP learns nothing about β without R, because β=Rδ and it only has δ.


#### 3.5.2. Analysis of Collusion

Suppose there exists collusion between some participants. InProtocols 1–3, all users only provide data, and there is no communication between users. Therefore, we only need to discuss the collusion between users and one service provider.Proposition 4.
(collusion) For Linear-SVM, Poly-SVM, and RBF-SVM(A), collusion between some users and SP1 or SP2 cannot help them to learn anything they do not know.Proof: .
There are two cases of collusion.Case 1: Some users collude with SP1. These users can provide their data to SP1. However, SP1 still cannot obtain any part ofQ because each entry of Q is divided between all users. SP1 and these users cannot learn anything they do not know.Case 2: Some users collude with SP2. SP2 hasC and it knows C=QR. Without R, matrix C cannot help them learn anything else. Hence, they also cannot obtain Q because only some users collude with SP2. Without Q, SP2 cannot compute R and β. SP2 and these users cannot learn anything they do not know.
ForProtocol 4, simply requiring that there is no collusion between two service providers cannot prevent privacy leakage. Protocol 4 uses random hij to keep any user from learning other user’s Δkij. This is similar to the secure multiparty summation protocol proposed by Clifton et al. [36], except that our arithmetic operation is multiplication. If any two users do not collude, this multiparty multiplication is secure. However, if there are two users colluding with each other, they may obtain the other user’s data. For example, userk−1 and userk+1 can easily compute userk’s Δkij=userk′sTij/userk−1′sTij. For more discussion on this problem, please see [37].


## 3.1. Main Steps of Our PP-SVM Training Algorithm

The key of our training algorithm is to solve the LS-SVM equationQβ=e securely. Figure 4 shows the procedure of PP-SVM training, which includes several steps as follows:(1)
SP2 sendspk2 to other participators.(2)
All users send encrypted data to SP1.(3)
SP1 computesEQ and EC=EQR and then sends EC to SP2 (R is used for masking Q).(4)
SP2 decryptsEC, solves Cδ=e, decomposes δ into δ=t1δ1+t2δ2, and then sends δ1,δ2 to SP1 (t1,t2∈ℝ and δ1,δ2∈ℝm+1).(5)
SP1 computesζ=Rδ1, η=Rδ2 (removing perturbation).Figure 4
The procedure of our PP-SVM training.Finally, the SP1 has random vectorsζ, η; SP2 has random numbers t1,t2. These data satisfy β=t1ζ+t2η, where β is the solution of LS-SVM equation. Because the two service providers do not collude, neither of them knows β.Furthermore, during the training procedure, SP1 and SP2 should not learn anything aboutQ. The reason for this is that someone can learn the kernel matrix from Q, because the difference between them is small, and thus can learn some information about xi from the kernel matrix, especially when the kernel function is simple (see the appendix in [24]).We use the notationsSP1E and SP2C instead of SP1 and SP2 in this section to make their roles easy to identify.


## 3.2. Securely Computing MatricesEΩ and EQ

### 3.2.1. Case 1: PP-SVM with Linear Kernel

For a linear-kernel matrix, itsi,jth entry Kxi,xj=xi,xj=∑k=1rxik,xjk. For Ω=ωijm×n, we have(13)Eωij=EyiyjKxi,xj=E∑k=1ryixik,yjxjk=∏k=1rEyixik,yjxjk.Based on (13), we design Protocol 1.Protocol 1.
ComputeEQ for linear-kernel PP-SVM.Input:userk provides xik; each yi is shared by all users, where 1≤i≤m and 1≤k≤r.Output: SP1 obtains EQ.(1)
Eachuserk computes Eyixik,yjxjk locally and sends them to SP1, where 1≤i,j≤m, 1≤k≤r.(2)
For any1​≤​i,j​≤​m, SP1 computes EΩ as follows:Eωij=∏k=1r​Eyixik,yjxjk.(3)
User sendsEγ−1 and all Eyi to SP1, who computes each Eωii+γ−1=Eωii⋅Eγ−1. Then, SP1 obtains EQ (γ is the parameter in (7)).


### 3.2.2. Case 2: PP-SVM with Polynomial Kernel

For a polynomial kernel matrix, itsi,jth entry Kxi,xj=axi,xj+cp=∑k=1raxik,xjk+cp. Hence,(14)Eωij=EyiyjKxi,xj=Eyiyj∑k=1raxik,xjk+cp.Based on (14), we design Protocol 2.Protocol 2.
ComputeEQ for polynomial kernel PP-SVM.Input: userk provides xik all yi, and a,c,p in the kernel function are shared by all users 1≤i≤m,1≤k≤r.Output: SP1E obtains EQ.(1)
user1 computes Eyiyj, Ec, and Eaxi1,xj1; other users compute Eaxik,xjk1≤i,j≤m,2≤k≤r. Then, all users send these data to SP1E.(2)
For1≤i,j≤m, SP1E computes(15)Tij=E∑k=1raxik,xjk+c=∏k=1rEaxik,xjk⋅Ec.(3)
user1 sends p to SP1E. For 1≤i,j≤m, let Sij=Tij. SP1E and SP2C repeatedly execute(16)Sij=EncMulSij,Tijp−1 times. Then, SP1E obtains(17)EKxi,xj=Sij=E∑k=1raxik,xjk+cp.(4)
SP1E and SP2C compute(18)Eωij=EncMulSij,Eyiyj1≤i,j≤m.Then,SP1E obtains EΩ.(5)
user1 sends Eγ−1 and all Eyi to SP1E, who computes Eωii+γ−1=Eωii⋅Eγ−1. Then, SP1E obtains EQ.Remark 1.
Becauseyi cannot be disclosed to service provider, two service providers must execute EncMul to generate Eωij, as shown in step 4. Another method is that SP1 sends all EKxi,xj to one user, who computes Eωij=EKxi,xjyiyj and returns it to SP1. In this way, two service providers can reduce the execution of EncMul once.
In addition, the degreep is the only parameter sent directly to SP1.


### 3.2.3. Case 3: PP-SVM with RBF Kernel

For a RBF kernel matrix, itsi,jth entry(19)Kxi,xj=exp−σxi−xj2=exp−σxi,xi−2xi,xj+xj,xj=exp−σ∑k=1rxik,xik−2xik,xjk+xjk,xjk=∏k=1rexp−σxik,xik−2xik,xjk+xjk,xjk.LetΔkij=exp−σxik,xik−2xik,xjk+xjk,xjk; we have(20)Eωij=EyiyjKxi,xj=Eyiyj∏k=1rΔkij.According to (9), we can design the following two methods for computing EΩ:(A)
SP1E collects EΔkij and EyiyjΔ1ij from users. Then, two servers use EncMul to compute Eωij.(B)
user1 chooses some random hij; all users try to compute Tij=hij∏k=1rΔkij. SP1E collects Eyiyj/hij and Tij; then, it can compute Eωij with them.Protocol 3 is designed based on method A.Protocol 3.
(method A)ComputeEQ for PP-SVM with RBF kernel.Input:userk provides xik, and each yi is shared by all users, where 1≤i≤m and 1≤k≤r.Output:SP1E obtains EQ.(1)
For any1≤i,j≤m, userk2≤k≤r computes EΔkij and user1 computes EyiyjΔ1ij. Then, all users send these data to SP1E.(2)
LetTij=EyiyjΔ1ij. SP1E and SP2C repeatedly execute(21)Tij=EncMulEΔkij,Tij,fork=2,3,…,r. Then, SP1E obtains(22)Eωij=Tij=Eyiyj∏k=1rΔkij1≤i,j≤m.(3)
user1 sends Eγ−1 and all Eyi to SP1E, who computes Eωii+γ−1=Eωii⋅Eγ−1. Then, SP1E obtains EQ.Remark 2.
Protocol 3 will call EncMul r−1 times. This leads to inefficiency because EncMul is a time-consuming protocol.
Protocol 4 is designed based on the method B.Protocol 4.
(method B) ComputeEQ for PP-SVM with RBF kernel.Input: userk provides xik, and each yi is shared by all users, where 1≤i≤m and 1≤k≤r.Output: SP1E obtains EQ.(1)
user1 chooses random real numbers hij>11≤i,j≤m and a random integer f>0, where f/hij>2g,g>10. Then, user1 computes Tij=hijΔ1ij for 1≤i,j≤m.(2)
user1 sends each Tij to user2, and user2 computes Tij=TijΔ2ij and then sends Tij to user3. One by one, other users do the same thing until userr computes Tij=TijΔrij and sends these data to SP1E.(3)
user1 computes Efyiyj/hij for 1≤i,j≤m; sends Efyiyj/hij to SP1E; and sends f to SP1E and SP2C.(4)
SP1E computes EΩ as follows:(23)Ef2ωij=Ef2yiyjhij∏k=1rΔkij≈EfyiyjhijfTij,where1≤i,j≤m.(5)
user1 sends Ef2γ−1 and all Ef2yi to SP1E, who computes Ef2ωii+f2γ−1=Ef2ωii⋅Ef2γ−1. Then, SP1E obtains Ef2Q.Remark 3.
The datayiyj/hij<1. To improve the accuracy, we multiply yiyj/hij by f and use the integer part of fyiyj/hij in subsequent computations. Proposition 1 will illustrate why it require f/hij>2g and g>10.
In this paper, we use Linear-SVM, Poly-SVM, RBF-SVM(A), and RBF-SVM(B) to denote the PP-SVM methods which useProtocols 1–4, respectively.
The RBF-SVM(B) is far more efficient than RBF-SVM(A), but it requires that any two participants do not collude with each other (see Section3.5.2).


## 3.2.1. Case 1: PP-SVM with Linear Kernel

For a linear-kernel matrix, itsi,jth entry Kxi,xj=xi,xj=∑k=1rxik,xjk. For Ω=ωijm×n, we have(13)Eωij=EyiyjKxi,xj=E∑k=1ryixik,yjxjk=∏k=1rEyixik,yjxjk.Based on (13), we design Protocol 1.Protocol 1.
ComputeEQ for linear-kernel PP-SVM.Input:userk provides xik; each yi is shared by all users, where 1≤i≤m and 1≤k≤r.Output: SP1 obtains EQ.(1)
Eachuserk computes Eyixik,yjxjk locally and sends them to SP1, where 1≤i,j≤m, 1≤k≤r.(2)
For any1​≤​i,j​≤​m, SP1 computes EΩ as follows:Eωij=∏k=1r​Eyixik,yjxjk.(3)
User sendsEγ−1 and all Eyi to SP1, who computes each Eωii+γ−1=Eωii⋅Eγ−1. Then, SP1 obtains EQ (γ is the parameter in (7)).


## 3.2.2. Case 2: PP-SVM with Polynomial Kernel

For a polynomial kernel matrix, itsi,jth entry Kxi,xj=axi,xj+cp=∑k=1raxik,xjk+cp. Hence,(14)Eωij=EyiyjKxi,xj=Eyiyj∑k=1raxik,xjk+cp.Based on (14), we design Protocol 2.Protocol 2.
ComputeEQ for polynomial kernel PP-SVM.Input: userk provides xik all yi, and a,c,p in the kernel function are shared by all users 1≤i≤m,1≤k≤r.Output: SP1E obtains EQ.(1)
user1 computes Eyiyj, Ec, and Eaxi1,xj1; other users compute Eaxik,xjk1≤i,j≤m,2≤k≤r. Then, all users send these data to SP1E.(2)
For1≤i,j≤m, SP1E computes(15)Tij=E∑k=1raxik,xjk+c=∏k=1rEaxik,xjk⋅Ec.(3)
user1 sends p to SP1E. For 1≤i,j≤m, let Sij=Tij. SP1E and SP2C repeatedly execute(16)Sij=EncMulSij,Tijp−1 times. Then, SP1E obtains(17)EKxi,xj=Sij=E∑k=1raxik,xjk+cp.(4)
SP1E and SP2C compute(18)Eωij=EncMulSij,Eyiyj1≤i,j≤m.Then,SP1E obtains EΩ.(5)
user1 sends Eγ−1 and all Eyi to SP1E, who computes Eωii+γ−1=Eωii⋅Eγ−1. Then, SP1E obtains EQ.Remark 1.
Becauseyi cannot be disclosed to service provider, two service providers must execute EncMul to generate Eωij, as shown in step 4. Another method is that SP1 sends all EKxi,xj to one user, who computes Eωij=EKxi,xjyiyj and returns it to SP1. In this way, two service providers can reduce the execution of EncMul once.
In addition, the degreep is the only parameter sent directly to SP1.


## 3.2.3. Case 3: PP-SVM with RBF Kernel

For a RBF kernel matrix, itsi,jth entry(19)Kxi,xj=exp−σxi−xj2=exp−σxi,xi−2xi,xj+xj,xj=exp−σ∑k=1rxik,xik−2xik,xjk+xjk,xjk=∏k=1rexp−σxik,xik−2xik,xjk+xjk,xjk.LetΔkij=exp−σxik,xik−2xik,xjk+xjk,xjk; we have(20)Eωij=EyiyjKxi,xj=Eyiyj∏k=1rΔkij.According to (9), we can design the following two methods for computing EΩ:(A)
SP1E collects EΔkij and EyiyjΔ1ij from users. Then, two servers use EncMul to compute Eωij.(B)
user1 chooses some random hij; all users try to compute Tij=hij∏k=1rΔkij. SP1E collects Eyiyj/hij and Tij; then, it can compute Eωij with them.Protocol 3 is designed based on method A.Protocol 3.
(method A)ComputeEQ for PP-SVM with RBF kernel.Input:userk provides xik, and each yi is shared by all users, where 1≤i≤m and 1≤k≤r.Output:SP1E obtains EQ.(1)
For any1≤i,j≤m, userk2≤k≤r computes EΔkij and user1 computes EyiyjΔ1ij. Then, all users send these data to SP1E.(2)
LetTij=EyiyjΔ1ij. SP1E and SP2C repeatedly execute(21)Tij=EncMulEΔkij,Tij,fork=2,3,…,r. Then, SP1E obtains(22)Eωij=Tij=Eyiyj∏k=1rΔkij1≤i,j≤m.(3)
user1 sends Eγ−1 and all Eyi to SP1E, who computes Eωii+γ−1=Eωii⋅Eγ−1. Then, SP1E obtains EQ.Remark 2.
Protocol 3 will call EncMul r−1 times. This leads to inefficiency because EncMul is a time-consuming protocol.
Protocol 4 is designed based on the method B.Protocol 4.
(method B) ComputeEQ for PP-SVM with RBF kernel.Input: userk provides xik, and each yi is shared by all users, where 1≤i≤m and 1≤k≤r.Output: SP1E obtains EQ.(1)
user1 chooses random real numbers hij>11≤i,j≤m and a random integer f>0, where f/hij>2g,g>10. Then, user1 computes Tij=hijΔ1ij for 1≤i,j≤m.(2)
user1 sends each Tij to user2, and user2 computes Tij=TijΔ2ij and then sends Tij to user3. One by one, other users do the same thing until userr computes Tij=TijΔrij and sends these data to SP1E.(3)
user1 computes Efyiyj/hij for 1≤i,j≤m; sends Efyiyj/hij to SP1E; and sends f to SP1E and SP2C.(4)
SP1E computes EΩ as follows:(23)Ef2ωij=Ef2yiyjhij∏k=1rΔkij≈EfyiyjhijfTij,where1≤i,j≤m.(5)
user1 sends Ef2γ−1 and all Ef2yi to SP1E, who computes Ef2ωii+f2γ−1=Ef2ωii⋅Ef2γ−1. Then, SP1E obtains Ef2Q.Remark 3.
The datayiyj/hij<1. To improve the accuracy, we multiply yiyj/hij by f and use the integer part of fyiyj/hij in subsequent computations. Proposition 1 will illustrate why it require f/hij>2g and g>10.
In this paper, we use Linear-SVM, Poly-SVM, RBF-SVM(A), and RBF-SVM(B) to denote the PP-SVM methods which useProtocols 1–4, respectively.
The RBF-SVM(B) is far more efficient than RBF-SVM(A), but it requires that any two participants do not collude with each other (see Section3.5.2).


## 3.3. Securely Computingβ and Splitting It between Two Service Providers

The decision function, which we call SVM model, can be written as follows:(24)fx=∑i=1mαiyiKxi,x+b=β⋅kx,where(25)β=b,α1,α2,…,αm,kx=1,y1Kx1,x,…,ymKxm,x.In this section, the two service providers will securely computeβ. Because β discloses the relationship between the input points and the hyperplane fx to some extent, we do not reveal β to service provider. To this end, we will randomly decompose β into a linear combination, then split this combination into two parts, and provide different parts to Evaluator and CSP. This ensures that both of the service providers learn nothing about β.In a word, we require that none of the service providers can learn anything aboutxi,yi,β, or Kxi,x when executing our algorithm.Protocol 5.
Computeβ and split it between two servers.Input: SP1E inputs EQ; CSP has the private key.Output: SP1E obtains vectors ζ, η; SP2C obtains real numbers t1, t2. These data satisfy β=t1ζ+t2η.(1)
SP1E chooses an invertible random R∈ℤ+m+1×m+1. For Linear-SVM, Poly-SVM, and RBF-SVM(A), let C=QR; SP1E computes each entry of EC as follows:(26)ECij=E∑k=1m+1QikRkj=∏k=1m+1EQikRkj.For RBF-SVM(B), letC=f2QR; SP1E computes(27)ECij=∏k=1m+1Ef2QikRkj,whereCij, Qik, Rkj are the elements of C, Q, R. Then, SP1E sends EC to SP2C.(2)
SP2C obtains C=DEC. Especially for method RBF-SVM(B), SP2 computes C=C/f2. Then, SP2 solves Cδ=e and obtains δ.(3)
Then,SP2C randomly divides δ into a linear combination as follows:(28)δ=t1δ1+t2δ2t1,t2∈ℝ,δ1,δ2∈ℝm+1.Then,SP2C sends vectors δ1,δ2 to SP1E.(4)
SP1E computes ζ=Rδ1 and η=Rδ2.Remark 4.
Step 1 uses an invertible matrixR to mask Q in an encrypted state. Step 3 decomposes δ into a linear combination. These random transformations prevent SP1 and SP2 from learning anything about Q or δ.
It is worth noting that keepingQ confidential is a key step to ensure the security of β. If someone obtains Q, they can compute β=Q−1e, where e=0,1,…,1 is the right-hand side of (6).
SP1 and SP2 will useζ, η, t1, and t2 to compute fx in prediction phase.


## 3.4. Correctness of Our Training Algorithm

It is easy to verify the correctness ofProtocols 1–3 by using the properties of Paillier encryption.InProtocol 4, we use secure multiplication which uses hij to conceal each user’s Δkij. The integers fyiyj/hij and fTij are used instead of fyiyj/hij and fTij in this protocol, which introduces error into system. Fortunately, the following proposition proves that the error is small.Proposition 1.
(precision)InProtocol 4, the use of fyiyj/hij and fTij introduces errors into the system, but the actual effect on each element in Q is less than 1/2g−1.
Proof: InProtocol 4, SP1 computes(29)Ef2ωij=EfyiyjhijfTij≈EfyiyjhijfTij.We usefyiyj/hijfTij instead of fyiyj/hijfTij. Let Q′ be a matrix and its i,jth entry be fyiyj/hijfTij.(30)Err=fyiyjhijfTij−fyiyjhijfTij=fhijfTij−fhijfTijyiyj=1or−1≤fhijfTij−fhijfTij+fhijfTij−fhijfTij<fhij+fhij∏k=1rΔkij<fhij+fhij0<Δkij<1.In step 2, SP2 computesC=C/f2=Q′/f2R. Clearly, it is equivalent to replacing Q with Q′/f2. This means the error for each entry in the matrix Q is Err/f2. We have(31)Errf2<1fhij+hijf<12ghij2+12g<12g−1f>2g.For example, if theg=11, the error is less than 10−3. The following proposition proves that the output of Protocol 5 is a linear combination of β.Proposition 2.
(correctness)InProtocol 5, SP1 has ζ and η; SP2 has t1 and t2. These data satisfy β=t1ζ+t2η, where β is the solution of LS-SVM equation.Proof: .
(32)t1ζ+t2η=Rt1δ1+t2δ2=Rδ=RR−1Q−1e=β.


## 3.5. Security of Our Training Algorithm

### 3.5.1. Security of the Protocol Itself

Protocols 1–4 only use Paillier encryption and protocol EncMul. Paillier encryption is semantically secure, and the security of EncMul has been confirmed by previous studies. Therefore, Protocols 1–4 do not disclose input data. The following proposition proves the security of Protocol 5.Proposition 3.
(security) InProtocol 5, two semi-honest and non-colluding service providers learn nothing about Q and β of the LS-SVM equation.Proof:SP1E only has the plaintext ζ and η. These data have nothing to do with Q; hence, SP1 cannot learn anything about Q. In addition, SP1 probably knows t1ζ+t2η=β. This gives it m+1 equations but m+3 unknowns t1,t2,β. Therefore, SP1 cannot also learn anything about β.SP2C only knows the matrix C. Even if it knows C=QR, it still cannot obtain anything about Q or R, because C=QR gives it m+12 equations but 2m+12 unknowns in Q and R. Meanwhile, CSP learns nothing about β without R, because β=Rδ and it only has δ.


### 3.5.2. Analysis of Collusion

Suppose there exists collusion between some participants. InProtocols 1–3, all users only provide data, and there is no communication between users. Therefore, we only need to discuss the collusion between users and one service provider.Proposition 4.
(collusion) For Linear-SVM, Poly-SVM, and RBF-SVM(A), collusion between some users and SP1 or SP2 cannot help them to learn anything they do not know.Proof: .
There are two cases of collusion.Case 1: Some users collude with SP1. These users can provide their data to SP1. However, SP1 still cannot obtain any part ofQ because each entry of Q is divided between all users. SP1 and these users cannot learn anything they do not know.Case 2: Some users collude with SP2. SP2 hasC and it knows C=QR. Without R, matrix C cannot help them learn anything else. Hence, they also cannot obtain Q because only some users collude with SP2. Without Q, SP2 cannot compute R and β. SP2 and these users cannot learn anything they do not know.
ForProtocol 4, simply requiring that there is no collusion between two service providers cannot prevent privacy leakage. Protocol 4 uses random hij to keep any user from learning other user’s Δkij. This is similar to the secure multiparty summation protocol proposed by Clifton et al. [36], except that our arithmetic operation is multiplication. If any two users do not collude, this multiparty multiplication is secure. However, if there are two users colluding with each other, they may obtain the other user’s data. For example, userk−1 and userk+1 can easily compute userk’s Δkij=userk′sTij/userk−1′sTij. For more discussion on this problem, please see [37].


## 3.5.1. Security of the Protocol Itself

Protocols 1–4 only use Paillier encryption and protocol EncMul. Paillier encryption is semantically secure, and the security of EncMul has been confirmed by previous studies. Therefore, Protocols 1–4 do not disclose input data. The following proposition proves the security of Protocol 5.Proposition 3.
(security) InProtocol 5, two semi-honest and non-colluding service providers learn nothing about Q and β of the LS-SVM equation.Proof:SP1E only has the plaintext ζ and η. These data have nothing to do with Q; hence, SP1 cannot learn anything about Q. In addition, SP1 probably knows t1ζ+t2η=β. This gives it m+1 equations but m+3 unknowns t1,t2,β. Therefore, SP1 cannot also learn anything about β.SP2C only knows the matrix C. Even if it knows C=QR, it still cannot obtain anything about Q or R, because C=QR gives it m+12 equations but 2m+12 unknowns in Q and R. Meanwhile, CSP learns nothing about β without R, because β=Rδ and it only has δ.


## 3.5.2. Analysis of Collusion

Suppose there exists collusion between some participants. InProtocols 1–3, all users only provide data, and there is no communication between users. Therefore, we only need to discuss the collusion between users and one service provider.Proposition 4.
(collusion) For Linear-SVM, Poly-SVM, and RBF-SVM(A), collusion between some users and SP1 or SP2 cannot help them to learn anything they do not know.Proof: .
There are two cases of collusion.Case 1: Some users collude with SP1. These users can provide their data to SP1. However, SP1 still cannot obtain any part ofQ because each entry of Q is divided between all users. SP1 and these users cannot learn anything they do not know.Case 2: Some users collude with SP2. SP2 hasC and it knows C=QR. Without R, matrix C cannot help them learn anything else. Hence, they also cannot obtain Q because only some users collude with SP2. Without Q, SP2 cannot compute R and β. SP2 and these users cannot learn anything they do not know.
ForProtocol 4, simply requiring that there is no collusion between two service providers cannot prevent privacy leakage. Protocol 4 uses random hij to keep any user from learning other user’s Δkij. This is similar to the secure multiparty summation protocol proposed by Clifton et al. [36], except that our arithmetic operation is multiplication. If any two users do not collude, this multiparty multiplication is secure. However, if there are two users colluding with each other, they may obtain the other user’s data. For example, userk−1 and userk+1 can easily compute userk’s Δkij=userk′sTij/userk−1′sTij. For more discussion on this problem, please see [37].


## 4. Our PP-SVM Prediction Algorithm

In this paper, each training data pointxi1≤i≤m is vertically partitioned between users. These users could be banks, insurance companies, e-commerce firms, etc., and they are unwilling to share their data with others. Meanwhile, the new data point x for prediction also includes the same attributes as xi. Indeed, it is difficult for someone else to collect the data for prediction from these users. Accordingly, we assume the data x is also vertically partitioned between these users.


### 4.1. Main Steps of Our PP-SVM Prediction Algorithm

In the prediction phase,userA wants to know about the category of object G. Therefore, it sends a request to all data owners (users); then, all users provide data x about G, and service providers will perform PP-SVM prediction algorithm. To determine the category of x, userA needs to know fx as follows:(33)fx=β,k=t1ζ,k+t2η,k,where k=1,k1,k2,…,km and ki=yiKxi,x, and ζ and η are held by SP1 and SP2. Figure 5 shows the procedure of prediction, which includes several steps as follows:Figure 5
The procedure of our PP-SVM prediction.Letk¯=k1,…,km, ζ¯=ζ1,…,ζm, and η¯=η1,…,ηm in the following steps.(1)
SP1 sendspk1 to other participators.(2)
All users send encrypted data to SP2.(3)
SP2 computesEk¯=Ek1,…,Ekm (maybe with the help of SP1).(4)
userA chooses u1,u2∈ℝ and sends them to SP1.(5)
SP1 choosesε∈ℤ+m; computes ζ′=u1ζ¯+ε, η′=u2η¯+ε, Eε; and then sends them to SP2.(6)
SP2 choosess∈ℤ+m and computes e1=s,ζ′, e2=s,η′, Ed=Es,ε, Ep=Ek¯+s. Then, it keeps e1,e2 by itself and sends Ed,Ep to SP1.(7)
SP1 decrypts the data received; computesv1=u1ζ¯,p+ζ0+d and v2=u2η¯,p+η0+d; and then sends v1, v2 to SP2.(8)
SP2 computesw1=t1v1−e1 and w2=t2v2−e2 and then sends w1,w2 to userA.(9)
userA computes the outy=w1/u1+w2/u2.Finally,userA obtains the outy, which is the value of fx. Because using the random vectors ε and s in this procedure, each service provider cannot learn the data held by the other party.


### 4.2. Our Protocol for PP-SVM Prediction

In this phase, SP1 and SP2 switch their roles in the training phase. SP1 becomes CSP and SP2 becomes Evaluator. We use the notationsSP1C and SP2E instead of SP1 and SP2 in Protocol 6 to show their roles. Let the new data point x=x1,x2,…,xr, where xk is owned by userk.Protocol 6.
Privacy-preserving SVM prediction.Input: userk provides xk1≤k≤r; SP1C and SP2E provide their data obtained in the training phaseOutput: only userA obtains the value of fx.(1)
ComputeEyiKxi,x, where 1≤i≤m.Case 1: Linear-SVM.(a)
Eachuserk computes Eyixik,xk locally and sends them to SP2E, where 1≤i≤m.(b)
SP2E computes the following data for 1≤i≤m.(34)EyiKxi,x=∏k=1rEyixik,xk.Case 2: Poly-SVM.(a)
Eachuserk computes Eaxik,xk and user1 computes all Eyi and Ec. They send all of them to SP2E.(b)
For1≤i≤m, SP2E computes(35)Ti=E∑k=1raxik,xk+c=∏k=1rEaxik,xk⋅Ec.(c)
LetSi=Ti. SP2E and SP1C repeatedly execute Si=EncMulSi,Tip−1 times. Then, SP2E obtains(36)Si=EKxi,x=E∑k=1raxik,xk+cp.(d)
Finally,SP2E and SP1C compute(37)EyiKxi,x=EncMulEyi,Si.Then,SP2E obtains EyiKxi,x for 1≤i≤m.Case 3 (for PP-SVM with RBF kernel):Choose one from the following two methods.Method RBF-SVM(A):(a)
LetΔki=exp−σxik,xik−2xik,xk+xk,xk. userkk≥2 computes EΔki; user1 computes EyiΔ1i, where 1≤i≤m. Then, all these data are sent to SP2E.(b)
For any1≤i≤m, let Ti=EyiΔ1i. Evaluator and CSP repeatedly execute Ti=EncMulEΔki,Ti for k=2,…,r. Finally, SP2E obtains(38)EyiKxi,x=Ti=Eyi∏k=1rΔki.Method RBF-SVM(B):(a)
LetΔki=exp−σxik,xik−2xik,xk+xk,xk. user1 chooses random real numbers hi>1 and computes Ti=hiΔ1i for any 1≤i≤m.(b)
user1 sends each Ti to user2, and user2 computes Ti=TiΔ2i and then sends Ti to user3. One by one, other users do the same thing until userr computes Ti=TiΔri and sends these data to SP2E.(c)
user1 chooses a random integer f>210hi, computes Efyi/hi, sends Efyi/hi to SP2E, and sends f to SP1C and SP2E.(d)
For1≤i≤m, SP2E computes(39)Ef2yiKxi,x=Ef2yi∏k=1rΔki=EfyihifTi.(2)
userA chooses two random real numbers u1, u2 and sends them to Evaluator, where u1>1, u2>1.(3)
SP1C chooses positive random integers ε1,…,εm and computes Eε1,Eε2,…,Eεm and(40)ζ1′=u1ζ1+ε1,…,ζm′=u1ζm+εm,η1′=u2η1+ε1,…,ηm′=u2ηm+εm,whereSP1C’s data ζ=ζ0,ζ1,…,ζm and η=η0,η1,…,ηm are obtained in Protocol 5. Then, SP1C sends all Eεi, ηi′, and ζi′ to SP2E.(4)
SP2E chooses positive random integers s1,…,sm. Let pi=yiKxi,x+si1≤i≤m, d=∑i=1msiεi. SP2E computes(41)Epi=EyiKxi,x⋅Esi,Ed=E∑i=1msiεi=∏i=1mEεisi,e1=∑i=1msiζi′,e2=∑i=1msiηi′,and sends allEpi,Ed to SP1C.(5)
SP1C obtains pi=DEpi, d=DEd. For Linear-SVM, Poly-SVM, and RBF-SVM(A), SP1C computes(42)v1=u1∑i=1mζipi+ζ+d,v2=u2∑i=1mηpi+η0+d.For RBF-SVM(B),SP1C computes(43)v1=u1∑i=1mζipi+f2ζ0+d,v2=u2∑i=1mηipi+f2η0+d.Then,SP1C sends v1,v2 to SP2E.(6)
For Linear-SVM, Poly-SVM, and RBF-SVM(A),SP2E computes(44)w1=t1v1−e1,w2=t2v2−e2.For RBF-SVM(B),SP2E computes(45)w1=t1v1−e1f2,w2=t2v2−e2f2.Then,SP2E sends w1,w2 to userA.(7)
userA computes fx as follows:(46)w1u1+w2u2.We chooseu1>1, u2>1 to make the computation more accurate.


### 4.3. Correctness and Security of Prediction Algorithm

InProtocol 6, two service providers compute EyiKxi,x in step 1. This step is similar to computing EΩ in Protocols 1–4. Its correctness is obvious. The following proposition proves that the output of Protocol 6 is fx.Proposition 5.
(correctness) InProtocol 6, userA finally obtains the value(47)fx=∑i=1mαiyiKxi,x+b.Proof: .
For Linear-SVM, Poly-SVM, and RBF-SVM(A),userA finally obtains the following value:(48)w1u1+w2u2=t1v1−e1u1+t2v2−e2u2=t1u1∑i=1mζpii+ζ0+d−u1∑i=1msiζi+εiu1+t2u2∑i=1mηipi+η0+d−u2∑i=1msiηi+εiu2=t1∑i=1mζiyiKxi,x+ζ0+d−∑i=1msiεi+t2∑i=1mηiyiKxi,x+η0+d−∑i=1msiεi=∑i=1mt1ζi+t2ηiyiKxi,x+t1ζ0+t2η0=∑i=1mαiyiKxi,x+bt1ζ+t2η=β.
There is a similar proof process for RBF-SVM(B).
The next proposition guarantees the security ofProtocol 6.Proposition 6.
(security) InProtocol 6, two non-colluding service providers cannot learn anything about the data xi,yi, x, fx, β, and Kxi,x.Proof: .
We do not discuss step 1 because it is essentially the same as computingEΩ in Protocols 1–4. The following discussion is about the other steps.
SP1C knows plaintext d, pi, ζ, and η. The ζ and η have nothing to do with pi and d. In fact, even if it knows(49)d=∑i=1msiεi,pi=yiKxi,x+si1≤i≤mand regards each yiKxi,x as an unknown variable ui, the number of unknowns (including ui and si) still far exceeds the number of equations given by pi and d. This ensures that SP1 learns nothing from pi and d. Meanwhile, SP1 still does not know t1,t2, which means it still cannot learn β. Thus, SP1 knows nothing about xi,yi, x, fx, β, or Kxi,x.
SP2E only receives plaintext ζi′, ηi′, v1,v2, where 1≤i≤m. Other encrypted data it has are not helpful in understanding private information. Under this circumstance, even if it knows the following equations:(50)ζi′=u1ζi+εi,v1=u1∑i=1mζipi+ζ0+d,ηi′=u2ηi+εi,v2=u2∑i=1mηipi+η0+d,
the number of unknowns (includingζi, ηi, εi, pi, u1, u2, d) is still far more than the number of equations. It cannot obtain any new information from these equations. Hence, SP2 learns nothing about xi,yi, x, fx, β, or Kxi,x. The following proposition discusses the collusion between userA and one service provider.Proposition 7.
(collusion) InProtocol 6, collusion between userA and SP1 or SP2 cannot help them to learn anything they do not know.Proof: .
There are two cases of collusion.Case 1userA colludes with SP1.  userA can provide w1,w2 to SP1. Even if they know the following equations:(51)ζi+εi,ηi+εi1≤i≤m,∑i=1mζipi+ζ0+d,∑i=1mηipi+η0+d,there are still unknownst1,t2,e1,e2,s1,…,sm in these equations. The number of unknowns still exceeds the number of equations. SP1 and userA cannot learn anything with these equations.Case 2:userA colludes with SP2. userA can give SP2u1 and u2, which can be used by SP2 to simplify (50). Then, SP2 obtains the values of the following expressions:(52)ζi+ɛi,ηi+ɛi,1≤i≤m,∑i=1mζipi+ζ0+s,∑i=1mηipi+η0+d.
Indeed, the number of unknownsζi,ηi,ɛi,pi,d is still far more than the number of these expressions. SP2 and userA cannot learn anything with these equations.


## 4.1. Main Steps of Our PP-SVM Prediction Algorithm

In the prediction phase,userA wants to know about the category of object G. Therefore, it sends a request to all data owners (users); then, all users provide data x about G, and service providers will perform PP-SVM prediction algorithm. To determine the category of x, userA needs to know fx as follows:(33)fx=β,k=t1ζ,k+t2η,k,where k=1,k1,k2,…,km and ki=yiKxi,x, and ζ and η are held by SP1 and SP2. Figure 5 shows the procedure of prediction, which includes several steps as follows:Figure 5
The procedure of our PP-SVM prediction.Letk¯=k1,…,km, ζ¯=ζ1,…,ζm, and η¯=η1,…,ηm in the following steps.(1)
SP1 sendspk1 to other participators.(2)
All users send encrypted data to SP2.(3)
SP2 computesEk¯=Ek1,…,Ekm (maybe with the help of SP1).(4)
userA chooses u1,u2∈ℝ and sends them to SP1.(5)
SP1 choosesε∈ℤ+m; computes ζ′=u1ζ¯+ε, η′=u2η¯+ε, Eε; and then sends them to SP2.(6)
SP2 choosess∈ℤ+m and computes e1=s,ζ′, e2=s,η′, Ed=Es,ε, Ep=Ek¯+s. Then, it keeps e1,e2 by itself and sends Ed,Ep to SP1.(7)
SP1 decrypts the data received; computesv1=u1ζ¯,p+ζ0+d and v2=u2η¯,p+η0+d; and then sends v1, v2 to SP2.(8)
SP2 computesw1=t1v1−e1 and w2=t2v2−e2 and then sends w1,w2 to userA.(9)
userA computes the outy=w1/u1+w2/u2.Finally,userA obtains the outy, which is the value of fx. Because using the random vectors ε and s in this procedure, each service provider cannot learn the data held by the other party.


## 4.2. Our Protocol for PP-SVM Prediction

In this phase, SP1 and SP2 switch their roles in the training phase. SP1 becomes CSP and SP2 becomes Evaluator. We use the notationsSP1C and SP2E instead of SP1 and SP2 in Protocol 6 to show their roles. Let the new data point x=x1,x2,…,xr, where xk is owned by userk.Protocol 6.
Privacy-preserving SVM prediction.Input: userk provides xk1≤k≤r; SP1C and SP2E provide their data obtained in the training phaseOutput: only userA obtains the value of fx.(1)
ComputeEyiKxi,x, where 1≤i≤m.Case 1: Linear-SVM.(a)
Eachuserk computes Eyixik,xk locally and sends them to SP2E, where 1≤i≤m.(b)
SP2E computes the following data for 1≤i≤m.(34)EyiKxi,x=∏k=1rEyixik,xk.Case 2: Poly-SVM.(a)
Eachuserk computes Eaxik,xk and user1 computes all Eyi and Ec. They send all of them to SP2E.(b)
For1≤i≤m, SP2E computes(35)Ti=E∑k=1raxik,xk+c=∏k=1rEaxik,xk⋅Ec.(c)
LetSi=Ti. SP2E and SP1C repeatedly execute Si=EncMulSi,Tip−1 times. Then, SP2E obtains(36)Si=EKxi,x=E∑k=1raxik,xk+cp.(d)
Finally,SP2E and SP1C compute(37)EyiKxi,x=EncMulEyi,Si.Then,SP2E obtains EyiKxi,x for 1≤i≤m.Case 3 (for PP-SVM with RBF kernel):Choose one from the following two methods.Method RBF-SVM(A):(a)
LetΔki=exp−σxik,xik−2xik,xk+xk,xk. userkk≥2 computes EΔki; user1 computes EyiΔ1i, where 1≤i≤m. Then, all these data are sent to SP2E.(b)
For any1≤i≤m, let Ti=EyiΔ1i. Evaluator and CSP repeatedly execute Ti=EncMulEΔki,Ti for k=2,…,r. Finally, SP2E obtains(38)EyiKxi,x=Ti=Eyi∏k=1rΔki.Method RBF-SVM(B):(a)
LetΔki=exp−σxik,xik−2xik,xk+xk,xk. user1 chooses random real numbers hi>1 and computes Ti=hiΔ1i for any 1≤i≤m.(b)
user1 sends each Ti to user2, and user2 computes Ti=TiΔ2i and then sends Ti to user3. One by one, other users do the same thing until userr computes Ti=TiΔri and sends these data to SP2E.(c)
user1 chooses a random integer f>210hi, computes Efyi/hi, sends Efyi/hi to SP2E, and sends f to SP1C and SP2E.(d)
For1≤i≤m, SP2E computes(39)Ef2yiKxi,x=Ef2yi∏k=1rΔki=EfyihifTi.(2)
userA chooses two random real numbers u1, u2 and sends them to Evaluator, where u1>1, u2>1.(3)
SP1C chooses positive random integers ε1,…,εm and computes Eε1,Eε2,…,Eεm and(40)ζ1′=u1ζ1+ε1,…,ζm′=u1ζm+εm,η1′=u2η1+ε1,…,ηm′=u2ηm+εm,whereSP1C’s data ζ=ζ0,ζ1,…,ζm and η=η0,η1,…,ηm are obtained in Protocol 5. Then, SP1C sends all Eεi, ηi′, and ζi′ to SP2E.(4)
SP2E chooses positive random integers s1,…,sm. Let pi=yiKxi,x+si1≤i≤m, d=∑i=1msiεi. SP2E computes(41)Epi=EyiKxi,x⋅Esi,Ed=E∑i=1msiεi=∏i=1mEεisi,e1=∑i=1msiζi′,e2=∑i=1msiηi′,and sends allEpi,Ed to SP1C.(5)
SP1C obtains pi=DEpi, d=DEd. For Linear-SVM, Poly-SVM, and RBF-SVM(A), SP1C computes(42)v1=u1∑i=1mζipi+ζ+d,v2=u2∑i=1mηpi+η0+d.For RBF-SVM(B),SP1C computes(43)v1=u1∑i=1mζipi+f2ζ0+d,v2=u2∑i=1mηipi+f2η0+d.Then,SP1C sends v1,v2 to SP2E.(6)
For Linear-SVM, Poly-SVM, and RBF-SVM(A),SP2E computes(44)w1=t1v1−e1,w2=t2v2−e2.For RBF-SVM(B),SP2E computes(45)w1=t1v1−e1f2,w2=t2v2−e2f2.Then,SP2E sends w1,w2 to userA.(7)
userA computes fx as follows:(46)w1u1+w2u2.We chooseu1>1, u2>1 to make the computation more accurate.


## 4.3. Correctness and Security of Prediction Algorithm

InProtocol 6, two service providers compute EyiKxi,x in step 1. This step is similar to computing EΩ in Protocols 1–4. Its correctness is obvious. The following proposition proves that the output of Protocol 6 is fx.Proposition 5.
(correctness) InProtocol 6, userA finally obtains the value(47)fx=∑i=1mαiyiKxi,x+b.Proof: .
For Linear-SVM, Poly-SVM, and RBF-SVM(A),userA finally obtains the following value:(48)w1u1+w2u2=t1v1−e1u1+t2v2−e2u2=t1u1∑i=1mζpii+ζ0+d−u1∑i=1msiζi+εiu1+t2u2∑i=1mηipi+η0+d−u2∑i=1msiηi+εiu2=t1∑i=1mζiyiKxi,x+ζ0+d−∑i=1msiεi+t2∑i=1mηiyiKxi,x+η0+d−∑i=1msiεi=∑i=1mt1ζi+t2ηiyiKxi,x+t1ζ0+t2η0=∑i=1mαiyiKxi,x+bt1ζ+t2η=β.
There is a similar proof process for RBF-SVM(B).
The next proposition guarantees the security ofProtocol 6.Proposition 6.
(security) InProtocol 6, two non-colluding service providers cannot learn anything about the data xi,yi, x, fx, β, and Kxi,x.Proof: .
We do not discuss step 1 because it is essentially the same as computingEΩ in Protocols 1–4. The following discussion is about the other steps.
SP1C knows plaintext d, pi, ζ, and η. The ζ and η have nothing to do with pi and d. In fact, even if it knows(49)d=∑i=1msiεi,pi=yiKxi,x+si1≤i≤mand regards each yiKxi,x as an unknown variable ui, the number of unknowns (including ui and si) still far exceeds the number of equations given by pi and d. This ensures that SP1 learns nothing from pi and d. Meanwhile, SP1 still does not know t1,t2, which means it still cannot learn β. Thus, SP1 knows nothing about xi,yi, x, fx, β, or Kxi,x.
SP2E only receives plaintext ζi′, ηi′, v1,v2, where 1≤i≤m. Other encrypted data it has are not helpful in understanding private information. Under this circumstance, even if it knows the following equations:(50)ζi′=u1ζi+εi,v1=u1∑i=1mζipi+ζ0+d,ηi′=u2ηi+εi,v2=u2∑i=1mηipi+η0+d,
the number of unknowns (includingζi, ηi, εi, pi, u1, u2, d) is still far more than the number of equations. It cannot obtain any new information from these equations. Hence, SP2 learns nothing about xi,yi, x, fx, β, or Kxi,x. The following proposition discusses the collusion between userA and one service provider.Proposition 7.
(collusion) InProtocol 6, collusion between userA and SP1 or SP2 cannot help them to learn anything they do not know.Proof: .
There are two cases of collusion.Case 1userA colludes with SP1.  userA can provide w1,w2 to SP1. Even if they know the following equations:(51)ζi+εi,ηi+εi1≤i≤m,∑i=1mζipi+ζ0+d,∑i=1mηipi+η0+d,there are still unknownst1,t2,e1,e2,s1,…,sm in these equations. The number of unknowns still exceeds the number of equations. SP1 and userA cannot learn anything with these equations.Case 2:userA colludes with SP2. userA can give SP2u1 and u2, which can be used by SP2 to simplify (50). Then, SP2 obtains the values of the following expressions:(52)ζi+ɛi,ηi+ɛi,1≤i≤m,∑i=1mζipi+ζ0+s,∑i=1mηipi+η0+d.
Indeed, the number of unknownsζi,ηi,ɛi,pi,d is still far more than the number of these expressions. SP2 and userA cannot learn anything with these equations.


## 5. Experiments

In this section, we evaluate our algorithm on accuracy and execution time. The datasets used in our experiments, including Liver Disorders, Sonar, and Breast Cancer Wisconsin, are obtained from the UCI Machine Learning Repository [38].


### 5.1. Experimental Settings

All our experiments are conducted on a Dell laptop with an Intel i7-4800MQ CPU (8 cores at 2.7 GHz) and 32 GB RAM, running Ubuntu Linux 20.04. We implement our protocols in Python and its extensions: gmpy2 [39] and bigfloat [40]. These two modules support high-precision arithmetic.Before starting our experiment, we normalize the input dataxi,x to the range 0,1 and set the class label yi to 1 or −1. We adopt a Paillier cryptosystem with 1024-bit modulus in our system. This means all input data and intermediate results only could be integers in −2512,2512, where negative integers are represented by 2’s complement.For the polynomial kernel, we only consider the quadratic polynomialaxi,xj+c2.


### 5.2. Accuracy

#### 5.2.1. The Effect of Different Fraction Length on the Error

We adopt fixed-point numbers in our system. Fixed-point arithmetic operation will bring truncation error.Experiment 1 investigates the effect of the fraction lengthq, which is used to convert a real number a to an integer a⋅2q. The dataset Liver Disorders is used in this experiment. We randomly choose 50 records for training and 20 records for prediction. Moreover, we split input data between 2 users.For different fraction lengths, we compare our methods with the ordinary SVM and compute the error offx between them at data points for prediction. For different kernel SVM, we choose parameter values as follows:(1)
Linear:γ=2.(2)
Polynomial:γ=3,a=1.5,c=1.(3)
RBF(A):γ=2,σ=11.1.(4)
RBF(B):γ=2,σ=11.1,h∈9e3,104,f=107,1012.In method RBF-SVM(B),h is used for secure multiplication. Giving h a wider range (e.g., h∈10,104) can make our protocol more secure. In our experiment, the small range of h actually limits f/h to a small range. Then, we can study the influence of fraction length on the error of RBF-SVM(B).The results of experiment 1 are shown in Table1. For our Linear-SVM, Poly-SVM, and RBF-SVM(A), it shows that the error decreases with the increase of fraction length q. However, for RBF-SVM(B), the variation of error is very small with the increase of q. The reason for this is that the RBF-SVM(B) performs fewer homomorphic computations than the other methods. We suggest q≥32 in most practical problems, which provides enough accuracy to guarantee the correctness of the classification.Table 1
Output errors of all methods with differentq (experiment 1).
Fraction lengthq8162432Linear1.2e − 026.8e − 052.4e − 076.9e − 10Polynomial9.9e − 024.8e − 041.1e − 063.9e − 09RBF(A)4.1e − 032.4e − 051.2e − 072.9e − 10RBF(B)f=1071.0e − 037.2 − 049.1e − 049.0e − 04RBF(B)f=10128.8e − 098.7e − 097.9e − 099.2e − 09From the last two lines of Table1, we know that the value of f/h has a significant impact on the accuracy of RBF-SVM(B). Experiment 2 is conducted to evaluate the effect of different f/h. In experiment 2, we choose q=32,γ=2,σ=11.1,h∈9000,104. The results are shown in Table 2. When f/h≈1, the predicted value is wrong. With the increase of f/h, the error of the predicted values decreases linearly.Table 2
Output errors of RBF-SVM(B) with differentf/h (experiment 2).
f/h≈1f/h≈102f/h≈103f/h≈105f/h≈108Error result6.1e − 038.3e − 045.3e − 064.8e − 09


#### 5.2.2. The Effect of Different Numbers of Users on the Error

Our methods merge all users’ data to generateEQ. More users mean more fixed-point computations, which may bring more errors to our system. Experiment 3 studies the influence of the number of users on the accuracy.The dataset Sonar is used in experiment 3. We choose 40 records from it for training and 20 records for prediction. Furthermore, we set the fraction lengthq=32. In addition, for RBF-SVM(B), we choose h∈28,212 and f=240. Then, we perform each method for the number of users r=2,5,10,15,30,40,50. Figure 6 shows the errors of fx for our methods and the ordinary SVM.Figure 6
The error of the predicted values (experiment 3).For our Linear-SVM, Poly-SVM, and RBF-SVM(A), Figure6 shows that the errors usually increase with the increasing number of users, but the errors increase very slowly. When the number of users r goes from 2 to 50, the errors increase by less than 7 times.We know that the RBF-SVM(A) needs to executeEncMulr−1 times when computing Eωij. Meanwhile, the Poly-SVM executes EncMul only twice for any number of users when computing Eωij. However, in Figure 6, we find little difference in accuracy between the methods RBF-SVM(A) and Poly-SVM. This means multiple calls to EncMul have little impact on accuracy.In addition, the errors of RBF-SVM(B) are almost invariant with the increasing number of users. We believe the reason is that all users use high-precision floating-point operations to merge data (secure multiplication), and then convert the results to fixed-point numbers with only one operation. Therefore, the number of users has little impact.


### 5.3. Execution Time

To investigate the performance of our algorithm, we divide each method into 4 stages:Stage A: each user computes part of matrixEΩ with local data.Stage B: Evaluator computesEΩ, EQ, and EC in an encrypted form.Stage C: CSP solves the encrypted equation; finally, CSP hast1,t2; and Evaluator obtains ζ,η.Stage D: all users submit a new data point together, and two service providers make prediction for it.


#### 5.3.1. The Complexity of Our Algorithm at Different Stages

Except arithmetic operations (add, mul, div), we also take random number generation (rnd),ex (exp), modular exponentiation (pow), encryption (Enc), decryption (Dec), and EncMul as basic operations.Table3 shows the complexity of each method at different stages. The time spent on different operations varies greatly. When we set the fraction length q=32 and limit the range of random numbers to 1,232, the execution time of these operations has the following relationship:(53)1EncMul≈4.5Dec≈9Enc≈180pow≈1800mul≈18000exp≈18000add≈105rnd.Table 3
The complexity of our algorithm at different stages.
MethodsLinear-SVMPoly-SVMRBF-SVM(A)RBF-SVM(B)Stage A (each user)mul:Onm2add: Onm2Enc: m2mul:Onm2add: Onm2Enc: m2mul:Onm2add: Onm2exp: m2 Enc: m2mul:Onm2add: Onm2exp: m2rnd: m2mul: rm2Enc: m2Stage B (SP1, SP2)mul:m+12m+rm2add: m+12mrnd: m+12pow: m+13mul:m+12m+rm2add: m+12mrnd: m+12pow: m+13EncMul:pm2mul:m+12madd: m+12mrnd: m+12pow: m+13EncMul:r−1m2mul:m+12madd: m+12mrnd: m+12pow: m+13+m2Stage C (SP1, SP2)mul:Om3, div: Om3, add: Om3 Dec: m2Stage D (each user)mul:Onmadd: OnmEnc: mmul:Onmadd: OnmEnc: mmul:Onmadd: Onmexp: mEnc: mmul:Onmadd: Onmexp: mrnd: mmul: rmEnc: mStage D (SP1, SP2userA)mul:Ormadd: OmEnc: mDec: mrnd: 2mpow: mmul:Ormadd: OmEnc: mDec: mrnd: 2mpow: mEncMul:pmmul:Omadd: OmEnc: mDec: mrnd: 2mpow: mEncMul:r−1mmul:Omadd: OmEnc: mDec: mrnd: 2mpow: mNote.n is the number of features, m is the number of data points (records), r is the number of users, exp is the ex, rnd is the random integer generation, pow is the modular exponentiation, Enc is the encryption, Dec is the decryption. Tasks performed by one user or tasks performed by all users in sequence.This relationship is not fixed. It varies with fraction length and random numbers and operands. For example, the exp in our system executes operations much faster than pow. The reason is that users use small numbers (plaintexts) for exp computation, but SP uses very large integers (ciphertexts, random numbers) for pow operation. In addition, because the pow operations in stage B use a lot of random numbers, only changing the range of random numbers will have a great impact on the running time.


#### 5.3.2. The Effect of Different Numbers of Records on the Execution Time

The number of input data pointsm has a great impact on the execution time, because all participators need to deal with m×m matrix. The problem is which stage is the bottleneck of performance.Experiment 4 investigates the effect of differentm on the execution time. The data used in this experiment are taken from the dataset Breast Cancer Wisconsin. We choose m= 40, 55, 70, 85, and 100 records for training and 1 record for prediction. Moreover, we split the data between r=2 users to reduce the impact of the number of users. We set the fraction length to q=32 and the range of random numbers to 1,232. The results are shown in Figure 7. Note that the execution time of stage A is the average execution time of all users.Figure 7
The execution time of each stage for different numbers of data points (experiment 4).It is easy to notice that stages C of all methods are the same. Therefore, the graphs of stages C of all methods in Figure7 are also the same. They can be regarded as a benchmark for comparison.Figure7 shows that the Poly-SVM and RBF-SVM(A) spend most of the time on stage B, and the execution time of stage B grows much faster than that of stage C with the increase of m. On the other hand, for the Linear-SVM or RBF-SVM(B), there is no huge difference between the execution time of stage B and that of stage C. This is because Poly-SVM and RBF-SVM(A) call protocol EncMul many times in stage B, while the other methods do not call it.Among all methods, we find that when the number of data points is the same, the maximum execution time of stage A or D does not exceed 200% of the minimum execution time of the same stage. This is not a significant difference.Comparing the efficiency of all methods under the same conditions, we have RBF-SVM(B)≈Linear-SVM≫Poly-SVM≈RBF-SVM(A). Calling EncMul takes up most of the execution time.


#### 5.3.3. The Effect of Different Numbers of Users on the Execution Time

Experiment 5 studies the effect of different numbers of usersr on the execution time. We use the same dataset and parameter settings as experiment 3 in this experiment. The results are shown in Figure 8. For each stage, we analyze the change of execution time as follows.Figure 8
The execution time of each stage for different numbers of users (experiment 5).(1) Stage A. Figure 8 shows that the execution time of stage A changes very little for all methods. The reasons are as follows.For any of Linear-SVM, Poly-SVM, or RBF-SVM(A), all users execute the protocol independently of each other. It is reasonable to assume that all users execute the protocol at this stage in parallel. For these methods, we take the average execution time of all users as the execution time of stage A, which is almost fixed with changingr.In the method RBF-SVM(B), all users in turn merge local data into a matrix (computingTij=TijΔkij by each user, userk). Although this step is related to r, it takes up only a small fraction of the execution time. The encryption operations performed by the last user take up most of the execution time of stage A.In sum, the execution time of stage A for all methods is hardly affected by the number of users.(2) Stage B. In stage B, Linear-SVM and Poly-SVM will perform multiplication r times for generating each entry of EΩ. For both of these two methods, this is the only step in stage B related to r. However, the time consumed by this step is far less than that consumed by other steps. For Linear-SVM, the pow operations are the most time-consuming steps and are independent of r. For Poly-SVM, the execution of EncMul takes up most of the execution time and has nothing to do with r. In addition, the computation of RBF-SVM(B) in stage B is completely independent of r. Hence, for Linear-SVM, Poly-SVM, and RBF-SVM(B), the execution time of stage B remains almost unchanged, as shown in Figure 8.Although both Poly-SVM and RBF-SVM(A) callEncMul in stage B, Poly-SVM with a kernel axi,xj+cp performs EncMulp times for each entry of EΩ, while RBF-SVM(A) performs EncMulr−1 times to do the same thing. Fortunately, the degree p is often a small integer. This reduces the negative impact of EncMul on Poly-SVM. However, for RBF-SVM(A), the situation is quite different. As shown in Figure 8, its execution time of stage B increases sharply with the increase of r. This disadvantage will affect the application of this method to a certain extent. For this reason, we design RBF-SVM(B) as an alternative.(3) Stage C. The tasks of all our methods at this stage are the same and independent of r. Figure 8 shows that the execution time of stage C is almost equal and fixed for all methods.(4) Stage D. In stage D, all methods need to compute the kernel function, which is the only step that may be related to the number of users. This step is similar to some computation procedures in stages A and B. The difference is that each method only needs to compute m values in stage D, but m2 values in stages A and B.Only the execution time of RBF-SVM(A) will be significantly affected because it will call EncMulEncMulr−1 times when computing each kernel function. This explains why, in Figure 8, the execution time of stage D of Linear-SVM, Poly-SVM, and RBF-SVM(B) changes very little with the increase of r, while the execution time of stage D of RBF-SVM(A) increases steadily.


### 5.4. Comparison with Another PP-SVM Algorithm

Park et al. [7] propose a PP-SVM training algorithm based on LS-SVM and they use CKKS [27] encryption to encrypt the input data. In this paper, we use the notation ⋅ to denote CKKS encryption algorithm. Their algorithm can be used in one client and one server environment. The client provides the encrypted matrix Q to the server, which uses gradient descent method to solve the equation QTQβ=QTe.


#### 5.4.1. The Modified Version of Park’s Training Method

We modify Park et al. method asProtocol 7 (MP’s method) to deal with the same problem as ours, and then we compare this modified method with our algorithm. We do not put the counterpart of RBF-SVM(B) in Protocol 7, because its performance is equivalent to that of Linear-SVM.Protocol 7.
(MP’s method): The modified version of Park’s training method.Input: each userk inputs xik, and yi is shared by all users, where 1≤i≤m, 1≤k≤r. The public key is shared by all participators, and userc has the private key.Output: Server obtains β.(1)
Users perform computation with local data.(a)
Linear kernel:Eachuserk computes yixik,yjxjk, and user1 also computes all yi. All these data are sent to server.(b)
Poly kernel:Eachuserk computes axik,xjk, and user1 also computes all yi and c. All these data are sent to server.(c)
RBF kernel (A):Eachuserk computes Δkij, and user1 also computes yi. Then, all these data are sent to server.(2)
Server computesQ.(a)
Linear kernel:Server computesΩij=∑k=1ryixik,yjxjk.(b)
Poly kernel:Server computesT1=∑k=1raxik,xjk+c=∑k=1raxik,xjk+c. Then, let T2=T1; server repeatedly computes T2=T2T1p−1 times and then computes Ωij=yiyjT2.(c)
RBF kernel (A):Server computesΩij=∏k=1rΔkijyiyj.Then, server computesΩii+γ−1=Ωii+γ−1. So far, sever has obtained all entries of Q.(3)
Server computesβ by gradient descent method.(a)
Server first computesQTQ and QTe with Q.(b)
Server chooses an initial vectorβ1 and then repeatedly computes βk as follows:(54)pk=QTQβk−QTeβk+1=βk−skpk,wherek=1,2,…,N and sk is learning rate.The server sent allβk to userc who decrypts them and determine if the iteration should be stopped.
Clearly, this modified Park’s method solves a problem just like ours. In this protocol, step 3 is the same as Park et al. method. Step 1 and step 2 adopt the ideas of this article. Of course, MP’s method uses CKKS encryption to compute both addition and multiplication between ciphers.
In this section, we compare MP’s method with ours. For a fair comparison, we do not use any packing technique in all the following experiments. Moreover, because the time spent on the client and prediction phase is far less than the training time spent on the server, we only focus on the execution time of training.
The server-side computation in the training phase includes computingEQ, computing EQTQ with EQ, and performing the gradient descent method. Obviously, the latter two computation processes are only related to the number of data points.


#### 5.4.2. Comparison of Server-Side Training Time between the Two Methods with Different Numbers of Users

In experiment 6, we choose 40 records from Sonar to be the training dataset. The data are vertically partitioned betweenr=5,10,20,40 users. The experimental results are shown in Table 4.Table 4
(Experiment 6) comparison of server-side training time between the two methods with different numbers of users (sec.).
Number of usersrLinear kernelPoly kernelRBF kernel (A)MP’sOursMP’sOursMP’sOurs5426.146.6425.5192.4463.5550.610435.847.8445.2191.5496.31169.720445.546.8430.9192.5562.12398.140429.147.9445.1192.3693.64865.2For the cases of linear and polynomial kernel, Table4 shows that our methods are more efficient. Although it takes longer to run the MP’s method, the training time of it with linear or polynomial kernel keeps almost unchanged with the increase of r. We believe the reason is as follows. When the number of records m is fixed, the MP’s method takes a fixed time to compute EQTQ and perform the gradient descent method. Meanwhile, although the time required to compute EQ is related to r, the MP’s Linear-kernel and Poly-kernel methods mainly perform efficient CKKS addition when computing EQ. The time they spent in computing EQ is far less than that spent in computing EQTQ and performing the gradient descent method. Therefore, we see in Table 4 that the server-side training time of MP’s method with Linear-kernel and Poly-kernel changes little with the increase of r. For RBF kernel, Table 4 shows that the training time of the two methods increases with the increase of r. The MP’s RBF kernel method mainly executes CKKS multiplication for computing EQ. The CKKS multiplication is a time-consuming operation, but it is still much more efficient than protocol EncMul. We know that our RBF-SVM(A) method spends most of its time executing EncMul, this makes MP’s method have better performance than RBF-SVM(A), as shown in Table 4.


#### 5.4.3. Comparison of Server-Side Training Time between the Two Methods with Different Numbers of Data Points

In experiment 7, we choosem=40, 60, 80, 100 records from Sonar to be training dataset and vertically partition the training data between r=2 users.Table5 shows the impact of m on server-side training time. For any type of kernel, the training time of both methods increases with the increase of m. However, the training time of MP’s method not only far exceeds ours, but also grows faster. Table 6 shows the two methods’ complexity of training phase. Meanwhile, in our experiment, the time consumed by the operations in Table 6 has the following relationship:(55)1EncMul≈4.5Dec≈10CKKS mul≈180pow.Table 5
(Experiment 7) comparison of server-side training time between the two methods with different numbers of data points (sec.).
Num. of data pointsmLinear kernelPoly kernelRBF kernel (A)MP’sOursMP’sOursMP’sOurs404304744719243917155106397108036910713317019201751951610193254985330027833309233332832Table 6
Two methods’ complexity of training phase.
MP’s methodOursLinear kernelPoly kernelRBF kernelOm3 mulOm3 powOm2 DecOm3 powOm2 EncMulOm2 DecOm3 powOm2 EncMulOm2 DecCKKS multiplication.The data in Table5 illustrates that Om3 CKKS multiplication grows faster than Om3pow+Om2EncMul+Om2Dec with the increase of m.For MP’s method, computingEQTQ and performing the gradient descent method take up most of the training time, as shown in Table 7. Actually, the computation of EQTQ is the preparation for the gradient descent method. Tables 5 and 7 illustrate that the gradient descent method is not a very efficient method in solving the equation.Table 7
(Experiment 7) the training time of MP’s method and the time consumed by two main steps of MP’s method (sec.).
Num. of data pointsmMP’s methodComputingEQTQGradient descentLinearPolyRBF4043044743928214055106310801071751258701920195119321458430853300333033322632625Note.TMP′s training=TEQ+TEQTQ+TGD method.Another uncertainty of the gradient descent method is how many times the iteration should be conducted before obtaining enough accurate result. The number of iterations has a significant impact on the training time. Park et al. performed the iteration 10 times in their experiments. It seems all right for their experiments, but there is no theoretical basis for doing this.The above comparisons show that each of the two methods has advantages and disadvantages. This leads to a simple idea of using CKKS encryption in our algorithm instead of Paillier encryption. This will combine the advantages of the two methods and seems more efficient. This idea is attractive, but it is not the focus of this paper. We left it as future work.


## 5.1. Experimental Settings

All our experiments are conducted on a Dell laptop with an Intel i7-4800MQ CPU (8 cores at 2.7 GHz) and 32 GB RAM, running Ubuntu Linux 20.04. We implement our protocols in Python and its extensions: gmpy2 [39] and bigfloat [40]. These two modules support high-precision arithmetic.Before starting our experiment, we normalize the input dataxi,x to the range 0,1 and set the class label yi to 1 or −1. We adopt a Paillier cryptosystem with 1024-bit modulus in our system. This means all input data and intermediate results only could be integers in −2512,2512, where negative integers are represented by 2’s complement.For the polynomial kernel, we only consider the quadratic polynomialaxi,xj+c2.


## 5.2. Accuracy

### 5.2.1. The Effect of Different Fraction Length on the Error

We adopt fixed-point numbers in our system. Fixed-point arithmetic operation will bring truncation error.Experiment 1 investigates the effect of the fraction lengthq, which is used to convert a real number a to an integer a⋅2q. The dataset Liver Disorders is used in this experiment. We randomly choose 50 records for training and 20 records for prediction. Moreover, we split input data between 2 users.For different fraction lengths, we compare our methods with the ordinary SVM and compute the error offx between them at data points for prediction. For different kernel SVM, we choose parameter values as follows:(1)
Linear:γ=2.(2)
Polynomial:γ=3,a=1.5,c=1.(3)
RBF(A):γ=2,σ=11.1.(4)
RBF(B):γ=2,σ=11.1,h∈9e3,104,f=107,1012.In method RBF-SVM(B),h is used for secure multiplication. Giving h a wider range (e.g., h∈10,104) can make our protocol more secure. In our experiment, the small range of h actually limits f/h to a small range. Then, we can study the influence of fraction length on the error of RBF-SVM(B).The results of experiment 1 are shown in Table1. For our Linear-SVM, Poly-SVM, and RBF-SVM(A), it shows that the error decreases with the increase of fraction length q. However, for RBF-SVM(B), the variation of error is very small with the increase of q. The reason for this is that the RBF-SVM(B) performs fewer homomorphic computations than the other methods. We suggest q≥32 in most practical problems, which provides enough accuracy to guarantee the correctness of the classification.Table 1
Output errors of all methods with differentq (experiment 1).
Fraction lengthq8162432Linear1.2e − 026.8e − 052.4e − 076.9e − 10Polynomial9.9e − 024.8e − 041.1e − 063.9e − 09RBF(A)4.1e − 032.4e − 051.2e − 072.9e − 10RBF(B)f=1071.0e − 037.2 − 049.1e − 049.0e − 04RBF(B)f=10128.8e − 098.7e − 097.9e − 099.2e − 09From the last two lines of Table1, we know that the value of f/h has a significant impact on the accuracy of RBF-SVM(B). Experiment 2 is conducted to evaluate the effect of different f/h. In experiment 2, we choose q=32,γ=2,σ=11.1,h∈9000,104. The results are shown in Table 2. When f/h≈1, the predicted value is wrong. With the increase of f/h, the error of the predicted values decreases linearly.Table 2
Output errors of RBF-SVM(B) with differentf/h (experiment 2).
f/h≈1f/h≈102f/h≈103f/h≈105f/h≈108Error result6.1e − 038.3e − 045.3e − 064.8e − 09


### 5.2.2. The Effect of Different Numbers of Users on the Error

Our methods merge all users’ data to generateEQ. More users mean more fixed-point computations, which may bring more errors to our system. Experiment 3 studies the influence of the number of users on the accuracy.The dataset Sonar is used in experiment 3. We choose 40 records from it for training and 20 records for prediction. Furthermore, we set the fraction lengthq=32. In addition, for RBF-SVM(B), we choose h∈28,212 and f=240. Then, we perform each method for the number of users r=2,5,10,15,30,40,50. Figure 6 shows the errors of fx for our methods and the ordinary SVM.Figure 6
The error of the predicted values (experiment 3).For our Linear-SVM, Poly-SVM, and RBF-SVM(A), Figure6 shows that the errors usually increase with the increasing number of users, but the errors increase very slowly. When the number of users r goes from 2 to 50, the errors increase by less than 7 times.We know that the RBF-SVM(A) needs to executeEncMulr−1 times when computing Eωij. Meanwhile, the Poly-SVM executes EncMul only twice for any number of users when computing Eωij. However, in Figure 6, we find little difference in accuracy between the methods RBF-SVM(A) and Poly-SVM. This means multiple calls to EncMul have little impact on accuracy.In addition, the errors of RBF-SVM(B) are almost invariant with the increasing number of users. We believe the reason is that all users use high-precision floating-point operations to merge data (secure multiplication), and then convert the results to fixed-point numbers with only one operation. Therefore, the number of users has little impact.


## 5.2.1. The Effect of Different Fraction Length on the Error

We adopt fixed-point numbers in our system. Fixed-point arithmetic operation will bring truncation error.Experiment 1 investigates the effect of the fraction lengthq, which is used to convert a real number a to an integer a⋅2q. The dataset Liver Disorders is used in this experiment. We randomly choose 50 records for training and 20 records for prediction. Moreover, we split input data between 2 users.For different fraction lengths, we compare our methods with the ordinary SVM and compute the error offx between them at data points for prediction. For different kernel SVM, we choose parameter values as follows:(1)
Linear:γ=2.(2)
Polynomial:γ=3,a=1.5,c=1.(3)
RBF(A):γ=2,σ=11.1.(4)
RBF(B):γ=2,σ=11.1,h∈9e3,104,f=107,1012.In method RBF-SVM(B),h is used for secure multiplication. Giving h a wider range (e.g., h∈10,104) can make our protocol more secure. In our experiment, the small range of h actually limits f/h to a small range. Then, we can study the influence of fraction length on the error of RBF-SVM(B).The results of experiment 1 are shown in Table1. For our Linear-SVM, Poly-SVM, and RBF-SVM(A), it shows that the error decreases with the increase of fraction length q. However, for RBF-SVM(B), the variation of error is very small with the increase of q. The reason for this is that the RBF-SVM(B) performs fewer homomorphic computations than the other methods. We suggest q≥32 in most practical problems, which provides enough accuracy to guarantee the correctness of the classification.Table 1
Output errors of all methods with differentq (experiment 1).
Fraction lengthq8162432Linear1.2e − 026.8e − 052.4e − 076.9e − 10Polynomial9.9e − 024.8e − 041.1e − 063.9e − 09RBF(A)4.1e − 032.4e − 051.2e − 072.9e − 10RBF(B)f=1071.0e − 037.2 − 049.1e − 049.0e − 04RBF(B)f=10128.8e − 098.7e − 097.9e − 099.2e − 09From the last two lines of Table1, we know that the value of f/h has a significant impact on the accuracy of RBF-SVM(B). Experiment 2 is conducted to evaluate the effect of different f/h. In experiment 2, we choose q=32,γ=2,σ=11.1,h∈9000,104. The results are shown in Table 2. When f/h≈1, the predicted value is wrong. With the increase of f/h, the error of the predicted values decreases linearly.Table 2
Output errors of RBF-SVM(B) with differentf/h (experiment 2).
f/h≈1f/h≈102f/h≈103f/h≈105f/h≈108Error result6.1e − 038.3e − 045.3e − 064.8e − 09


## 5.2.2. The Effect of Different Numbers of Users on the Error

Our methods merge all users’ data to generateEQ. More users mean more fixed-point computations, which may bring more errors to our system. Experiment 3 studies the influence of the number of users on the accuracy.The dataset Sonar is used in experiment 3. We choose 40 records from it for training and 20 records for prediction. Furthermore, we set the fraction lengthq=32. In addition, for RBF-SVM(B), we choose h∈28,212 and f=240. Then, we perform each method for the number of users r=2,5,10,15,30,40,50. Figure 6 shows the errors of fx for our methods and the ordinary SVM.Figure 6
The error of the predicted values (experiment 3).For our Linear-SVM, Poly-SVM, and RBF-SVM(A), Figure6 shows that the errors usually increase with the increasing number of users, but the errors increase very slowly. When the number of users r goes from 2 to 50, the errors increase by less than 7 times.We know that the RBF-SVM(A) needs to executeEncMulr−1 times when computing Eωij. Meanwhile, the Poly-SVM executes EncMul only twice for any number of users when computing Eωij. However, in Figure 6, we find little difference in accuracy between the methods RBF-SVM(A) and Poly-SVM. This means multiple calls to EncMul have little impact on accuracy.In addition, the errors of RBF-SVM(B) are almost invariant with the increasing number of users. We believe the reason is that all users use high-precision floating-point operations to merge data (secure multiplication), and then convert the results to fixed-point numbers with only one operation. Therefore, the number of users has little impact.


## 5.3. Execution Time

To investigate the performance of our algorithm, we divide each method into 4 stages:Stage A: each user computes part of matrixEΩ with local data.Stage B: Evaluator computesEΩ, EQ, and EC in an encrypted form.Stage C: CSP solves the encrypted equation; finally, CSP hast1,t2; and Evaluator obtains ζ,η.Stage D: all users submit a new data point together, and two service providers make prediction for it.


### 5.3.1. The Complexity of Our Algorithm at Different Stages

Except arithmetic operations (add, mul, div), we also take random number generation (rnd),ex (exp), modular exponentiation (pow), encryption (Enc), decryption (Dec), and EncMul as basic operations.Table3 shows the complexity of each method at different stages. The time spent on different operations varies greatly. When we set the fraction length q=32 and limit the range of random numbers to 1,232, the execution time of these operations has the following relationship:(53)1EncMul≈4.5Dec≈9Enc≈180pow≈1800mul≈18000exp≈18000add≈105rnd.Table 3
The complexity of our algorithm at different stages.
MethodsLinear-SVMPoly-SVMRBF-SVM(A)RBF-SVM(B)Stage A (each user)mul:Onm2add: Onm2Enc: m2mul:Onm2add: Onm2Enc: m2mul:Onm2add: Onm2exp: m2 Enc: m2mul:Onm2add: Onm2exp: m2rnd: m2mul: rm2Enc: m2Stage B (SP1, SP2)mul:m+12m+rm2add: m+12mrnd: m+12pow: m+13mul:m+12m+rm2add: m+12mrnd: m+12pow: m+13EncMul:pm2mul:m+12madd: m+12mrnd: m+12pow: m+13EncMul:r−1m2mul:m+12madd: m+12mrnd: m+12pow: m+13+m2Stage C (SP1, SP2)mul:Om3, div: Om3, add: Om3 Dec: m2Stage D (each user)mul:Onmadd: OnmEnc: mmul:Onmadd: OnmEnc: mmul:Onmadd: Onmexp: mEnc: mmul:Onmadd: Onmexp: mrnd: mmul: rmEnc: mStage D (SP1, SP2userA)mul:Ormadd: OmEnc: mDec: mrnd: 2mpow: mmul:Ormadd: OmEnc: mDec: mrnd: 2mpow: mEncMul:pmmul:Omadd: OmEnc: mDec: mrnd: 2mpow: mEncMul:r−1mmul:Omadd: OmEnc: mDec: mrnd: 2mpow: mNote.n is the number of features, m is the number of data points (records), r is the number of users, exp is the ex, rnd is the random integer generation, pow is the modular exponentiation, Enc is the encryption, Dec is the decryption. Tasks performed by one user or tasks performed by all users in sequence.This relationship is not fixed. It varies with fraction length and random numbers and operands. For example, the exp in our system executes operations much faster than pow. The reason is that users use small numbers (plaintexts) for exp computation, but SP uses very large integers (ciphertexts, random numbers) for pow operation. In addition, because the pow operations in stage B use a lot of random numbers, only changing the range of random numbers will have a great impact on the running time.


### 5.3.2. The Effect of Different Numbers of Records on the Execution Time

The number of input data pointsm has a great impact on the execution time, because all participators need to deal with m×m matrix. The problem is which stage is the bottleneck of performance.Experiment 4 investigates the effect of differentm on the execution time. The data used in this experiment are taken from the dataset Breast Cancer Wisconsin. We choose m= 40, 55, 70, 85, and 100 records for training and 1 record for prediction. Moreover, we split the data between r=2 users to reduce the impact of the number of users. We set the fraction length to q=32 and the range of random numbers to 1,232. The results are shown in Figure 7. Note that the execution time of stage A is the average execution time of all users.Figure 7
The execution time of each stage for different numbers of data points (experiment 4).It is easy to notice that stages C of all methods are the same. Therefore, the graphs of stages C of all methods in Figure7 are also the same. They can be regarded as a benchmark for comparison.Figure7 shows that the Poly-SVM and RBF-SVM(A) spend most of the time on stage B, and the execution time of stage B grows much faster than that of stage C with the increase of m. On the other hand, for the Linear-SVM or RBF-SVM(B), there is no huge difference between the execution time of stage B and that of stage C. This is because Poly-SVM and RBF-SVM(A) call protocol EncMul many times in stage B, while the other methods do not call it.Among all methods, we find that when the number of data points is the same, the maximum execution time of stage A or D does not exceed 200% of the minimum execution time of the same stage. This is not a significant difference.Comparing the efficiency of all methods under the same conditions, we have RBF-SVM(B)≈Linear-SVM≫Poly-SVM≈RBF-SVM(A). Calling EncMul takes up most of the execution time.


### 5.3.3. The Effect of Different Numbers of Users on the Execution Time

Experiment 5 studies the effect of different numbers of usersr on the execution time. We use the same dataset and parameter settings as experiment 3 in this experiment. The results are shown in Figure 8. For each stage, we analyze the change of execution time as follows.Figure 8
The execution time of each stage for different numbers of users (experiment 5).(1) Stage A. Figure 8 shows that the execution time of stage A changes very little for all methods. The reasons are as follows.For any of Linear-SVM, Poly-SVM, or RBF-SVM(A), all users execute the protocol independently of each other. It is reasonable to assume that all users execute the protocol at this stage in parallel. For these methods, we take the average execution time of all users as the execution time of stage A, which is almost fixed with changingr.In the method RBF-SVM(B), all users in turn merge local data into a matrix (computingTij=TijΔkij by each user, userk). Although this step is related to r, it takes up only a small fraction of the execution time. The encryption operations performed by the last user take up most of the execution time of stage A.In sum, the execution time of stage A for all methods is hardly affected by the number of users.(2) Stage B. In stage B, Linear-SVM and Poly-SVM will perform multiplication r times for generating each entry of EΩ. For both of these two methods, this is the only step in stage B related to r. However, the time consumed by this step is far less than that consumed by other steps. For Linear-SVM, the pow operations are the most time-consuming steps and are independent of r. For Poly-SVM, the execution of EncMul takes up most of the execution time and has nothing to do with r. In addition, the computation of RBF-SVM(B) in stage B is completely independent of r. Hence, for Linear-SVM, Poly-SVM, and RBF-SVM(B), the execution time of stage B remains almost unchanged, as shown in Figure 8.Although both Poly-SVM and RBF-SVM(A) callEncMul in stage B, Poly-SVM with a kernel axi,xj+cp performs EncMulp times for each entry of EΩ, while RBF-SVM(A) performs EncMulr−1 times to do the same thing. Fortunately, the degree p is often a small integer. This reduces the negative impact of EncMul on Poly-SVM. However, for RBF-SVM(A), the situation is quite different. As shown in Figure 8, its execution time of stage B increases sharply with the increase of r. This disadvantage will affect the application of this method to a certain extent. For this reason, we design RBF-SVM(B) as an alternative.(3) Stage C. The tasks of all our methods at this stage are the same and independent of r. Figure 8 shows that the execution time of stage C is almost equal and fixed for all methods.(4) Stage D. In stage D, all methods need to compute the kernel function, which is the only step that may be related to the number of users. This step is similar to some computation procedures in stages A and B. The difference is that each method only needs to compute m values in stage D, but m2 values in stages A and B.Only the execution time of RBF-SVM(A) will be significantly affected because it will call EncMulEncMulr−1 times when computing each kernel function. This explains why, in Figure 8, the execution time of stage D of Linear-SVM, Poly-SVM, and RBF-SVM(B) changes very little with the increase of r, while the execution time of stage D of RBF-SVM(A) increases steadily.


## 5.3.1. The Complexity of Our Algorithm at Different Stages

Except arithmetic operations (add, mul, div), we also take random number generation (rnd),ex (exp), modular exponentiation (pow), encryption (Enc), decryption (Dec), and EncMul as basic operations.Table3 shows the complexity of each method at different stages. The time spent on different operations varies greatly. When we set the fraction length q=32 and limit the range of random numbers to 1,232, the execution time of these operations has the following relationship:(53)1EncMul≈4.5Dec≈9Enc≈180pow≈1800mul≈18000exp≈18000add≈105rnd.Table 3
The complexity of our algorithm at different stages.
MethodsLinear-SVMPoly-SVMRBF-SVM(A)RBF-SVM(B)Stage A (each user)mul:Onm2add: Onm2Enc: m2mul:Onm2add: Onm2Enc: m2mul:Onm2add: Onm2exp: m2 Enc: m2mul:Onm2add: Onm2exp: m2rnd: m2mul: rm2Enc: m2Stage B (SP1, SP2)mul:m+12m+rm2add: m+12mrnd: m+12pow: m+13mul:m+12m+rm2add: m+12mrnd: m+12pow: m+13EncMul:pm2mul:m+12madd: m+12mrnd: m+12pow: m+13EncMul:r−1m2mul:m+12madd: m+12mrnd: m+12pow: m+13+m2Stage C (SP1, SP2)mul:Om3, div: Om3, add: Om3 Dec: m2Stage D (each user)mul:Onmadd: OnmEnc: mmul:Onmadd: OnmEnc: mmul:Onmadd: Onmexp: mEnc: mmul:Onmadd: Onmexp: mrnd: mmul: rmEnc: mStage D (SP1, SP2userA)mul:Ormadd: OmEnc: mDec: mrnd: 2mpow: mmul:Ormadd: OmEnc: mDec: mrnd: 2mpow: mEncMul:pmmul:Omadd: OmEnc: mDec: mrnd: 2mpow: mEncMul:r−1mmul:Omadd: OmEnc: mDec: mrnd: 2mpow: mNote.n is the number of features, m is the number of data points (records), r is the number of users, exp is the ex, rnd is the random integer generation, pow is the modular exponentiation, Enc is the encryption, Dec is the decryption. Tasks performed by one user or tasks performed by all users in sequence.This relationship is not fixed. It varies with fraction length and random numbers and operands. For example, the exp in our system executes operations much faster than pow. The reason is that users use small numbers (plaintexts) for exp computation, but SP uses very large integers (ciphertexts, random numbers) for pow operation. In addition, because the pow operations in stage B use a lot of random numbers, only changing the range of random numbers will have a great impact on the running time.


## 5.3.2. The Effect of Different Numbers of Records on the Execution Time

The number of input data pointsm has a great impact on the execution time, because all participators need to deal with m×m matrix. The problem is which stage is the bottleneck of performance.Experiment 4 investigates the effect of differentm on the execution time. The data used in this experiment are taken from the dataset Breast Cancer Wisconsin. We choose m= 40, 55, 70, 85, and 100 records for training and 1 record for prediction. Moreover, we split the data between r=2 users to reduce the impact of the number of users. We set the fraction length to q=32 and the range of random numbers to 1,232. The results are shown in Figure 7. Note that the execution time of stage A is the average execution time of all users.Figure 7
The execution time of each stage for different numbers of data points (experiment 4).It is easy to notice that stages C of all methods are the same. Therefore, the graphs of stages C of all methods in Figure7 are also the same. They can be regarded as a benchmark for comparison.Figure7 shows that the Poly-SVM and RBF-SVM(A) spend most of the time on stage B, and the execution time of stage B grows much faster than that of stage C with the increase of m. On the other hand, for the Linear-SVM or RBF-SVM(B), there is no huge difference between the execution time of stage B and that of stage C. This is because Poly-SVM and RBF-SVM(A) call protocol EncMul many times in stage B, while the other methods do not call it.Among all methods, we find that when the number of data points is the same, the maximum execution time of stage A or D does not exceed 200% of the minimum execution time of the same stage. This is not a significant difference.Comparing the efficiency of all methods under the same conditions, we have RBF-SVM(B)≈Linear-SVM≫Poly-SVM≈RBF-SVM(A). Calling EncMul takes up most of the execution time.


## 5.3.3. The Effect of Different Numbers of Users on the Execution Time

Experiment 5 studies the effect of different numbers of usersr on the execution time. We use the same dataset and parameter settings as experiment 3 in this experiment. The results are shown in Figure 8. For each stage, we analyze the change of execution time as follows.Figure 8
The execution time of each stage for different numbers of users (experiment 5).(1) Stage A. Figure 8 shows that the execution time of stage A changes very little for all methods. The reasons are as follows.For any of Linear-SVM, Poly-SVM, or RBF-SVM(A), all users execute the protocol independently of each other. It is reasonable to assume that all users execute the protocol at this stage in parallel. For these methods, we take the average execution time of all users as the execution time of stage A, which is almost fixed with changingr.In the method RBF-SVM(B), all users in turn merge local data into a matrix (computingTij=TijΔkij by each user, userk). Although this step is related to r, it takes up only a small fraction of the execution time. The encryption operations performed by the last user take up most of the execution time of stage A.In sum, the execution time of stage A for all methods is hardly affected by the number of users.(2) Stage B. In stage B, Linear-SVM and Poly-SVM will perform multiplication r times for generating each entry of EΩ. For both of these two methods, this is the only step in stage B related to r. However, the time consumed by this step is far less than that consumed by other steps. For Linear-SVM, the pow operations are the most time-consuming steps and are independent of r. For Poly-SVM, the execution of EncMul takes up most of the execution time and has nothing to do with r. In addition, the computation of RBF-SVM(B) in stage B is completely independent of r. Hence, for Linear-SVM, Poly-SVM, and RBF-SVM(B), the execution time of stage B remains almost unchanged, as shown in Figure 8.Although both Poly-SVM and RBF-SVM(A) callEncMul in stage B, Poly-SVM with a kernel axi,xj+cp performs EncMulp times for each entry of EΩ, while RBF-SVM(A) performs EncMulr−1 times to do the same thing. Fortunately, the degree p is often a small integer. This reduces the negative impact of EncMul on Poly-SVM. However, for RBF-SVM(A), the situation is quite different. As shown in Figure 8, its execution time of stage B increases sharply with the increase of r. This disadvantage will affect the application of this method to a certain extent. For this reason, we design RBF-SVM(B) as an alternative.(3) Stage C. The tasks of all our methods at this stage are the same and independent of r. Figure 8 shows that the execution time of stage C is almost equal and fixed for all methods.(4) Stage D. In stage D, all methods need to compute the kernel function, which is the only step that may be related to the number of users. This step is similar to some computation procedures in stages A and B. The difference is that each method only needs to compute m values in stage D, but m2 values in stages A and B.Only the execution time of RBF-SVM(A) will be significantly affected because it will call EncMulEncMulr−1 times when computing each kernel function. This explains why, in Figure 8, the execution time of stage D of Linear-SVM, Poly-SVM, and RBF-SVM(B) changes very little with the increase of r, while the execution time of stage D of RBF-SVM(A) increases steadily.


## 5.4. Comparison with Another PP-SVM Algorithm

Park et al. [7] propose a PP-SVM training algorithm based on LS-SVM and they use CKKS [27] encryption to encrypt the input data. In this paper, we use the notation ⋅ to denote CKKS encryption algorithm. Their algorithm can be used in one client and one server environment. The client provides the encrypted matrix Q to the server, which uses gradient descent method to solve the equation QTQβ=QTe.


### 5.4.1. The Modified Version of Park’s Training Method

We modify Park et al. method asProtocol 7 (MP’s method) to deal with the same problem as ours, and then we compare this modified method with our algorithm. We do not put the counterpart of RBF-SVM(B) in Protocol 7, because its performance is equivalent to that of Linear-SVM.Protocol 7.
(MP’s method): The modified version of Park’s training method.Input: each userk inputs xik, and yi is shared by all users, where 1≤i≤m, 1≤k≤r. The public key is shared by all participators, and userc has the private key.Output: Server obtains β.(1)
Users perform computation with local data.(a)
Linear kernel:Eachuserk computes yixik,yjxjk, and user1 also computes all yi. All these data are sent to server.(b)
Poly kernel:Eachuserk computes axik,xjk, and user1 also computes all yi and c. All these data are sent to server.(c)
RBF kernel (A):Eachuserk computes Δkij, and user1 also computes yi. Then, all these data are sent to server.(2)
Server computesQ.(a)
Linear kernel:Server computesΩij=∑k=1ryixik,yjxjk.(b)
Poly kernel:Server computesT1=∑k=1raxik,xjk+c=∑k=1raxik,xjk+c. Then, let T2=T1; server repeatedly computes T2=T2T1p−1 times and then computes Ωij=yiyjT2.(c)
RBF kernel (A):Server computesΩij=∏k=1rΔkijyiyj.Then, server computesΩii+γ−1=Ωii+γ−1. So far, sever has obtained all entries of Q.(3)
Server computesβ by gradient descent method.(a)
Server first computesQTQ and QTe with Q.(b)
Server chooses an initial vectorβ1 and then repeatedly computes βk as follows:(54)pk=QTQβk−QTeβk+1=βk−skpk,wherek=1,2,…,N and sk is learning rate.The server sent allβk to userc who decrypts them and determine if the iteration should be stopped.
Clearly, this modified Park’s method solves a problem just like ours. In this protocol, step 3 is the same as Park et al. method. Step 1 and step 2 adopt the ideas of this article. Of course, MP’s method uses CKKS encryption to compute both addition and multiplication between ciphers.
In this section, we compare MP’s method with ours. For a fair comparison, we do not use any packing technique in all the following experiments. Moreover, because the time spent on the client and prediction phase is far less than the training time spent on the server, we only focus on the execution time of training.
The server-side computation in the training phase includes computingEQ, computing EQTQ with EQ, and performing the gradient descent method. Obviously, the latter two computation processes are only related to the number of data points.


### 5.4.2. Comparison of Server-Side Training Time between the Two Methods with Different Numbers of Users

In experiment 6, we choose 40 records from Sonar to be the training dataset. The data are vertically partitioned betweenr=5,10,20,40 users. The experimental results are shown in Table 4.Table 4
(Experiment 6) comparison of server-side training time between the two methods with different numbers of users (sec.).
Number of usersrLinear kernelPoly kernelRBF kernel (A)MP’sOursMP’sOursMP’sOurs5426.146.6425.5192.4463.5550.610435.847.8445.2191.5496.31169.720445.546.8430.9192.5562.12398.140429.147.9445.1192.3693.64865.2For the cases of linear and polynomial kernel, Table4 shows that our methods are more efficient. Although it takes longer to run the MP’s method, the training time of it with linear or polynomial kernel keeps almost unchanged with the increase of r. We believe the reason is as follows. When the number of records m is fixed, the MP’s method takes a fixed time to compute EQTQ and perform the gradient descent method. Meanwhile, although the time required to compute EQ is related to r, the MP’s Linear-kernel and Poly-kernel methods mainly perform efficient CKKS addition when computing EQ. The time they spent in computing EQ is far less than that spent in computing EQTQ and performing the gradient descent method. Therefore, we see in Table 4 that the server-side training time of MP’s method with Linear-kernel and Poly-kernel changes little with the increase of r. For RBF kernel, Table 4 shows that the training time of the two methods increases with the increase of r. The MP’s RBF kernel method mainly executes CKKS multiplication for computing EQ. The CKKS multiplication is a time-consuming operation, but it is still much more efficient than protocol EncMul. We know that our RBF-SVM(A) method spends most of its time executing EncMul, this makes MP’s method have better performance than RBF-SVM(A), as shown in Table 4.


### 5.4.3. Comparison of Server-Side Training Time between the Two Methods with Different Numbers of Data Points

In experiment 7, we choosem=40, 60, 80, 100 records from Sonar to be training dataset and vertically partition the training data between r=2 users.Table5 shows the impact of m on server-side training time. For any type of kernel, the training time of both methods increases with the increase of m. However, the training time of MP’s method not only far exceeds ours, but also grows faster. Table 6 shows the two methods’ complexity of training phase. Meanwhile, in our experiment, the time consumed by the operations in Table 6 has the following relationship:(55)1EncMul≈4.5Dec≈10CKKS mul≈180pow.Table 5
(Experiment 7) comparison of server-side training time between the two methods with different numbers of data points (sec.).
Num. of data pointsmLinear kernelPoly kernelRBF kernel (A)MP’sOursMP’sOursMP’sOurs404304744719243917155106397108036910713317019201751951610193254985330027833309233332832Table 6
Two methods’ complexity of training phase.
MP’s methodOursLinear kernelPoly kernelRBF kernelOm3 mulOm3 powOm2 DecOm3 powOm2 EncMulOm2 DecOm3 powOm2 EncMulOm2 DecCKKS multiplication.The data in Table5 illustrates that Om3 CKKS multiplication grows faster than Om3pow+Om2EncMul+Om2Dec with the increase of m.For MP’s method, computingEQTQ and performing the gradient descent method take up most of the training time, as shown in Table 7. Actually, the computation of EQTQ is the preparation for the gradient descent method. Tables 5 and 7 illustrate that the gradient descent method is not a very efficient method in solving the equation.Table 7
(Experiment 7) the training time of MP’s method and the time consumed by two main steps of MP’s method (sec.).
Num. of data pointsmMP’s methodComputingEQTQGradient descentLinearPolyRBF4043044743928214055106310801071751258701920195119321458430853300333033322632625Note.TMP′s training=TEQ+TEQTQ+TGD method.Another uncertainty of the gradient descent method is how many times the iteration should be conducted before obtaining enough accurate result. The number of iterations has a significant impact on the training time. Park et al. performed the iteration 10 times in their experiments. It seems all right for their experiments, but there is no theoretical basis for doing this.The above comparisons show that each of the two methods has advantages and disadvantages. This leads to a simple idea of using CKKS encryption in our algorithm instead of Paillier encryption. This will combine the advantages of the two methods and seems more efficient. This idea is attractive, but it is not the focus of this paper. We left it as future work.


## 5.4.1. The Modified Version of Park’s Training Method

We modify Park et al. method asProtocol 7 (MP’s method) to deal with the same problem as ours, and then we compare this modified method with our algorithm. We do not put the counterpart of RBF-SVM(B) in Protocol 7, because its performance is equivalent to that of Linear-SVM.Protocol 7.
(MP’s method): The modified version of Park’s training method.Input: each userk inputs xik, and yi is shared by all users, where 1≤i≤m, 1≤k≤r. The public key is shared by all participators, and userc has the private key.Output: Server obtains β.(1)
Users perform computation with local data.(a)
Linear kernel:Eachuserk computes yixik,yjxjk, and user1 also computes all yi. All these data are sent to server.(b)
Poly kernel:Eachuserk computes axik,xjk, and user1 also computes all yi and c. All these data are sent to server.(c)
RBF kernel (A):Eachuserk computes Δkij, and user1 also computes yi. Then, all these data are sent to server.(2)
Server computesQ.(a)
Linear kernel:Server computesΩij=∑k=1ryixik,yjxjk.(b)
Poly kernel:Server computesT1=∑k=1raxik,xjk+c=∑k=1raxik,xjk+c. Then, let T2=T1; server repeatedly computes T2=T2T1p−1 times and then computes Ωij=yiyjT2.(c)
RBF kernel (A):Server computesΩij=∏k=1rΔkijyiyj.Then, server computesΩii+γ−1=Ωii+γ−1. So far, sever has obtained all entries of Q.(3)
Server computesβ by gradient descent method.(a)
Server first computesQTQ and QTe with Q.(b)
Server chooses an initial vectorβ1 and then repeatedly computes βk as follows:(54)pk=QTQβk−QTeβk+1=βk−skpk,wherek=1,2,…,N and sk is learning rate.The server sent allβk to userc who decrypts them and determine if the iteration should be stopped.
Clearly, this modified Park’s method solves a problem just like ours. In this protocol, step 3 is the same as Park et al. method. Step 1 and step 2 adopt the ideas of this article. Of course, MP’s method uses CKKS encryption to compute both addition and multiplication between ciphers.
In this section, we compare MP’s method with ours. For a fair comparison, we do not use any packing technique in all the following experiments. Moreover, because the time spent on the client and prediction phase is far less than the training time spent on the server, we only focus on the execution time of training.
The server-side computation in the training phase includes computingEQ, computing EQTQ with EQ, and performing the gradient descent method. Obviously, the latter two computation processes are only related to the number of data points.


## 5.4.2. Comparison of Server-Side Training Time between the Two Methods with Different Numbers of Users

In experiment 6, we choose 40 records from Sonar to be the training dataset. The data are vertically partitioned betweenr=5,10,20,40 users. The experimental results are shown in Table 4.Table 4
(Experiment 6) comparison of server-side training time between the two methods with different numbers of users (sec.).
Number of usersrLinear kernelPoly kernelRBF kernel (A)MP’sOursMP’sOursMP’sOurs5426.146.6425.5192.4463.5550.610435.847.8445.2191.5496.31169.720445.546.8430.9192.5562.12398.140429.147.9445.1192.3693.64865.2For the cases of linear and polynomial kernel, Table4 shows that our methods are more efficient. Although it takes longer to run the MP’s method, the training time of it with linear or polynomial kernel keeps almost unchanged with the increase of r. We believe the reason is as follows. When the number of records m is fixed, the MP’s method takes a fixed time to compute EQTQ and perform the gradient descent method. Meanwhile, although the time required to compute EQ is related to r, the MP’s Linear-kernel and Poly-kernel methods mainly perform efficient CKKS addition when computing EQ. The time they spent in computing EQ is far less than that spent in computing EQTQ and performing the gradient descent method. Therefore, we see in Table 4 that the server-side training time of MP’s method with Linear-kernel and Poly-kernel changes little with the increase of r. For RBF kernel, Table 4 shows that the training time of the two methods increases with the increase of r. The MP’s RBF kernel method mainly executes CKKS multiplication for computing EQ. The CKKS multiplication is a time-consuming operation, but it is still much more efficient than protocol EncMul. We know that our RBF-SVM(A) method spends most of its time executing EncMul, this makes MP’s method have better performance than RBF-SVM(A), as shown in Table 4.


## 5.4.3. Comparison of Server-Side Training Time between the Two Methods with Different Numbers of Data Points

In experiment 7, we choosem=40, 60, 80, 100 records from Sonar to be training dataset and vertically partition the training data between r=2 users.Table5 shows the impact of m on server-side training time. For any type of kernel, the training time of both methods increases with the increase of m. However, the training time of MP’s method not only far exceeds ours, but also grows faster. Table 6 shows the two methods’ complexity of training phase. Meanwhile, in our experiment, the time consumed by the operations in Table 6 has the following relationship:(55)1EncMul≈4.5Dec≈10CKKS mul≈180pow.Table 5
(Experiment 7) comparison of server-side training time between the two methods with different numbers of data points (sec.).
Num. of data pointsmLinear kernelPoly kernelRBF kernel (A)MP’sOursMP’sOursMP’sOurs404304744719243917155106397108036910713317019201751951610193254985330027833309233332832Table 6
Two methods’ complexity of training phase.
MP’s methodOursLinear kernelPoly kernelRBF kernelOm3 mulOm3 powOm2 DecOm3 powOm2 EncMulOm2 DecOm3 powOm2 EncMulOm2 DecCKKS multiplication.The data in Table5 illustrates that Om3 CKKS multiplication grows faster than Om3pow+Om2EncMul+Om2Dec with the increase of m.For MP’s method, computingEQTQ and performing the gradient descent method take up most of the training time, as shown in Table 7. Actually, the computation of EQTQ is the preparation for the gradient descent method. Tables 5 and 7 illustrate that the gradient descent method is not a very efficient method in solving the equation.Table 7
(Experiment 7) the training time of MP’s method and the time consumed by two main steps of MP’s method (sec.).
Num. of data pointsmMP’s methodComputingEQTQGradient descentLinearPolyRBF4043044743928214055106310801071751258701920195119321458430853300333033322632625Note.TMP′s training=TEQ+TEQTQ+TGD method.Another uncertainty of the gradient descent method is how many times the iteration should be conducted before obtaining enough accurate result. The number of iterations has a significant impact on the training time. Park et al. performed the iteration 10 times in their experiments. It seems all right for their experiments, but there is no theoretical basis for doing this.The above comparisons show that each of the two methods has advantages and disadvantages. This leads to a simple idea of using CKKS encryption in our algorithm instead of Paillier encryption. This will combine the advantages of the two methods and seems more efficient. This idea is attractive, but it is not the focus of this paper. We left it as future work.


## 6. Conclusion

In this paper, we presented a privacy-preserving SVM algorithm on vertically partitioned data. Non-colluding two-server architecture is the starting point of this work. This architecture makes it possible for us to design a PP-SVM algorithm only using additive homomorphic encryption and random transformation method. Unlike previous research, our algorithm conceals all users’ training data, the decision function, the data for prediction, and the predicted result. In short, our algorithm is encrypted in the whole process. The experiments show that our Linear-SVM, Poly-SVM, and RBF-SVM(B) are highly efficient, and our RBF-SVM(A) is still attractive for a small number of data owners. For future work, we will consider improving the efficiency of our algorithm with other encryption techniques and extending our idea to the case of horizontally partitioned data.



---

*Source: 9983463-2022-06-10.xml*