# Privacy-Preserving Federated Learning Framework with General Aggregation and Multiparty Entity Matching

Authors: Zhou Zhou; Youliang Tian; Changgen Peng
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

The requirement for data sharing and privacy has brought increasing attention to federated learning. However, the existing aggregation models are too specialized and deal less with users’ withdrawal issue. Moreover, protocols for multiparty entity matching are rarely covered. Thus, there is no systematic framework to perform federated learning tasks. In this paper, we systematically propose a privacy-preserving federated learning framework (PFLF) where we first construct a general secure aggregation model in federated learning scenarios by combining the Shamir secret sharing with homomorphic cryptography to ensure that the aggregated value can be decrypted correctly only when the number of participants is greater thant. Furthermore, we propose a multiparty entity matching protocol by employing secure multiparty computing to solve the entity alignment problems and a logistic regression algorithm to achieve privacy-preserving model training and support the withdrawal of users in vertical federated learning (VFL) scenarios. Finally, the security analyses prove that PFLF preserves the data privacy in the honest-but-curious model, and the experimental evaluations show PFLF attains consistent accuracy with the original model and demonstrates the practical feasibility.


---

## Body

## 1. Introduction

In 2016, AlphaGo used 300,000 sets of flag games as training data and beat the world’s top professional go players. Artificial intelligence (AI) has shown great potential and is expected to show itself in many fields and make important contributions [1]. In traditional AI, data processing needs to aggregate a large amount of data for model training. However, due to industry competition, privacy protection requirements, business management, and other issues, data of various industries forms islands, which are difficult to share. Therefore, data quality and availability is one of the constraints on AI development [2]. On the other hand, data privacy and security have become the focus of the world’s attention [3] following the devastating losses caused by data leaks in recent years. The European Union recently introduced a new law—General Data Protection Regulations (GDPR) [4]—that shows the increasingly strict management of user data privacy and security will be the world trend. So the enactment of laws and regulations also brings new challenges to the traditional AI processing mode.How to solve the problem of data isolation and data fusion on the premise of protecting users’ privacy has become an urgent task for the development of AI. The federated learning (FL) framework, first proposed by Google in 2016 [5, 6], well meets those requirements. In the FL model, each participant keeps the local data training model, only transmits the parameters of each model to an aggregation server using the new cryptography technology, and the server returns the aggregation parameters to each participant for updating after the completion of parameter aggregation [7]. In the end, establishing the virtual common model, using the encryption mechanism to complete the parameter exchange is consistent with the optimal model trained from the data aggregation [8] under the traditional model. Recently, research of the federated learning has become a hot topic, and a lot of deep learning works focusing on privacy protecting have been done. In 2019, Yang et al. systematically introduced the federated learning framework, application, and research direction [9], which helps us to control and understand federated learning as a whole. The federated learning framework has been applied and extended to Deep Neural Networks (DNN), eXtreme Gradient Boosting (XGBoost), Random Forest (RF), and other algorithms [2, 10, 11], of which the used techniques include secret sharing [12], differential privacy [13], and homomorphic cryptography [14].At present, there are still the following problems about privacy-protecting FL. First, there are few protocols that involve multiple user entity matching [15] and ensuring their privacy in concurrent mode. In addition, too much interaction between users is required when encrypted gradients or parameters are passed to the server. Furthermore, the protocol only considers that all users participate online throughout the training cycle without going offline or that the recovery of correct data requires the assistance of other participants when one participant goes offline. Finally, the existing schemes are of poor generality and are often only for specific machine learning algorithms and application scenarios.To solve the above problems, we propose a novel PFLF with general aggregation and multiparty entity matching. In this framework, we propose a general aggregation model (GAM) that can be used in many applications where aggregation is required and privacy is protected. Under our GAM, we construct a multiparty entity matching protocol (MEMP), which can complete the confirmation of the common user data without leaking any disjoint entity information. In addition, we design the vertical federated logistic regression (VFLR) algorithm while keeping the data in the local database. In summary, our contributions can be summarized as follows:(i)
We propose a PFLF that includes the GAM, MEMP, and VFLR to achieve multiscenario data aggregation, multiparty matching, and privacy protections(ii)
We exploit the homomorphic encryption and the improved Shamir secret reconstruction to ensure that only the aggregator receives messages from at leastt participants; it can recover the secret and remove mask to acquire correct parameters or product. In the GAM, there is little interaction with other participants(iii)
We propose MEMP to confirm common entities based on GAM and the multiplicative homomorphism of RSA. It can enable participants with different data characteristics to determine common entities without leaking or inferring other useful information(iv)
We design a privacy-preserving VFLR by using Paillier homomorphic encryption and merging GAM and LR. It can train a secure VFLR and support the withdrawal of participants. In addition, the prediction accuracy of the model is not affected(v)
We give a comprehensive security analysis for our framework. We claim that the attackers will not acquire any useful information even if there is no more thant participant collusion. Besides, extensive experiments are operated to confirm that our framework is effective and efficientThe rest of the paper is organized as follows. In Section2, we describe the preliminaries and the main technology. In Section 3, we describe the system architecture, security model, and problem description. In Section 4, we describe the algorithm details of our GAM with privacy protection and construct the secure MEMP and VFLR model. In Section 5, we demonstrate the security analysis of framework. Experimental evaluation and related work are discussed in Sections 6 and 7, respectively. Finally, we give the conclusion of the paper in Section 8.


## 2. Preliminary

### 2.1. Logistic Regression Algorithm

Consider a datasetxi,yii=1m with d dimension, in which xi=x1i,x2i,⋯,xdi∈Rd, yxi∈0,1. The predicted value is mapped between 0 and 1 by the sigmoid function [16] hθx=1/1+e−θTx, where θTx=∑j=0dθjxj and x0=1. The objective function is defined as follows:
(1)Lθ=1m∑i=1m−yiloghθxi−1−yilog1−hθxi+λ2m∑j=1dθj2.The gradient descent method is used to minimize the value of the objective function, and the model parameters are updated as follows:(2)θj=θj−αm∑i=0mhθxi−yixji−λmθj.When given a new dataxnew, the predictive value of logistic regression is set to
(3)ynew=1hθxnew≥0.5,0hθxnew<0.5.


### 2.2. Homomorphic Encryption

The Paillier scheme satisfying the additive homomorphism [17] is as follows: p,q are large primes of equal length chosen randomly; n=pq,φn=p−1q−1 are calculated. Given the random number g∈ℤn2∗, then we have the public key pk=n,g and the private key sk=φn,φn−1modn. For the encryption, given the random number r satisfying 0<r<n,r∈ℤn2∗, we have the ciphertext C=gmrnmodn2, where M is the plaintext. In the decryption phase, m is obtained by computing m=Lcφnmodn2φn−1, where Lx=x−1/n.We mainly use the following properties of Paillier homomorphic encryption. Additivity can be indicated asDEm1,r1Em2,r2modn2=m1+m2.


### 2.3. Secret Sharing

The secret sharing (SS) scheme [18] adopted in our scheme is used to mask the data ciphertext transmitted by participants, but ensures that the aggregator recovers the ciphertext product and it also helps the scheme support the withdrawal of participants. For t,n SS scheme, the secret s is split into n shares. s can be recovered only if at least t random shares are provided. The share generation algorithm is illustrated as SS.shares,t,n=u,su∣u∈U, in which n represents the number of participants involved in SS and U=1,2,⋯,n is the set of participants and su is the share for each user u. The secret can be recovered by at least t participants contained in U′U′⊆U using Lagrange interpolation base SS.reconu,su∣u∈U′,t as follows:
(4)s=∑i=1U′siιi0,where ιi0=∏j=1,i≠jU′idi/idj−idi is computed. Here, we can use idi representing the identity of the ith participant.


## 2.1. Logistic Regression Algorithm

Consider a datasetxi,yii=1m with d dimension, in which xi=x1i,x2i,⋯,xdi∈Rd, yxi∈0,1. The predicted value is mapped between 0 and 1 by the sigmoid function [16] hθx=1/1+e−θTx, where θTx=∑j=0dθjxj and x0=1. The objective function is defined as follows:
(1)Lθ=1m∑i=1m−yiloghθxi−1−yilog1−hθxi+λ2m∑j=1dθj2.The gradient descent method is used to minimize the value of the objective function, and the model parameters are updated as follows:(2)θj=θj−αm∑i=0mhθxi−yixji−λmθj.When given a new dataxnew, the predictive value of logistic regression is set to
(3)ynew=1hθxnew≥0.5,0hθxnew<0.5.


## 2.2. Homomorphic Encryption

The Paillier scheme satisfying the additive homomorphism [17] is as follows: p,q are large primes of equal length chosen randomly; n=pq,φn=p−1q−1 are calculated. Given the random number g∈ℤn2∗, then we have the public key pk=n,g and the private key sk=φn,φn−1modn. For the encryption, given the random number r satisfying 0<r<n,r∈ℤn2∗, we have the ciphertext C=gmrnmodn2, where M is the plaintext. In the decryption phase, m is obtained by computing m=Lcφnmodn2φn−1, where Lx=x−1/n.We mainly use the following properties of Paillier homomorphic encryption. Additivity can be indicated asDEm1,r1Em2,r2modn2=m1+m2.


## 2.3. Secret Sharing

The secret sharing (SS) scheme [18] adopted in our scheme is used to mask the data ciphertext transmitted by participants, but ensures that the aggregator recovers the ciphertext product and it also helps the scheme support the withdrawal of participants. For t,n SS scheme, the secret s is split into n shares. s can be recovered only if at least t random shares are provided. The share generation algorithm is illustrated as SS.shares,t,n=u,su∣u∈U, in which n represents the number of participants involved in SS and U=1,2,⋯,n is the set of participants and su is the share for each user u. The secret can be recovered by at least t participants contained in U′U′⊆U using Lagrange interpolation base SS.reconu,su∣u∈U′,t as follows:
(4)s=∑i=1U′siιi0,where ιi0=∏j=1,i≠jU′idi/idj−idi is computed. Here, we can use idi representing the identity of the ith participant.


