# Privacy-Preserving Outsourced Logistic Regression on Encrypted Data from Homomorphic Encryption

Authors: Xiaopeng Yu; Wei Zhao; Yunfan Huang; Juan Ren; Dianhua Tang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Logistic regression is a data statistical technique, which is used to predict the probability that an event occurs. For some scenarios where the storage capabilities and computing resources of the data owner are limited, the data owner wants to train the logistic regression model on the cloud service provider, while the high sensitivity of training data requires effective privacy protection methods that enable efficient model training without exposing information about the training data to untrusted cloud service providers. Recently, several works have used cryptographic techniques to implement privacy-preserving logistic regression in such application scenarios. However, on large-scale training datasets, the existing works still have the problems of long model training time and poor model performance. To solve these problems, based on the homomorphic encryption (HE), we propose an efficient privacy-preserving outsourced logistic regression (P2OLR) on encrypted training data, which enables data owners to utilize the powerful storage and computing resources of cloud service providers for logistic regression analysis without exposing data privacy. Furthermore, the proposed scheme can pack multiple messages into one ciphertext and perform the same arithmetic evaluations on multiple plaintext slots by using the batching technique and single instruction multiple data (SIMD) mechanism in HE. On three public training datasets, the experimental results show that, compared with the existing schemes, the proposed scheme has better performance in terms of the encryption and decryption time of the data owner, the storage of encrypted training data, and the training time and accuracy of the model.


---

## Body

## 1. Introduction

Logistic regression (LR) [1] is a popular classification method, which has been used in numerous practical applications including cancer diagnosis [2], credit scoring [3], genome-wide association study [4], and more. LR can not only be applied to the problem of predicting the probability of occurrence of various events, but also is competitive with other classification algorithms in terms of prediction accuracy. In some practical application setting, the data owners have the limited computing and storage resources, and thus wants to outsource some of the heavy computation in logistic regression model training, the outsourced data analysis [5] has received considerable attention recently, which enables data owners to train a LR model using the powerful storage capacity and computing resources of cloud service providers [6].However, the high sensitivity of training data requires to perform an effective privacy protection [7–10] that enable efficient and secure logistic regression analysis without leaking information about the training data to untrusted cloud service provider. Recently, to meet such application requirements, based on the cryptographic techniques like secure multiparty computation (MPC) [11] and homomorphic encryption (HE) [12], there have been several researches on the privacy-preserving logistic regression (PPLR) [13–22], which enables data owners to employ the service providers’ powerful data storage and computing resources for logistic regression model training without exposing its own data privacy. Specifically, the data owner encrypts its training data, and sends encrypted training data to the service provider. The service provider can train a logistic regression model on encrypted training data, and returns the encrypted training result to the data owner. The data owner can decrypt the encrypted training result to obtain final training result.Unfortunately, on large-scale training dataset, the existing PPLR schemes [13–22] still have the bottlenecks of high model training time and low model precision. To solve these problems, based on the HE cryptographic technique [23] that has the property that the operation results on ciphertexts are consistent with those on plaintexts, we design an efficient privacy-preserving outsourced logistic regression (P2OLR). The main contributions are as follows:(1)
Firstly, we propose a method for achieving P2OLR on encrypted data from HE. To speed up the model training, the proposed P2OLR scheme employs the batching technique to pack multiple elements into multiple plaintext slots, encrypts them into one ciphertext, and performs the same arithmetic operations to multiple plaintext slots in the SIMD mechanism.(2)
Secondly, we evaluate the proposed P2OLR on three public datasets [18]. Under the same experimental environment, compared with the related P2OLR [17, 18, 22], the model training time of the proposed P2OLR is reduced by more than 71.7%, and the proposed P2OLR has a better model performance.The rest of this paper is arranged as follows. We present the related works in Section2. We review the preliminaries related to our P2OLR in Section 3. In Section 4, ourP2OLR is described. The performance evaluation for our P2OLR is presented in Section 5. The security analysis of our P2OLR is shown in Section 6. Finally, we conclude in Section 7.


## 2. Related Works

