Parameter-free HE-friendly Logistic Regression
Authors: Junyoung Byun
Woojin Lee
Jaewook Lee
Venue: NeurIPS 2021 Poster (2021)
Keywords: homomorphic encryption
logistic regression
parameter-free

Abstract: Privacy in machine learning has been widely recognized as an essential ethical and legal issue, because the data used for machine learning may contain sensitive information. Homomorphic encryption has recently attracted attention as a key solution to preserve privacy in machine learning applications. However, current approaches on the training of encrypted machine learning have relied heavily on hyperparameter selection, which should be avoided owing to the extreme difficulty of conducting validation on encrypted data. 
In this study, we propose an effective privacy-preserving logistic regression method that is free from the approximation of the sigmoid function and hyperparameter selection. In our framework, a logistic regression model can be transformed into the corresponding ridge regression for the logit function. We provide a theoretical background for our framework by suggesting a new generalization error bound on the encrypted data. Experiments on various real-world data show that our framework achieves better classification results while reducing latency by $\sim68\%$, compared to the previous models.

Parameter-free HE-friendly Logistic Regression
Junyoung Byun" Seoul National University
Woojin Lee" Dongguk University-Seoul Seoul, Korea wj wj9260dgu. ac
Jaewook Leet
Seoul National University Seoul, Korea
Seoul, Korea
quswns95@snu.ac. ac.
jaewook@smu. ac kr
Abstract
Privacy in machine learning has been widely recognized as an essential ethical and legal issue, because the data used for machine learning may contain sensitive information. Homomorphic encryption has recently attracted attention as key solution to preserve privacy in machine learning applications. However, current approaches on the training of encrypted machine learning have relied heavily on hyperparameter selection, which should be avoided owing to the extreme difficulty conducting validation on encrypted data. In this study, we propose an effective Trivacy-preservie logistic regression method that is free from the approximation the sigmoid function and hyperparameter selection. In our framework, a logistic regression model can be transformed into the corresponding ridge regression for the logit function. We provide theoretical background for our framework by suggesting generalization error bound the encrypted data. Experiments on various real-world data show that our framework achieves better classification results while reducing latency by 68%, compared to the previous models.
Introduction
Machine learning on encrypted data (MLED) an effective method ensure privacy for both machine learning models and data used for the model training. Unlike other privacy-preservngg machine learning methods, MLED does require decryption of intermediate products of the algorithm or data transfer between participants, enabling complete outsourcing of machine learning. As data have become increasingly valuable, MLED models have been actively studied in an attempt to combine data and computing power that separated from each other. With the development of efficient homomorphic encryption (HE) schemes that enable MLED, recent studies 4 9 38 30, 29 31 cover most machine learning models, from simple linear regression to deep neural networks (DNN).
However, current research on MLEDs remains lacking owing to the limitations of the proposed HE schemes. Operations on ciphertexts are very inefficient in terms of computation time and memory consumption, compared to operations on plaintexts. In addition, after performing certain number of operations, costly procedure called bootstrapping is required [19 5 Therefore, the majority of studies are limited the inference phase, assuming a situation that provides machine learning inference as service. The training phase should be studied more deeply top extract the maximum value from the data.
One of the MLED models, whose training steps have been commonly studied, is logistic regression (LR). LR is simple classification model that linearly divides the data space, which is used effectively in various fields, including medicine, marketing, and geology g 10 28 [23] trained an encrypted LR model with gradient descent and approximated the sigmoid function with the most similar polynomials within certain range. Despite performing well on several benchmark datasets, their
"quual contribution.
t Corresponning author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

methodology raises some concerns because the training parameters, such as learning rate, number of iterations, and range of sigmoid function approximation should be predetermined. Indeed, this problem is common for all proposed MLED training models.
In this study, we propose effective privacy-preserving LR method that is free from most hyper- parameter selections. First, we train an unencrypted classification model to extract the prediction probability for each label. Then, we solve for a ridge regression that predicts the logit result of the estimated probability. Our theoretical results provide a new generalization error bound, which can be optimized by properly estimating the logit and our proposed mean matching, which aims to reduce the gap between the distributions of encrypted and unencrypted data. To benefit from the trade-off off between security and efficiency, we define private variables, whose privacy is more important than the privacy of others, which has been widely recognized in other fields but has rarely been introduced into MLED. The experimental results show that, compared to the prior encrypted L.R models, our method achieves better classification results and lower training latency.
2 Preliminary Information
Throughout this paper, vectors are written in bold lowercase and matrices in bold uppercase. A ciphertext is indicated in the form of the corresponding message enclosed in brackets (c.g. [m]]. Operations between ciphertexts or between ciphertext and plaintext are both represented same as those between plaintexts.
Fully Homomorphic Encryption A fully HE (FHE) scheme consists of four procedures KGen, Enc, Dec and Eval. KGen generates secret key sk and public key pk [18]. A message m is encrypted to a ciphertext [m] = Enc(m, and a ciphertext [m'] ] is decrypted back to a plain- text m' = Dec((m'), sk). Eval evaluates a function f with vector of ciphertexts ([mi).... ..... [mx]) as an input; thus, it holds that Dec(Evall ([mm)])))___))))) [m f.kk), sk) = f(m1. m An FHE scheme naturally enables addition and multiplication; therefore, non-polynomial operations must be approximated by polynomial operations. Noise introduced when a message is first encrypted, which grows as the operation between eiphertexts proceeds. If the noise exceeds certain level, the ciphertext cannot be decrypted correctly. FHE allows an unlimited number of operations through bootstrapping which resets the noise, but bootstrapping incurs a large computational cost. Therefore, leveled HE (LHE) which avoids bootstrapping is preferred in many studies, with the number of operations required and corresponding scheme parameters determined in advance. In the case of using gradient descent in MLED training. LHE is not suitable because the number of iterations is very limited; whereas our method is suitable for LHE because the number of required operations is not too large and can be determined before implementation.
Logistic Regression with HE given by
The loss function of LR is the negative loglliiel,hood, which is
J(0) = Σ log(1 + exp(-y'80 x'))
where the weight vector, x' is i-th input and y E (+1,-1) is the label of i-th input. 22 minimized (I) with Nesterov's 's accelerated gradient, which is a slight modification of the gradient descent algorithm. The gradient descent algorithm can be written as follows:
0J = 00
0 = 0: 11::
9t =
sig( - yf x
y' g'
where 77 is the learning rate and sig(x) = 1/(1 + exp((=)) is the sigmoid function. When imple- menting this model with HE, there are two major limitations. The first is the selection of the learning rate and number of iterations for the gradient descent. In Figure [(a) we plotted how the loss changes according to the number of iterations for different learning rates. Observe that, the performance can vary drastically depending on the learning rate. In addition, the optimal learning rate is different depending on the number of iterations (compare the orange line (1) = 0.1) and pink line (1) = 0.01)). When dealing with plaintext, the optimal parameters can be found through cross validation, but this is impossible in MLED because the the weight vector cannot be decrypted during training. On the other hand, method can obtain closed form solution without using gradient descent.

---

sigmoid range:
0.0001
0.001
0.01
range:
range: 16
==
range: 20
tteratioss
(a) Importance of choosing the appropriate parame-(0) (b) Approximation performance of sigmoid function decreases as possible range of input grows
ters in learning L.
Figure I; Sensitivity analysis on the hyperparameters in previous privacy preserving LR
Another limitation that sigmoid function cannot evaluated efficiently using HE, Because the low-order Taylor expansion results in good approximation only in localized domain, [22] approximated the sigmoid function with a polynomial showing the lowest mean squared error in the domain [-8, 8). Figure [(b) shows the different approximation results according the domain range when approximated by a 3rd order polynomial. The maximum error between the polynomial and the sigmoid function is 0.11 when the range is [-8,8, 8] (blue line), which increases to 0.26 when the range [-20, 20 (red line). Therefore, the sigmoid function, which is not possible for encrypted data. Conversely, method solves ridge regression on the ciphertext; thus, there is no need to evaluate the sigmoid function.
essential to obtain tight bound for the input value of
Partial Eneryption Private Variables has been widely accepted that privacy for some vari- ables is more important than security for other variables. In the field of privacy-preservee data mining, k-anonymity [40 transforms the published variables to prevent exposure of personal identity, Subsequent concepts, such I-diversity (32 41 and t-closeness 27 were proposed protect other private variables, including personal income and medical records. In fair machine learning studies which have gained popularity recently, variables that may cause discrimination are defined as sensitive variables, which are required to be not disclosed [20] 21]. In cryptography research, presented security criteria and variables
25 42,
39
selectively encrypted accordingly.
When partially encrypting some private variables, the main purpose is to achieve trade-off between security and computation & storage efficiency. In Chapter [3 propose efficient ridge regression method with partially encrypted dataset that cannot be directly applied to LR. We separate operations on encrypted and non-encrypted variables, whereas in LR, the input of the sigmoid function the weighted sum of all variables. In addition, simply applying the existing LR algorithm to partially encrypted data does not result in sufficient efficiency nor does it solve the problems of parameter selection. We solve this problem by replacing the LR with ridge regression for the pre-calculated logit.
3 Framework
In this study, we propose new framework that can effectively handle classification tasks, while preserving the privacy of private variables. We two different datasets for the same vari- ables. D1 {ax) villi n.] and D2 { vb) 1, n2). where æ
(o/1 Thpp ( e))) contains encrypted private variables.
Threat Model
The participants of our framework consist of data owners O, modeler M and crypto-service provider C. We assume that the participants are honest-but-curioon and do not collude, which is widely accepted in MLED studies 37 34
1 35 Our security goals follows:
Neither M nor C should obtain information private variables.

---

Neither O nor C should obtain information on the learned model.
Protocol
The details of our protocol achieve the security goal are as follows:
(Teacher modeling) M trains a teacher model fa with an unenerypted dataset D1, where Dj is owned by M or publicly available.
(Encryption) C generates keys (pk, sk) and sends pk to O and M. O encrypts the private variables of their dataset D2 and sends D2 to M.
(Training on encrypted data) M infers encrypted logit Enc((2) = f. (D2) and evaluates Enc((2) = Enc( + Enc (B) through mean matching. M trains the prreecy-prsserving ridge regression on D2 and Enc(1z) and obtains Enc(w).
(Decryption) M generates a random polynomial and sends Enc(w + +r) to C. C decrypts w +r, adds random discrete Gaussian noise and sends w +r e back to M. M subtracts r, and the final weight obtained as w +
Similar to 12 [ the security of our protocol follows directly from the semantic security (against passive adversaries) of the underlying HE scheme. In our protocol, e added to defend against attack proposed by (26]. which, according to [6] with a high probability causes only <I bits of precision loss.
Our framework consists of three steps, excluding encryption and decryption. The first step is teacher modeling, which is the first of our protocol, and the second and third steps are mean matching and ridge regression, which corresponds with the third protocol.
Teacher modeling In the first step, M trains classification model with D1, which mimics the first phase of the knowledge distillation in the first model; then, we extract the soft probability from the target label. However, our method has several major differences from knowledge distillation. First, knowledge distillation aims to train a rather simple model that performs comparably to a complex teacher model, in which extracting the probability is a means achieve the goal. On the other hand, in our framework the probability plays a more important role. We transform the classification task into regression problem through the probability. Another difference is that in our method, the teacher model does not need to be a complex model. There are several advantages to using a simple model as a teacher model, which we will demonstrate later.
Mcanwhile, we should assume that M should possess an unencrypted D1 that can be used in step 1. Considering that M is depicted
company seeking to profit from their model in many studies 30 29 31, there may be individuals who provide their private information to M in return. To be more realistic, we assumed there are relatively few people who publish their private information. Moreover, the underlying distributions of DD and D2 are heterogeneous because they have different features than those who do not want to provide private information. To fit the former setting, we use simple model that generalizes sufficiently with a small amount of data as the teacher model.
Mean matching In the second step, using the teacher model M infers the logit of D22 In the case where the teacher model uses LR, the inference is simply an inner product between the model parameter 0 and x s, which can be efficiently computed with HE using slot rotation (See the Allsum algorithm in 223 ). Denoting the teacher model as fa and logits of Dj and D2 as l and l2, respectively, we can obtain l2 from D2 using the teacher model fa. However, because D1 and D2 have different distributions, also I and le might. Therefore, rather than directly using the logit distribution lg, we suggest adding regularization term l2 so that it can consider the difference between two distributions. The 3 should satisfy:
E. E((s(a)) + 1 Σnvi
(3)
Σn
Now applying the regularization term B, we can obtain the shifted logit iz where iž (xx) + B.
Note that 3 can be seen as simplified version of kernel mean matching reported in [17,, which is widely used in domain adaptation studies [24] Kernel mean matching attempts to match the means of the distributions of æs kernel space. When directly applying mean matching to logits, the distributions of logits are foreed to become similar, which has a negative effect on moving the

---

Slep
Teacher modeling
Step 2 Mean matching
Step 3 Ridge Regression
Tran fodt -f usin
Obrain 1 using encrypted Rec
Train Bae(F) Enefss) - EnciB) using 2,
(xbo))
4
H
Hnn (2) +1 Bnc Eno(ls)
End 4 Enc (f) End
argiinng 46445)
Teandoorm Ey
2 2G
Figure 2: Overall framework of our proposed method
prediction away from the true label. Therefore, multiplied the logit by weight, which reflects the distribution the true label.
Ridge regression Finally, we train ridge regression D2, where the target variable is the shifted logit l2, not y2. Intuitively, using well-estimated probability enables a training at least as accurate as that achieved when using a binary target; our theoretical results reported Chapter | support this claim. By encrypting small private portion of the entire information, we can train efficient ridge regression without having to explore the learning parameters. Let X ((=))² ... (a 2===>= )²)²
R">xx (x+t), [H,] = [[h]]-- ... [he)) the encrypted columns of X and X the other columns.
Then the ridge estimate is
f- X(X X(X [T] = xx (XX" +AI,,))-(12 [22] 11--XXX"--1 + 112)
Because XX
X(-)) X (-8) + H² by applying the Sherman inversion formula
we have
(XXT + A111)) = A A H A-
where A X (-s) (-s) + XIn2. Using the singular value decomposition (SVD) of ((-s) UVVI where U E _==Xma and V E RRxp are orthogonal matrices, and Σ E Rm=Xp is diagonal
matrix with diagonal entries 01 2 ... 2 Op 2 Jpt1 =... .... = =nn = 0, we have
A- = (UEE +bn U(EE" + -11z))
Then the ridge estimate be rewritten
f f= [1z] XA [T) +
no unu H.) of +
(Ie (I++
Σ
1
H
_ uu u [T2]
(5)
0
+ x
E Σラ バ H u H.). The result implies that, by separating the operations that involve encrypted data from those that do not, we can reduce the dimension of the matrix inversion from (p+ x (++ to x f. Using the Newton-Schulz iterative algorithm 3 for matrix inversion, multiplications between (p + E) (p + é) matrices reduce to & matrices, which results in a quadratic reduction in the computation cost. Moreover, it is known that Newton-Schula type methods can fail with large matrices (15), thus reducing the size the matrix greatly improves the stability. It is notable that when = 1 or 2, the matrix inverse reduces to scalar inverse, and can be more easily calculated with Goldschmidt's division algorithm [1].
where u, are the columns of U and
multiplications between
Based on having the freedom to choose upt Uny because dpt1 = Ong 0,, [E] and f can be further simplified as
5

---

Algorithm Training Ridge Regression with Encrypted Private Variable
Input: uneneypted data ((s)). encrypted private variable [ho]. encrypted target variable [t]
Output: two ciphertexts [w) [w.] such that the weight vector of Ridge regression is w" (w)-s) Wa)
< Pre-computationn's
[ Calculate matrix A = (X (-6) X(-.) + ) using the collected user data X(-))
[-] Obtain orthogonal matrices U (Un ... Up), V vp) and diagonal entries or (01,'',, ,pp
using the SVD of (-))
< Commutations on Encrypted data'>
[-] [ci] < MatVecProd
x U, [4): [ca] < MatVecProd V, o U, (hal):
[-] [ca] t MatVecProd(U, -2 U, [ [ca] f MatVecProd(U, ح U. (h.)):
[-] [cs] <- ([ha] - [c-))/)) [ca] InnerProduct((ss]) [[s)]][])s) [c>] Inv[lnnerrroduc(((s]]] [h.]) + 1)
[-] Output [w>[-)]] < [ei] - [ea] [co] [e7] and [w>.] < [cs] [c7]
p+C
3 3|= = Σ
1 Ho):
j=1 0f +
p+f ugu 7 [a)
p+f
f [1] XA 2 +
Σ
(I++
Σ !=ر of + A
[H [HSle,uf
of +
(6)
by choosing
p4-k1
Upth hg
uu (u))
Uptk up+k/ /pttt/lúpteel) h = I,..,..
Algorithm Algorithm descrrbes the procedure of training ridge regression, assuming that there is one private variable. For convenience, our method was described as obtaining the ridge estimate, but infer the test data, the algorithm is slightly modified to output the weight vector. We assume that all n2 samples of private variables are encoded into a single ciphertext to enable SIMD operations. the number of samples is larger than the maximum number of samples which can be packed into ciphertext, we can naturally split the samples into multiple ciphertexts. Excluding addition and multi- plication operations for the ciphertext, the algorithm consists of three functions: InnerProduct, Inv, InnerProduct returns ciphertext in which the values of all plaintext slots are the same as the inner product of the two vectors. Inv evaluates Goldschmidt's division algorithm stated in Algorithm I however, in the case where 2 3, it evaluates an iterative method for matrix inversion. MatVecProduce evaluates efficient matrix-vector multiplication using SVD of the input matrix. The detailed algorithms of these functions are provided in the Appendix.
and MatVecProduce
Extension to nonlinear models A limitation of our framework is that it can only model the linear relationship between the input variables and target variable. However, when partially encrypting private variables, our method has the capacity to model the nonlinear relationship between variables using kernel methods. The formulation opf the extension, and some experimental results are provided in the Appendix.
4 Theoretical Framework
This section provides the theory behind proposed methodology. We provide a generalization error bound for the proposed method.
Consider a classification task with an input space X, an output space )' = (0. 1). and hypothesis
space = X'x (0, Let Let = [z, = (x, v:) E Z i= 1,... N₂ represent the given open labelled data of N, samples. In our classification settings, we have two distinct distributions: (x, y) ~ Ds

---

according to sample distribution Ds over Z with E y and (x,p) ~ Dr according to target distribution Dy over Z with p [0, 1].
Utilizing these concepts and following the notations in 33 a hypothesis
2 - R a scoring function such that assign to each point the class label of the maximum score h(x, y), that is, arg myx (xx,3) y). The margin En (z) at a sample example z = (x, y) ~ Ds is then defined by
E1 (z) h(x, v) max hu (x, 3/)
4'
Thus, h misclassifies z iff En (z) - 0.
The generalization error (or risk) of a hypothesis h E H == {h 2 - R) in sample distribution D3 and true target distribution Dr are defined, respectively, by
RDz (h) Dg (x)so))
RD, (h) Ey-D, ( (m)sol
We next define the H--divergence (short version of -AA--divergence) as in [2] which measures the discrepancy between two different distributions in by
Du (Ds, Dr)
sup N.VER
RD, (h') RD. (h)l
We are now ready to derive the following generalization enror risk in our classification setting. Lemma 1. Let D and Dr be the sample and the true target distributions, respectively. Then for any hypothesis E H, the following inequality holds:
RD, (h) I min R.s (h') + Dz(Ds, Dr)
NEH
As result, the upper bound of empirical expected target error can be decomposed into two parts: The first term is the empirical source error. In our framework, we try to minimize this term by training a teacher classification model with D in the first step. Then the second term the H-divergence between the Ds and Dr which implies that we should reduce the gap between two distributions to achieve better performance. The mean matching step in our framework corresponds to this part, which is simplified version of kernel mean matching [17).
We next present the following margin bound for classification in the probably approximately correct (PAC) learning framework.
Theorem 2. Let Ds and Dr be the sample and the true target distributions, respectively. Then, for any O, with probability at least
the following classification generalization bound holds for
all hypothesis hs E Hpp =(xx, 3) B (yx) ||B||2 I 1/p. ||x||| S r]:
(h) 1
logno (1 + -2. + Dx,, (Ds, DT)
N
16r
log loga
log 2
+
(8)
PVN N
N
2N
where = log(1 + 1/e).
5 Experiments
In this section, we evaluate our method using various real-world datasets. Through experiments, argue that our method achieves better classification results compared to the existing methods with a shorter computation time. In addition, verify that even when the distributions of published and encrypted data are very different, our method can properly correct the difference and maintain the classification performance.
Datasets We used five widely used classification datasets from the UCI data repository: The adult income dataset (Adult), bank marketing dataset (Bank), Wisconsin Breast Cancer dataset (Cancer), Pima Indians Diabetes dataset (Diabetes), and Australian Credit Approval (Credit) dataset [[I] Adult and Bank datasets are commonly used in fair machine learning studies, thus, we treat variables that can induce social bias, such as gender and age, like private variables. For the other datasets, the variable that had the greatest impact the classification performance was selected as a private variable. In practical applications, data owners can flexibly set private variables according to their security standards. The explanation for each dataset is provided in the Appendix.
7

---

Table 1: Classification Results on five datasets.
Computation time
Time per iteration
Accuracy (%)
Dataset
(sec)
(sec)
LRHE
Ours
Ours-grad
LRHE
Ours
Ours-grad
LRHE
Ours-grad
Adult
81.913
83.123
82.759
306.061
102.25
1488.65
58.372
55,786
Bank
89.712
89.823
89,934
248.854
82.315
1095.44
47.528
43.184
Cancer
86.957
90.580
90.580
225.286
73.392
968.019
42,419
37.791
Diabetes
71.429
75.325
76.623
184.733
61.183
700,522
35.038
30.927
Credit
97.794
98.453
98.529
201.763
65.344
828.833
38.415
34.757
Experimental Setup All the experiments were performed on a machine equipped with 40 threads of an Intel Xeon R-2660 v3 @ @2.60GHz CPU processor. We implemented step 1 of our framework with Python 3.6.3, using the LR module in the scikit-learn library. Other steps were implemented with C++, using HEAAN v1.1 [7] for HE, HEAAN is an implementation of the CKKS scheme; a detailed description of the scheme and its parameters are provided in the Appendix. We used privacy-preserving LR depicted in (23) (LRHE) only MLED training model that works within a practical computation time, We do not compare our method to the HE-friendly SVM model reported in [36], because their model assumes that the data owners pre-compute the kernel matrix, which can leak information about the model. Comparing our model to DNN models reported in [29] is not of our interest because their model has latency that is too high. Note that we trained LRHE with all variables encrypted because LRHE hardly benefits from partial encryption, as mentioned in Chapter 2 Indeed, encrypting only private variables for LRHE resulted in time savings of less than 1.2%.
baseline comparison method because it is the
For each dataset, randomly sampled 20% test samples, and 20% of the other 80% were treated as plaintext data, which were used for the training of step 1. We encrypted the private variables the remaining 60% and used them for steps 2 and 3. For CKKS parameters, we used N = 2 Qr. 2200 and P 240 The sigmoid function approximation degree for LRHE was set to 3 because increasing the degree results in larger multiplicative depth and less possible number of gradient descents with LHE. In addition, we observed that increasing the degree up to did not significantly affect the performance of the model. The learning rate for LRHE was chosen in {0.001, 0.0001, 0.00001) } to achieve the best classification performance.
We compared the methods in terms of their classification accuracy and computation time. The results of the experiments summarized in Table For all datasets, Ours achieved higher accuracy and lower latency compared to LRHE In particular, regarding the computation time, Ours can reduce latency by 66-68% through efficient computation using private variables. Although the performance of LR using plaintext is not inferior to ours, the performance of LRHE degrades owing to the sigmoid approximation and limited iterations of gradient descent. On the other hand, because Ours is free from parameter selection, its performance does not decrease compared to the same operation using plaintext.
Results
As an ablation study, we additionally trained step 3 of Ours using gradient descent, with all variables encrypted (denoted Ours-grad in Table []. Because the multiplicative depth per iteration of Ours-grad is lower than that of LRHE owing to not using the sigmoid approximation, we trained Ours-grad for eight iterations. The learning rate that requires the most computation time in Ours-grad is the matrix-matrix multiplication, which causes Ours-grad to have greater latency compared to LRHE. However, the computation time per iteration of LRHE is higher than that of Ours-grad, and the result of the matrix-matrix multiplication can be reused through the iterations after calculating once. Therefore, it is implied that as the number of iterations increases, Ours-grad will be more efficient than LRHE In addition, the classification performance of Ours-grad is similar to or better than that of Ours, which means that Ours-grad converges better by allowing more iterations than LRHE Therefore, even in situations where the partial encryption of private variables is limited, our method has an advantage over the existing methods.
in {0.001, 0.0001, 0.00001) }. The procedure
Effectiveness of mean matching In this section, we verify that the mean matching in step 2 of our method is a simple but effective way to mitigate performance degradation due the difference between distributions of unencrypted and encrypted data. Here, we do not randomly divide the dataset,
8

---

Dh
D2
0-
-10
-20
10
-30
-20
(a) Visualization of Dj and D2 with different distri-(b) Logit distribution of 4 (red), la (green), la (or- ange). The blue histogram refers to the distribution of logit of X2 when trained with X2.
butions.
Figure 3: Effectiveness of Mean Matching
Table 2: Ablation study for mean matching. Criteria refers the criteria for dividing the datasets.
Accuracy (%)
Dataset
Criteria
LR with X1
Ours-without mean matching
Ours
LRHE
X1 "Marital' 0
Adult
63.330
63.330
69.471
68.690
X2 'Marital'
X1 'Gucoose' 117
Diabetes
29.487
29.487
80.769
80.769
X2 "Glucose' < 117
X1 "A4"= =0
Credit
20.833
20.833
79.167
79.167
X2: '4'
instead divide it referring to the value of a certain variable. Diabetes dataset, for example, was divided according to whether the value of 'Glucose' variable was greater than (or less than) its median. Figure 3(a) plots the dimension reduction result for Diabetes dataset using t-stochastic neighborhood embedding and confirms that the two subsets (X, and X2) have very separate distributions compared to each other. We sampled 20% of the entire dataset from X, and trained step with the samples. 80% X2 was used for steps and 3, with the remaining 20% of X2 used as the test samples.
Table 2 summarizes the experimental results for three datasets: Adult, Diabetes and Credit. For the other two, there were no variables that could properly divide them. The test accuracy of the LR model trained with X, was lower than that of the LRHE trained with X₂ because the domains of X, and X2 were different, and the test set was sampled from X2. The performance of Ours without mean matching the classification accuracy of Ours was raised to the same level as that of LRHE. Even when the accuracy of LR with Xı was 50% or lower than that of LRHE, applying mean matching completely recovered the classification performance of Ours.
not different from that of the LR with X1. However, with mean matching
To verify why the mean matching of our method works well, in Figure ((b) we plotted the histogram of logits inferred by LR models, the figure, the red and blue histograms represent the distributions of logit of X, for LR learned with X; (=I,) and logit of X2 for L.R learned with X2, respectively. Thus, the blue histogram can be seen as distribution of the logit of X₂ when it is classified "correctly". However, because the model is biased toward the distribution of X, when trained with X1, the distribution of the logit of X2 (=l2) is also biased toward the distribution of the logit of X,, as shown in the green histogram. Therefore, mean matching plays the role of shifting the biased distribution (orange histogram) to fit the correct distribution.
6 Conclusion
We proposed an efficient HE-friendly classification method, that protects both the users' private information and secrecy of the model. We trained a ridge regression model for the logit instead of logistic regression, which has closed-form solution and is free from parameter search. To extract

---

logit values from binary label, we trained a teacher model on unencrypted data that can output logit, similar that of knowledge distillation. Owing to encrypting only private variables that require high level of security instead of encrypting all information, our method can achieve higher efficiency and training stability. Our algorithm HE scheme-free; it can bring efficiency when implemented with any widely used HE schemes.
Although our study aims extend the existing machine learning method in the privacy-preserving direction, our model can be corrupted by malicious participants because our security model is limited to semi-honest, non-colluding participants. Designing a secure system for weaker security assumptions should be conducted in future
f studies.
Acknowledgments and Disclosure of Funding
This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry Science and Technology Information and Communication (2019RIA2C2002388)
References
[1] Y. Aono, T. Hayashi, T. Phong, and I.. Wang. Input and output privacy-preserving linear regression. IEICE TRANSACTIONS on Information and Systems, 100(10):2339-2447 2017.
[2] S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. W. Vaughan. A theory of learning from different domains. Machine learning, 79(1):151-175. 2010.
[3] A. Ben-ll An iterative method for computing the generalized inverse of an arbitrary matrix. Mathematics of Computation, pages
1965.
[4] Y.-R. Chen, A. Rezapour, and W.-G. Tzeng, Privacy-preserving ridge regression distributed data. Information Sciences, 451:34 2018
[5] J. H. Cheon, K. Han, A. Kim, M. Kim, and Y. Song. Bootstrapping for approximate homo- morphic encryption. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 360-384. Springer, 2018.
[6] J. H. Cheon, S. Hong, and D. Kim. Remark the security of ckks scheme in practice. IACR Cryptol. ePrint Arch., 2020:1581, 2020.
[7] J. H. Cheon, A. Kim, M. Kim, and Y. Song. Homomorphie encryption for arithmetic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security, pages 409-437. Springer, 2017.
[8] E. Christodoulou, J. Ma, G. S. Collins, F. W. Steyerberg, J. Y. Verbakel, and B. Van Calster. A systematic review shows no performance benefit of machine learning over logistic regression for clinical prediction models. Journal of clinical epidemiology. 11::1-222 2019.
[9] M. d. Cock, R. Dowsley, A. C. Nascimento, and S. C. Newman. Fast, privacy preserving linear regression over distributed datasets based on pre-distributed data. In Proceedings of the 8th ACM Workshop Artificial Intelligence and Security, pages 3 3-14, 2015.
[10] A. De Caigny, K. Coussement, and K. W. De Bock. A new hybrid classification algorithm for customer chur prediction based on logistic regression and decision trees. European Journal of Operational Research, 269(2):760-77) 2018.
[11] D. Dua and C. Graff. UCI machine learning repository, 2017.
[12] H. Fang and Q. Qian. Privacy preserving machine learning with homomorphic encryption and federated learning, Future Internet, 13(4):94, 2021.
[13] K. Gai, M. Qiu, and H. Zhao. Privacy-preserving data encryption strategy for big data mobile cloud computing. IEEE Transactions on Big Data, 2017.
10

---

[14] R. E. Goldschmidt. Applications of division by convergence. PhD thesis, Massachusetts Institute of Technology, 1964.
[15] R. M. Gower and P. Richtárik. Linearly convergent randomized iterative methods for computing the pseudoinverse. arXiv preprint arXivv1611.062255, 2016.
[16] Graepel, K. Lauter, and M. Nachrig. MI confidential: Machine learning on encrypted data. In International Conference on Information Security and Cryptology, pages 1-21. Springer, 2012.
[17] A. Gretton, A. Smola, J. Huang, M. Schmittfull, K. Borgwardt, and B. Schölkopf. Covariate shift by kernel mean matching. Dataset shift in machine learning, 3(4):5, 2009.
[18] S. Halevi. Homomorphic encryption. tutorials on the foundations of cryptography. isc, 2017.
[19] S. Halevi and V. Shoup. Bootstrapping for helib. In Annual International conference on the theory and applications of cryptographic techniques, pages 641-670. Springer, 2015.
[20] M. Jagielski, M. Kearns, J. Mao, A. Oprea, A. Roth, S. Sharifi-Malvajerii, and J. Ullman. Differentially private fair learning. In International Conference on Machine Learning, pages 4000-3008 PMLR, 2019.
[21] N. Kilbertus, A. Gascón, M. Kusner, M. Veale, K. Gummadi, and A. Weller. Blind justice: Fairness with encrypted sensitive attributes. International Conference on Machine Learning, pages
PMLR, 2018.
[22] A. Kim, Y. Song, M. Kim, K. Lee, and H. Cheon. Logistic regression model training based on the approximate homomorphic encryption. BMC medical genomics, 1 144):333,,, 2018.
[23] M. Kim, Y. Song, S. Wang. Y. Xia, and X. Jiang. Secure logistic regression based on homomor- phic encryption: Design and evaluation. JMIR medical informatics, 6(2):e19, 2018.
[24] W. Lee, H. Kim, and J. Lee. Compact class-conditional domain invariant learning for multi-class domain adaptation. Pattern Recognition, 112:107763, 2021.
[25] W. Lee, H. Ko, Byun, T. Yoon, and J. Lee. Fair clustering with fair correspondence distribution. Information Sciences, 581:155-178, 2021.
[26] B. Li and D. Micciancio. On the security of homomorphic encryption on approximate num- bers. In Annual International Conference on the Theory and Applications of Cryptogruphic Techniques, pages 648 648-677. Springer, 2021.
[27] N. Li, T. Li, and S. Venkatasubrammanian. t-closeness: Privacy beyond k-anonymity and 1- diversity. In 2007 IEEE 23rd International Conference on Data Engineering, pages 106-115. IEEE, 2007.
[28] L. Lombardo and P. M. Mai. Presenting logistic regression-based landslide susceptibility results. Engineering geology, 244:14-24, 2018
[29] Q Lou, B. Feng, G. C. Fox, and L. Jiang. Glyph: Fast and accurately training deep neural networks encrypted data. arXiv preprint 1eXXiv1911.071000 2019.
[30] Q Lou and L. Jiang. She: A fast and accurate deep neural network for encrypted data. arXiv preprint 17Xiv:1906.001493 2019.
[31] Q. Lou, W.-j Lu, C. Hong, and I.. Jiang. Falcon: Fast spectral inference encrypted data. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 2364-2374. Curran Associates, Inc., 2020.
[32] A. Machanavaijhala, D. Kifer, J. Gehrke, and M. Venkitasubramanian. 1-diversity: Privacy heyond k-anonymity, ACM Transactions on Knowledge Discovery from Data (TKDDD))) 1(1):3es, 2007.
[33] M. Mohri, A. Rostamizadeh, and Talwalkar. Foundations of machine learning. MIT press, 2018.

---

[34] T. Morshed, D. Alhadidi, and N. Mohammed. Parallel linear regression on encrypted data. In 2018 16th Anmual Conference on Privacy, Security and Trust (PST), pages 1-5, IEEE, 2018.
[35] V. Nikolaenko, U. Weinsberg, S. Ioannidis, M. Joye, D. Boneh, and N. Taft. Privacy-preserving ridge regression on hundreds of millions of records. In 2013 IEEE Symposium on Security and Privacy, pages 334-344 IEEE, 2013.
[36] S. Park, J. Byun, Lee, J. H. Cheon, and J. Lee. He-friendly algorithm for privacy-preservngg svm training. IEEE Access, 8:57414-5740 57425, 2020.
[37] G. Qiu, X. Gui, and Y. Zhao. Privacy-preserving linear regression on distributed data by homomorphic encryption and data masking. IEEE Access, 8:107601-107613, 2020.
[38] C. E. Rasmussen. Gaussian processes in machine learning. In Summer school on machine learning, pages 63-71. Springer, 2003.
[39] M. Sumathi and S. Sangeetha. Enhanced elliptic curve cryptographic technique for protecting sensitive attributes in cloud storage. In 2018 IEEE International Conference on Computational Intelligence and Computing Research (ICCIC), pages 1-5. IEEE, 2018
[40] L. Sweeney. k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Base Systems, 10(05):557-570, 2002.
[41] Q. Wang and X. Shi. (a, d)-diversity: Privacy protection based on I-diversity. In 2009 WRI World Congress on Software Engineering, volume 3, pages 367-372. IEEE, 2009.
[42] T. Yoon, J. Lee, and W. Lee. Joint transfer of model knowledge and fairness over domains using wasserstein distance. IEEE Access, 8:1 1373833-123798 2020.
12


Reviews:
[{"review_id": "pbvDVq5oiZH", "reviewer": "Reviewer_WfvM", "summary": "This paper tackles the problem of performing logistic regression in a homomorphic encryption setting. The propose the following:\n\n- Pretrain a regular logistic regression on some public data (completely plaintext)\n\n- Run this network on the private data to produce soft targets (and shift the means of the soft targets to deal with datashift shift, with a hyper-parameter)\n\n- Solve ridge regression (possibly with some non-private variables) to estimate these targets on the private data\n\nThe authors provide a fast solution for step 3 and show that their model can outperform LRHE in accuracy and speed on different datasets from the UCI repository. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nThe authors propose to tackle the problem of hyper-parameter selection in homomorphic encryption by leveraging a plaintext-text dataset at the start of the training process. This offers an interesting novel direction to explore. \n\nQuality / Significance:\n\nThe core claims of this paper are:\n\n*Introducing a hyper-parameter free version of HE logistic regression\n\nHowever, the paper introduces a hyper-parameter lamba for their ridge regression which still needs to be selected somehow. Perhaps I’m misunderstanding something but there seems to be a hyper-parameter here. \n\n*This method is faster and more accurate than prior work\n\nI have a few questions here. Is the LRHE baseline also adapted to only use a few private variables? It seems that the number of private variables here is critical to runtime and so a head to head comparison where all variables are private is critical.  Moreover, how does LRHE use the plaintext data? Does it not use it all? If so, that isn't a fair comparison to the model here. \n\nAlso, how does it compare to other mechanisms for using the plaintext data? For example, can the pretrained teacher be used as an initial guess of weights for both LRHE and this approach? Moreover, how does it perform by itself without any training on the private data (in table 1)?\n\nAs of now, it is difficult to assess the significance of these results. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper notes that this framework cannot be used for nonlinear models easily (like NNs), however, it can be used with kernel methods.  The study does not note possible negative social impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "keeeosHgMz", "reviewer": "Reviewer_XQWo", "summary": "This paper introduces an interesting new approach for learning a classifier on homomorphically encrypted data. A few important assumptions are made: only very few features (one to three maybe) are privacy-protected and the modeler is able to build a regression model on a part of the dataset. Next, further training data including private features are used to convert the initial model into a Ridge regression model. The key innovation is that the encrypted computation step can be isolated to make it very simple when few features are encrypted.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the idea is very interesting and hits many of the pain-points in learning on encrypted data. Realistically not all features are equally private, so it's great to see that this can be taken advantage of so well. Another huge advantage is getting rid of the sigmoid approximation, which is always problematic due to inability to control the input range.\n\nThis work seems totally novel and interesting to me, but I'm not enough of an expert to evaluate whether (from an ML point-of-view) the approach that is taken is actually sound. The encrypted computing part is rather simple and could be done with a number of techniques to achieve semi-honest security.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Training on encrypted data can raise all kinds of new concerns. For example, poisoning becomes really challenging to prevent, as input data can't be validated by the modeler. This may or may not matter, depending on the exact use-case. Maybe some paragraph discussing concrete scenarios, where the proposed system makes sense, could be added.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Ua4__kNk1Kf", "reviewer": "Reviewer_xo2J", "summary": "The paper tackles with the hyper-parameter tuning problem in logistic regression on encrypted data. Assuming a fraction of public data and a fraction of public features, the authors show by experiments that similar or better accuracy can be achieved with ~3x speed.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I find the classification-to-regression idea and the computation trick quite interesting. The speed-up is significant and evident. I think this part is solid work and makes a good publication. However, I have to say that as a non-expert, I cannot judge the novelty of the idea and the trick. In particular, I feel that this classification-to-regression idea may generally be useful in domain adaptation / transfer learning. I cannot tell if it already appeared in that community. Secondly, I suppose the linear algebraic trick used in lines 150-176 was at least partially known. For example, I suppose Equation (4) should be well-known, but is it so well-known that no reference is needed/possible? Some notes would definitely help readers like me.\n\nOn the other hand, I have one major criticism: The theory in section 4 doesn't seem to make any contribution to the paper. It also doesn't make much sense to me. I recommend removing this part, together with the claim that the authors find a new bound. Otherwise, section 4 needs a significant improvement at the very least. For example, in Theorem 2, I don't know what is $\\\\tilde\\{H\\}\\_0$. The definition in line 214 doesn't make much sense to me. According to line 209, $R_{D_T}$ relies on a ground truth $c_T$. What is it? Why are we interested in the divergence defined in line 214? How does $H$ and $\\tilde{H}$ effect the divergence? Is it an original definition or is there a source? I couldn't find it in the book cited. In the proof of Theorem 2, the authors cited Theorem 13.2 of the book, but that deals with multi-class case. Isn't 13.4 a better fit for the binary problem in the paper? I'd like to see the response on this issue and am open to change my rating.\n\nFinally, a comment on the presentation as a non-expert reader: It takes a bit effort for me to figure out who does what and who sees what and why the protocol is secure. Stating these facts with explicit reference to Figure 2 and/or Algorithm 1 may help.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "O30KUH1_Zn8", "reviewer": "Reviewer_WSkd", "summary": "This study considers a situation that a part of unencrypted samples are available while the other samples are provided with encrypted by FHE (or LHE). First, the modeler trains a logistic regression model with unencrypted samples. By using this model, given encrypted samples,  the modeler obtains the encrypted logits. To absorb the difference of sample generating distributions of non-private samples and private samples, moment matching is applied on encrypted logits (I could not understand why this works).  Then, ridge regression is solved with the encrypted logits with labels, in that the solution can be obtained in an analytic form instead of iterative methods as logistic regression regularly requires.\n**Due to the lack of a detailed description of the security model and global information flow of the protocol, this summary might be wrong. \n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In my understanding, this paper does not contain a technically original contribution, while a practical solution for logistic regression model training over FHE is presented by combining known techniques in matrix algebra and cryptography. In this sense, this paper presented a meaningful construction of logistic regression over FHE.\n\nThe weak point of this manuscript is that the contents of the paper overly emphasize the detailed mathematical operations while necessary information to understand the security model considered in this study is lost. Due to the lack of this, the reviewer could not understand the information flow between data owner, modeler, and crypto-service provider. Also, the reviewer could not understand who wanted to protect what from whom by this protocol. For this reason, the reviewer thinks it is not appropriate this publish this manuscript in its current form.\n\nLine 130 \n...we should assume that M should possess unencrypted D1 that can be used for step 1\n\nThis paper does not give a specific security setting (who does what and what is private). Without a clear description of the security model, it is impossible to see if the presented scheme is secure or not.\n\n\nAlso, line 120\n... The details of our protocol to achieve the security goal is in Appendix.\n\nThe protocol itself is the main contribution of this work so it should be contained in the main body.\n\nLine142\n... we suggest adding a regularization term β on l2 so that it can take into account the difference between two distributions\n\nThis does not make sense. Why regularization term can resolve the difference between two distributions? \n\nLine 148\n...By encrypting a small private portion of the whole information, \n\nDoes this mean that some portion (samples? variables?) is private and the other (samples? variables?) are not private?  Who decides which is private and which is not?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No.\nI think this type of study is originally presented to enhance privacy, no need to support it.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an interesting solution to the problem of training models on private data. The progress is made by first noticing that not all features are equally sensitive and then using it to reduce the classification problem, which is hard to train using HE to a regression problem that is easier to solve.
Most reviewers agreed that the paper makes a nice contribution to the field and should be accepted. The presentation of the work is fine but could be improved. Adding to comments made by the reviewers note, for example, that on line 122 “knowledge distillation” is discussed as if it was already presented before. The line reads “…which mimics the first phase of the knowledge distillation in that …” but this is the first-time knowledge distillation is being discussed. In this case, removing the “the” before “knowledge distillation” and adding a reference to a relevant paper could help the reader. We encourage the authors to revisit the paper and try to improve it readability.

Decision: Accept (Poster)