# Multiparty Homomorphic Machine Learning with Data Security and Model Preservation

Authors: Fengtian Kuang; Bo Mi; Yang Li; Yuan Weng; Shijie Wu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

With the widespread application of machine learning (ML), data security has been a serious issue. To eliminate the conflict between data privacy and computability, homomorphism is extensively researched due to its capacity of performing operations over ciphertexts. Considering that the data provided by a single party are not always adequate to derive a competent model via machine learning, we proposed a privacy-preserving training method for the neural network over multiple data providers. Moreover, taking the trainer’s intellectual property into account, our scheme also achieved the goal of model parameter protection. Thanks to the hardness of the conjugate search problem (CSP) and discrete logarithm problem (DLP), the confidentiality of training data and system model can be reduced to well-studied security assumptions. In terms of efficiency, since all messages are coded as low-dimensional matrices, the expansion rates with regard to storage and computation overheads are linear compared to plaintext implementation without accuracy loss. In reality, our method can be transplanted to any machine learning system involving multiple parties due to its capacity of fully homomorphic computation.


---

## Body

## 1. Introduction

With the continuous development of artificial intelligence, data have become precious resources due to their value for mining. Nevertheless, numerous private information is embodied as data, which may be abused to violate personal privacy, business secrets, or even state secrets. For example, once a patient’s medical record is exposed to insurance companies, they may never sell him some kind of medical insurance [1]. Similarly, many other machine learning applications have also caught sight of privacy infringements, such as financial analysis, product customization, and public opinion surveillance [2–4]. On the other hand, any data-driving mechanism heavily relies on the quantity and quality of information, which brings about the conflict between data usability and data confidentiality. Fortunately, secure multiparty computation (SMC) [5–7] and homomorphic encryption (HE) [8, 9] provide us powerful tools to process data in a concealed manner. Therefore, the remaining problem to address is how to devise a cryptosystem that is applicable for machine learning in consideration of storage and computation overheads.As a cryptographic technology orienting decentralized systems, secure multiparty computation aims at data confidentiality for distributed participants. Despite the privacy concern, the involved parties can still figure out a public output as they wish. Based on such cryptosystem, F. Ö. Çatak et al. [10] proposed a privacy-preserving learning protocol for classification in virtue of vertically segmented data from multiple parties. Since the data is just partially shared without concealing, semantic security is unachievable as plain data dose. The first provable secure ML protocol of this kind is presented by R. Devin et al. [11] for text classification. Howbeit, their research only focused on the privacy of data classification and left the learning process unaddressed.Oriented at centralized systems, homomorphic encryption is another way towards secure machine learning, which is capable of performing specific operations over ciphertexts. Researches of applying FE for data privacy during machine learning have developed rapidly since the significant innovation [12] appeared in 2016. Y. Aono et al. [13] combined the additive homomorphism with deep learning to narrow the gap between system functionality and data security, by applying FH technology to asynchronous stochastic gradient descent algorithm. F. Bourse et al. [14] improved the FHE structure of Chillotti et al. [15] and proposed a homomorphic neural network evaluation framework, namely, FHE-DiNN. Its complexity is strictly linear in network depth, but the model parameters must be proactively predefined. Based on a multikey variant of two HE schemes [16, 17] with ciphertexts packed, H. Chen et al. [18] provided a suite of interfaces for secure machine learning which also exploited bootstrapping for arbitrary circuit evaluation. As matter of fact, almost all existing FHE-based machine learning algorithms are based on the algebraic structure of lattice, such as BGV [19–21], CKKS [22–24], and NTRU [25–27]. These methods suffer from a common defect that decryption may fail due to noise growth. Though bootstrapping can be deemed as an effective tool for noise control, its extra computational burden is hardly acceptable. Surprisingly, J. Li et al. [28] discovered an alternative tool, saying Conjugate Search Problem, to actualize full homomorphism without noise interference. They also applied such cryptosystem for privacy-preserving data training, which achieved the same accuracy as the plaintexts used for learning.Though more comprehensible and effective than lattice-based secure machine learning, Li’s scheme can only be applied to the scenario of a signal data provider. Ordinarily, one party can always provide a small quantity of data which may incur an overfitted model. To ensure the generalization of machine learning, data from diverse sources should be gathered for a specific learning task. In the circumstances of multiparty secure machine learning, each data provider may conceal their information by a dependent key. Therefore, a training framework that operates over heterogeneous (i.e., encrypted by different keys) ciphertext is desiderated. Conversely, the parameters of the system model should be taken as assets held by the trainer as in general business operation. Thus, we should also make sure that the machine is concealed, even when not thoroughly trained.To preserve the privacy of all participants, this paper presents a complete machine learning mechanism in virtue of CSP and DLP hardness. Our contributions are summarized as follows.


### 1.1. Contributions

(1)
We coded float-type data as low-dimensional upper triangular matrices that are homomorphic under the operations of addition, subtraction, multiplication, division, and comparison. With the help of CSP, the plain matrices can also be projected to semantically secure ciphertexts homomorphically under the same kind of operations. That is to say, our basic cryptosystem is fully homomorphic, since addition and multiplication are simultaneously implemented. Therefore, we can realize secure training and classification/regression once private data are provided under the same key.(2)
We constructed a cyclic group by lifting the plain matrices to a Galois domain. Thereafter, key switching (switch a ciphertext encrypted by one key to another) is made possible via DLP for the purpose of cooperative training.(3)
We combined the two aforementioned technologies and devised a secure machine learning protocol under semihonest model, which preserves the privacy of multiple data providers as well as that of the trainer.


## 1.1. Contributions

(1)
We coded float-type data as low-dimensional upper triangular matrices that are homomorphic under the operations of addition, subtraction, multiplication, division, and comparison. With the help of CSP, the plain matrices can also be projected to semantically secure ciphertexts homomorphically under the same kind of operations. That is to say, our basic cryptosystem is fully homomorphic, since addition and multiplication are simultaneously implemented. Therefore, we can realize secure training and classification/regression once private data are provided under the same key.(2)
We constructed a cyclic group by lifting the plain matrices to a Galois domain. Thereafter, key switching (switch a ciphertext encrypted by one key to another) is made possible via DLP for the purpose of cooperative training.(3)
We combined the two aforementioned technologies and devised a secure machine learning protocol under semihonest model, which preserves the privacy of multiple data providers as well as that of the trainer.