## 3. System Architecture

In this section, we introduce the system architecture, illustrated in Figure1. Some frequently used notations of the paper are listed in Table 1.Figure 1
System architecture.Table 1
Notation table.
NotationDescriptionEkpThe homomorphic encryption with public keykpe,dThe public key and private key for RSAℤP∗A cyclic group of orderP, primitive gsiThe secret share distributed to the participantsUiXkiThekth sample of the ith participantΘiThe characteristic weight of theith participantHA hash functionhθFunction prediction of logistic regression


### 3.1. System Model

Our framework involves three types of participating entities: a key generation center (KGC), a center server (CS), and a set of average participants (AP). Details are presented as follows.Key Generation Center. KGC primarily performs key generation and distribution. Its main purpose is to initialize the system, generate public and private keys for homomorphic encryption, generate subsecrets based on Shamir secret sharing, assign corresponding public and private keys to CS, and distribute subsecrets to each general participant. Afterwards, it will go offline.Center Server. CS is often the initiator of a federated learning mission. It is the one who has data labels, coordinating the execution of the entire process. It aggregates the parameters uploaded by all online participants. In MEMP, it calculates the user intersection and returns the common entity. In VFLR, it returns the calculated sample error. In the process, we hope that CS can infer nothing except the uploaded ciphertext and the final result.Average Participants. AP refers to participants who participate in model training without tags. It involves multiple average participants, namely, AP=U1,U2,⋯,Un. In the aggregation framework, they are usually done with local encryption and send values for aggregation.


### 3.2. Security Model

Based on [19], in our scheme, we assume that the interaction channels through CS and AP are secure and not subject to risks such as tampering, and all participants except KGC are considered to be honest-but-curious. KGC is a trusted party which always performs its tasks honestly and does not collude with any entity. CS and AP honestly follow the agreed process, but may try to learn all possible information that is of interest to them from their received messages. We define a threat model with an honest-but-curious adversary A who can corrupt at most t−1 parties and obtain their inputs or other private information. In the entity matching protocol, what A wants to know is users’ information and CS’s private key. In the model building and prediction phase, A makes full use of the information it holds to learn about the data including data characteristics and weights of other honest parties. Our model needs to meet the following security requirements.Data Privacy. CS cannot recognize any private data uploaded by Ui, and other Uj (j≠i) cannot infer the private data of others. For example, mark matrix and model parameters must not be exposed.Secure Withdrawal. CS and Ui cannot continue to use the information of the exiting participants for subsequent calculations, and the process of recovering the aggregated value cannot reveal the parameters of the exiting participants if any participant drops in a round. There should be a safe way to deal with delayed transmissions and not be mistaken for offline.


### 3.3. Problem Description

In order to achieve a GAM that can enable aggregated messages to be decrypted only if they come from at leastt participants, while ensuring that individual parameter ciphertext is not exposed, we introduce some cryptographic tools. For example, the transformed Shamir secret sharing scheme helps achieve threshold aggregation and cover the homomorphic ciphertext of each participant. Homomorphic encryption features facilitate obtaining the product or sum of parameter plaintext through ciphertext aggregation. Furthermore, the same entity between different participants needs to be determined for multiple participants with different characteristics in the vertical federated mode. Firstly, we should design a MEMP with privacy protection, through which multiple participants obtain their overlapping entity IDs without exposing their respective data. After then, we use these common entities’ data with different characteristics to train the learning model while ensuring local data privacy. To achieve these two goals, under our aggregation model, we use RSA blind signature to generate data identity libraries, record the matching results by token matrix, and use RSA and Paillier as homomorphic encryption for specific functional requirements. In particular, the prediction accuracy of VFLR realized by the framework is unchanged, and it can support the withdrawal of participants.


## 3.1. System Model

Our framework involves three types of participating entities: a key generation center (KGC), a center server (CS), and a set of average participants (AP). Details are presented as follows.Key Generation Center. KGC primarily performs key generation and distribution. Its main purpose is to initialize the system, generate public and private keys for homomorphic encryption, generate subsecrets based on Shamir secret sharing, assign corresponding public and private keys to CS, and distribute subsecrets to each general participant. Afterwards, it will go offline.Center Server. CS is often the initiator of a federated learning mission. It is the one who has data labels, coordinating the execution of the entire process. It aggregates the parameters uploaded by all online participants. In MEMP, it calculates the user intersection and returns the common entity. In VFLR, it returns the calculated sample error. In the process, we hope that CS can infer nothing except the uploaded ciphertext and the final result.Average Participants. AP refers to participants who participate in model training without tags. It involves multiple average participants, namely, AP=U1,U2,⋯,Un. In the aggregation framework, they are usually done with local encryption and send values for aggregation.


## 3.2. Security Model

Based on [19], in our scheme, we assume that the interaction channels through CS and AP are secure and not subject to risks such as tampering, and all participants except KGC are considered to be honest-but-curious. KGC is a trusted party which always performs its tasks honestly and does not collude with any entity. CS and AP honestly follow the agreed process, but may try to learn all possible information that is of interest to them from their received messages. We define a threat model with an honest-but-curious adversary A who can corrupt at most t−1 parties and obtain their inputs or other private information. In the entity matching protocol, what A wants to know is users’ information and CS’s private key. In the model building and prediction phase, A makes full use of the information it holds to learn about the data including data characteristics and weights of other honest parties. Our model needs to meet the following security requirements.Data Privacy. CS cannot recognize any private data uploaded by Ui, and other Uj (j≠i) cannot infer the private data of others. For example, mark matrix and model parameters must not be exposed.Secure Withdrawal. CS and Ui cannot continue to use the information of the exiting participants for subsequent calculations, and the process of recovering the aggregated value cannot reveal the parameters of the exiting participants if any participant drops in a round. There should be a safe way to deal with delayed transmissions and not be mistaken for offline.


## 3.3. Problem Description

In order to achieve a GAM that can enable aggregated messages to be decrypted only if they come from at leastt participants, while ensuring that individual parameter ciphertext is not exposed, we introduce some cryptographic tools. For example, the transformed Shamir secret sharing scheme helps achieve threshold aggregation and cover the homomorphic ciphertext of each participant. Homomorphic encryption features facilitate obtaining the product or sum of parameter plaintext through ciphertext aggregation. Furthermore, the same entity between different participants needs to be determined for multiple participants with different characteristics in the vertical federated mode. Firstly, we should design a MEMP with privacy protection, through which multiple participants obtain their overlapping entity IDs without exposing their respective data. After then, we use these common entities’ data with different characteristics to train the learning model while ensuring local data privacy. To achieve these two goals, under our aggregation model, we use RSA blind signature to generate data identity libraries, record the matching results by token matrix, and use RSA and Paillier as homomorphic encryption for specific functional requirements. In particular, the prediction accuracy of VFLR realized by the framework is unchanged, and it can support the withdrawal of participants.


## 4. Construction of PFLF

Our PFLF implements a systematic FL process, including three main functions. Firstly, it can realize multiparty data aggregation without data leakage. Secondly, it can find the common set of entities of multiple participants without revealing useful information. For VFL scenarios, subsequent joint training can only be completed if the common entities are identified. When using logistic regression algorithm in VFL scenario, secure data aggregation is necessary after entity matching is completed. So, thirdly, we design the VFLR. In particular, the aggregation in our framework is generic, not only for a specific machine learning algorithm but also for all application scenarios based on thresholds. In this section, we present the details of our GAM and its role in constructing MEMP and VFLR.


### 4.1. A Novel GAM

A common aggregation model is suitable for such application scenarios where the aggregation server CS can decrypt and obtain the desired results through homomorphic encryption only when messages received are from at leastt participants. Through this model, the participants’ private data is fully protected in the process of achieving the interaction purpose according to the protocol, and when there are participants offline, the aggregated messages that do not involve the offline information can be recovered quickly. Here, firstly, based on the mentioned SS scheme, we can make the following transformation.Each userUi chooses a random number βik, where i=1,2,⋯,t is the number of participants who reconstructed the secret and k is the number of samples. For the secret reconstruction formula s=∑i=1U′siιi0, let us multiply both sides of this equation by random numbers βik and the equation is transformed into the following form:
(5)β1ks=β1ks1ι10+s2ι20+⋯+stιt0,β2ks=β2ks1ι10+s2ι20+⋯+stιt0,⋯βtks=βtks1ι10+s2ι20+⋯+stιt0.We can sum both sides of this equation and get(6)∑i=1tβiks=∑i=1tβiks1ι10+∑i=1tβiks2ι20+⋯+∑i=1tβikβikstιt0.When used for threshold encryption, it converts to(7)g∑i=1tβiks1ι10Ekm1kg∑i=1tβiks2ι20Ekm2k⋯g∑i=1tβikstιt0Ekmtk=g∑i=1tβiks1ι10+∑i=1tβiks2ι20+⋯+∑i=1tβikstιt0∏i=1tEkmik=g∑i=1tβiks∏i=1tEkmik.We assume that in such a scenario, each participantUi having a message mik needs to ask CS to help calculate ∑i=1nmik, but does not want to disclose mik to others and also does not want CS to infer some private data through the message sent by themselves to carry out various possible calculations. Figure 2 shows its workflow. In this way, they can do it like this: Ui first computes g∑i=1tβiksiιi0Ekmik and sends it to CS according to the above equation, the receiver with the private key ks can decrypt and get ∑i=1tmik when each participant makes public the value gβik corresponding to βik, and there exists the secret s=kp and the public key k=kp. Besides, Ek satisfies homomorphic encryption which refers to multiplicative homomorphism in our entity matching protocol and additive homomorphism in our joint model training. How the model supports users’ withdrawal is described in detail in Section 4.3. If the model is used for horizontal federated learning, mik can be gradient and other important parameters. Later in the VFLR section, we will focus on using logistic regression to explain the framework.Figure 2
Workflow of the GAM.


### 4.2. Secure Multiparty Entity Matching