There have been a lot of works on achieving PPLR using cryptographic techniques. In this paper, we mainly focus on the PPLR based on HE. To outsource the LR model training to a cloud service provider in a privacy-preserving manner, based on the HE scheme (FV) [24], Charlotte et al. [13] proposed an algorithm to train a LR model on an homomorphically encrypted dataset, which is implemented based on the FV-NFLlib library [25]. However, the accuracy of model is poor due to the use of a quadratic polynomial to approximate the sigmoid function. Furthermore, the training time grows linearly in the number of training samples. Using the HE scheme (FV) [24] and 1 bit gradient descent (GD) method, Chen et al. [14] presented a method to train LR over encrypted data, which is implemented through the SEAL library [26], and allows an arbitrary number of iterations by using bootstrapping [27] in FV, but bootstrapping introduces a significant decrease in performance. Focusing on the prediction process of LR, based on the HE scheme (BGV) [28], Li and Sun [15] proposed a secure protocol to solve the data leakage problem during the LR prediction process, and implement their scheme by the HElib library [29]. Based on the Chimera framework [30] that allows switching between HE schemes TFHE [31] and CKKS [23], Carpov et al. [16] proposed a solution to achieve semi-parallel LR on encrypted genomic data, which performs the bootstrapping [27] without re-encrypting the genomic data for an arbitrary number of iterations, and is implemented by using TFHE library [32] and HEAAN library [33].Adapting the packing and parallelization techniques of approximate HE scheme (CKKS) [23], Kim et al. [17] proposed a PPLR, which is implemented through using the HEAAN library [33], and uses least squares approximation to improve the accuracy and efficiency of LR model training. However, as the number of iterations increases, the parameters of the CKKS scheme also need to become larger, which makes the training time increase dramatically. Kim et al. [18] applied the HE scheme (CKKS) [23] to achieve PPLR. Their scheme is implemented via using the HEAAN library [33]. Moreover, they devised an encoding method to decrease the storage of encrypted training data and adapted Nesterov’s accelerated GD method to reduce the number of iterations as well as the computational cost. However, their scheme requires the assumption that both the number of training samples and features are power-of-two, which makes the scheme unsuitable for practical applications. To reduce the number of iterations, Cheon et al. [19] proposed an ensemble GD method based on the HE scheme (CKKS) [23], and applied it to the PPLR, in which they approximate the sigmoid function using a polynomial of 5-degree obtained by least squares approximation. Their scheme is implemented based on the HEAAN library [34]. To run a genome-wide association study on encrypted data, using the SIMD capabilities of HE scheme (CKKS) and Nesterov’s accelerated GD, Bergamaschi et al. [20] introduced a method for homomorphic training of LR model, which is implemented based on the HElib library [29]. To protect the private information of both parties, based on the HE scheme (CKKS) [23] and gradient sharing technology, Wei et al. [21] proposed a protocol to train an LR model on vertically distributed data between two parties, which does not require trusted third-party nodes and is implemented by the HElib library [29]. Based on the HE scheme (CKKS) [23], Fan et al. [22] offered a PPLR algorithm, where they approximate the sigmoid function in LR by Taylor’s theorem, and use row encoding to encrypt training samples, but as the number of samples increased, this will lead to longer model training time.


## 3. Preliminaries

### 3.1. System Model

As can be seen in Figure1, the system model of the proposed P2OLR considers two entities, namely a data owner (DO) and a service provider (SP). For readability, the definitions of the notations in this paper are shown in Table 1. DO: It has limited computational resources, and wants to use SP’s data analysis service on encrypted data to train a LR model without revealing its own training data privacy. SP: It is a semi-trusted entity with powerful data storage and computing capabilities, and can provide data analysis and statistical services on encrypted data for DO. Specifically, DO chooses poly_modulus_degree N, coeff_modulus Q, and runs key_generation algorithm to generate the secret_key sk, public_key pk, relinearization_key rk, galois_key gk. Next, DO encrypts the training data D∈ℝm×n into ciphertexts D, encrypts the initial weight w00,w10,⋯,wn−10 into ciphertexts W0, encrypts the learning rate α into one ciphertext α/m, and sends N, Q, Δ, pk, rk, gk, t, D, W0, α/m to SP. SP performs the P2OLR algorithm and returns the ciphertext result Wt of the t -th iteration to DO. DO decrypts the ciphertext result Wt to obtain final result w0t,w1t,⋯,wn−1t.Figure 1
System model.Table 1
The definitions of the notations.
NotationsDefinitionsxA message vectorx0,x1,⋯,xN/2−1xThe plaintext of message vectorxxThe ciphertext of message vectorxXA listx0,x1,…,xn−1XiThei ciphertext of ciphertext list Xix∗yThe multiplication ofx and y, namely x0⋅y0,x1⋅y1,⋯,xN/2−1⋅yN/2−1x⋅yThe product ofx and y, namely x0⋅y0,x1⋅y1,⋯,xN/2−1⋅yN/2−1x+yThe addition ofx and y, namely x0+y0,x1+y1,⋯,xN/2−1+yN/2−1x−yThe subtraction ofx and y, namely x0+y0,x1+y1,⋯,xN/2−1+yN/2−1


### 3.2. Homomorphic Encryption