## 2. System Model

Neural network (NN) is employed as the engineering background and verification model in this paper due to its extensive application. Nevertheless, it is worth mentioning that our scheme can be applied to most machine learning algorithms if privacy is significant to multiple participants.


### 2.1. Neural Network Model

A typical neural network contains three or more layers, which turns into a deep learning model if hidden layers are multiple [29]. The certain principle of NN lies in the fact that numerous neurons can automatically extract features of the inputs layer by layer. Besides the topology of NN, the most important factors that defined it are the weights and bias designated to each link and neuron. As for learning, the essence is how to adjust these parameters in virtue of training data via iterative forward-/back-propagation. Thereafter, to securely implement a neural network model, we should homomorphically evaluate the following functions.Forward calculation (e.g., sigmoid):(1)ffw=sigmoidai,wi+bi,whereai and wi are the input and weight vectors corresponding to the proactive links of neuron i, while bi represents its bias.Backward calculation:Loss function (e.g., quadratic loss function):(2)fbw_loss=LY|fX=∑ntn−on2,wheretn is the target value and on is the actual value.Parameter adjusting (e.g., gradient descent):(3)fbw_adj=oldwj,k−Δwj,k,(4)Δwj,k=α⋅Ek⋅Ok1−Ok⋅OjT,where Ek is the error vector between the target value and the actual value, OjT is the transpose of the output of the current layer node, and Ok is the output of the node of the next layer.


### 2.2. System Model and Security Goal

In our system, a powerful trainer expects to acquire a neural network whose topology is predefined. To ensure the completeness of the resultant model, they may request multiple parties for training data. However, the data providers concern about privacy leakage though they have strong wills to cooperate. Meanwhile, the trainer also worries that the system parameters may expose and infringe their intellectual property. Therefore, we should preserve the privacy of all participants and guarantee the functionality of machine learning at the same time. Moreover, taking the trained neural network as a service, a user may not only desire to designate a classification/regression task to the server but also be anxious about data abuse.


### 2.3. Adversary Model

Suppose that the trainer and all data providers are honest but curious during the whole process. That is to say, they will completely follow the protocol to avoid unnecessary disputes but may be interested in the privacy contained within the data. Furthermore, it is reasonable to assume that both the trainer and data owner are provided with PPT (probabilistic polynomial time) computational power. However, since the trainer is always better equipped than data providers, the hypothesis that they have the accessibility to a quantum machine may also be valid. To define the success of privacy violation, we exploit the concept of symmetric IND-CPA (indistinguishability under chosen-plaintext attack) as below.


### 2.4. Symmetric IND-CPA [30]

Define an experiment under symmetric cryptosystemSE=SE.KeyGen,SE.Enc,SE.Dec as(5)ExpHE,ACPAκ:k←HE.KeyGenκ,M0,M1←AHE.Enck⋅⋅,forM0=M1,γ←R0,1,C∗=HE.DecMγ,γ′=AC∗,Output1,ifγ=γ′,and0otherwise,for any PPT adversary A that queries the oracle HE.Enck⋅ polynomial times. Thus, the adversary’s advantage can be expressed by(6)AdvHE,ACPAκ=PrExpHE,ACPAλ=1−12.Then the cryptosystemSE is IND-CPA-secure if AdvHE,ACPAκ<ϵκ, where ϵκ stands for a negligible function in the security parameter κ.


## 2.1. Neural Network Model

A typical neural network contains three or more layers, which turns into a deep learning model if hidden layers are multiple [29]. The certain principle of NN lies in the fact that numerous neurons can automatically extract features of the inputs layer by layer. Besides the topology of NN, the most important factors that defined it are the weights and bias designated to each link and neuron. As for learning, the essence is how to adjust these parameters in virtue of training data via iterative forward-/back-propagation. Thereafter, to securely implement a neural network model, we should homomorphically evaluate the following functions.Forward calculation (e.g., sigmoid):(1)ffw=sigmoidai,wi+bi,whereai and wi are the input and weight vectors corresponding to the proactive links of neuron i, while bi represents its bias.Backward calculation:Loss function (e.g., quadratic loss function):(2)fbw_loss=LY|fX=∑ntn−on2,wheretn is the target value and on is the actual value.Parameter adjusting (e.g., gradient descent):(3)fbw_adj=oldwj,k−Δwj,k,(4)Δwj,k=α⋅Ek⋅Ok1−Ok⋅OjT,where Ek is the error vector between the target value and the actual value, OjT is the transpose of the output of the current layer node, and Ok is the output of the node of the next layer.


## 2.2. System Model and Security Goal

In our system, a powerful trainer expects to acquire a neural network whose topology is predefined. To ensure the completeness of the resultant model, they may request multiple parties for training data. However, the data providers concern about privacy leakage though they have strong wills to cooperate. Meanwhile, the trainer also worries that the system parameters may expose and infringe their intellectual property. Therefore, we should preserve the privacy of all participants and guarantee the functionality of machine learning at the same time. Moreover, taking the trained neural network as a service, a user may not only desire to designate a classification/regression task to the server but also be anxious about data abuse.


## 2.3. Adversary Model

Suppose that the trainer and all data providers are honest but curious during the whole process. That is to say, they will completely follow the protocol to avoid unnecessary disputes but may be interested in the privacy contained within the data. Furthermore, it is reasonable to assume that both the trainer and data owner are provided with PPT (probabilistic polynomial time) computational power. However, since the trainer is always better equipped than data providers, the hypothesis that they have the accessibility to a quantum machine may also be valid. To define the success of privacy violation, we exploit the concept of symmetric IND-CPA (indistinguishability under chosen-plaintext attack) as below.


## 2.4. Symmetric IND-CPA [30]