As shown in Algorithm1, the secure multiparty entity matching protocol completes the confirmation of the common entity of multiple participants under the premise of protecting privacy. In the protocol, there is a CS with data sample identity usk and a set of average participants U=U1,U2,⋯,Un with their own data sample uik, which represents the identity of the kth sample for the ith participant. Note that we briefly describe the situation of sending a message M from A to B as A⇒B:M. The protocol workflow is shown in Figure 3. The process of the protocol is shown as below.Figure 3
Workflow of the MEMP.In the initial parameter setting phase, the CS sets the penalty term, coefficientλ, and maximum iteration number maxiter of the model. T generates a public-private key kp,ks for homomorphic encryption of the later model building and predicting. The algorithm introduces an RSA encryption with a blind factor to mask confidential information, so the public-private key N,e,d, N,ei,di, i∈1,2,⋯,n are generated by T. In the following, we omit the modulus N for RSA. In addition, T also generates subshares si and si′ of the public key kp and e for Ui based on the identity of Ui using SS.sharekp,t,n or SS.sharee,t,n.In the exchange of information phase, each participantUi chooses a random number ri, computes vik=rieHuikdi, and sends it to CS. CS chooses a random number rsi to reflect the randomness of the interaction and uses the private key d for signature vikdrcs and sends disturbed cik=riHuikdidrcs to Ui. Disturbing the order of ci1,ci2,⋯,cik can eliminate the correspondence between cik and uik so that Ui cannot lock the IDs corresponding to the intersection of Ui and CS in the comparison phase. Furthermore, CS calculates random identifiers of each entity for different participants: dij=HHusjdrsiei. Then, CS sends d11,d12,⋯,d1j,⋯,dn1,dn2,⋯,dnj to corresponding participants U1,U2,⋯,Un−1 for comparison.In the comparison phase, each participantUi eliminates the blind factor and opens its signature for cik to obtain Huikdrsiei and uses the hash function to compute gik=HHuikdrsiei. By comparing them with dij, CS gets an l-dimensional matrix bi1,bi2,⋯,bij. bij=1 if dij belongs to gik. If not, bij=aij, where aij is a random number and aij>1. In this way, each participant creates a comparison matrix.In the solution phase, each participantUi chooses a set of random number pij (i.e.,p11,p12,⋯,p1j,,⋯,pn1,pn2,⋯,pnj,) and encrypts its matrix by computing gsi′ιi0∑i=1npijbije with RSA.After then,Ui sends their encrypted matrix to CS for aggregation. At last, CS aggregates matrix values of n participants by computing ∏i=1,jn,jgsi′ιi0∑i=1npijbije and uses its private key d to decrypt, obtaining ∏i=1,jn,jbij. Because CS can recover the secret e by computing ∑i=1si′ιi0. Specific analysis can refer to Secure Model Building.In the identification phase, CS finds the corresponding entity by the value of∏i=1,jn,jbij. Because each dij comes from CS, then if it is 1, it means that each participant has a corresponding dij, and if not, it means that at least one participant does not have dij. Therefore, CS can find the right entity usj based on ∏i=1,jn,jbij. In the end, CS broadcasts common entity IDs to other participants for following model training.Algorithm 1: MEMP.
Input: a central server CS, a set of participants U=U1,U2,⋯,Un, and a trusted party T.Output: common entity IDs.1: CS sets the parameters for model trainingpenalty,λ,maxiter.2:T generates a public-private key kp,ks for homomorphic encryption, a public-private key N,e,d for RSA encryption for CS, also generates average participants’ public-private keys N,ei,di and subshares of the public key kp and e based on the identity of the participants, i.e., T⇒U:u,su∣u∈U=SS.sharekp,t,n. Here, U1,U2,⋯,Un get subshares s1,s2,⋯,sn for kp and subshares s1′,s2′,⋯,sn′ for e.3: Each participantUi chooses a random number ri, computes vik=rieHuikdi, and operates U⇒CS:vik.4: CS chooses a random numberrsi, uses the private key for signature vikdrsi, gets each cik=riHuikdidrsi, and returns them to Ui after disturbing the order of cik.5:fori=1⟶ndo6:forj=1⟶ldo7:  CS computes for thel entities: dij=HHusjdrsiei.8: CS sendsd11,d12,⋯,d1j,⋯,dn1,dn2,⋯,dnj to corresponding participants U1,U2,⋯,Un−1.9:fori=1⟶ndo10: Each participantUi eliminates the blind factor and di for cik, obtains Huikdrsiei, and computes their hash values gik=HHuikdrsiei.11:forj=1⟶ldo12:  Each participant generates its ownl-dimensional matrix bi1,bi2,⋯,bij by determining whether dij belongs to its gik.13:ifdij∈gikthen14:bij=1.15:else16:bij=aij, where aij is a random number and aij>1.17: Each participantUi chooses a set of random number pij and encrypts its matrix with gsi′ιi0∑i=1npijbije, operating Ui⇒CS:encryptedmatrix.18: CS aggregates matrix values by computing∏i=1,jn,jgsi′ιi0∑i=1npijbije and obtains ∏i=1,jn,jbij by decrypting.19:if∏i=1,jn,jbij==1then20: CS finds the correspondingusj.21: CS broadcastsusj to other participants U1,U2,⋯,Un−1.22:return common entity IDs: usj.


### 4.3. Secure Model Building

#### 4.3.1. Secure Training

For logistic regression to find the better model with gradient descent method, the part that needs to be computed jointly iserror using the predicted value and the sample label. It is better for CS to do the aggregation and calculation since sample labels are mastered by CS. The workflow is shown in Figure 4. To protect the confidentiality of each participant’s data, the aggregated data is received in ciphertext. Consequently, we chose to use Paillier homomorphic encryption to do the computation. However, each participant’s data cannot be decrypted separately by CS; for this reason, we apply Shamir secret sharing scheme such as Formula (7) to ensure that CS could decrypt only after the aggregation operation was completed. The detailed process is shown in Algorithm 2.Figure 4
Workflow of the VFLR.The number of common entities of all participants ism, the average participants in the joint modeling are UiUi∈U, and each average participant secretly keeps a subsecret as si. Now given a cyclic group G and its primitive g, Uii∈1,n computes Dki=ΘiXki, in which Xki is the kth sample for the ith participant Ui. With subsecret si and identities, Ui can compute its own siιi0. In order to keep the subsecret si dynamic, for each sample, Ui adds a random factor or the time stamp βik to calculate Cki=gsiιi0∑i=1nβikEkpDki and sends it to CS after other participants release their gβik. At this point, although CS gets the ciphertext of each participant, he cannot decrypt it because he cannot get the subsecret si. Only when messages are received from at least t participants can aggregation ∏i=1nCki that can be generated, i.e.,
(8)∏i=1nCki=∏i=1ngsiιi0∑i=1nβikEkpDki=g∑i=1nsiιi0∑i=1nβikEkp∑i=1nDki,where g∑i=1nsiιi0∑i=1nβik=g∑i=1nβikkp. Because kp and g∑i=1nβik are public to CS, CS can decrypt and get ∑i=1nΘiXki to compute errork. The next step, CS will broadcast errork to current participants U′U′⊆U. Each participant and CS can update weight parameter by computing Θi=Θi+α/m∑k=1merrorkXki−λ/mΘi. All steps are repeated until the maximum number of iterations is reached.


#### 4.3.2. Withdrawal of Participants

Some participants may withdraw from federated learning, such as being unwilling to contribute models or dropping offline. In order to deal with the above situation, we can make a contract to reduce the occurrence of withdrawal. It is assumed that each average participantUi will be paid a certain amount based on their contribution in each iteration. The total expenditure and maximum number of iterations set by CS are Amounts and t. The contract signed by all participants is as follows: (1) n average participants submit a deposit to CS, and the deposit is Amounts/t. (2) In the FL, if CS receives all the messages within the maximum allowable period, the errors will be returned normally to all participants according to the protocol. (3) Else, CS will send withdrawal confirmation request to participants who did not send the message. If they report it is delayed, the delayed messages can still be used to compute the aggregated value. But these delayed participants will not get paid this round. (4) Once the participant reports withdrawal, the deposit will be distributed to other online participants, including CS. Rational participants generally do not withdraw in order to maximize their own interests. (5) Upon completion of the FL, deposits will be returned to all the online participants. Particularly, if some participants withdraw during training, CS requires each participant to resend the message without the identity of the quitters in order to decrypt. Because of the randomness of Cki, CS cannot use the message sent twice to perform comparison calculation and get useful data. The reason is that CS still cannot get the subsecret to reconstruct the polynomial.Algorithm 2: VFLR.
Input: a central server CS, a set of participants U=U1,U2,⋯,Un, instance space of m samples of each participants, subshares s1,s2,⋯,sn, cyclic group G, and its primitive g.Output: federated logistic regression model.1:fork=1⟶mdo2:fori=1⟶ndo3:Ui computes Dki=ΘiXki.4:Ui chooses random number βik and makes public its gβik.5:Ui uses others’ gβik to compute Cki=gsiιi0∑i=1nβikEkpDki and sends it to CS.6:fork=1⟶mdo7:if someone exits then8:  CS eliminates the value involving information of quitters inιi0.9: CS performs the aggregation∏i=1nCki and decrypts to get ∑i=1nΘiXki.10: CS computeserrork=yk−1/1+e−∑i=1nΘiXki+ΘsXks.11: broadcastserrork.12: Each participant and CS can update weight parameter by computingΘi=Θi+α/m∑k=1m‍errorkXki−λ/mΘi.13: Repeat all until reaching the termination condition.14:return built model.


### 4.4. Secure Predicting