Homomorphic encryption (HE) is a cryptographic technique, which allows operations on ciphertexts without decryption, and guarantees that the computation results on ciphertexts are consistent with the computation results on plaintexts. We adopt the HE scheme (CKKS) [23] based on the Ring Learning with Errors (RLWE) problem, which can encrypt multiple elements in one ciphertext and supports the single instruction multiple data (SIMD) operations. Suppose ΦMX=XN+1 denotes the M -th cyclotomic polynomial, where N is power of 2. ℛ=ℤX/XN+1 denotes the cyclotomic ring of polynomials. ℛq=ℛ/qℛ=ℤqX/XN+1 denotes the residue ring of ℛ modulo q. ℍ denotes a subring of complex vector ℂN that is isomorphic to ℂN/2. σ:ℛ⟶σℛ⊆ℍ denotes a canonical embedding that transforms a plaintext polynomial ℛ into a complex vector ℍ. π:ℍ⟶ℂN/2 denotes a natural projection that transforms a complex vector ℂN to ℂN/2. HE scheme (CKKS) [23] supports the operations as follows, which can be found in the Appendix. For ease of description, we define the Algorithms 1–9.Algorithm 1:x=Encx.
Input: xOutput: x(1)
encode_double (x, Δ, x)(2)
encrypt (x, x)(3)
return: xAlgorithm 2:x0,x1,⋯,xn−1=DecX.
Input: XOutput: x0,x1,⋯,xn−1(1)
for (i=0 to n−1) do(2)
decrypt (Xi, xi)(3)
decode_double (xi, xi)(4)
xi=xi.get0(5)
end for(6)
return: x0,x1,…,xn−1Algorithm 3:x∗y=Mulx,y.
Input: x,yOutput: x∗y(1)
mod_switch_to_inplace (y, x.parms_id())(2)
multiply (x, y, x∗y)(3)
relinearize_inplace (x∗y, rk)(4)
rescale_to_next_inplace (x∗y)(5)
x∗y.set_scale (Δ)(6)
return: x∗yAlgorithm 4:x∗y=Mul_Plainx,y.
Input: x,yOutput: x∗y(1)
encode_double (y, Δ, y)(2)
mod_switch_to_inplace (y, x.parms_id())(3)
multiply_plain (x, y, x∗y)(4)
rescale_to_next_inplace (x∗y)(5)
x∗y.set_scale (Δ)(6)
return: x∗yAlgorithm 5:x+y=Addx,y.
Input: x,yOutput: x+y(1)
mod_switch_to_inplace (y, x.parms_id())(2)
add (x, y, x+y)(3)
return: x+yAlgorithm 6:x+y=Add_Plainx,y.
Input: x,yOutput: x+y(1)
encode_double (y, Δ, y)(2)
mod_switch_to_inplace (y, x.parms_id())(3)
add_plain (x, y, x+y)(4)
return: x+yAlgorithm 7:x−y=Subx,y.
Input: x,yOutput: x−y(1)
mod_switch_to_inplace (y, x.parms_id())(2)
sub (x, y, x−y)(3)
return: x−yAlgorithm 8:x=Add_Inplacex,y.
Input: x,yOutput: x(1)
mod_switch_to_inplace (x, y.parms_id())(2)
add_inplace (x, y)(3)
return: xAlgorithm 9:y=Rotate_Sumx.
Input: x=x0,x1,⋯,xN/2−1Output: y=∑i=0N/2−1xi,∑i=0N/2−1xi,⋯,∑i=0N/2−1xi(1)
y=x(2)
for (k=N/2; k≥1; k=k/2) do(3)
rotate_vector (y, k, gk, z)(4)
add_inplace (y, z)(5)
end for(6)
return: y


### 3.3. Sigmoid Approximation

Since the existing HE scheme can only effectively support polynomial arithmetic computations, the computation of sigmoid functionσx=1/1+e−x using HE is a barrier to the realization of P2OLR. To find a approximate polynomial of σx, adapting the least squares method, we consider the 7° polynomial gx=a0+a1x+a3x3+a5x5+a7x7 over the domain −8,8, where a0=1/2, a1=1.73496/8, a3=4.19407/83, a5=5.43402/85, a7=2.50739/87. σx and gx can be seen in Figure 2, the maximum errors between σx and gx are about 0.032. gx over encrypted data x from HE can be achieved by the Algorithm 10.Figure 2
Sigmoid approximation.Algorithm 10:gx=Sigmoid_Approximationx.
Input: xOutput: gx(1)
x∗x=Mulx,x(2)
x∗x∗x∗x=Mulx∗x,x∗x(3)
x∗x∗x∗x∗x∗x=Mulx∗x∗x∗x,x∗x(4)
a7∗x=Mul_Plainx,a7(5)
a7∗x∗x∗x∗x∗x∗x∗x=Mulx∗x∗x∗x∗x∗x,a7∗x(6)
a5∗x=Mul_Plainx,a5(7)
a5∗x∗x∗x∗x∗x=Mulx∗x∗x∗x,a5∗x(8)
a3∗x=Mul_Plainx,a3(9)
a3∗x∗x∗x=Mulx∗x,a3∗x(10)
a1∗x=Mul_Plainx,a1(11)
a0+a1∗x=Add_Plaina1∗x,a0(12)
a0+a1∗x−a3∗x∗x∗x=Suba3∗x∗x∗x,a0+a1∗x(13)
a0+a1∗x−a3∗x∗x∗x+a5∗x∗x∗x∗x∗x=Adda5∗x∗x∗x∗x∗x,a0+a1∗x−a3∗x∗x∗x(14)
a0+a1∗x−a3∗x∗x∗x+a5∗x∗x∗x∗x∗x−a7∗x∗x∗x∗x∗x∗x∗x=Suba7∗x∗x∗x∗x∗x∗x∗x,a0+a1∗x−a3∗x∗x∗x+a5∗x∗x∗x∗x∗x(15)
return: gx=a0+a1∗x−a3∗x∗x∗x+a5∗x∗x∗x∗x∗x−a7∗x∗x∗x∗x∗x∗x∗x.


### 3.4. Logistic Regression

Logistic regression (LR) is a statistical analysis method for predicting the probability of an event. We consider the case where the predicted value is a binary dependent variable. Assuming that a dataset consists ofm samples of the form yi,xi with yi∈0,1 and xi=xi,1,xi,2,⋯,xi,N/2−1∈ℝn−1, the goal of LR is to find the optimal parameters w=w0,w1,⋯,wn−1 that minimizes the negative log-likelihood function (loss function) Jw=1/m⋅∑i=0m−1yi⋅logσdi⋅wT+1−yi⋅1−logσdi⋅wT, where di=1,xi. A common method for minimizing loss function Jw is a gradient descent (GD) algorithm, which finds the local extremum of a loss function by following the direction of the gradient. The gradient of Jw with respect to w is calculated by ∇Jw=1/m⋅∑i=0m−1σ−di⋅wT−yi⋅di. Let wk be the regression parameters and αk is a learning rate in the k-th iteration of the GD algorithm, the GD algorithm can update wk+1 by wk+1←wk−αk/m⋅∑i=0m−1σdi⋅wT−yi⋅di.