Define an experiment under symmetric cryptosystemSE=SE.KeyGen,SE.Enc,SE.Dec as(5)ExpHE,ACPAκ:k←HE.KeyGenκ,M0,M1←AHE.Enck⋅⋅,forM0=M1,γ←R0,1,C∗=HE.DecMγ,γ′=AC∗,Output1,ifγ=γ′,and0otherwise,for any PPT adversary A that queries the oracle HE.Enck⋅ polynomial times. Thus, the adversary’s advantage can be expressed by(6)AdvHE,ACPAκ=PrExpHE,ACPAλ=1−12.Then the cryptosystemSE is IND-CPA-secure if AdvHE,ACPAκ<ϵκ, where ϵκ stands for a negligible function in the security parameter κ.


## 3. Cryptographic Construction

Focusing on the security goals presented in the system model, we are now ready to construct our cryptographic building blocks. In this part, we first explore the homomorphism of conjugate search problem to underpin the functionality of training over homogeneous (i.e., encrypted by the same key) ciphertexts. Then, we present a key switching technology that can convert a ciphertext encrypted by one key to be decryptable by another.Conjugate search problem is a special form of group factorization problem (GFP) [31], defined as follows.


### 3.1. Conjugate Search Problem (CSP) [31]

GivenC,M∈Ψ×Ψ over a nonabelian algebraic structure Ψ, it is intractable to solve H∈Ψ such that C=HMH−1.B. Evgeni [32] proved that the CSP is postquantum secure over the general linear group GLdR (R means real number field) if d≥4. Hence, to assure system security, we should code the message as a matrix with degree larger than 4.To protect the privacy of data providers without affecting the accuracy of training, we resort to homomorphic encryption that is capable of actualizing the forward-/backward-propagation processes covertly. Thereafter, we devised a way that makes CSP semantically secure and homomorphic. It is worth noting that the conjugate search problem is resistant to quantum attacks, which dispels the privacy concern for data providers even if the trainer is extremely equipped.A typical homomorphic encryption algorithm can be noted as a tetradHE=HE.KeyGen,HE.Enc,HE.Dec,HE.Eval, standing for the functions of key generation, encryption, decryption, and evaluation, respectively.For any datam over the message space R, we first code it as an upper triangular matrix M∈R6×6 as follows.


### 3.2. Encoding

Convert the messagem into three pairs of random numbers a1,a2, a3,a4, and a5,a6, satisfying a1+a2=m, a3+a4=a5+a6=r, and a32−a42a52−a62=1, where r is a constant random number of the system. Thus, we can construct the following matrices:(7)M1=a1a2a2a1,M2=a3a4a4a3,M3=a5a6a6a5.Combining the above matrices, the messagem is finally coded as(8)M=M1R1R20M2R300M3,where 0 represents the 2×2 all-zero matrix and Rii=1,2,3 stands for random matrices uniformly sampled from R2×2.For clarity, we denote the space of coded messages asΓ. It is interesting that Γ naturally constitutes a multiplicative cyclic group (excluding the elements whose determinants are zero) and R∼Γ (homomorphic). Furthermore, it is well known that all square matrices with the same dimension compose a ring. Though Γ⊆R6×6 and its elements are commutative for multiplication, there is an overwhelming probability that a matrix P uniformly sampled from R6×6 is noncommutative with the coded message M. Thereupon, a CSP-based fully homomorphic encryption algorithm can be actualized as below.


### 3.3. Key Generation

HE.KeyGen1κ: uniformly sample a matrix from R9×9, which can also be represented as a combination of nine 6×6 random matrices, namely,(9)P=P1P2P3P4P5P6P7P8P9,forPi=pi1pi2pi3pi4,i=1,2,…,9.The probability thatP is communitive with elements in Γ should be negligible. Then, the algorithm takes k=P as the symmetric key.


### 3.4. Encryption

HE.EncP,M: output(10)C=PMP−1=PM1R1R20M2R300M3P−1as the ciphertext of message m (coded as a matrix M).


### 3.5. Decryption

HE.DecP,C: compute M=P−1CP to obtain(11)M1=a1a2a2a1.Then, figure outm=a1+a2 to recover the plaintext.


### 3.6. Evaluation

HE.Evalf,C1,…,Cl: We describe the very basic operations underpinning formulae (2)-(4) in advance. Suppose that C1 and C2 are ciphertexts corresponding to m1 and m2 under the same key; the additive and multiplicative arithmetic can be simply carried out by Cadd=C1+C2 and Cmul=C1C2. These two operations can be trivially assembled to realize the functions for backward propagation. However, since the exponential operation cannot be implemented directly via homomorphic addition and multiplication, some activation functions of forward propagation such as sigmoid should be approximated as the form of polynomials. Thereby, we resort to a specific conversion [32–34],(12)sigmodx=0.000734x4+0.014222x3+0.108706x2+0.392773x+0.571859,−∞<x≤−1.5,0.002083x5+0.020833x3+0.25x+0.5,−1.5<x≤1.5,−0.000734x4+0.014222x3−0.108706x2+0.3922773x+0.428141,1.5<x<∞,to replace(13)sigmodx=11+e−x.Noting that the aforementioned formula is expressed as a piecewise function, to homomorphically decide which subfunction should be carried out, we can encrypt the numbers of−1.5 and 1.5 and compare them with x for branching.To program a piecewise function, J. Li et al. [28] presented a homomorphic algorithm that covertly compares the size between two ciphertexts. Though our scheme is similar to that of [28], we argue that their cryptosystem is not semantically secure because a2i−1+a2i=m and a2i−1 is always bigger than a2i for i=1,2,3.


### 3.7. Security Analysis of [28]