Secure prediction should ensure that user data privacy is not compromised and that model parameters are not exposed. As described by Algorithm3, results inquirer R intends to provide a set of data for prediction without privacy leakage and all data characteristics correspond to all participants in the current model. First, R, respectively, encrypts the data with Ekp′Xki, for example, Xki belongs to a characteristic that corresponds to Ui. Each participant computes Ekp′XkiΘi through R’s public key kp′ and communicates it to CS. The aggregation operation is still done by CS to protect the parameters Θi from being exposed. Then, CS computes Ekp′XksΘs∏i=1nEkp′XkiΘi and returns it to R. The joint value ΘiXki could be get with private key ks′ by R, which computes predicted results h using hθx=1/1+e−θTx.Algorithm 3: Secure predicting.
Input: federated logistic regression model, results inquirer R, and its instance space.Output: predicted results.1:fori=1⟶ndo2:R, respectively, encrypts the data Ekp′Xki belonging to the characteristics of different participants including CS.3: Each participant computesEkp′XkiΘi and communicates it to CS.4: CS does an aggregate operationEkp′XksΘs∏i=1nEkp′XkiΘi and returns it to R.5:R decrypts and gets ΘiXki.6:R gets predicted results h by hθx=1/1+e−θTx.7:return result h.


## 4.1. A Novel GAM

A common aggregation model is suitable for such application scenarios where the aggregation server CS can decrypt and obtain the desired results through homomorphic encryption only when messages received are from at leastt participants. Through this model, the participants’ private data is fully protected in the process of achieving the interaction purpose according to the protocol, and when there are participants offline, the aggregated messages that do not involve the offline information can be recovered quickly. Here, firstly, based on the mentioned SS scheme, we can make the following transformation.Each userUi chooses a random number βik, where i=1,2,⋯,t is the number of participants who reconstructed the secret and k is the number of samples. For the secret reconstruction formula s=∑i=1U′siιi0, let us multiply both sides of this equation by random numbers βik and the equation is transformed into the following form:
(5)β1ks=β1ks1ι10+s2ι20+⋯+stιt0,β2ks=β2ks1ι10+s2ι20+⋯+stιt0,⋯βtks=βtks1ι10+s2ι20+⋯+stιt0.We can sum both sides of this equation and get(6)∑i=1tβiks=∑i=1tβiks1ι10+∑i=1tβiks2ι20+⋯+∑i=1tβikβikstιt0.When used for threshold encryption, it converts to(7)g∑i=1tβiks1ι10Ekm1kg∑i=1tβiks2ι20Ekm2k⋯g∑i=1tβikstιt0Ekmtk=g∑i=1tβiks1ι10+∑i=1tβiks2ι20+⋯+∑i=1tβikstιt0∏i=1tEkmik=g∑i=1tβiks∏i=1tEkmik.We assume that in such a scenario, each participantUi having a message mik needs to ask CS to help calculate ∑i=1nmik, but does not want to disclose mik to others and also does not want CS to infer some private data through the message sent by themselves to carry out various possible calculations. Figure 2 shows its workflow. In this way, they can do it like this: Ui first computes g∑i=1tβiksiιi0Ekmik and sends it to CS according to the above equation, the receiver with the private key ks can decrypt and get ∑i=1tmik when each participant makes public the value gβik corresponding to βik, and there exists the secret s=kp and the public key k=kp. Besides, Ek satisfies homomorphic encryption which refers to multiplicative homomorphism in our entity matching protocol and additive homomorphism in our joint model training. How the model supports users’ withdrawal is described in detail in Section 4.3. If the model is used for horizontal federated learning, mik can be gradient and other important parameters. Later in the VFLR section, we will focus on using logistic regression to explain the framework.Figure 2
Workflow of the GAM.


## 4.2. Secure Multiparty Entity Matching

As shown in Algorithm1, the secure multiparty entity matching protocol completes the confirmation of the common entity of multiple participants under the premise of protecting privacy. In the protocol, there is a CS with data sample identity usk and a set of average participants U=U1,U2,⋯,Un with their own data sample uik, which represents the identity of the kth sample for the ith participant. Note that we briefly describe the situation of sending a message M from A to B as A⇒B:M. The protocol workflow is shown in Figure 3. The process of the protocol is shown as below.Figure 3
Workflow of the MEMP.In the initial parameter setting phase, the CS sets the penalty term, coefficientλ, and maximum iteration number maxiter of the model. T generates a public-private key kp,ks for homomorphic encryption of the later model building and predicting. The algorithm introduces an RSA encryption with a blind factor to mask confidential information, so the public-private key N,e,d, N,ei,di, i∈1,2,⋯,n are generated by T. In the following, we omit the modulus N for RSA. In addition, T also generates subshares si and si′ of the public key kp and e for Ui based on the identity of Ui using SS.sharekp,t,n or SS.sharee,t,n.In the exchange of information phase, each participantUi chooses a random number ri, computes vik=rieHuikdi, and sends it to CS. CS chooses a random number rsi to reflect the randomness of the interaction and uses the private key d for signature vikdrcs and sends disturbed cik=riHuikdidrcs to Ui. Disturbing the order of ci1,ci2,⋯,cik can eliminate the correspondence between cik and uik so that Ui cannot lock the IDs corresponding to the intersection of Ui and CS in the comparison phase. Furthermore, CS calculates random identifiers of each entity for different participants: dij=HHusjdrsiei. Then, CS sends d11,d12,⋯,d1j,⋯,dn1,dn2,⋯,dnj to corresponding participants U1,U2,⋯,Un−1 for comparison.In the comparison phase, each participantUi eliminates the blind factor and opens its signature for cik to obtain Huikdrsiei and uses the hash function to compute gik=HHuikdrsiei. By comparing them with dij, CS gets an l-dimensional matrix bi1,bi2,⋯,bij. bij=1 if dij belongs to gik. If not, bij=aij, where aij is a random number and aij>1. In this way, each participant creates a comparison matrix.In the solution phase, each participantUi chooses a set of random number pij (i.e.,p11,p12,⋯,p1j,,⋯,pn1,pn2,⋯,pnj,) and encrypts its matrix by computing gsi′ιi0∑i=1npijbije with RSA.After then,Ui sends their encrypted matrix to CS for aggregation. At last, CS aggregates matrix values of n participants by computing ∏i=1,jn,jgsi′ιi0∑i=1npijbije and uses its private key d to decrypt, obtaining ∏i=1,jn,jbij. Because CS can recover the secret e by computing ∑i=1si′ιi0. Specific analysis can refer to Secure Model Building.In the identification phase, CS finds the corresponding entity by the value of∏i=1,jn,jbij. Because each dij comes from CS, then if it is 1, it means that each participant has a corresponding dij, and if not, it means that at least one participant does not have dij. Therefore, CS can find the right entity usj based on ∏i=1,jn,jbij. In the end, CS broadcasts common entity IDs to other participants for following model training.Algorithm 1: MEMP.
Input: a central server CS, a set of participants U=U1,U2,⋯,Un, and a trusted party T.Output: common entity IDs.1: CS sets the parameters for model trainingpenalty,λ,maxiter.2:T generates a public-private key kp,ks for homomorphic encryption, a public-private key N,e,d for RSA encryption for CS, also generates average participants’ public-private keys N,ei,di and subshares of the public key kp and e based on the identity of the participants, i.e., T⇒U:u,su∣u∈U=SS.sharekp,t,n. Here, U1,U2,⋯,Un get subshares s1,s2,⋯,sn for kp and subshares s1′,s2′,⋯,sn′ for e.3: Each participantUi chooses a random number ri, computes vik=rieHuikdi, and operates U⇒CS:vik.4: CS chooses a random numberrsi, uses the private key for signature vikdrsi, gets each cik=riHuikdidrsi, and returns them to Ui after disturbing the order of cik.5:fori=1⟶ndo6:forj=1⟶ldo7:  CS computes for thel entities: dij=HHusjdrsiei.8: CS sendsd11,d12,⋯,d1j,⋯,dn1,dn2,⋯,dnj to corresponding participants U1,U2,⋯,Un−1.9:fori=1⟶ndo10: Each participantUi eliminates the blind factor and di for cik, obtains Huikdrsiei, and computes their hash values gik=HHuikdrsiei.11:forj=1⟶ldo12:  Each participant generates its ownl-dimensional matrix bi1,bi2,⋯,bij by determining whether dij belongs to its gik.13:ifdij∈gikthen14:bij=1.15:else16:bij=aij, where aij is a random number and aij>1.17: Each participantUi chooses a set of random number pij and encrypts its matrix with gsi′ιi0∑i=1npijbije, operating Ui⇒CS:encryptedmatrix.18: CS aggregates matrix values by computing∏i=1,jn,jgsi′ιi0∑i=1npijbije and obtains ∏i=1,jn,jbij by decrypting.19:if∏i=1,jn,jbij==1then20: CS finds the correspondingusj.21: CS broadcastsusj to other participants U1,U2,⋯,Un−1.22:return common entity IDs: usj.


## 4.3. Secure Model Building

### 4.3.1. Secure Training

For logistic regression to find the better model with gradient descent method, the part that needs to be computed jointly iserror using the predicted value and the sample label. It is better for CS to do the aggregation and calculation since sample labels are mastered by CS. The workflow is shown in Figure 4. To protect the confidentiality of each participant’s data, the aggregated data is received in ciphertext. Consequently, we chose to use Paillier homomorphic encryption to do the computation. However, each participant’s data cannot be decrypted separately by CS; for this reason, we apply Shamir secret sharing scheme such as Formula (7) to ensure that CS could decrypt only after the aggregation operation was completed. The detailed process is shown in Algorithm 2.Figure 4
Workflow of the VFLR.The number of common entities of all participants ism, the average participants in the joint modeling are UiUi∈U, and each average participant secretly keeps a subsecret as si. Now given a cyclic group G and its primitive g, Uii∈1,n computes Dki=ΘiXki, in which Xki is the kth sample for the ith participant Ui. With subsecret si and identities, Ui can compute its own siιi0. In order to keep the subsecret si dynamic, for each sample, Ui adds a random factor or the time stamp βik to calculate Cki=gsiιi0∑i=1nβikEkpDki and sends it to CS after other participants release their gβik. At this point, although CS gets the ciphertext of each participant, he cannot decrypt it because he cannot get the subsecret si. Only when messages are received from at least t participants can aggregation ∏i=1nCki that can be generated, i.e.,
(8)∏i=1nCki=∏i=1ngsiιi0∑i=1nβikEkpDki=g∑i=1nsiιi0∑i=1nβikEkp∑i=1nDki,where g∑i=1nsiιi0∑i=1nβik=g∑i=1nβikkp. Because kp and g∑i=1nβik are public to CS, CS can decrypt and get ∑i=1nΘiXki to compute errork. The next step, CS will broadcast errork to current participants U′U′⊆U. Each participant and CS can update weight parameter by computing Θi=Θi+α/m∑k=1merrorkXki−λ/mΘi. All steps are repeated until the maximum number of iterations is reached.