## 3.1. System Model

As can be seen in Figure1, the system model of the proposed P2OLR considers two entities, namely a data owner (DO) and a service provider (SP). For readability, the definitions of the notations in this paper are shown in Table 1. DO: It has limited computational resources, and wants to use SP’s data analysis service on encrypted data to train a LR model without revealing its own training data privacy. SP: It is a semi-trusted entity with powerful data storage and computing capabilities, and can provide data analysis and statistical services on encrypted data for DO. Specifically, DO chooses poly_modulus_degree N, coeff_modulus Q, and runs key_generation algorithm to generate the secret_key sk, public_key pk, relinearization_key rk, galois_key gk. Next, DO encrypts the training data D∈ℝm×n into ciphertexts D, encrypts the initial weight w00,w10,⋯,wn−10 into ciphertexts W0, encrypts the learning rate α into one ciphertext α/m, and sends N, Q, Δ, pk, rk, gk, t, D, W0, α/m to SP. SP performs the P2OLR algorithm and returns the ciphertext result Wt of the t -th iteration to DO. DO decrypts the ciphertext result Wt to obtain final result w0t,w1t,⋯,wn−1t.Figure 1
System model.Table 1
The definitions of the notations.
NotationsDefinitionsxA message vectorx0,x1,⋯,xN/2−1xThe plaintext of message vectorxxThe ciphertext of message vectorxXA listx0,x1,…,xn−1XiThei ciphertext of ciphertext list Xix∗yThe multiplication ofx and y, namely x0⋅y0,x1⋅y1,⋯,xN/2−1⋅yN/2−1x⋅yThe product ofx and y, namely x0⋅y0,x1⋅y1,⋯,xN/2−1⋅yN/2−1x+yThe addition ofx and y, namely x0+y0,x1+y1,⋯,xN/2−1+yN/2−1x−yThe subtraction ofx and y, namely x0+y0,x1+y1,⋯,xN/2−1+yN/2−1


## 3.2. Homomorphic Encryption

Homomorphic encryption (HE) is a cryptographic technique, which allows operations on ciphertexts without decryption, and guarantees that the computation results on ciphertexts are consistent with the computation results on plaintexts. We adopt the HE scheme (CKKS) [23] based on the Ring Learning with Errors (RLWE) problem, which can encrypt multiple elements in one ciphertext and supports the single instruction multiple data (SIMD) operations. Suppose ΦMX=XN+1 denotes the M -th cyclotomic polynomial, where N is power of 2. ℛ=ℤX/XN+1 denotes the cyclotomic ring of polynomials. ℛq=ℛ/qℛ=ℤqX/XN+1 denotes the residue ring of ℛ modulo q. ℍ denotes a subring of complex vector ℂN that is isomorphic to ℂN/2. σ:ℛ⟶σℛ⊆ℍ denotes a canonical embedding that transforms a plaintext polynomial ℛ into a complex vector ℍ. π:ℍ⟶ℂN/2 denotes a natural projection that transforms a complex vector ℂN to ℂN/2. HE scheme (CKKS) [23] supports the operations as follows, which can be found in the Appendix. For ease of description, we define the Algorithms 1–9.Algorithm 1:x=Encx.
Input: xOutput: x(1)
encode_double (x, Δ, x)(2)
encrypt (x, x)(3)
return: xAlgorithm 2:x0,x1,⋯,xn−1=DecX.
Input: XOutput: x0,x1,⋯,xn−1(1)
for (i=0 to n−1) do(2)
decrypt (Xi, xi)(3)
decode_double (xi, xi)(4)
xi=xi.get0(5)
end for(6)
return: x0,x1,…,xn−1Algorithm 3:x∗y=Mulx,y.
Input: x,yOutput: x∗y(1)
mod_switch_to_inplace (y, x.parms_id())(2)
multiply (x, y, x∗y)(3)
relinearize_inplace (x∗y, rk)(4)
rescale_to_next_inplace (x∗y)(5)
x∗y.set_scale (Δ)(6)
return: x∗yAlgorithm 4:x∗y=Mul_Plainx,y.
Input: x,yOutput: x∗y(1)
encode_double (y, Δ, y)(2)
mod_switch_to_inplace (y, x.parms_id())(3)
multiply_plain (x, y, x∗y)(4)
rescale_to_next_inplace (x∗y)(5)
x∗y.set_scale (Δ)(6)
return: x∗yAlgorithm 5:x+y=Addx,y.
Input: x,yOutput: x+y(1)
mod_switch_to_inplace (y, x.parms_id())(2)
add (x, y, x+y)(3)
return: x+yAlgorithm 6:x+y=Add_Plainx,y.
Input: x,yOutput: x+y(1)
encode_double (y, Δ, y)(2)
mod_switch_to_inplace (y, x.parms_id())(3)
add_plain (x, y, x+y)(4)
return: x+yAlgorithm 7:x−y=Subx,y.
Input: x,yOutput: x−y(1)
mod_switch_to_inplace (y, x.parms_id())(2)
sub (x, y, x−y)(3)
return: x−yAlgorithm 8:x=Add_Inplacex,y.
Input: x,yOutput: x(1)
mod_switch_to_inplace (x, y.parms_id())(2)
add_inplace (x, y)(3)
return: xAlgorithm 9:y=Rotate_Sumx.
Input: x=x0,x1,⋯,xN/2−1Output: y=∑i=0N/2−1xi,∑i=0N/2−1xi,⋯,∑i=0N/2−1xi(1)
y=x(2)
for (k=N/2; k≥1; k=k/2) do(3)
rotate_vector (y, k, gk, z)(4)
add_inplace (y, z)(5)
end for(6)
return: y