By computing(14)detC∗−TC′=detPdetM1∗−tM1′R1∗R2∗0M2∗−tM2′R3∗00M2∗+tM2′detP−1,where Ri∗ is also a random matrix, for(15)T=tR1R20tR300t,where(16)t=0110,and Rii=1,2,3 is uniformly sampled from R2×2, the adversary carries out a chosen-plaintext attack such as the following.ExpHE,ACPAκ:,k←HE.KeyGenκ,M0,M1,C′←AHE.Enck⋅⋅,,forM0=M1,C′=HE.EnckM′,andM0<M′<M1,γ←R0,1,C∗=HE.DecMγ,γ′=1ifdetC∗−TC′,andγ′=0otherwise,Output1,ifγ=γ′,and0otherwise.Considering that(17)detC∗−TC′=detPdetM1∗−tM1′detM2∗−tM2′detM3∗−tM3′detP−1,i=1,2,3,where(18)detMi∗−tMi′=a2i−1∗−a2i′2−a2i∗−a2i−1′2,=m∗−m′a2i−1∗−a2i∗+a2i−1′−a2i′,since a2i−1>a2i is guaranteed throughout Li’s scheme [28], a2i−1∗−a2i∗+a2i−1′−a2i′ must be positive. It is obvious that detPdetP−1=1; hence, the adversary can easily determine whether m∗=m0 or m∗=m1 by checking the sign of detC∗−TC′. That is to say,(19)AdvHE,ACPAκ=PrExpHE,ACPAκ=1−12=1.It seems that the conflict between piecewise function evaluation and IND-CPA security is infeasible to address. However, we can introduce a specific form of ciphertext which can be used to encrypt a designated number and compare it with any other normal ciphertext. Our construction is given below.The data provider randomly chooses a nonzero numberk∈R−0 and encrypts m′ as(20)C′=PM′P−1=PkM1′R1R20kM2′R300kM3′P−1,for(21)Mi′=ai1′ai2′ai3′ai4′,i=1,2,3,which satisfies(22)ai1′+ai4′=k≠0,i=1,2,3,ai2′+ai3′=−k≠0,i=1,2,3,ai1′ai4′−ai2′ai3′=m′,i=1,ai1′ai4′−ai2′ai3′=r,i=2,3.To compareC′ with general cipher C∗ without decryption, the evaluator computes(23)Δ=detC∗C′detC′−detC∗−C′=k2m∗−m′and thus achieves(24)Ccomp=m∗>m′ifΔ>0,m∗>m′ifΔ=0,m∗>m′ifΔ<0.


### 3.8. Correctness

The correctness of encryption and decryption algorithms is straightforward, so we only focus on the homomorphism of evaluation.Homomorphic addition: since(25)Cadd=C1+C2,=P−1M11R11R120M12R1300M13P+P−1M21R21R220M22R2300M23P,=P−1M11+M21R11+R21R12+R220M12+M22R13+R2300M13+M23P,we can decrypt it as(26)Madd=PC1+C2P−1,=M11+M21R11+R21R12+R220M12+M22R13+R2300M13+M23because(27)M11+M21=a11+a21a12+a22a12+a22a11+a21.The addition ofm1 and m2 can be decoded as(28)madd=a11+a21+a12+a22=m1+m2.Homomorphic multiplication: because(29)Cmul=C1C2,=P−1M11R11R120M12R1300M13M21R21R220M22R2300M23P,=P−1M11M21R1∗R2∗0M12M22R3∗00M13M23P,M11M21=a11a21+a12a22a11a22+a12a21a12a21+a11a22a12a22+a11a21,we can deduce that(30)a11a21+a12a22+a11a22+a12a21=a11+a12a21+a22=m1m2.Homomorphic comparison: on the premise ofdetPdetP−1=1, it can be seen that(31)Δ=detC∗C′detC′−detC∗−C′,=detM∗M′detM′−detM∗−M′a,=∏i=13detMi∗kMi′detkMi′−∏i=13detMi∗−kMi′.According to formula (21), we have(32)detMi∗kMi′detkMi′=a2i−1∗2−a2i∗2,detMi∗−Mi′=a2i−1∗2−a2i∗2−k22ia2i−1∗+a2i∗−detMi′,i=1,2,3.Recall thata2i−1∗+a2i∗=m∗ and ai1′ai4′−ai2′ai3′=m′ when i=1, while a2i−1∗+a2i∗=ai1′ai4′−ai2′ai3′=r when i=2,3. In terms of the condition that a32−a42a52−a62=1, we can reduce formula (30) to(33)Δ=k2m∗−m′.It is obvious that the signs ofΔ and m∗−m′ are exactly the same, since k2>0, which determines the relationship between m∗ and m′ without decryption.


### 3.9. Security

Thanks to the hardness of Conjugate Search Problem, an adversary must findP such that P−1CP=M to recover the plaintext. As for the semantic security of our scheme, it can be seen that a2i−1∗−a2i∗+a2i−1′−a2i′ in formula (17) is not always positive due to arbitrary relationship between a2i−1 and a2i. Therefore, when an adversary executes a chosen-plaintext attack as mentioned before, their advantage is negligible. Noting that any normal ciphertext can just be compared with specifically encrypted messages without decryption, the data provider has full control over their privacy and permits exact comparisons only if necessary.After each training, the neural network coefficients are concealed by the key of the data provider. When multiple data providers take part in the training process, those semimanufactured parameters should also be re-encrypted under the key of subsequent data holder for homomorphic computation. Therefore, we devised a way to decrypt and re-encrypt the machine coefficients without exposing them to data providers, in consideration of the trainer’s property right. Our key switching scheme is based on the hardness of Discrete Logarithm Problem (DLP).


### 3.10. Discrete Logarithm Problem

Given a cyclic groupG, a generator g∈G, and a random element h∈G, it is difficult to find the discrete logarithm a such that ga=h.Accordingly, if an adversary has obtained a ciphertexty=hb=gab∈G, it is hard for them to recover h because of the confidentiality on ab [35]. However, in light of the Lagrange theorem [36], we can exploit a trapdoor to reverse y back to h.


### 3.11. Lagrange Theorem