### 4.3.2. Withdrawal of Participants

Some participants may withdraw from federated learning, such as being unwilling to contribute models or dropping offline. In order to deal with the above situation, we can make a contract to reduce the occurrence of withdrawal. It is assumed that each average participantUi will be paid a certain amount based on their contribution in each iteration. The total expenditure and maximum number of iterations set by CS are Amounts and t. The contract signed by all participants is as follows: (1) n average participants submit a deposit to CS, and the deposit is Amounts/t. (2) In the FL, if CS receives all the messages within the maximum allowable period, the errors will be returned normally to all participants according to the protocol. (3) Else, CS will send withdrawal confirmation request to participants who did not send the message. If they report it is delayed, the delayed messages can still be used to compute the aggregated value. But these delayed participants will not get paid this round. (4) Once the participant reports withdrawal, the deposit will be distributed to other online participants, including CS. Rational participants generally do not withdraw in order to maximize their own interests. (5) Upon completion of the FL, deposits will be returned to all the online participants. Particularly, if some participants withdraw during training, CS requires each participant to resend the message without the identity of the quitters in order to decrypt. Because of the randomness of Cki, CS cannot use the message sent twice to perform comparison calculation and get useful data. The reason is that CS still cannot get the subsecret to reconstruct the polynomial.Algorithm 2: VFLR.
Input: a central server CS, a set of participants U=U1,U2,⋯,Un, instance space of m samples of each participants, subshares s1,s2,⋯,sn, cyclic group G, and its primitive g.Output: federated logistic regression model.1:fork=1⟶mdo2:fori=1⟶ndo3:Ui computes Dki=ΘiXki.4:Ui chooses random number βik and makes public its gβik.5:Ui uses others’ gβik to compute Cki=gsiιi0∑i=1nβikEkpDki and sends it to CS.6:fork=1⟶mdo7:if someone exits then8:  CS eliminates the value involving information of quitters inιi0.9: CS performs the aggregation∏i=1nCki and decrypts to get ∑i=1nΘiXki.10: CS computeserrork=yk−1/1+e−∑i=1nΘiXki+ΘsXks.11: broadcastserrork.12: Each participant and CS can update weight parameter by computingΘi=Θi+α/m∑k=1m‍errorkXki−λ/mΘi.13: Repeat all until reaching the termination condition.14:return built model.


## 4.3.1. Secure Training

For logistic regression to find the better model with gradient descent method, the part that needs to be computed jointly iserror using the predicted value and the sample label. It is better for CS to do the aggregation and calculation since sample labels are mastered by CS. The workflow is shown in Figure 4. To protect the confidentiality of each participant’s data, the aggregated data is received in ciphertext. Consequently, we chose to use Paillier homomorphic encryption to do the computation. However, each participant’s data cannot be decrypted separately by CS; for this reason, we apply Shamir secret sharing scheme such as Formula (7) to ensure that CS could decrypt only after the aggregation operation was completed. The detailed process is shown in Algorithm 2.Figure 4
Workflow of the VFLR.The number of common entities of all participants ism, the average participants in the joint modeling are UiUi∈U, and each average participant secretly keeps a subsecret as si. Now given a cyclic group G and its primitive g, Uii∈1,n computes Dki=ΘiXki, in which Xki is the kth sample for the ith participant Ui. With subsecret si and identities, Ui can compute its own siιi0. In order to keep the subsecret si dynamic, for each sample, Ui adds a random factor or the time stamp βik to calculate Cki=gsiιi0∑i=1nβikEkpDki and sends it to CS after other participants release their gβik. At this point, although CS gets the ciphertext of each participant, he cannot decrypt it because he cannot get the subsecret si. Only when messages are received from at least t participants can aggregation ∏i=1nCki that can be generated, i.e.,
(8)∏i=1nCki=∏i=1ngsiιi0∑i=1nβikEkpDki=g∑i=1nsiιi0∑i=1nβikEkp∑i=1nDki,where g∑i=1nsiιi0∑i=1nβik=g∑i=1nβikkp. Because kp and g∑i=1nβik are public to CS, CS can decrypt and get ∑i=1nΘiXki to compute errork. The next step, CS will broadcast errork to current participants U′U′⊆U. Each participant and CS can update weight parameter by computing Θi=Θi+α/m∑k=1merrorkXki−λ/mΘi. All steps are repeated until the maximum number of iterations is reached.


## 4.3.2. Withdrawal of Participants

Some participants may withdraw from federated learning, such as being unwilling to contribute models or dropping offline. In order to deal with the above situation, we can make a contract to reduce the occurrence of withdrawal. It is assumed that each average participantUi will be paid a certain amount based on their contribution in each iteration. The total expenditure and maximum number of iterations set by CS are Amounts and t. The contract signed by all participants is as follows: (1) n average participants submit a deposit to CS, and the deposit is Amounts/t. (2) In the FL, if CS receives all the messages within the maximum allowable period, the errors will be returned normally to all participants according to the protocol. (3) Else, CS will send withdrawal confirmation request to participants who did not send the message. If they report it is delayed, the delayed messages can still be used to compute the aggregated value. But these delayed participants will not get paid this round. (4) Once the participant reports withdrawal, the deposit will be distributed to other online participants, including CS. Rational participants generally do not withdraw in order to maximize their own interests. (5) Upon completion of the FL, deposits will be returned to all the online participants. Particularly, if some participants withdraw during training, CS requires each participant to resend the message without the identity of the quitters in order to decrypt. Because of the randomness of Cki, CS cannot use the message sent twice to perform comparison calculation and get useful data. The reason is that CS still cannot get the subsecret to reconstruct the polynomial.Algorithm 2: VFLR.
Input: a central server CS, a set of participants U=U1,U2,⋯,Un, instance space of m samples of each participants, subshares s1,s2,⋯,sn, cyclic group G, and its primitive g.Output: federated logistic regression model.1:fork=1⟶mdo2:fori=1⟶ndo3:Ui computes Dki=ΘiXki.4:Ui chooses random number βik and makes public its gβik.5:Ui uses others’ gβik to compute Cki=gsiιi0∑i=1nβikEkpDki and sends it to CS.6:fork=1⟶mdo7:if someone exits then8:  CS eliminates the value involving information of quitters inιi0.9: CS performs the aggregation∏i=1nCki and decrypts to get ∑i=1nΘiXki.10: CS computeserrork=yk−1/1+e−∑i=1nΘiXki+ΘsXks.11: broadcastserrork.12: Each participant and CS can update weight parameter by computingΘi=Θi+α/m∑k=1m‍errorkXki−λ/mΘi.13: Repeat all until reaching the termination condition.14:return built model.


## 4.4. Secure Predicting

Secure prediction should ensure that user data privacy is not compromised and that model parameters are not exposed. As described by Algorithm3, results inquirer R intends to provide a set of data for prediction without privacy leakage and all data characteristics correspond to all participants in the current model. First, R, respectively, encrypts the data with Ekp′Xki, for example, Xki belongs to a characteristic that corresponds to Ui. Each participant computes Ekp′XkiΘi through R’s public key kp′ and communicates it to CS. The aggregation operation is still done by CS to protect the parameters Θi from being exposed. Then, CS computes Ekp′XksΘs∏i=1nEkp′XkiΘi and returns it to R. The joint value ΘiXki could be get with private key ks′ by R, which computes predicted results h using hθx=1/1+e−θTx.Algorithm 3: Secure predicting.
Input: federated logistic regression model, results inquirer R, and its instance space.Output: predicted results.1:fori=1⟶ndo2:R, respectively, encrypts the data Ekp′Xki belonging to the characteristics of different participants including CS.3: Each participant computesEkp′XkiΘi and communicates it to CS.4: CS does an aggregate operationEkp′XksΘs∏i=1nEkp′XkiΘi and returns it to R.5:R decrypts and gets ΘiXki.6:R gets predicted results h by hθx=1/1+e−θTx.7:return result h.


## 5. Security Analysis

In this section, we prove that our scheme is secure based on the simulator under the honest-but-curious setting. Recall that the involved parties aren participants U1,U2,⋯,Un and the CS. We assume an honest-but-curious adversary A who can corrupt participants but at most t−1. According to [20], we define the security of our framework by comparing the real interaction and ideal interaction. In the real interaction, there is an environment Z which chooses inputs and receives outputs of uncorrupted participants. The adversary A who can interact arbitrarily with the environment Z forwards all received messages to Z and acts as instructed by Z. We let REALZ,A,π represent the view of A. Similarly, we let IDEALZ,S,F represent the view of S where adversary S and honest participants interact with the environment Z running the dummy protocol in the presence of functionality F.Definition 1.
A protocolπ is secure if for every admissible adversary A attacks the real interaction, there exists a simulator S=Su,Scs attacking the ideal interaction, such that the environment Z cannot distinguish between the ideal view of S and the real view of A.


### 5.1. Security of GAM