## 3.3. Sigmoid Approximation

Since the existing HE scheme can only effectively support polynomial arithmetic computations, the computation of sigmoid functionσx=1/1+e−x using HE is a barrier to the realization of P2OLR. To find a approximate polynomial of σx, adapting the least squares method, we consider the 7° polynomial gx=a0+a1x+a3x3+a5x5+a7x7 over the domain −8,8, where a0=1/2, a1=1.73496/8, a3=4.19407/83, a5=5.43402/85, a7=2.50739/87. σx and gx can be seen in Figure 2, the maximum errors between σx and gx are about 0.032. gx over encrypted data x from HE can be achieved by the Algorithm 10.Figure 2
Sigmoid approximation.Algorithm 10:gx=Sigmoid_Approximationx.
Input: xOutput: gx(1)
x∗x=Mulx,x(2)
x∗x∗x∗x=Mulx∗x,x∗x(3)
x∗x∗x∗x∗x∗x=Mulx∗x∗x∗x,x∗x(4)
a7∗x=Mul_Plainx,a7(5)
a7∗x∗x∗x∗x∗x∗x∗x=Mulx∗x∗x∗x∗x∗x,a7∗x(6)
a5∗x=Mul_Plainx,a5(7)
a5∗x∗x∗x∗x∗x=Mulx∗x∗x∗x,a5∗x(8)
a3∗x=Mul_Plainx,a3(9)
a3∗x∗x∗x=Mulx∗x,a3∗x(10)
a1∗x=Mul_Plainx,a1(11)
a0+a1∗x=Add_Plaina1∗x,a0(12)
a0+a1∗x−a3∗x∗x∗x=Suba3∗x∗x∗x,a0+a1∗x(13)
a0+a1∗x−a3∗x∗x∗x+a5∗x∗x∗x∗x∗x=Adda5∗x∗x∗x∗x∗x,a0+a1∗x−a3∗x∗x∗x(14)
a0+a1∗x−a3∗x∗x∗x+a5∗x∗x∗x∗x∗x−a7∗x∗x∗x∗x∗x∗x∗x=Suba7∗x∗x∗x∗x∗x∗x∗x,a0+a1∗x−a3∗x∗x∗x+a5∗x∗x∗x∗x∗x(15)
return: gx=a0+a1∗x−a3∗x∗x∗x+a5∗x∗x∗x∗x∗x−a7∗x∗x∗x∗x∗x∗x∗x.


## 3.4. Logistic Regression

Logistic regression (LR) is a statistical analysis method for predicting the probability of an event. We consider the case where the predicted value is a binary dependent variable. Assuming that a dataset consists ofm samples of the form yi,xi with yi∈0,1 and xi=xi,1,xi,2,⋯,xi,N/2−1∈ℝn−1, the goal of LR is to find the optimal parameters w=w0,w1,⋯,wn−1 that minimizes the negative log-likelihood function (loss function) Jw=1/m⋅∑i=0m−1yi⋅logσdi⋅wT+1−yi⋅1−logσdi⋅wT, where di=1,xi. A common method for minimizing loss function Jw is a gradient descent (GD) algorithm, which finds the local extremum of a loss function by following the direction of the gradient. The gradient of Jw with respect to w is calculated by ∇Jw=1/m⋅∑i=0m−1σ−di⋅wT−yi⋅di. Let wk be the regression parameters and αk is a learning rate in the k-th iteration of the GD algorithm, the GD algorithm can update wk+1 by wk+1←wk−αk/m⋅∑i=0m−1σdi⋅wT−yi⋅di.


## 4. Privacy-Preserving Outsourced Logistic Regression