DenoteH as a subgroup of finite G; then, H|G, for H and G are the orders of groups H and G.Since anyh∈G generates a subgroup H⊆G via H=ha|a∈Z, we can conclude that hG=e in terms of the Lagrange theorem, where e is the identity of group G.Based on the aforementioned mathematical tools, we are now ready to construct our key switching scheme as a triadKS=KS.KeyGen,KS.CSPtoDLP,KS.DLPtoCSP. Without loss of generality, we denote kt=b,s, kA=PA, and kB=PB as secret keys belonging to the trainer T and two data providers A and B, respectively. Then KS.KeyGen can be used to generate the encryption/decryption key pair for the trainer, while KS.CSPtoDLP is used to convert a ciphertext CA encrypted by kA to be decryptable by kt and KS.CSPtoDLP is utilized to modify Ct (encrypted under kt) as CB whose corresponding key is kB.


### 3.12. Key Generation

KS.KeyGen1κ: as mentioned before, we denote the space of coded messages as Γ. Suppose that the precision of matrix elements in HE is l-bits whose integer part is m-bits and the decimal part is n-bits. We can multiply any coded plaintext M by 2n to lift it over Z2l6×6. Accordingly, the message space is changed to a cyclic group Γ′ for Γ′=212l2l−13. Moreover, for each 2nMi, it composes a group Γi′ satisfying Γi′=2l−1. Thereby, we uniformly sample an odd number b∈Z2l−1 and compute s∈Z2l−1 such that s⋅b=1mod2l−1. Output kt=b,s as the key to the trainer.


### 3.13. SwitchingCA to CtKS.CSPtoDLPCA

The trainerT changes the encrypted model parameters CA as CA′=2nCAmod2l∈Z2l6×6 and sends CAt=CA′bmod2l to data provider A. On receiving CAt, A computes Ct=PA−1CAtPAmod2l as their response.


### 3.14. SwitchingCt to CBKS.DLPtoCSPCt

On receivingCt from the trainer T, the data provider B computes their response as CtB=PBCtPB−1mod2l. Therefore, the trainer T can reverse CtB back to a ciphertext CB=PBMPB−1 purely encrypted under kB via CB′=CtBsmod2l and then right-shift its elements by n-bits.


### 3.15. Correctness

SinceCA′=PA2nMPA−1mod2l, we have(34)CAt=PA2nMPA−1PA2nMPA−1,…,PA2nMPA−1︸btimes=PA2nMbPA−1mod2l.Thus,Ct=PA−1PA2nMbPA−1PA=2nMbmod2l.Similarly, becauseCtB=PB2nMbPB−1mod2l,(35)CB′=PB2nMb⋅sPB−1mod2l,=PB2nM11+k12l−1R1∗R2∗02nM21+k32l−1R3∗002nM31+k32l−1PB−1,where ki are integers for i=1,2,3.During the encoding process inHE, it is easy to choose a2i−1 such that 2na2i−1≠0mod2l. Considering that a1+a2=m and a2i−1+a2i=r for i=1,2, the space of 2nMi must be a cyclic group Γi′ for Γi′=2l−1. According to the Lagrange Theorem, it can be seen that 2nMi1+ki2l−1=2nMimod2l; thus CB′=PB2nMPB−1mod2l. By right-shifting n-bits on CB′, we obtain CB=PBMPB−1.


### 3.16. Security

Note that, after receivingCAt, the trainer can trivially compute M=Ctsmod2l/2n to recover the message. Nevertheless, since the model parameters are of their intellectual property, such operation does not conflict with our security goal.As for data providers, they can just witness an exponential form of the plaintext (i.e.,Ct=2nMbmod2l). According to the hardness of DLP, the information about message M will not be exposed.


## 3.1. Conjugate Search Problem (CSP) [31]

GivenC,M∈Ψ×Ψ over a nonabelian algebraic structure Ψ, it is intractable to solve H∈Ψ such that C=HMH−1.B. Evgeni [32] proved that the CSP is postquantum secure over the general linear group GLdR (R means real number field) if d≥4. Hence, to assure system security, we should code the message as a matrix with degree larger than 4.To protect the privacy of data providers without affecting the accuracy of training, we resort to homomorphic encryption that is capable of actualizing the forward-/backward-propagation processes covertly. Thereafter, we devised a way that makes CSP semantically secure and homomorphic. It is worth noting that the conjugate search problem is resistant to quantum attacks, which dispels the privacy concern for data providers even if the trainer is extremely equipped.A typical homomorphic encryption algorithm can be noted as a tetradHE=HE.KeyGen,HE.Enc,HE.Dec,HE.Eval, standing for the functions of key generation, encryption, decryption, and evaluation, respectively.For any datam over the message space R, we first code it as an upper triangular matrix M∈R6×6 as follows.


## 3.2. Encoding

Convert the messagem into three pairs of random numbers a1,a2, a3,a4, and a5,a6, satisfying a1+a2=m, a3+a4=a5+a6=r, and a32−a42a52−a62=1, where r is a constant random number of the system. Thus, we can construct the following matrices:(7)M1=a1a2a2a1,M2=a3a4a4a3,M3=a5a6a6a5.Combining the above matrices, the messagem is finally coded as(8)M=M1R1R20M2R300M3,where 0 represents the 2×2 all-zero matrix and Rii=1,2,3 stands for random matrices uniformly sampled from R2×2.For clarity, we denote the space of coded messages asΓ. It is interesting that Γ naturally constitutes a multiplicative cyclic group (excluding the elements whose determinants are zero) and R∼Γ (homomorphic). Furthermore, it is well known that all square matrices with the same dimension compose a ring. Though Γ⊆R6×6 and its elements are commutative for multiplication, there is an overwhelming probability that a matrix P uniformly sampled from R6×6 is noncommutative with the coded message M. Thereupon, a CSP-based fully homomorphic encryption algorithm can be actualized as below.


## 3.3. Key Generation

HE.KeyGen1κ: uniformly sample a matrix from R9×9, which can also be represented as a combination of nine 6×6 random matrices, namely,(9)P=P1P2P3P4P5P6P7P8P9,forPi=pi1pi2pi3pi4,i=1,2,…,9.The probability thatP is communitive with elements in Γ should be negligible. Then, the algorithm takes k=P as the symmetric key.


## 3.4. Encryption