In the GAM, although CS can collude with at mostt−1 participants to obtain the privacy of honest participants, they get nothing but aggregated results. Since each participant’s data is encrypted as g∑i=1tβiks1ιi0Ekmik, based on the security of Shamir secret sharing and homomorphic encryption, only the privacy of mik is discussed here.Theorem 2.
For secure aggregated framework, there exists a PPT simulatorSuorScs that can simulate the ideal view IDEALZ,S,Fgam which is computationally indistinguishable from the real view of AuorACS. Fgam is illustrated as Table 2, where a subset W⊆U∪CS represents joint attackers.Table 2
Definition ofFgam.
Give functionfkx1,x2,⋯xn=k−1∏i=1nbrifkxi with homomorphic encryption function fk and ∏i=1nbri=k when i≥t.Fgam’s operation is as follows:(1) On input (Input, sid,mi) from Ui, set xi=mi and send (Input, sid,Ui,mi) to adversary A.(2) On input (Compute, sid,Ui) from Ui, choose ri∈RZP∗ randomly, compute brifkxi, and send them to CS if i≥t. If Ui∈W⊆U is corrupted, send (xi,ri) to it.(3) On input (Aggregate, sid,CS), compute fk−1k−1∏i=1n‍brifkxi and send it to CS.According to whether CS is involved in collusion, the discussion is divided into two situations.Case 1.
Excluding CS fromW.Proof.
Since CS is not compromised, the view constructed by simulatorSu is independent of the input of CS. So the simulator Su can execute a simulation by asking Fgam to generate fake data as inputs of the honest users, but the true inputs for honest-but-curious users. When sending brifkxi, the simulator utilizes random number instead of true data. As aggregating and decrypting, CS returns aggregated result that does not indicate which special participants’ brifkxi are aggregated. Hence, the ideal view simulated by Su is indistinguishable from the real view of Au since it is impossible to determine that ∑i=1U⊇Wxi is obtained from real data.☐Case 2.
Including CS inW.Proof.
To prove the indistinguishability of the views in Case2, the simulator gradually makes some improvements to the protocol. There exists hyb1, hyb2 that imply secure modification to the original protocol, ensuring the indistinguishability of the changed protocol from the original protocol, in our hybrid argument.
hyb1: in this hybrid, the simulatorSCS generates the masked input for honest participants as below:
(9)yi=riEkmik,instead of utilizing
(10)yi=g∑i=1tβiksiιi0Ekmik.
Becauseg∑i=1tβik is a random number, we can get g∑i=1tβiksiιi0 is also a random value. The DDH assumption ensures that it is easy to infer they are indistinguishable.
hyb2: in this hybrid, the simulator generates encryptedEkti by replacing mik with a random number ti. The security of the encryption algorithm ensures the indistinguishability of the two ciphertexts. Therefore, the simulator submits
(11)yi=riti,instead of sending
(12)yi=riEkmik.
Accordingly, the simulation has been completed sinceSCS successfully simulates the real view without acquiring xi(mik) and subsecret si and we can infer that the output of this hybrid is indistinguished from the real one.☐


### 5.2. Security of MEMP

In the process of confirming the identity of the common entity, no entity information other than a common identity is available between participants. Thus, not only can the true identity of the entity not be exposed but its hash value cannot be either. The reason is that some honest-but-curious participants can calculate the hash value of a possible identifier to determine whether it belongs toUi. It is necessary to cover the confidential information with a random factor similar to a blind signature. We prove the following two theorems by constructing two separate simulators Su and Scs to show that the real views and ideal views are computationally indistinguishable.Theorem 3.
For group entity matching, there exists a PPT simulatorSu or Scs that can simulate the ideal view IDEALZ,S,Fem which is computationally indistinguishable from the real view of Au or Acs.Let us divideFem into two parts, such as Fem1 and Fem2. Fem1 is the process from the beginning to the establishment of the comparison matrix, and Fem2 means the process from the encrypted comparison matrix to the end, similar to the previous Fgam. The description of Fem1 is shown in Table 3.Table 3
Definition ofFem1.
Fem1’s operation is as follows:(1) On input (Init, sid,idi,IDi1,IDi2,⋯,IDik) from Ui, generate random numbers hi1,hi2,⋯,hik for the corresponding IDi1,IDi2,⋯,IDik, store (idi,IDi1,hi1,IDi2,hi2,…), and send (idi,IDi1,hi1,IDi2,hi2,…) to corrupted adversary A.(2) On input (Init, sid,CS,IDs1,IDs2,⋯,IDsl) from CS, generate l random numbers hs1,hs2,⋯,hsl.Once the IDs of the CS and Ui are equal, there sets hsj=hit, j∈1,k,t∈1,l.For corrupted CS, send (ids,IDs1,hs1,IDs2,hs2,⋯) to it. Store them.(3) On input (signature, sid,Ui,di) from Ui, choose ri∈RZP∗ randomly, and compute signdi,reeihit.Send them to CS and store (Ui,sid,ri).(4) On input (Bsignature, sid,CS,d,signdi,reeihit) from CS, compute signd,signdi,reeihit.Send rsisignd,signdi,reeihit to Ui, where rsi are random numbers.(5) On input (Open, sid,Ui,signd,signdi,reeihit) from Ui. Check whether there exists (Ui,sid,ri).If exiting, hitdrsiei can be got, or abandon it. Generate random Hit and store (Ui,sid,hitdrsiei,Hit).(6) On input (Sign, sid,CS,Ui,d), compute (signd,hsjrsieei). Generate random Hsj for every signd,hsjrsieei.If existing signd,hsjrsieei=hitdrsiei, setting Hsj=Hit and storing (CS,sid,hitdrsiei,Hsj). Send (CS,sid,Hsj) to the corresponding Ui.(7) On input (Compare, Ui,sid,CS), generate the l−dimensional comparison matrix using 1 and random numbers, where there exist Hsj in (Ui,sid,hitdrsiei,Hit), 1 will be set, or a random number will be set.Here, we only complete the proof of the ideal viewIDEALZ,S,Fem1 which is computationally indistinguishable from the real view of Au or Acs. There are still two cases to prove.Case 1 (excluding CS fromW).
Just consider the average participantsUi that are compromised.Proof.
Suppose a group of participants is corrupted in the beginning. Because the views of corrupted participants and the inputs of honest participants are irrelevant and the values of all honest participants are meaningless for corrupted participants according to the real protocolπem, so the simulator Su first can run the protocol with the true inputs while using dummy data as the inputs of honest participants, namely, Su asks Fem1 to generate random numbers as the inputs of honest particpants. After the blind signature is executed, the value returned from CS is added with a random number of CS so that Su cannot distinguish whether the values are generated from real data. Then, an l-dimensional matrix is generated by comparing dummy data with a set of generated comparative values from CS. Since the participant’s entity data does not leave the local, the generated matrix is derived from random numbers. Hence, the simulated l-dimensional matrix is indistinguishable from the one that is using true data for comparison.☐Case 2 (including CS inW).
Namely, consider the corrupted CS andUi.Proof.
For the corrupted CS andSu, denote the views of CS and participants Ui as VCS=viewCS and Vu=viewu1,viewu2,⋯,viewun. Based on the process of the MEMP, we can derive viewCS=vik,cik,dij and viewui=vik,cik,gik, where i∈1,n, j∈1,l and ik refers to the kth entity’s identity of the ith participants. It can be found that the elements belonging to viewCS and viewui can be treated as random values. Therefore, we can infer that viewCS and viewui are simulatable for SCS and Su, and the simulated views cannot be distinguished computationally by the adversary.The proof of the second part aboutFem2 is similar to Theorem 2, so we will not go into details.


### 5.3. Security of VFLR

In the model training, CS needs to get messages sent by at leastt participants to decrypt the correct value so that the data for each participant cannot be retrieved and messages retrieved by CS can only be aggregated values without revealing anything else due to the combination of homomorphic encryption and threshold methods. The following theorem will be proved to show the security of the VFLR model.Theorem 4.
For secure VFLR model, there exists aPPT simulator Su or Scs that can simulate the ideal view IDEALZ,S,Fml which is computationally indistinguishable from the real view ofAu or Acs.Our VFLR calls the previous aggregation framework, and its security is based on the proof of Theorem2. Since Theorem 2 has been proved, here we only do a simple description for VFLR.Proof.
Similar to the proof of Theorem2, for a group of corrupted participants, Su can run them using their local data while for honest participants Su simulate them with dummy data. Therefore, Su run Fml to generate random values to replace the masked ΘiXki as the inputs of honest participants. In the model building, what the honest-but-curious participants get is the errors rather than some information that reflects real data and they cannot identify whether the aggregated values used to calculate the errors are based on real data. Therefore, the view of Su is indistinguishable from a real one.☐Considering the corrupted CS,SCS run Fml to generate dummy labels, with which Fml computes the errors after obtaining the aggregation. Because local data are within honest participants, the outputs cannot reveal specific information. Therefore, there exist a PPT simulator Scs that can simulate the ideal view which is computationally indistinguishable from the real view of Acs.


## 5.1. Security of GAM

In the GAM, although CS can collude with at mostt−1 participants to obtain the privacy of honest participants, they get nothing but aggregated results. Since each participant’s data is encrypted as g∑i=1tβiks1ιi0Ekmik, based on the security of Shamir secret sharing and homomorphic encryption, only the privacy of mik is discussed here.Theorem 2.
For secure aggregated framework, there exists a PPT simulatorSuorScs that can simulate the ideal view IDEALZ,S,Fgam which is computationally indistinguishable from the real view of AuorACS. Fgam is illustrated as Table 2, where a subset W⊆U∪CS represents joint attackers.Table 2
Definition ofFgam.
Give functionfkx1,x2,⋯xn=k−1∏i=1nbrifkxi with homomorphic encryption function fk and ∏i=1nbri=k when i≥t.Fgam’s operation is as follows:(1) On input (Input, sid,mi) from Ui, set xi=mi and send (Input, sid,Ui,mi) to adversary A.(2) On input (Compute, sid,Ui) from Ui, choose ri∈RZP∗ randomly, compute brifkxi, and send them to CS if i≥t. If Ui∈W⊆U is corrupted, send (xi,ri) to it.(3) On input (Aggregate, sid,CS), compute fk−1k−1∏i=1n‍brifkxi and send it to CS.According to whether CS is involved in collusion, the discussion is divided into two situations.Case 1.
Excluding CS fromW.Proof.
Since CS is not compromised, the view constructed by simulatorSu is independent of the input of CS. So the simulator Su can execute a simulation by asking Fgam to generate fake data as inputs of the honest users, but the true inputs for honest-but-curious users. When sending brifkxi, the simulator utilizes random number instead of true data. As aggregating and decrypting, CS returns aggregated result that does not indicate which special participants’ brifkxi are aggregated. Hence, the ideal view simulated by Su is indistinguishable from the real view of Au since it is impossible to determine that ∑i=1U⊇Wxi is obtained from real data.☐Case 2.
Including CS inW.Proof.
To prove the indistinguishability of the views in Case2, the simulator gradually makes some improvements to the protocol. There exists hyb1, hyb2 that imply secure modification to the original protocol, ensuring the indistinguishability of the changed protocol from the original protocol, in our hybrid argument.
hyb1: in this hybrid, the simulatorSCS generates the masked input for honest participants as below:
(9)yi=riEkmik,instead of utilizing
(10)yi=g∑i=1tβiksiιi0Ekmik.
Becauseg∑i=1tβik is a random number, we can get g∑i=1tβiksiιi0 is also a random value. The DDH assumption ensures that it is easy to infer they are indistinguishable.
hyb2: in this hybrid, the simulator generates encryptedEkti by replacing mik with a random number ti. The security of the encryption algorithm ensures the indistinguishability of the two ciphertexts. Therefore, the simulator submits
(11)yi=riti,instead of sending
(12)yi=riEkmik.
Accordingly, the simulation has been completed sinceSCS successfully simulates the real view without acquiring xi(mik) and subsecret si and we can infer that the output of this hybrid is indistinguished from the real one.☐