Based on the HE scheme, we propose a P2OLR, where we employ the batching method to pack multiple elements into multiple plaintext slots, and encrypt them into one ciphertext, and then perform the same arithmetic evaluations to multiple plaintext slots through the SIMD mechanism. To reduce the parameters of HE scheme (CKKS) as well as improve the performance of P2OLR, the proposed P2OLR allows the interaction between DO and SP during iterative training. Specifically, SP returns the ciphertext training result to DO after certain number of iterations t. DO decrypts the ciphertext training result, and determines whether the performance of the model has met the requirements. If so, stops training. Otherwise, sends encrypted weights to SP to continue training. Let(1)D=y0y1⋮ym−1x0,1x1,1⋮xm−1,1x0,2x1,2⋮xm−1,2⋯⋯⋱⋯x0,n−1x1,n−1⋮xm−1,n−1.denote the training data sets held by DO, where D consists of m samples of the form yi,xi,1,xi,2,⋯,xi,N/2−1 with yi∈0,1 and xi,1,xi,2,⋯,xi,N/2−1∈ℝn−1. The first column of D denotes the label, other columns D denote the features. Since DO has limited computational resources, DO wants to outsource to SP to train a LR model without disclosing its own training data privacy. The specific description of the proposed P2OLR is as follows.(1)
DO generatessk,pk,rk,gk, computes l=2m/N, calls the Algorithm 1 to encrypt the training data D into l×n ciphertexts(2)y0T=Ency0,y1,⋯,yN/2−1,y1T=EncyN/2,yN/2+1,⋯,yN−1,yl−1T=Encym−l−1⋅N/2,ym−l−1⋅N/2+1,⋯,ym−1,x0,1T=Encx0,1,x1,1,⋯,yN/2−1,1,x0,n−1T=Encx0,n−1,x1,n−1,⋯,yN/2−1,n−1,x0,2T=Encx0,2,x1,2,⋯,yN/2−1,2,x1,1T=EncxN/2,1,xN/2+1,1,⋯,yN−1,1,x1,2T=EncxN/2,2,xN/2+1,2,⋯,yN−1,2,x1,n−1T=EncxN/2,n−1,xN/2+1+1,n−1,⋯,yN−1,n−1,xl−1,1T=Encxm−l−1⋅N/2,1,xm−l−1⋅N/2+1,1,⋯,ym−1,1,xl−1,2T=Encxm−l−1⋅N/2,2,xm−l−1⋅N/2+1,2,⋯,ym−1,2xl−1,n−1T=Encxm−l−1⋅N/2,n−1,xm−l−1⋅N/2+1,n−1,⋯,ym−1,n−1.calls the Algorithm 1 to encrypt the initial weightw00,w10,⋯,wn−10 into n ciphertexts(3)w00=Encw00,w00,⋯,w00︸N/2,w10=Encw10,w10,⋯,w10︸N/2,wN−10=Encw10,w10,⋯,w10︸N/2,calls the Algorithm 1 to encrypt the learning rateα into one ciphertext(4)αm=Encα/m,0,0,⋯,0︸N/2.and sendsy0T, y1T, ⋯, yl−1T, x0,1T, x0,2T, ⋯, x0,n−1T, x1,1T, x1,2T, ⋯, x1,n−1T, xl−1,1T, xl−1,2T, ⋯, xl−1,n−1T, w00, w10, ⋯, wn−10, α/m, N, Q, sk, pk, rk, gk, t to SP.(2)
SP computes ciphertexts(5)xi,0T=Enc1,1,⋯,1︸N/2,i=1,2,⋯,l−2,xl−1,0T=Enc1,1,⋯,1︸m−l−1⋅N/2,and sets the lists(6)Y=y0T,y1T,⋯,yl−1T,X0=x0,0T,x0,1T,x0,2T,⋯,x0,n−1T,X1=x1,0T,x1,1T,x1,2T,⋯,x1,n−1T,Xl−1=xl−1,0T,xl−1,1T,xl−1,2T,⋯,xl−1,n−1T,W0=w00,w10,⋯,wn−10.Next, SP calls the Algorithm 11, and returns the ciphertext resultWt to DO.(3)
DO calls the Algorithm 2 to decrypt the ciphertext resultWt into the result w0t,w1t,⋯,wn−1t=DecWt. Next, DO judges whether w0t,w1t,⋯,wn−1t has met the requirements. If so, terminates the training. Otherwise, DO calls the Algorithm 1 to encrypt w0t,w1t,⋯,wn−1t into n ciphertexts(7)w00=Encw0t,w0t,⋯,w0t︸N/2,w10=Encw1t,w1t,⋯,w1t︸N/2,wn−10=Encwn−1t,wn−1t,⋯,wn−1t︸N/2.and sendsw00, w10, ⋯, wn−10 to SP to continue training.Algorithm 11:P2OLR.
Input: Y, X0, X1, ⋯, Xl−1, w0, α/m, N, Q,., sk, pk, rk, gk, tOutput: Wt(1)
for (k=0 to t−1) do(2)
for (i=0 to l−1) do(3)
for (j=0 to n−1) do(4)
Cij=MulWkj,Xij(5)
end for(6)
Oi=0(7)
for (j=0 to n−1) do(8)
Oi=Add_InplaceOi,Cij(9)
end for(10)
Gi=Sigmoid_ApproximationOi(11)
G′i=SubGi,Yi(12)
for (j=0 to n−1) do(13)
Ci′j=MulG′i,Xij(14)
end for(15)
end for(16)
for (j=0 to n−1) do(17)
Zi=0(18)
for (i=0 to l−1) do(19)
Zj=Add_InplaceZj,Ci′j(20)
end for(21)
Z′j=Rotate_SumZj(22)
Z′j=MulZ′j,α/m(23)
Wk+1j=SubWkj,Z″j(24)
W′k+1j=Mul_PlainWk+1j,1(25)
W″k+1j=Rotate_SumW′k+1j(26)
end for(27)
end for(28)
return: Wt


## 5. Performance Evaluation

