{'fraction_non_alphanumeric': 0.045743287491814014, 'fraction_numerical': 0.007727570399476097, 'mean_word_length': 4.209996588195155, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Secure Approximation Guarantee for Cryptographically Private Empirical Risk Minimization

Privacy concern has been increasingly important in many machine learning (ML) problems. We study empirical risk minimization (ERM) problems under secure multi-party computation (MPC) frameworks. Main technical tools for MPC have been developed based on cryptography. One of limitations in current cryptographically private ML is that it is computationally intractable to evaluate non-linear functions such as logarithmic functions or exponential functions. Therefore, for a class of ERM problems such as logistic regression in which non-linear function evaluations are required, one can only obtain approximate solutions. In this paper, we introduce a novel cryptographically private tool called secure approximation guarantee (SAG) method. The key property of SAG method is that, given an arbitrary approximate solution, it can provide a non-probabilistic assumption-free bound on the approximation quality under cryptographically secure computation framework. We demonstrate the benefit of the SAG method by applying it to several problems including a practical privacy-preserving data analysis task on genomic and clinical information.


Introduction
Privacy preservation has been increasingly important in many machine learning (ML) tasks. In this paper, we consider empirical risk minimizations (ERMs) when the data is distributed among multiple parties, and these parties are unwilling to share their data to other parties. For example, if two parties have different sets of features for the same group of people, they might want to combine these two datasets for more accurate predictive model building. On the other hand, due to privacy concerns or legal regulations, these two parties might want to keep their own data private. The problem of learning from multiple confidential databases have been studied under the name of secure multi-party computation (secure MPC). This paper is motivated by our recent secure MPC project on genomic and clinical data. Our task is to develop a model for predicting the risk of a disease based on genomic and clinical information of potential patients. The difficulty of this problem is that genomic information were collected in a research institute, while clinical information were collected in a hospital, and both institutes do not want to share their data to others. However, since the risk of the disease is dependent both on genomic and clinical features, it is quite valuable to use both types of information for the risk modeling.
Various tools for secure MPC have been taken from cryptography, and privacy-preserving ML approaches based on cryptographic techniques have been called cryptographically private ML. A key building block of cryptographically private ML is homomorphic encryption by which sum or product of two encrypted values can be evaluated without decryption. Many cryptographically private ML algorithms have been developed, e.g., for linear regression [1,2] and SVM [3,4] by using homomorphic encryption property. One of limitations in current cryptographically private ML is that it is computationally intractable to evaluate non-linear functions such as logarithmic functions or exponential functions in homomorphic encryption framework.
Since non-linear function evaluations are required in many fundamental statistical analyses such as logistic regression, it is crucially important to develop a method that can alleviate this computational bottleneck.
One way to circumvent this issue is to approximate non-linear functions. For example, in Nardi et al.'s work [5] for secure logistic regression, the authors proposed to approximate a logistic function by sum of step functions, which can be computed under secure computation framework.
Due to the very nature of MPC, even after the final solution is obtained, the users are not allowed to access to private data. When the resulting solution is an approximation, it is important for the users to be able to check its approximation quality. Unfortunately, most existing cryptographically private ML method does not have such an approximation guarantee mechanism. Although a probabilistic approximation guarantee was provided in the aforementioned secure logistic regression study [5], the approximation bound derived in that work depends on the unknown true solution, meaning that the users cannot make sure how much they can trust the approximate solution.
The goal of this paper is to develop a practical method for secure computations of ERM problems. To this end, we introduce a novel secure computation technique called secure approximation guarantee (SAG) method. Given an arbitrary approximate solution of an ERM problem, the SAG method provides nonprobabilistic assumption-free bounds on how far the approximate solution is away from the true solution.
A key difference of our approach with existing ones is that our approximation bound is not for theoretical justification of an approximation algorithm itself, but for practical decision making based on a given approximate solution. Our approximation bound can be obtained without any information about the true solution, and it can be computed with a reasonable computational cost under secure computation framework, i.e., without the risk of disclosing private information.
The proposed SAG method can provide non-probabilistic bounds on a quantity depending on the true solution of the ERM problem under cryptographically secure computation framework, which is valuable for making decisions when only an approximate solution is available. In order to develop the SAG method, we introduce two novel technical contributions in this paper. We first introduce a novel algorithmic framework for computing approximation guarantee that can be applied to a class of ERM problems whose loss function is non-linear and its secure evaluation is difficult. In this framework, we use a pair of surrogate loss functions that bounds the non-linear loss function from below and above. Our second contribution is to implement these surrogate loss functions by piecewise-linear functions, and show that they can be cryptographically securely computed. Furthermore, we empirically demonstrate that the bounds obtained by the SAG method is much tighter than the bounds in Nardi et al.'s method [5] despite the former is non-probabilistic and assumption-free. Figure 1 is an illustration of the SAG method in a simple logistic regression example.
In machine learning literature, significant amount of works on differential privacy [6] have been recently studied. The objective of differential privacy is to disclose an information from confidential database without taking a risk of revealing private information in the database, and random perturbation is main technical tool for protecting differential privacy. We note that the privacy concern studied in this paper is rather different from those in differential privacy. Although it would be interesting to study how the latter type of privacy concerns can be handled with the approach we discussed here, we would focus in this paper on privacy regarding cryptographically private ML.
Notations We use the following notations in the rest of the paper. We denote the sets of real numbers and integers as R and Z, respectively. For a natural number N , we define [N ] := {1, 2, . . . , N } and Z N := {0, 1, . . . , N − 1}. The Euclidean norm is written as · . Indicator function is written as I χ i.e., I χ = 1 if χ is true, and I χ = 0 otherwise. For a protocol Π between two parties, we use the notation Π(I A , I B ) →   The left plot (A) shows the logistic function (blue) and its approximation (red) proposed in [5]. The right plot (B) shows the true (blue) and approximate (red) class probabilities of five training instances (the instance IDs 1, . . . , 5 are shown in the horizontal axis), where the former is obtained with true logistic function, while the latter is obtained with the approximate logistic function. The green intervals in plot (B) are the approximation guarantee intervals provided by the SAG method. The key property of the SAG method is that these intervals are guaranteed to contain the true class probabilities. Thus they can be used for certainly classifying some of these five instances to either positive or negative class. Noting that the lower bounds of the class probabilities are greater than 0.5 in the instances 1 and 4, they would be certainly classified to positive class. Similarly, noting that the upper bounds of the class probabilities are smaller than 0.5 in the instances 3 and 5, they would be certainly classified to negative class.

Problem statement
Empirical risk minimization (ERM) Let {(x i , y i ) ∈ X × Y} i∈[n] be the training set, where the input domain X ⊂ R d is a compact region in R d , and the output domain Y is {−1, +1} in classification problems and R in regression problems. In this paper, we consider the following class of empirical risk minimization problems: where is a loss function subdifferentiable and convex with respect to w, and λ > 0 is the regularization parameter. L 2 regularization in (1) ensures that the solution w is within a compact region W ⊂ R d .
We consider the cases where is hard to compute in secure computation framework, i.e., includes non-linear functions such as log and exp. Popular examples includes logistic regression Poisson regression and exponential regression (y, x w) := (y exp(−x w)) − x w.
Secure two-party computation We consider secure two-party computation scenario where the training is vertically-partitioned between two parties A and B [7], i.e., A and B own different sets of features for common set of n instances. More precisely, let party A own the first d A features and party B own the last d B features, i.e., d A + d B = d. We consider a scenario where the labels {y i } i∈[n] are also owned by either party, and we let party B own them here. We assume that both parties can identify the instance index i ∈ [n], i.e., it is possible for both parties to make communications with respect to a specified instance.
We denote the input data matrix owned by parties A and B as X A and X B , respectively. Furthermore, we denote the n-dimensional vector of the labels as y := [y 1 , . . . , y n ] .
Semi-honest model In this paper, we develop the SAG method so that it is secure (meaning that private data is not revealed to the other party) under the semi-honest model [8]. In this security model, any parties are allowed to guess other party's data as long as they follow the specified protocol. In other words, we assume that all the parties do not modify the specified protocol. The semi-honest model is standard security model in cryptographically private ML.

Cryptographically Secure Computation
Paillier cryptosystem For secure computations, we use Paillier cryptosystem [9] as an additive homomorphic encryption tool, i.e., we can obtain E(a + b) from E(a) and E(b) without decryption, where a and b are plaintexts and E(·) is the encryption function. Paillier cryptosystem has the semantic security [10] (the IND-CPA security), which roughly means that it is difficult to judge whether a = b or a = b by knowing E(a) and E(b).
Paillier cryptosystem is a public key cryptosystem with additive homomorphism over Z N (i.e., modN ).
In public key cryptosystem, the private key is two large prime numbers p and q, and the public key is where N = pq and g is an integer co-prime with N 2 . Given a plaintext m ∈ Z N , a ciphertext of E(m) is obtained with a random integer R ∈ Z N as follows: Ciphertext E(m) is decrypted with the private key whatever R is chosen. With the encryption, the following additive homomorphism holds for any plaintexts a, b ∈ Z N : Hereafter, we denote by E pk A (·) and E pk B (·) the encryption functions with the public keys issued by party A and B, respectively.
Note that we need computations of real numbers rather than integers in data analysis tasks. First, negative numbers can be treated with the similar technique to the two's complement. In order to handle real numbers, we multiply a magnification constant M for each input real number for expressing it with an integer. Here, there is a tradeoff between the accuracy and range of acceptable real number, i.e., for large M , accuracy would be high, but only possible to handle a limited range of real numbers.

Related works
The most general framework for cryptographically private ML is the Yao's garbled circuit [11], where any desired secure computation is expressed as an electronic circuit with encrypted components. In principle, Yao's garbled circuit can evaluate any function securely, but its computational costs are usually extremely large. Unfortunately, it is impractical to use Yao's garbled circuit for secure computations of ERM problems.
Nardi et al. [5] studied cryptographically private approach for logistic regression. As briefly mentioned in §1, in order to circumvent the difficulty of secure non-linear function evaluations, the authors proposed to approximate logistic function by empirical cumulative density function (CDF) of logistic distributions (see Figure 1(A) as an example). Denoting the true solution and the approximate solution as w * andŵ, respectively, the authors showed that where L is the sample size for the empirical CDF, λ min is the smallest eigenvalue of Fisher information matrix depending on w * , and c > 0, c 1 > 0, γ ∈ (0, 1/2) are constants. This approximation error bound cannot be used for knowing the approximation quality of the given approximate solutionŵ: the bound depends on the unknown true solution w * because λ min depends on it. Furthermore, in experiment section, we demonstrate that the SAG method can provide much tighter non-probabilistic bounds than the above probabilistic bound in Nardi et al.'s method [5].

Secure Approximation Guarantee(SAG)
The basic idea behind the SAG method is to introduce two surrogate loss functions φ and ψ that bound the target non-linear loss function from below and above. In what follows, we show that, given an arbitrary approximate solutionŵ, if we can securely evaluate φ(ŵ), ψ(ŵ) and a subgradient ∂φ/∂w | w=ŵ , we can securely compute bounds on the true solution w * which itself cannot be computed under secure computation framework.
First, the following theorem states that we can obtain a ball in the solution space in which the true solution w * certainly exists.
∀y ∈ Y, x ∈ X , w ∈ W, and assume that they are convex and subdifferentiable with respect to w. Then, for anyŵ ∈ W, i.e., the true solution w * is located within a ball in W with the center and the radius The proof of Theorem 1 is presented in Appendix.
Using Theorem 1, we can compute a pair of lower and upper bounds of any linear score in the form of η w * for an arbitrary η ∈ R d as the following Corollary states. where The proof of Corollary 2 is presented in Appendix.
Many important quantities in data analyses are represented as a linear score. For example, in binary classification, the classification resultỹ of a test inputx is determined by the sign of the linear scorẽ x w * . It suggests that we can certainly classify the test instance as LB(x w * ) > 0 ⇒ỹ = +1 and , of the trained model, by setting η = e h where e h is a d-dimensional vector of all 1s except 0 in the h-th component, we can obtain a pair of lower and upper bounds on the coefficient as LB(e h w * ) ≤ w * h ≤ U B(e h w * ). We note that Theorem 1 and Corollary 2 are inspired by recent works on safe screening and related problems [12][13][14][15][16][17][18][19], where an approximate solution is used for bounding the optimal solution without solving the optimization problem.

SAG implementation with piecewise-linear functions
In this section, we present how to compute the bounds on the true solution discussed in §3 under secure computation framework. Specifically, we propose using piecewise-linear functions for the two surrogate loss functions φ and ψ. In §4.1, we present a protocol of secure piecewise-linear function evaluation (SP L). In §4.2, we describe a protocol for securely computing the bounds. In the appendix, we describe a specific implementation for logistic regression.

Secure piecewise-linear function computation
Let us denote a piecewise-linear function with K pieces defined in s ∈ [T 0 , T K ] as where are the coefficients of the j-th linear segment and An advantage of piecewise-linear functions is that, for any one-dimensional convex function, a lower bounding function can be easily obtained by using its tangents, while an upper bounding function can be also easily obtained by using its chords. In addition, we can easily control the trade-off between the accuracy and the computational complexity by changing the number of pieces K. Figure 2 shows examples of two piecewise-linear surrogate loss functions for a non-linear function log(1 + exp(−s)) for several values of K.
The following theorem states that a piecewise-linear function g(s) can be securely evaluated.
Theorem 3. Suppose that party A has E pk B (s A ) and party B has E pk A (s B ) such that s = s A + s B . Then, the two parties can securely evaluate the encrypted value of the piecewise-linear function value g(s) in the sense that there is a secure protocol that outputs E pk B (g A ) and E pk A (g B ) respectively to party A and party The proof of Theorem 3 is presented in Appendix. In the proof, we develop such a protocol called SP L, whose input-output property is represented as .
Let o j (s) := I s∈[Tj−1,Tj ) , j ∈ [K], denote the indicator of an event that a scalar s is in the j-th piece.
The difficulty of secure piecewise-linear function evaluation is that we need to securely compute E(o j (s)).
We use a protocol presented by Veugen et al. [20] in order to compute E(I a<b ) from E(a) and E(b), and then compute E(o j (s)) as Using the indicators {o j (s)} j∈ [K] , the piecewise-linear function value g(s) is written as which can be securely computed if E(o j (s)) and E(s) are available.
We finally note that, in Theorem 1, when φ(s) is represented as a piecewise-linear function, its subderivative ∂φ(s)/∂s is represented as a piecewise-constant function and so is the subgradient ∇Φ(ŵ). We can develop a secure piecewise-constant function evaluation protocol based on the same idea as above (detailed in the proof of Theorem 3 in Appendix).

Secure bound computation
We describe here how to compute the bounds on the true solution in the form of (6) when the surrogate loss functions φ and ψ are implemented with piecewise-linear functions. We consider a class of loss functions that can be decomposed as (y, x w) = u(s(y, x w)) + v(y, x w), where u is a non-linear function whose secure evaluation is difficult, while s(y, x w), v(y, x w), and their subgradients are assumed to be securely evaluated. Note that most commonly-used loss functions can be written in this form. For example, in the case of logistic regression (2), u(s) = log(1 + exp(−s)), s(y, x w) = x w and v(y, x w) = −yx w.
We consider a situation that two parties A and B own encrypted approximate solutionŵ separately for their own features, i.e., parties A and B own E pk B (ŵ A ) and E pk A (ŵ B ), respectively, whereŵ A andŵ B the first d A and the following d B components ofŵ.

Secure computations of the ball
The following theorem states that the center m(ŵ) and the radius r(ŵ) can be securely computed.
Theorem 4. Suppose that party A has X A and E pk B (ŵ A ), while party B has X B , y and E pk A (ŵ B ). Then, the two parties can securely compute the center m(ŵ) and the radius r(ŵ) in the sense that there is a secure protocol that outputs E pk B (m A (ŵ)) and E pk B (r A (ŵ) 2 ) to party A, and E pk A (m B (ŵ)) and E pk A (r B (ŵ) 2 ) to party B such that m A (ŵ) + m B (ŵ) = m(ŵ) and r A (ŵ) 2 + r B (ŵ) 2 = r(ŵ) 2 .
We call such a protocol as secure ball computation (SBC) protocol. whose input-output property is characterized as To prove Theorem 4, we only describe secure computations of three components in the SBC protocol. We omit the security analysis of the other components because they can be easily derived from the security properties of Paillier cryptosystem [9], comparison protocol [20] and multiplication protocol [21]. Encrypted values of ∇Φ(ŵ) This quantity can be obtained by summing ∇φ at w =ŵ. Since ∇φ = ∂ ∂w u(s) + ∂v ∂w = u (s) ∂s ∂w + ∂v ∂w , its encrypted version can be written as E(∇φ) = E(u (s) ∂s ∂w )E( ∂v ∂w ). Here, u (s) can be securely evaluated because u is piecewise-constant function, while ∂s ∂w and ∂v ∂w are securely computed from the assumption in (10). For computing E(u (s) ∂s ∂w ) from E(u (s)) and E( ∂s ∂w ), we can use the secure multiplication protocol in [21].
Encrypted value of r(ŵ) 2 In order to compute this quantity, we need the encrypted value of 1 2 (ŵ + 1/λ∇Φ) 2 , which can be also computed by using the secure multiplication protocol in [21].

Secure computations of the bounds
Finally we discuss here how to securely compute the upper and the lower bounds in (6) from the encrypted m(ŵ) and r(ŵ) 2 . The protocol depends on who owns the test instance and who receives the resulted bounds.
We describe here a protocol for a particular setup where the test instancex is owned by two parties A and B, i.e.,x = [x Ax B ] wherex A andx B are the first d A and the following d B components ofx, and that the lower and the upper bounds are given to either party. Similar protocols can be easily developed for other setups.
Theorem 5. Let party A ownsx A , E pk B (m A (ŵ)) and E pk B (r A (ŵ) 2 ), and party B ownsx B , E pk A (m B (ŵ)) and E pk A (r B (ŵ) 2 ), respectively. Then, either party A or B can receive the lower and the upper bounds of x w * in the form of (6) without revealingx A andx B to the others. The proof of Theorem 5 is presented in Appendix. We note that a party who receives bounds from the protocol would get some information about the center m B (ŵ) and the radius r B (ŵ), but no other information about the original dataset is revealed.

Experiments
We conducted experiments for illustrating the performances of the proposed SAG method. The experimental setup is as follows. We used Paillier cryptosystem with N = 1024-bit public key and comparison protocol by Veugen et al. [20] for 60 bits of integers. The program is implemented with Java, and the communications between two parties are implemented with sockets between two processes working in the same computer. We In what follows, we call the bounds or intervals obtained by the SAG method as SAG bounds and SAG intervals, respectively.

Logistic regression
We first investigated several properties of the SAG method for the logistic regression (2) by applying it to four benchmark datasets summarized in Table 1. the probability 90% (see (5)). The blue, green and purple ones were obtained by the SAG method with K = 100, 1000 and ∞, respectively, where K is the number of pieces in the piecewise-linear approximations.
Here, K = ∞ means that the true loss function was used as the two surrogate loss functions φ and ψ. The results clearly indicate that bounds obtained by the SAG method are clearly tighter than those by Nardi et al.'s approach despite that the latter is probabilistic and cannot be securely computed in practice. When comparing the results with different K, we can confirm that large K yields tighter bounds. The results with K = 1000 are almost as tight as those obtained with the true loss function (K = ∞).    Finally, we examined the computation time for computing the SAG bounds. Table 2 shows the computation time per instance with K = {100, 200, 500, 1000}. The results suggest that the computational cost is almost linear in K, meaning that the computation of piecewise-linear functions dominates the cost. Although this task can be completely parallelized per instance, further speed-up would be desired when K is larger than 1000.

Poisson and exponential regressions
We applied the SAG method to Poisson regression (3) and exponential regression (4). Poisson regression was applied to a problem for predicting the number of produced seeds 2 . Exponential regression was applied to a problem for predicting survival time of lung cancer patients 3 . The results are shown in Figure 6

Privacy-preserving logistic regression to genomic and clinical data analysis
Finally, we apply the SAG method to a logistic regression on a genomic and clinical data analysis, which is the main motivation of this work ( §1). In this problem, we are interested in modeling the risk of a disease based on genomic and clinical information of potential patients. The difficulty of this problem is that genomic information were collected in a research institute, while clinical information were collected in a hospital, and both institutes do not want to share their data to others. However, since the risk of the disease is dependent both on genomic and clinical features, it is quite valuable to use both types of information for the risk modeling. Our goal is to find genomic and clinical features that highly affect the risk of the disease.
To this end, we use the SAG method for computing the bounds of coefficients of the logistic regression model as described in §3.
In this experiment, 13 genomic (SNP) and 10 clinical features of 134 potential patients are provided from a research institute and a hospital, respectively 4 . The SAG bounds on each of these 23 coefficients are plotted in Figure 7. Although we do not know the true coefficient values, we can at least identify features that positively/negatively correlated with the disease risk (note that, if the lower/upper bound is greater/smaller than 0, the feature is guaranteed to have positive/negative coefficient in the logistic regression model).

Conclusions
We studied empirical risk minimization (ERM) problems under secure multi-party computation (MPC) frameworks. We developed a novel technique called secure approximation guarantee (SAG) method that can be used when only an approximate solution is available due to the difficulty of secure non-linear function evaluations. The key property of the SAG method is that it can securely provide the bounds on the true solution, which is practically valuable as we illustrated in benchmark data experiments and in our motivating problem on genomic and clinical data.
Plugging this into (14), we have Furthermore, noting that φ and Φ are convex with respect to w, by the definition of convex functions we get By plugging (16) into (15), Noting that (17) is a quadratic function of w * , we obtain It means that the optimal solution w * is within a ball with the center m(ŵ) and the radius r(ŵ), which completes the proof.
Proof of Corollary 2. We show that the lower bound of the linear model output value w * x is x m(ŵ) − x r(ŵ) under the constraint that w * − m(ŵ) ≤ r(ŵ).
To formulate this, let us consider the following constrained optimization problem Using a Lagrange multiplier µ > 0, the problem (18) is rewritten as where µ is strictly positive because the constraint w − m(ŵ) 2 ≤ r(ŵ) 2 is strictly active at the optimal solution. By letting ∂H(µ)/∂µ = 0, the optimal µ is written as Substituting µ * into H(µ), The upper bound part can be shown similarly.
Proof of Theorem 3 (Protocol evaluating piecewise linear function and its subderivative securely) First we explain the outline of the protocol of secure comparison by Veugen et al. [20]. The protocol returns the result of comparison E pk B (I q>0 ) (given to party A) for the encrypted values E pk B (q) (owned by party A) with the following two steps: • Party A and B obtain q A := R and q B := q + R, respectively, where R is a random value, and • Party A and B compare q A and q B with the implementation of bit-wise comparison with Paillier cryptosystem (see the original paper).
Let us denote the protocol of the latter by SC(q A , q B ) → (E pk B (I q A >q B ), E pk A (I q A >q B )), that is, SC is a protocol comparing two private, unencrypted values owned by two parties q A , q B .
The protocol for Theorem 3 is as follows: 1. Party A computes E pk B (s) = E pk B (s A + s B ) from E pk B (s A ) and E pk A (s B ) as follows: • Party B generates a random value R ∈ Z N/2 (N is defined in §2.2), then sends E pk A (s B − R) = E pk A (s B ) −R and E pk B (R) to party A.
• Party A decrypts E pk A (s B − R) and computes E pk B (s A + s B ) as: See [23] for the security of the part. : Party B similarly computes for E pk A . The idea is shown in Figure 8.

Party
A computes g Aj := α j p A + β j , and party B g Bj := α j p B for all j ∈ [K]. Note that g Aj + g Bj = α j s + β j .
6. Compute encrypted g A and g B . Because g A + g B = g(s) after taking g A = j∈[K] o j g Aj and g B = j∈[K] o j g Bj (see (9) in §4), party A computes E pk B (g A ) as Party B similarly computes E pk A (g B ).
To obtain the subderivative g (s) = j∈[K] o j α j , during the protocol for Theorem 3, party A computes E pk B (g (s)) as Party B similarly computes E pk A (g (s)).

Output of A U B, LB
Output of B ∅ Step 1. Party A and B computes: , E pk A (r 2 ). // The similar manner to the protocol for Theorem 3, step 1 step 2. Compute E pk B ( x 2 r 2 ) using the protocol for multiplication in [21].
Party B computes the followings and sends to A. The security is proved as follows: all techniques used in the protocol are secure with the same discussions as previous. The remaining problem is that whether party A can guessx B from U B and LB. Party A can ). However, because party A does not know m A , m B , r 2 A or r 2 B , party A cannot guessx B either 5 .  To apply this for SP L, we set E pk B (s A ) := E pk B (x Aŵ A ) and E pk A (s B ) := E pk A (x Bŵ B ) since we assume party A and B knows E pk B (ŵ A ) and E pk A (ŵ B ), respectively. Note that s A + s B = s because x = [x A x B ]

Example Protocol for the Logistic Regression
and w = [w A w B ] . Take piecewise linear functions u(s) and u(s) as lower and upper bounds of u(s), respectively. With it, we can compute φ, ψ and ∇φ in SAG as follows: ψ| w=ŵ −φ| w=ŵ = u(x ŵ) − u(x ŵ), which are all computable with SP L.
After these preparations, we can conduct the protocol SBC as Protocol 2. Input from B {x iB , y i } i∈[n] , E pk A (ŵ B ) Output to A E pk B (m A ), E pk B (r 2 A ) Output to B E pk A (m B ), E pk A (r 2 B ) (where r 2 A + r 2 B = r 2 ) Step1 Party B sends E pk B (y) to party A.
Step3 Party A and B compute encrypted m and r.