## 5.2. Security of MEMP

In the process of confirming the identity of the common entity, no entity information other than a common identity is available between participants. Thus, not only can the true identity of the entity not be exposed but its hash value cannot be either. The reason is that some honest-but-curious participants can calculate the hash value of a possible identifier to determine whether it belongs toUi. It is necessary to cover the confidential information with a random factor similar to a blind signature. We prove the following two theorems by constructing two separate simulators Su and Scs to show that the real views and ideal views are computationally indistinguishable.Theorem 3.
For group entity matching, there exists a PPT simulatorSu or Scs that can simulate the ideal view IDEALZ,S,Fem which is computationally indistinguishable from the real view of Au or Acs.Let us divideFem into two parts, such as Fem1 and Fem2. Fem1 is the process from the beginning to the establishment of the comparison matrix, and Fem2 means the process from the encrypted comparison matrix to the end, similar to the previous Fgam. The description of Fem1 is shown in Table 3.Table 3
Definition ofFem1.
Fem1’s operation is as follows:(1) On input (Init, sid,idi,IDi1,IDi2,⋯,IDik) from Ui, generate random numbers hi1,hi2,⋯,hik for the corresponding IDi1,IDi2,⋯,IDik, store (idi,IDi1,hi1,IDi2,hi2,…), and send (idi,IDi1,hi1,IDi2,hi2,…) to corrupted adversary A.(2) On input (Init, sid,CS,IDs1,IDs2,⋯,IDsl) from CS, generate l random numbers hs1,hs2,⋯,hsl.Once the IDs of the CS and Ui are equal, there sets hsj=hit, j∈1,k,t∈1,l.For corrupted CS, send (ids,IDs1,hs1,IDs2,hs2,⋯) to it. Store them.(3) On input (signature, sid,Ui,di) from Ui, choose ri∈RZP∗ randomly, and compute signdi,reeihit.Send them to CS and store (Ui,sid,ri).(4) On input (Bsignature, sid,CS,d,signdi,reeihit) from CS, compute signd,signdi,reeihit.Send rsisignd,signdi,reeihit to Ui, where rsi are random numbers.(5) On input (Open, sid,Ui,signd,signdi,reeihit) from Ui. Check whether there exists (Ui,sid,ri).If exiting, hitdrsiei can be got, or abandon it. Generate random Hit and store (Ui,sid,hitdrsiei,Hit).(6) On input (Sign, sid,CS,Ui,d), compute (signd,hsjrsieei). Generate random Hsj for every signd,hsjrsieei.If existing signd,hsjrsieei=hitdrsiei, setting Hsj=Hit and storing (CS,sid,hitdrsiei,Hsj). Send (CS,sid,Hsj) to the corresponding Ui.(7) On input (Compare, Ui,sid,CS), generate the l−dimensional comparison matrix using 1 and random numbers, where there exist Hsj in (Ui,sid,hitdrsiei,Hit), 1 will be set, or a random number will be set.Here, we only complete the proof of the ideal viewIDEALZ,S,Fem1 which is computationally indistinguishable from the real view of Au or Acs. There are still two cases to prove.Case 1 (excluding CS fromW).
Just consider the average participantsUi that are compromised.Proof.
Suppose a group of participants is corrupted in the beginning. Because the views of corrupted participants and the inputs of honest participants are irrelevant and the values of all honest participants are meaningless for corrupted participants according to the real protocolπem, so the simulator Su first can run the protocol with the true inputs while using dummy data as the inputs of honest participants, namely, Su asks Fem1 to generate random numbers as the inputs of honest particpants. After the blind signature is executed, the value returned from CS is added with a random number of CS so that Su cannot distinguish whether the values are generated from real data. Then, an l-dimensional matrix is generated by comparing dummy data with a set of generated comparative values from CS. Since the participant’s entity data does not leave the local, the generated matrix is derived from random numbers. Hence, the simulated l-dimensional matrix is indistinguishable from the one that is using true data for comparison.☐Case 2 (including CS inW).
Namely, consider the corrupted CS andUi.Proof.
For the corrupted CS andSu, denote the views of CS and participants Ui as VCS=viewCS and Vu=viewu1,viewu2,⋯,viewun. Based on the process of the MEMP, we can derive viewCS=vik,cik,dij and viewui=vik,cik,gik, where i∈1,n, j∈1,l and ik refers to the kth entity’s identity of the ith participants. It can be found that the elements belonging to viewCS and viewui can be treated as random values. Therefore, we can infer that viewCS and viewui are simulatable for SCS and Su, and the simulated views cannot be distinguished computationally by the adversary.The proof of the second part aboutFem2 is similar to Theorem 2, so we will not go into details.


## 5.3. Security of VFLR

In the model training, CS needs to get messages sent by at leastt participants to decrypt the correct value so that the data for each participant cannot be retrieved and messages retrieved by CS can only be aggregated values without revealing anything else due to the combination of homomorphic encryption and threshold methods. The following theorem will be proved to show the security of the VFLR model.Theorem 4.
For secure VFLR model, there exists aPPT simulator Su or Scs that can simulate the ideal view IDEALZ,S,Fml which is computationally indistinguishable from the real view ofAu or Acs.Our VFLR calls the previous aggregation framework, and its security is based on the proof of Theorem2. Since Theorem 2 has been proved, here we only do a simple description for VFLR.Proof.
Similar to the proof of Theorem2, for a group of corrupted participants, Su can run them using their local data while for honest participants Su simulate them with dummy data. Therefore, Su run Fml to generate random values to replace the masked ΘiXki as the inputs of honest participants. In the model building, what the honest-but-curious participants get is the errors rather than some information that reflects real data and they cannot identify whether the aggregated values used to calculate the errors are based on real data. Therefore, the view of Su is indistinguishable from a real one.☐Considering the corrupted CS,SCS run Fml to generate dummy labels, with which Fml computes the errors after obtaining the aggregation. Because local data are within honest participants, the outputs cannot reveal specific information. Therefore, there exist a PPT simulator Scs that can simulate the ideal view which is computationally indistinguishable from the real view of Acs.


## 6. Performance Evaluation

In this section, the effectiveness and efficiency of the experiment are presented.


### 6.1. Experiment Configuration