We implement all experiments on a 32-core Intel Xeon CPU with 256 GB RAM. We compare the performance of the proposed P2OLR with the related P2OLR [17, 18, 22]. We employ 5-fold cross-validation method to obtain the validity of the experimental results. For [17, 18], the implementations are publicly available at [35, 36], respectively, which use the HEAAN library [33] to provide HE cryptographic operations. For [22] and the proposed P2OLR, we employ the Microsoft SEAL library [26] for the HE cryptographic operations. For all experiments, we set the learning rate α=0.01, random initial weight vector w00,w10,⋯,wn−10 maximum number of iterations λ=20, and scaling factor Δ=240. To guarantee κ=128 bit security, the scheme [17] takes the polynomial-modulus-degree N=217, coefficient-modulus Q around 2204 to 2406 bits; the scheme [18] sets the N=216, Q=1176 bits; the scheme [22] chooses the N=215, Q=320 bits; For the proposed P2OLR, we select N=215, Q=512 bits. Using the three datasets [18]: D1—Umaru Impact Study, D2—Myocardial Infarction Study from Edinburgh, D3—Nhanes III, we compare the proposed P2OLR with the related P2OLR [17, 18, 22] in terms of the encryption time (E. time) and decryption time (D. time) of DO, storage of encrypted training data, and training time (T. time), accuracy, precision, recall, F1-score and AUC of model. All comparison results are shown as an average of 10 experiments. The performance comparisons of the proposed P2OLR and the related P2OLR [17, 18, 22] are shown in Table 2.Table 2
Performance comparisons.
DatasetmnλSchemeE. time (s)D. time (s)Storage (MB)T. time (min)Accuracy (%)Precision (%)Recall (%)F1-score (%)AUCD1575820[17]7.044.93648.5677.3574.892.371.480.50.68[18]2.180.3936.7510.0974.490.971.480.00.65[22]30.280.061438.7526.6774.490.971.480.00.66P2OLR2.010.2372.002.6480.695.677.485.50.73D21253920[17]8.175.19726.8683.5781.689.782.485.90.82[18]2.210.4136.7510.2883.090.483.586.80.86[22]68.350.063133.7557.3582.790.482.986.50.86P2OLR2.160.2680.002.9190.695.190.692.80.88D3156491520[17]14.4811.651203.00121.9579.150.061.255.00.83[18]13.960.48147.0020.8679.250.261.355.20.71[22]823.560.0639123.75718.2577.952.462.256.90.71P2OLR3.490.45128.004.2183.760.364.262.20.85From Table2, we can see that, compared with the related P2OLR [17, 18, 22], the proposed P2OLR has a better performance. Specifically, as shown in Figure 3, under the training dataset D1, the encryption time of DO in the proposed P2OLR is 2.01 s, which is reduced by nearly 71.4%, 7.8%, and 93.3% respectively compared with the encryption time of DO in [17, 18, 22]; under the training dataset D2, the encryption time of DO in the proposed P2OLR is 2.16 s, which is reduced by nearly 73.6%, 2.3%, and 96.8% respectively compared with the encryption time of DO in [17, 18, 22]; under the training dataset D3, the encryption time of DO in the proposed P2OLR is 3.49 s, which is reduced by nearly 75.9%, 81.6%, and 75.0% respectively compared with the encryption time of DO in [17, 18, 22].Figure 3
The encryption time of DO.
(a)(b)(c)As can be seen in Figure4, under the training dataset D1, the decryption time of DO in the proposed P2OLR is 0.23 s, which is reduced by almost 95.3% and 41.0% respectively in comparison to the decryption time of DO in [17, 18]; under the training dataset D2, the decryption time of DO in the proposed P2OLR is 0.26 s, which is reduced by almost 95.0% and 36.6% respectively in comparison to the decryption time of DO in [17, 18]; under the training dataset D3, the decryption time of DO in the proposed P2OLR is 0.45 s, which is reduced by almost 96.1% and 6.1% respectively in comparison to the decryption time of DO in [17, 18]. The decryption time of DO in [22] is smaller in comparison to that of the proposed P2OLR.Figure 4
The decryption time of DO.
(a)(b)(c)As described in Figure5, under the training dataset D1, the storage of encrypted training data in the proposed P2OLR is 72.00 MB, compared with the storage of encrypted training data in [17, 22], which is reduced by nearly 88.9% and 95.0%; under the training dataset D2, the storage of encrypted training data in the proposed P2OLR is 80.00 MB, compared with the storage of encrypted training data in [17, 22], which is reduced by nearly 89.0% and 97.4%; under the training dataset D3, the storage of encrypted training data in the proposed P2OLR is 128.00 MB, compared with the storage of encrypted training data in [17, 18, 22], which is reduced by nearly 89.4%, 13.0% and 99.7% respectively. Although the storage of encrypted training data for dataset D1 and D2 in [18] is smaller than that of the proposed P2OLR, as the number of samples m and features n increases, for dataset D3, the storage of encrypted training data in the proposed P2OLR is smaller than that of [22].Figure 5
The storage of encrypted training data.
(a)(b)(c)As displayed in Figure6, under the training dataset D1, the training time of model in the proposed P2OLR is 2.64 min, which is reduced by almost 96.6%, 73.8%, and 90.1% respectively than the training time of model in [17, 18, 22]; under the training dataset D2, the training time of model in the proposed P2OLR is 2.91 min, which is reduced by almost 96.5%, 71.7%, and 95.0% respectively than the training time of model in [17, 18, 22]; under the training dataset D3, the training time of model in the proposed P2OLR is 4.21 min, which is reduced by almost 96.5%, 79.8%, and 99.4% respectively than the training time of model in [17, 18, 22].Figure 6
The training time of model.
(a)(b)(c)As illustrated in Figure7, under the training dataset D1, the average accuracy of model in the proposed P2OLR is 80.6%, which has nearly 5.8%, 6.2%, and 6.2% improvement respectively compared with the average accuracy of model in [17, 18, 22]; under the training dataset D2, the average accuracy of model in the proposed P2OLR is 90.6%, which has nearly 9.0%, 7.6%, and 7.9% improvement respectively compared with the average accuracy of model in [17, 18, 22]; under the training dataset D3, the average accuracy of model in the proposed P2OLR is 83.7%, which has nearly 4.6%, 4.5%, and 5.8% improvement respectively compared with the average accuracy of model in [17, 18, 22].Figure 7
The accuracy of model.
(a)(b)(c)As illustrated in Figure8, under the training dataset D1, the average precision of model in the proposed P2OLR is 95.6%, which has nearly 3.3%, 4.7%, and 4.7% improvement respectively compared with the average precision of model in [17, 18, 22]; under the training dataset D2, the average precision of model in the proposed P2OLR is 95.1%, which has nearly 5.4%, 4.7%, and 4.7% improvement respectively compared with the average precision of model in [17, 18, 22]; under the training dataset D3, the average precision of model in the proposed P2OLR is 60.3%, which has nearly 10.3%, 10.1%, and 7.9% improvement respectively compared with the average precision of model in [17, 18, 22].Figure 8
The precision of model.
(a)(b)(c)As illustrated in Figure9, under the training dataset D1, the average recall of model in the proposed P2OLR is 77.4%, which has nearly 6.0%, 6.0%, and 6.0% improvement respectively compared with the average recall of model in [17, 18, 22]; under the training dataset D2, the average recall of model in the proposed P2OLR is 90.6%, which has nearly 8.2%, 7.1%, and 7.7% improvement respectively compared with the average recall of model in [17, 18, 22]; under the training dataset D3, the average recall of model in the proposed P2OLR is 64.2%, which has nearly 3.0%, 2.9%, and 2.0% improvement respectively compared with the average recall of model in [17, 18, 22].Figure 9
The recall of model.
(a)(b)(c)As illustrated in Figure10, under the training dataset D1, the average F1-score of model in the proposed P2OLR is 85.5%, which has nearly 5.0%, 5.5%, and 5.5% improvement respectively compared with the average F1-score of model in [17, 18, 22]; under the training dataset D2, the average F1-score of model in the proposed P2OLR is 92.8%, which has nearly 6.9%, 4.0%, and 4.3% improvement respectively compared with the average F1-score of model in [17, 18, 22]; under the training dataset D3, the average F1-score of model in the proposed P2OLR is 62.2%, which has nearly 7.2%, 7.0%, and 5.3% improvement respectively compared with the average F1-score of model in [17, 18, 22].Figure 10
The F1-score of model.
(a)(b)(c)As demonstrated in Figure11, under the training dataset D1, the AUC of model in the proposed P2OLR is 0.73, compared with the AUC of model in [17, 18, 22], which has nearly 0.05, 0.08, and 0.07 improvement respectively; under the training dataset D2, the AUC of model in the proposed P2OLR is 0.88, compared with the AUC of model in [17, 18, 22], which has nearly 0.06, 0.02, and 0.02 improvement respectively; under the training dataset D3, the AUC of model in the proposed P2OLR is 0.85, compared with the AUC of model in [17, 18, 22], which has nearly 0.02, 0.14, and 0.14 improvement respectively.Figure 11
The AUC of model.
(a)(b)(c)


