Security-preserving Support Vector Machine with Fully Homomorphic Encryption

Abstract

Recently, security issues have become more and more important to apply machine learning models to a real-world problem. It is necessary to preserve the data privacy for using sensitive data and to protect the information of a trained model for defending the intentional attacks. In this paper, we want to propose a security-preserving learning framework using fully homomorphic encryption for support vector machine model. Our approach aims to train the model on encrypted domain to preserve data and model privacy with the reduced communication between the servers. The proposed procedure includes our protocol, data structure and homomorphic evaluation.

-

As machine learning models have been effectively applied to various real-world problems, collecting data from various sources became crucial for many service providers (Park, Hah, and Lee 2017) . In this situation, privacy issues have become a major problem in the learning society. Therefore, it is necessary to preserve the privacy of the data and the security of the learning process without compromising the performance of the learning algorithms.

Homomorphic encryption (HE) enables computations on encrypted data (ciphertext) which are equivalent to operations on decrypted data (plaintext) (Gentry 2009) . In recent years, privacy-preserving machine learning applications have developed, but they have high computational cost and huge memory burden. Cheon et al. developed a homomorphic encryption scheme for approximate arithmetic (HEAAN) (Cheon et al. 2017) .

Support vector machine (SVM) is one of the most effective machine learning algorithms for classification (Cortes and Vapnik 1995) . The training data and the model parameters should be protected to apply the SVM model to the security-preserving scenario. Therefore, in this paper, we propose the implementation for the training phase of the SVM classifier on the encrypted domain with the HEAAN scheme. Copyright held by authors as additions and multiplications on encrypted data. Recently, HEAAN scheme (Cheon et al. 2017) was developed to carry out approximate computations efficiently.

For the (leveled) HEAAN of depth L, we set the parameters such as a power of two M 0, integers p, q0, qL = pL q0, h and P , and a real for -bit security. The specifications of the algorithm are as follows. - (pk; sk; evk) KeyGen(1 ) - ~c Encrypt(pk, m): Sample ~r 2 R2 and e0; e1 DGqL ( 2).

Output ~c ~r pk + (m + e0; e1) 2 Rq2L . - m Decrypt(sk, ~c = (c0; c1)): Output m c0 + c1 s mod q`. - cadd Add(~c1, ~c2): Output ~cadd ~c1 + ~c2 mod q`. - cm~ult Mult(~c1, ~c2): Set c1 = (b1; a1) and c2 = (b2; a2). Let (d0; d1; d2) (b1 b2; a1 b2+a2 b1; a1 a2) 2 Rq3` . Output ~cmult (d0; d1) + b P1 (d2 evk (mod P q`))e 2 Rq2` . - ~c0 Rescaling`!`0 (~c): For a level ` ciphertext ~c, output ~c0 b qq``0 ~ce 2 Rq2`0 at level `0.

For more details, we recommend to see (Cheon et al. 2017) .

Least Square Support Vector Machine

The SVM aims to find the maximum margin hyperplane, given the training examples f(x1; y1); :::; (xn; yn)g Rd f 1; 1g. To train the SVM model over encrypted data, we used a nonlinear least-square SVM with a basis function (x) : Rd ! Rl that minimizes the following optimization problem (Suykens and Vandewalle 1999) : 1 Pn n i=1 ei + kwk2 (1) min w;b;ei ei; 8i = 1; : : : ; n; where w 2 Rl. To solve the problem (1), we construct the Lagrangian function: L(w; b; e; ) = kwk2 + n1 Pin=1 ei2 Pin=1 if[w (xi)+b]+ei 1g. With the optimality conditions of the Lagrangian function, the following linear system is obtained by removing w and e:

Ab = 0 y yT + In b = where 2 R(n+1) (n+1) s.t. i;j = k(xi; xj ). We introduce an additional least square problem with gradient descent method for the system (2), which convergence can be guaranteed by the well-posedness of. The matrix A can be decomposed as follows:

1 A = ( y 1 yT ) where represents a Hadmard product. By Schur product theorem, the first term becomes PSD with Mercer kernel. Therefore, the linear system (2) is well-posed with some > 0, and the convergence of iterative method can be gauranteed. With these design components, the intermediate dycryptions for training the SVM model can be reduced.

Implementation

In this paper, we propose a protocol which can reduce the communication to construct kernel matrix and to learn the model parameters with FHE operations. Figure 1 illustrates the whole procedure of our protocol which secures serverside and data provider-side information because all operations can be performed on encrypted domain.

Data Structure

As mentioned previously, we first compute the kernel matrix from the encrypted data. For simplicity, we assume that the kernel matrix is encrypted as a ciphertext. We want to build a parallelizable procedure because of computational cost and large memory of ciphertext. The HEAAN scheme supports slot-wise operation over ciphertext, so the operations of matrices should be replaced with addition and Hadmard product. We propose data structure for calculating the inner product matrix. Assume that Z 2 Rn d and ZZT ; Z^j 2 Rn n.

ZZT = Z^ 1 ^ 1T + Z + Z^ d

Z^ dT ; Z = 64 ...

2z11 zn1 . . .

... 75 ; Z^ j = 64 ...

2z1j z1j z2j . .

. z2j . . .

znj 3

... 75 : znj The multiplication of cihpertexts in this operation can be performed on d different machines in parallel.

Secure-Preserving Iterative Training

In this study, to efficiently implement the gradient descent method, we utilize the symmetricity of the matrix (3) in matrix multiplication. To learn b, the updated equation is bk+1 = bk AT (Abk 1~). Matrix-vector multiplication on the encrypted domain is efficiently implemented by rotating the slots. We used pre-computed AT A by using the symmetric property instead of two matrix-vector multiplications per iteration. Therefore, the resulting update equation is bk+2 = Mbk c, where M = (I AT A)2 and c = ((1 + )I AT A)AT b are pre-computed.

Comparison

Our procedure replaces the dual convex optimization with numerical gradient descent to implement the securitypreserving LSSVM. To illustrate the result of this replacement, we compare the classification performances with RBF and polynomial kernels for some real datasets used in (Suykens and Vandewalle 1999) . Table 1 shows that the replacement does not severely affect the performances. From this results, we can expect to develop a secure-preserving SVM without compromising the performance.

Conclusion

In this paper, we present a new framework to train the LSSVM model using HEAAN. This framework includes protocol, data structure and secure-preserving iterative training procedure. Our method considers the reduction of computational cost and memory burden that are the common problem for the application of HE scheme. The proposed solution can be helpful to show the potential for the practical utilization of machine learning models without concerns on security and privacy issues.

Acknowledgement

This work was supported in part by NRF of Korea grants No. 2018R1D1A1A02085851, 2016R1A2B3014030 and 2017R1A5A1015626.

References

[Cheon et al. 2017] Cheon , J. H. ; Kim , A. ; Kim , M. ; and Song, Y.

2017. Homomorphic encryption for arithmetic of approximate numbers . In ASIACRYPT 2017 , 409 - 437 . Springer.

[Cortes and Vapnik 1995 ] Cortes, C. , and Vapnik , V. 1995 .

Support-vector networks . Machine learning 20(3) : 273 - 297 .

[Gentry 2009] Gentry, C. 2009 . A fully homomorphic encryption scheme . Ph.D. Dissertation , Stanford University. http: //crypto.stanford.edu/craig.

[Park, Hah, and Lee 2017] Park, S. ; Hah , J.; and Lee , J. 2017 . Inductive ensemble clustering using kernel support matching . Electronics Letters 53 ( 25 ): 1625 - 1626 .

[Suykens and Vandewalle 1999 ] Suykens, J. A. , and Vandewalle , J.

1999. Least squares support vector machine classifiers . Neural processing letters 9 (3) : 293 - 300 .