HE.EncP,M: output(10)C=PMP−1=PM1R1R20M2R300M3P−1as the ciphertext of message m (coded as a matrix M).


## 3.5. Decryption

HE.DecP,C: compute M=P−1CP to obtain(11)M1=a1a2a2a1.Then, figure outm=a1+a2 to recover the plaintext.


## 3.6. Evaluation

HE.Evalf,C1,…,Cl: We describe the very basic operations underpinning formulae (2)-(4) in advance. Suppose that C1 and C2 are ciphertexts corresponding to m1 and m2 under the same key; the additive and multiplicative arithmetic can be simply carried out by Cadd=C1+C2 and Cmul=C1C2. These two operations can be trivially assembled to realize the functions for backward propagation. However, since the exponential operation cannot be implemented directly via homomorphic addition and multiplication, some activation functions of forward propagation such as sigmoid should be approximated as the form of polynomials. Thereby, we resort to a specific conversion [32–34],(12)sigmodx=0.000734x4+0.014222x3+0.108706x2+0.392773x+0.571859,−∞<x≤−1.5,0.002083x5+0.020833x3+0.25x+0.5,−1.5<x≤1.5,−0.000734x4+0.014222x3−0.108706x2+0.3922773x+0.428141,1.5<x<∞,to replace(13)sigmodx=11+e−x.Noting that the aforementioned formula is expressed as a piecewise function, to homomorphically decide which subfunction should be carried out, we can encrypt the numbers of−1.5 and 1.5 and compare them with x for branching.To program a piecewise function, J. Li et al. [28] presented a homomorphic algorithm that covertly compares the size between two ciphertexts. Though our scheme is similar to that of [28], we argue that their cryptosystem is not semantically secure because a2i−1+a2i=m and a2i−1 is always bigger than a2i for i=1,2,3.


## 3.7. Security Analysis of [28]

By computing(14)detC∗−TC′=detPdetM1∗−tM1′R1∗R2∗0M2∗−tM2′R3∗00M2∗+tM2′detP−1,where Ri∗ is also a random matrix, for(15)T=tR1R20tR300t,where(16)t=0110,and Rii=1,2,3 is uniformly sampled from R2×2, the adversary carries out a chosen-plaintext attack such as the following.ExpHE,ACPAκ:,k←HE.KeyGenκ,M0,M1,C′←AHE.Enck⋅⋅,,forM0=M1,C′=HE.EnckM′,andM0<M′<M1,γ←R0,1,C∗=HE.DecMγ,γ′=1ifdetC∗−TC′,andγ′=0otherwise,Output1,ifγ=γ′,and0otherwise.Considering that(17)detC∗−TC′=detPdetM1∗−tM1′detM2∗−tM2′detM3∗−tM3′detP−1,i=1,2,3,where(18)detMi∗−tMi′=a2i−1∗−a2i′2−a2i∗−a2i−1′2,=m∗−m′a2i−1∗−a2i∗+a2i−1′−a2i′,since a2i−1>a2i is guaranteed throughout Li’s scheme [28], a2i−1∗−a2i∗+a2i−1′−a2i′ must be positive. It is obvious that detPdetP−1=1; hence, the adversary can easily determine whether m∗=m0 or m∗=m1 by checking the sign of detC∗−TC′. That is to say,(19)AdvHE,ACPAκ=PrExpHE,ACPAκ=1−12=1.It seems that the conflict between piecewise function evaluation and IND-CPA security is infeasible to address. However, we can introduce a specific form of ciphertext which can be used to encrypt a designated number and compare it with any other normal ciphertext. Our construction is given below.The data provider randomly chooses a nonzero numberk∈R−0 and encrypts m′ as(20)C′=PM′P−1=PkM1′R1R20kM2′R300kM3′P−1,for(21)Mi′=ai1′ai2′ai3′ai4′,i=1,2,3,which satisfies(22)ai1′+ai4′=k≠0,i=1,2,3,ai2′+ai3′=−k≠0,i=1,2,3,ai1′ai4′−ai2′ai3′=m′,i=1,ai1′ai4′−ai2′ai3′=r,i=2,3.To compareC′ with general cipher C∗ without decryption, the evaluator computes(23)Δ=detC∗C′detC′−detC∗−C′=k2m∗−m′and thus achieves(24)Ccomp=m∗>m′ifΔ>0,m∗>m′ifΔ=0,m∗>m′ifΔ<0.


## 3.8. Correctness

The correctness of encryption and decryption algorithms is straightforward, so we only focus on the homomorphism of evaluation.Homomorphic addition: since(25)Cadd=C1+C2,=P−1M11R11R120M12R1300M13P+P−1M21R21R220M22R2300M23P,=P−1M11+M21R11+R21R12+R220M12+M22R13+R2300M13+M23P,we can decrypt it as(26)Madd=PC1+C2P−1,=M11+M21R11+R21R12+R220M12+M22R13+R2300M13+M23because(27)M11+M21=a11+a21a12+a22a12+a22a11+a21.The addition ofm1 and m2 can be decoded as(28)madd=a11+a21+a12+a22=m1+m2.Homomorphic multiplication: because(29)Cmul=C1C2,=P−1M11R11R120M12R1300M13M21R21R220M22R2300M23P,=P−1M11M21R1∗R2∗0M12M22R3∗00M13M23P,M11M21=a11a21+a12a22a11a22+a12a21a12a21+a11a22a12a22+a11a21,we can deduce that(30)a11a21+a12a22+a11a22+a12a21=a11+a12a21+a22=m1m2.Homomorphic comparison: on the premise ofdetPdetP−1=1, it can be seen that(31)Δ=detC∗C′detC′−detC∗−C′,=detM∗M′detM′−detM∗−M′a,=∏i=13detMi∗kMi′detkMi′−∏i=13detMi∗−kMi′.According to formula (21), we have(32)detMi∗kMi′detkMi′=a2i−1∗2−a2i∗2,detMi∗−Mi′=a2i−1∗2−a2i∗2−k22ia2i−1∗+a2i∗−detMi′,i=1,2,3.Recall thata2i−1∗+a2i∗=m∗ and ai1′ai4′−ai2′ai3′=m′ when i=1, while a2i−1∗+a2i∗=ai1′ai4′−ai2′ai3′=r when i=2,3. In terms of the condition that a32−a42a52−a62=1, we can reduce formula (30) to(33)Δ=k2m∗−m′.It is obvious that the signs ofΔ and m∗−m′ are exactly the same, since k2>0, which determines the relationship between m∗ and m′ without decryption.