Four clientsA, B, C, and D are built to simulate the feasibility and performance, in which A, B, and C refer to the average participants and D means the aggregator with sample labels. We carry out our experiments on the device with CPU i7-6700, 3.2 GHz, and Memory 24 G. The programs in the experiments are implemented in Python, and the length of p and q are set to 512 bits for RSA and Paillier. We adopt a finite field ℤP∗ with P=211 and the standard Shamir’s t−n secret sharing to generate the shares of secret.In the MEMP, we generated different random values between 52252800000000000000 and 52252800000000000550 as identification of user samples forA, B, C, and D, respectively, satisfying that the number of intersection of A, B, C, and D is 60, 120, 180, and 240. In VFLR, we selected 300 digits from the handwritten digits dataset (handwritten digit dataset: https://scikit-learn.org/stable/modules/generated/sklearn.datasets.load_digits.html), which contains 64 features. A, B, and C, respectively, hold 20 features in these samples, while D contains 4 features and 1 label. Since the dataset is multiclassified, we set 0 to 4 as category 1 and 5 to 9 as category 2.


### 6.2. Performance Analysis of the MEMP

For the MEMP, in the simulations, we get the execution time ofUi (A,B,C) and the CS (D) when increasing the amount of data from 100 to 500. Note that the time to initialize the system ignored in all experiments and A represents the size of samples in A, the same thing for B,C,D. Ui (A,B,C) first calculates the median value for comparison through CS, the computation of which is related to the amount of their own data, and then the size of the calculated comparison matrix is related to the amount of CS’s data. When the number of samples’ identification of A, B, and C increases, the increase of computation time of A, B, or C is mainly reflected in generating sample identification library, and the most time-consuming in D is the blind signature. Figure 5 shows the calculation time of A and D when the number of samples in D is 100 and the samples in Ui (A,B,C) fluctuate from 100 to 500. Figures 6 and 7 show the changing trend of running time of A and D with the increase of D when the amounts of A, B, and C are all 100. As the sample amount of D is increasing, the encryption time is proportional to the data volume of D. Because the time of aggregation and decryption is related to its own data volume, its identification volume affects the size of an identification matrix, thereby affecting the aggregation volume, resulting in a linear increase in the time of aggregation and decryption. However, changes in the intersection of A, B, C, and D will not affect the respective calculation time that is only related to the amount of data of all parties, as is shown in Figures 8 and 9.Figure 5
Running time with different sample sizes inUi.Figure 6
Running time ofA with increasing samples in D.Figure 7
Running time ofD with increasing samples in D.Figure 8
Running time ofA with different amounts of intersection.Figure 9
Running time ofD with different amounts of intersection.


### 6.3. Performance Analysis of the VFLR

In the VFLR, there is no approximation algorithm applied here so that the updated parameters in our VFLR are exactly the same as those in the traditional logistic regression. Therefore, the training accuracy is also consistent. The main observation here is the running time of the VFLR. The extra cost in training is mainly from power exponent and homomorphism. In the training phase,te represents the time of a complete encryption and ts represents the time of an aggregation and decryption for n paticipants. When the sample size is m, complexity time of encryption and aggregation, respectively, is ote·m and ots·m. We selected 400 samples and set the number of features at each end to 20. When the number of data amount is 100, 200, 300, and 400, respectively, the time for a single end to complete an iteration and the time for D to complete aggregation and decryption are captured. (See Figures 10 and 11.) As the figures show, we gradually adjust the data volume from 100 to 400, and the running time increases approximately linearly.Figure 10
Running time ofUi with different amounts of data.Figure 11
Running time of CS with different amounts of data.


### 6.4. Communication Overhead

Since the establishment of the user identification library and the generation of the comparison matrix can be done offline in the MEMP, we discuss the communication overhead of the MEMP from the perspective of the proposed aggregation model. The same is true for the VFLR, because its execution process is completely consistent with the GAM. Let the length of the ciphertext of each participant becl and the length of the H and error, respectively, be H and error where cl>H and cl>error. In the MEMP, it only takes one turn to complete the comparison and identify the common entity. If CS sends l entity mask, the communication load for each participant is l·cl. In order for participants to complete the comparison, the CS needs to send corresponding entity mask for n participants so that the communication load of CS is H·l·n+n·ID. In the VFLR, we just consider the communication load for one iteration. Each participant sends ciphertext of size cl·m. The CS just needs to return errors of m samples, so the communication load of CS is m·error. In this way, the total space complexity of MEMP and VFLR can be expressed as on·l·cl and on·m·cl. We can see that as the number of participants or samples increases, the total communication overhead also grows linearly.


## 6.1. Experiment Configuration

Four clientsA, B, C, and D are built to simulate the feasibility and performance, in which A, B, and C refer to the average participants and D means the aggregator with sample labels. We carry out our experiments on the device with CPU i7-6700, 3.2 GHz, and Memory 24 G. The programs in the experiments are implemented in Python, and the length of p and q are set to 512 bits for RSA and Paillier. We adopt a finite field ℤP∗ with P=211 and the standard Shamir’s t−n secret sharing to generate the shares of secret.In the MEMP, we generated different random values between 52252800000000000000 and 52252800000000000550 as identification of user samples forA, B, C, and D, respectively, satisfying that the number of intersection of A, B, C, and D is 60, 120, 180, and 240. In VFLR, we selected 300 digits from the handwritten digits dataset (handwritten digit dataset: https://scikit-learn.org/stable/modules/generated/sklearn.datasets.load_digits.html), which contains 64 features. A, B, and C, respectively, hold 20 features in these samples, while D contains 4 features and 1 label. Since the dataset is multiclassified, we set 0 to 4 as category 1 and 5 to 9 as category 2.


## 6.2. Performance Analysis of the MEMP

For the MEMP, in the simulations, we get the execution time ofUi (A,B,C) and the CS (D) when increasing the amount of data from 100 to 500. Note that the time to initialize the system ignored in all experiments and A represents the size of samples in A, the same thing for B,C,D. Ui (A,B,C) first calculates the median value for comparison through CS, the computation of which is related to the amount of their own data, and then the size of the calculated comparison matrix is related to the amount of CS’s data. When the number of samples’ identification of A, B, and C increases, the increase of computation time of A, B, or C is mainly reflected in generating sample identification library, and the most time-consuming in D is the blind signature. Figure 5 shows the calculation time of A and D when the number of samples in D is 100 and the samples in Ui (A,B,C) fluctuate from 100 to 500. Figures 6 and 7 show the changing trend of running time of A and D with the increase of D when the amounts of A, B, and C are all 100. As the sample amount of D is increasing, the encryption time is proportional to the data volume of D. Because the time of aggregation and decryption is related to its own data volume, its identification volume affects the size of an identification matrix, thereby affecting the aggregation volume, resulting in a linear increase in the time of aggregation and decryption. However, changes in the intersection of A, B, C, and D will not affect the respective calculation time that is only related to the amount of data of all parties, as is shown in Figures 8 and 9.Figure 5
Running time with different sample sizes inUi.Figure 6
Running time ofA with increasing samples in D.Figure 7
Running time ofD with increasing samples in D.Figure 8
Running time ofA with different amounts of intersection.Figure 9
Running time ofD with different amounts of intersection.


## 6.3. Performance Analysis of the VFLR

In the VFLR, there is no approximation algorithm applied here so that the updated parameters in our VFLR are exactly the same as those in the traditional logistic regression. Therefore, the training accuracy is also consistent. The main observation here is the running time of the VFLR. The extra cost in training is mainly from power exponent and homomorphism. In the training phase,te represents the time of a complete encryption and ts represents the time of an aggregation and decryption for n paticipants. When the sample size is m, complexity time of encryption and aggregation, respectively, is ote·m and ots·m. We selected 400 samples and set the number of features at each end to 20. When the number of data amount is 100, 200, 300, and 400, respectively, the time for a single end to complete an iteration and the time for D to complete aggregation and decryption are captured. (See Figures 10 and 11.) As the figures show, we gradually adjust the data volume from 100 to 400, and the running time increases approximately linearly.Figure 10
Running time ofUi with different amounts of data.Figure 11
Running time of CS with different amounts of data.


## 6.4. Communication Overhead

Since the establishment of the user identification library and the generation of the comparison matrix can be done offline in the MEMP, we discuss the communication overhead of the MEMP from the perspective of the proposed aggregation model. The same is true for the VFLR, because its execution process is completely consistent with the GAM. Let the length of the ciphertext of each participant becl and the length of the H and error, respectively, be H and error where cl>H and cl>error. In the MEMP, it only takes one turn to complete the comparison and identify the common entity. If CS sends l entity mask, the communication load for each participant is l·cl. In order for participants to complete the comparison, the CS needs to send corresponding entity mask for n participants so that the communication load of CS is H·l·n+n·ID. In the VFLR, we just consider the communication load for one iteration. Each participant sends ciphertext of size cl·m. The CS just needs to return errors of m samples, so the communication load of CS is m·error. In this way, the total space complexity of MEMP and VFLR can be expressed as on·l·cl and on·m·cl. We can see that as the number of participants or samples increases, the total communication overhead also grows linearly.


## 7. Related Work

Many privacy-preserving models for specific machine learning algorithms have emerged. There mainly exist two kinds of technologies adopted in the privacy-preserving training, i.e., differential privacy [21] and cryptography-based approaches. Differential privacy applied to FL can prevent clients from trying to reconstruct the private data of other clients by exploiting the global model, as done in [13, 22]. It adds noise to the original dataset or gradient parameters while ensuring the availability of the data. But it brings low accuracy. The cryptographic technologies can provide privacy protection while ensuring accuracy. Secure multiparty computation, secret sharing, and homomorphic encryption are the common methods. For example, Aono et al. [23] used homomorphic encryption to improve the logistic regression algorithm ensuring the security of the training and predicting data. Liu et al. [24] propose a secret sharing-based federated extreme boosting learning framework to achieve privacy-preserving model training for mobile crowdsensing. Xu et al. [25] proposed a privacy-preserving and verifiable federated learning framework based on homomorphic hash functions, in which clients can verify whether the result returned by cloud server is correct.Some previous works with privacy preserving over vertical data partition are discussed in [26, 27]. However, there exist potential privacy risks as a result of revealing class distribution over the given attributes. Research on VFL is first proposed in [28], where a federated logistic regression scheme is designed through an additively homomorphic scheme. Nock et al. [29] then provide a formal assessment of how errors in entity resolution impact learning. Cheng et al. [30] propose a novel lossless privacy-preserving tree-boosting system, which conducts a learning process on multiple parties with partially common user samples but different feature sets. Fu et al. [31] combines Lagrange interpolation and Chinese remainder theorem to realize the secure aggregation of gradients. But some works assume sample entities already being matched or they only deal with two VFL participants. The proposed framework is more advantages than those approaches as it can support multiparticipant VFL by taking into account entity matching and model training with withdrawal of participants. Table 4 shows the functional comparison between our framework and existing two main works from GAM, multiparticipants (M-p), entity matching (EM), withdrawal of participants (WP). Table 5 shows the comparison of computation and communication mainly for secure aggregation from the participant and aggregator’s main function operation, communication rounds (Comm-rounds), and mask number (i.e., the number of message received by the aggregator), where SC represents the times of secret reconstruction, CR represents the times of calculation of Chinese residual theorem, HE represents the times of homomorphic encryption, R represents the times of pseudorandom generator, and P represents the times of calculation of the power exponent. It can be seen from Table 5 that our scheme has advantages over reference [25] in terms of calculation and communication overhead. Compared with [25, 31], although our scheme applies the principle of secret sharing, it does not need to spend the overhead of secret reconstruction.Table 4
Comparison of functionality.
SchemeGAMM-pEMWPCheng et al.’s scheme [30]×√××Fu et al.’s scheme [31]√√××Our scheme√√√√Table 5
Comparison of computation and communication.
SchemeParticipantAggregatorComm-roundsMask numberXu et al.’s scheme [25]1R+2SCtSC2n·t+1Fu et al.’s scheme [31]2SC+2CR1CR1nOur scheme1R+1HE+1P1HE+1P1n


## 8. Conclusion

For privacy protection of data aggregation and joint training in federated learning, as well as entity matching, we designed a PFLF where we proposed a general aggregation model and designed a multiparty entity matching protocol, which can find the common entity of multiple participants without data disclosure. In addition, our GAM was used to improve logistic regression algorithm to ensure the confidentiality of data samples during training and support the withdrawal of participants over VFL. The security analysis of the scheme was given based on the simulator, and the performance of the system was tested with the experimental data. The next research will focus on optimizing the operating load of the system and considering cases where the participants are malicious to construct a verifiable federated learning framework and design incentives to facilitate federated learning.



---

*Source: 6692061-2021-06-28.xml*