## 6. Security Analysis

In a semi-honest adversary model, we assume that DO and SP hold the public keypk, relinearization key rk, galois key gk, and only DO holds the secret key sk. For our P2OLR that evaluates deterministic function f, following the simulation-based paradigm [37], we consider the security model for security analysis, namely, DO encrypts its private data x and sends x to SP. SP performs the homomorphic operations on x to obtain y, homomorphically evaluates fx on x to obtain fx, and sends fx to DO. DO decrypts fx and obtains fx.Theorem 1.
We assume that SP is a semi-honest entity and assume that DO and SP do not collude with each other. Letx be a private data of DO. If the HE scheme [23] provides semantic security, after performing the homomorphic operations on x and the evaluation of fx on x, DO learns fx but nothing else, SP learns nothing.
Security Proof. The security proof of the proposed P2OLR follows the simulation-based paradigm [37]. Let the view of DO and SP during the evaluation be VDO and VSP, respectively. The view VSP of SP consists of pk,rk,gk,x,y,fx. We construct a simulator SSP as follows. SSP randomly chooses input data x′,y′,fx′. Then, SSP simulates VSP by VSP′=pk,rk,gk,x′,y′,fx′. Since the HE scheme [23] provides semantic security by assumption, VSP and VSP′ are indistinguishable. Therefore, the proposed P2OLR is secure against a semi-honest SP.


## 7. Conclusion

In this paper, we present a method for achieving a P2OLR on encrypted training data, which enables data owners to utilize the powerful storage and computing resources of cloud service providers for logistic regression analysis without exposing the privacy of training data. We take advantage of the batching technique and SIMD mechanism in HE to speed up the training progress. On the three public datasets, compared with the related P2OLR schemes [17, 18, 22], the model training time of the proposed P2OLR is reduced by more than 71.7%, and the proposed P2OLR has over 4.5%, 3.3%, 2.0%, 4.0%, and 0.02 performance in terms of the accuracy, precision, recall, F1-score, and AUC of model. There are still some limitations in applying our scheme to arbitrary datasets and performing arbitrary number of iterations on encrypted training data. In the future, we will extend our scheme to efficiently support P2OLR with arbitrary number of iterations.



---

*Source: 1321198-2022-07-21.xml*