## 3.9. Security

Thanks to the hardness of Conjugate Search Problem, an adversary must findP such that P−1CP=M to recover the plaintext. As for the semantic security of our scheme, it can be seen that a2i−1∗−a2i∗+a2i−1′−a2i′ in formula (17) is not always positive due to arbitrary relationship between a2i−1 and a2i. Therefore, when an adversary executes a chosen-plaintext attack as mentioned before, their advantage is negligible. Noting that any normal ciphertext can just be compared with specifically encrypted messages without decryption, the data provider has full control over their privacy and permits exact comparisons only if necessary.After each training, the neural network coefficients are concealed by the key of the data provider. When multiple data providers take part in the training process, those semimanufactured parameters should also be re-encrypted under the key of subsequent data holder for homomorphic computation. Therefore, we devised a way to decrypt and re-encrypt the machine coefficients without exposing them to data providers, in consideration of the trainer’s property right. Our key switching scheme is based on the hardness of Discrete Logarithm Problem (DLP).


## 3.10. Discrete Logarithm Problem

Given a cyclic groupG, a generator g∈G, and a random element h∈G, it is difficult to find the discrete logarithm a such that ga=h.Accordingly, if an adversary has obtained a ciphertexty=hb=gab∈G, it is hard for them to recover h because of the confidentiality on ab [35]. However, in light of the Lagrange theorem [36], we can exploit a trapdoor to reverse y back to h.


## 3.11. Lagrange Theorem

DenoteH as a subgroup of finite G; then, H|G, for H and G are the orders of groups H and G.Since anyh∈G generates a subgroup H⊆G via H=ha|a∈Z, we can conclude that hG=e in terms of the Lagrange theorem, where e is the identity of group G.Based on the aforementioned mathematical tools, we are now ready to construct our key switching scheme as a triadKS=KS.KeyGen,KS.CSPtoDLP,KS.DLPtoCSP. Without loss of generality, we denote kt=b,s, kA=PA, and kB=PB as secret keys belonging to the trainer T and two data providers A and B, respectively. Then KS.KeyGen can be used to generate the encryption/decryption key pair for the trainer, while KS.CSPtoDLP is used to convert a ciphertext CA encrypted by kA to be decryptable by kt and KS.CSPtoDLP is utilized to modify Ct (encrypted under kt) as CB whose corresponding key is kB.


## 3.12. Key Generation

KS.KeyGen1κ: as mentioned before, we denote the space of coded messages as Γ. Suppose that the precision of matrix elements in HE is l-bits whose integer part is m-bits and the decimal part is n-bits. We can multiply any coded plaintext M by 2n to lift it over Z2l6×6. Accordingly, the message space is changed to a cyclic group Γ′ for Γ′=212l2l−13. Moreover, for each 2nMi, it composes a group Γi′ satisfying Γi′=2l−1. Thereby, we uniformly sample an odd number b∈Z2l−1 and compute s∈Z2l−1 such that s⋅b=1mod2l−1. Output kt=b,s as the key to the trainer.


## 3.13. SwitchingCA to CtKS.CSPtoDLPCA

The trainerT changes the encrypted model parameters CA as CA′=2nCAmod2l∈Z2l6×6 and sends CAt=CA′bmod2l to data provider A. On receiving CAt, A computes Ct=PA−1CAtPAmod2l as their response.


## 3.14. SwitchingCt to CBKS.DLPtoCSPCt

On receivingCt from the trainer T, the data provider B computes their response as CtB=PBCtPB−1mod2l. Therefore, the trainer T can reverse CtB back to a ciphertext CB=PBMPB−1 purely encrypted under kB via CB′=CtBsmod2l and then right-shift its elements by n-bits.


## 3.15. Correctness

SinceCA′=PA2nMPA−1mod2l, we have(34)CAt=PA2nMPA−1PA2nMPA−1,…,PA2nMPA−1︸btimes=PA2nMbPA−1mod2l.Thus,Ct=PA−1PA2nMbPA−1PA=2nMbmod2l.Similarly, becauseCtB=PB2nMbPB−1mod2l,(35)CB′=PB2nMb⋅sPB−1mod2l,=PB2nM11+k12l−1R1∗R2∗02nM21+k32l−1R3∗002nM31+k32l−1PB−1,where ki are integers for i=1,2,3.During the encoding process inHE, it is easy to choose a2i−1 such that 2na2i−1≠0mod2l. Considering that a1+a2=m and a2i−1+a2i=r for i=1,2, the space of 2nMi must be a cyclic group Γi′ for Γi′=2l−1. According to the Lagrange Theorem, it can be seen that 2nMi1+ki2l−1=2nMimod2l; thus CB′=PB2nMPB−1mod2l. By right-shifting n-bits on CB′, we obtain CB=PBMPB−1.


## 3.16. Security

Note that, after receivingCAt, the trainer can trivially compute M=Ctsmod2l/2n to recover the message. Nevertheless, since the model parameters are of their intellectual property, such operation does not conflict with our security goal.As for data providers, they can just witness an exponential form of the plaintext (i.e.,Ct=2nMbmod2l). According to the hardness of DLP, the information about message M will not be exposed.


## 4. Privacy-Preserving Machine Learning with Multiple Data Providers

To preserve privacy for machine learning, many cryptographic training and classification/regression methods have been proposed in the scene of a single data provider. In most cases, data should be sourced from multiple providers to guarantee the generality of training. Therefore, we present a secure machine learning mechanism with the capacity of training as well as classification/regression in consideration of data and parameter privacy.As for training, the cloud is supposed to obtain model parameters with the help of labeled data. During the initialization phase, the trainerT computes kt←KS.KeyGen1κ for key switching and each data provider i generates ki←HE.KeyGen1κ for homomorphic training.Denote the encoded training data owned by provideri as Mi and the system parameters as Mt. The server primarily encrypts the initialized system coefficients (may contain some private intellectual property information) as Ct=2nMtbmod2l to the first data provider who executes C1←HE.Enck1,M1 and C˜1←KS.DLPtoCSPCt as their response. On encrypted data C1 and C˜1 corresponding to the same key k1, the cloud can thus achieve C¯1←HE.Evalftraining,C˜1 which are updated system parameters decryptable by k1.For clarity, we describe the above processes as shown in Table1.Table 1
Initialization and first training.
Key generationData providersCloudki←HE.KeyGen1κkt←KS.KeyGen1κFirst trainingData provider 1CloudReceivesCt⇐Ct=2nMtbmod2lC˜1←KS.DLPtoCSPCt⇒ReceivesC˜1C1←HE.Enck1,M1⇒ReceivesC1C¯1←HE.Evalftraining,C1,C˜1Note thatKS.DLPtoCSP⋅ is a protocol that should be carried out by both the data provider and the cloud.To make the updated coefficients homomorphically computable with data encrypted by the following providers, we can exploit the key switching scheme to re-encrypt it. Without loss of generality, the updated parameters under keyki will be represented as C¯i. By means of Ct←KS.CSPtoDLPC¯i and C˜i+1←KS.DLPtoCSPCt, the cloud can obtain the re-encrypted coefficients C˜i+1 with the help of successive providers. After receiving Ci+1 from the next provider, they can compute C¯i+1←HE.Evalftraining,Ci+1,C˜i+1 since both ciphertexts are encrypted by ki+1. In consideration of the final parameters C¯N, the cloud needs to execute Ct←KS.CSPtoDLPC¯N with the last provider and then computes M=Ctsmod2l/2n to restore the plain parameters.The subsequent training and recovering processes are presented in Table2.Table 2
Subsequent training and recovering.
Subsequent trainingData providersiCloudReceivesC¯i⇐C¯iCt←KS.CSPtoDLPC¯i⇒ReceivesCtData providersi+1CloudReceivesCt⇐CtC˜i+1←KS.DLPtoCSPCt,⇒ReceivesC˜i+1Ci+1←HE.Encki+1,Mi+1⇒ReceivesCi+1C¯i+1←HE.Evalftraining,Ci+1,C˜i+1RecoveringData providerNCloudReceivesC¯N⇐C¯NCt←KS.CSPtoDLPC¯N⇒ReceivesCtMt←Ctsmod2l/2nThe classification/regression process is straightforward that, on encrypted dataCu←HE.Encku,Mu and system parameters C˜u←KS.DLPtoCSPCt for Ct=2nMtbmod2l, the cloud can homomorphically compute C¯u←HE.Evalfcla/reg,Cu,C˜u. By decrypting the received C¯u, the user obtains the classification/regression result such that Mcla/reg←HE.Decku,C¯u. This process can be found in Table 3.Table 3
Classification and regression.
Classification/regressionUseruCloudReceivesCt⇐Ct=2nMtbmod2lC˜u←KS.DLPtoCSPCt⇒ReceivesC˜uCu←HE.Encku,Mu⇒ReceivesCuReceivesC¯u⇐C¯u←HE.Evalfcla/reg,Cu,C˜uMcla/reg←HE.Decku,C¯u


## 5. Experiment Analysis

We drew support from the power load data of Chongqing Tongnan Electric Power Co., Ltd., dating from May 4 to May 10 in 2015, to verify the effectiveness of our training method. A short-term electrical load prediction model is also testified in virtue of 96 historical data pieces sampled during 4 consecutive days. The original machine learning model is exactly the same as that of [29], which has considered nothing about privacy. Our experiment environment is shown in Table 4.Table 4
Experiment environment.
CPUOSRAM (GB)Programming languagei5-10210 U 1.60 GHzWin10 64-bit16PythonTo simulate the scenario of multiparty machine learning, we divide the data into three parts and realize the training process corresponding to 3 different keys inHE. To prove that our method is not harmful to the accuracy of the trained network, as is shown in Figure 1, we compared the prediction result directly achieved via original model (without privacy-preserving) with that of ours (privacy-preserving scheme). Figure 1 illustrates that the two results are completely consistent.Figure 1
Comparison of prediction results.The experimental results are shown in Table5; our scheme can perform encryption training and prediction for multiple data providers in general machine learning. As for the efficiency of training and prediction, our scheme is 73578 and 12000 times slower than its plain version. Nevertheless, since the server is always powerful on computational capacity and the data providers only have to carry out trivial multiplications over R6×6, our scheme is practical in cloud environments. Moreover, if the accuracy is tolerable, we can shorten the ciphertext to make it more efficient.Table 5
Computational efficiency.
ModelTraining timePredicted timeEpochsOriginal model0.19 s4 ms400Our model233.33 min48 s400In terms of communication overheads, encrypted data for training or prediction are 18 times larger than plain messages. In each iteration, the cloud should also exchange the ciphertexts of system parameters with two successive data providers, which are also 18 times of original coefficients. Considering that the expansion rate is not big and system parameters are quite limited, the communication burden causes just little performance degradation.


## 6. Conclusions

We presented a privacy-preserving machine learning method that works over multiple data providers in this paper. Thanks to the hardness of the conjugate search problem, data can be homomorphically processed for training or classification/regression under the same key. It is worth mentioning that we solved the intrinsic conflict between IND-CPA security and homomorphic comparision (without decryption), by specifically encoding the data which is allowed to be compared. To support training among multiple data providers, a key switching technology is also proposed based on the difficulty of the discrete logarithm problem and Lagrange theorem, which evaded the necessity of multikey homomorphic computation. Experiment illustrated that the accuracy of machine learning cannot be affected by the privacy capability of our scheme. The expansion rate of computation/communication complexity is small enough, which makes the scheme practical in cloud environments.



---

*Source: 6615839-2021-01-11.xml*