# Efficient Personalized Recommendation Based on Federated Learning with Similarity Ciphertext Calculation

Authors: Xixian Wang; Xiaoming Wang; Binrui Huang; Mingzhan Dai; Jianwei Li
Journal: Security and Communication Networks
 (2022)

---

## Abstract

With the popularity of big data, people get less useful information because of the large amount of data, which makes the Recommender System come into being. However, the privacy and accuracy of the Recommender System still have great challenges. To address these challenges, an efficient personalized recommendation scheme is proposed based on Federated Learning with similarity ciphertext calculation. In this paper, we first design a Similarity calculation algorithm based on Orthogonal Matrix in Ciphertext (SOMC), which can compute the Similarity between users’ demand and Items’ attributes under ciphertext with a low calculation cost. Based on SOMC, we construct an efficient recommendation scheme by employing the Federated Learning framework. The important feature of the proposed approach is improving the accuracy of recommendation while ensuring the privacy of both the users and the Agents. Furthermore, the Agents with good performance are selected according to their Reliability scores to participate in the federal recommendation, so as to further make the accuracy of recommendation better. Under the defined threat model, it is proved that the proposed scheme can meet the privacy requirements of users and Agents. Experiments show that the proposed scheme has optimized accuracy and efficiency compared with existing schemes.


---

## Body

## 1. Introduction

With the rise of big data, information overload makes people get more useless information. Therefore, Recommender System is gradually popular, the purpose of Recommender System is providing users with personalized online products or service recommendations, and Recommender System has become an important way to resolve information overload issues, which brings opportunities and challenges to education, medical and other industries. However, the current Recommender System has many potential risks, of which the privacy disclosure is one of the primary concerns [1]. In general, the Recommender System consists of two parts: recommender server and users. In order to get a superior model for recommendation, the traditional Recommender System uses a central architecture and usually collects a large amount of feedback information such as user preferences [2]. But the information is often sensitive to users and can lead to serious privacy and security risks: the users’ raw data may be disclosed from the feedback information from some programs [3]. For example, Recommender System only needs to obtain the records about users watching movies, and can infer some privacy information (e.g., age, income, medical history, etc.). In addition, Recommender System may collect users’ personal data and share it with a third party to obtain profits [4]. Once this information is abused, the consequences are unimaginable.As a result, people are increasingly concerned about their data privacy, and they hope that their private information will not be known by Internet applications. In existing research, there are many methods to protect data privacy, such as anonymity, differential privacy, homomorphic encryption and Federated Learning (FL). Federated Learning is a popular tool to reduce privacy risks. Thus, FL has received increasing attention. Such as [5], it uses FL to protect users’ healthcare data privacy in the big data scenario. And in [6], based on the framework of FL, a recommendation scheme is proposed. The scheme defines multiple agents for collaborative recommendation, and the FL framework is used to ensure the users’ data privacy and to make the recommended items more reliable. However, in the system model of this scheme, the settings of the cloud are completely trusted, which is difficult to achieve in practice, and all the records are stored in the cloud in plaintext, so there is still a risk of exposing privacy.In other aspects, the concept of similarity is often introduced in order to achieve better recommendations [7, 8]. Generally, in order to ensure the accuracy of recommended items, many Recommender Systems need to calculate two parameters [9]. One is the similarity between users’ demands and the attributes of recommended items, and the other is the users’ evaluations about recommendation items. For the former, the higher similarity implies that the items will be more appropriate for the needs of users. For the latter, it means that items will have higher recommendation priority. After receiving recomendation items, the users will evaluate the recommendation items, i.e., submit feedback scores. The Recommender System will collect these scores and calculate the reliability of the recommendation agents according to the evaluations.Obviously, it is essential to protect users’ privacy in the current Recommender System. When users submit requirements or estimates, they wish their information to be protected. This is because the users’ demands and evaluations are usually related to the privacy of information [10]. To solve these problems, some feasible solutions were provided, such as [9, 11], but there are some problems: the encryption method is too complicated and the computation load is too heavy, and the server is set to be fully trusted, which is difficult to achieve in reality.To address these above challenges, we first set the cloud to be semi-trusted, which means that it is possible to spy on users’ privacy. This makes our scheme have better practicability. Then we take the similarity as the criterion to select the recommendation items to improve the accuracy of recommendations. Next each user evaluates the recommendation items after receiving items, and the Cloud server evaluates the reliability of the recommendation agents according to the evaluations. Last, our scheme uses the FL framework to improve recommendation accuracy and protect users’ privacy. The comparison of our scheme and some studies about recommendation is discussed in Table1.Table 1
Recommended method comparison.
SchemesEncryption methodCloudFrameworkZhang et al. [12].BGNhonest-but-curiouscentralizedXu et al. [13]Modified Paillierhonest-but-curiouscentralizedPeng et al. [10]MTDT-PKChonest-but-curiouscentralizedZhou et al. [6]Nonefully trustedFLour schemeSOMChonest-but-curiousFLIn this paper, we focus on how to perform a more secure and effective recommendation process with a Federated Learning framework. Our contribution is summarized as follows:(i)
We design a Similarity calculation algorithm based on Orthogonal Matrix in Ciphertext (SOMC), which can not only reduce the calculation overhead, but also ensure the privacy and security of users.(ii)
Based on SOMC, we construct an efficient recommendation scheme by employing the Federated Learning model, named Efficient Recommendation Based on Federated Learning (ERBFL). ERBFL can securely aggregate the recommendation weight from the multiple Agents and calculate the similarity between users’ demand and Items’ attributes under ciphertext, so as to improve the accuracy of recommendation while ensuring the privacy of both the users and the Agents. Moreover, the Agents with the good performance are selected according to their Reliability scores to participate in the federal recommendation, so as to further make better the accuracy of recommendation.(iii)
Under the defined threat model, we prove the proposed scheme is to meet the privacy requirements of users and Agents. In addition, we conduct experiments that show our scheme has optimized accuracy and efficiency compared with existing schemes.The rest of this paper is divided into six parts. State-of-the-art solutions about the privacy protection problem of Recommender System are described in Section2. Following this we present the preliminaries of proposed work in Section 3. ERBFL scheme is discussed in detail in Section 4, and its security analysis are presented in Section 5. Comprehensive performance evaluation is given in Section 6. Conclusions are drawn in Section 7.


## 2. Related Works

Recent years, Recommender System helps to solve the problem of information overload while providing personalized information retrieval [14]. However, in order to improve the recommendation efficiency, the system requires the personal information of users, which is a serious privacy concern for many users [15, 16]. Recent research indicates that there are two methods to solve the privacy problem of the Recommender system: Architecture-based and Algorithms-based [17].Architecture-based solutions usually exploit distributed data storage to minimize the threat of data leakage, but some existing schemes [18, 19] still have the risk of leaking users’ privacy and increasing the computing burden of local devices. Algorithms-based solutions are different from them, usually utilize an encryption algorithm to protect the original sensitive data. Several studies have revealed that the encryption-based solution can reduce the risk of leaking users’ privacy [17]. At present, some researchers have proposed various solutions to the privacy protection recommendation system, such as [20–22]. Erkin et al. [20] prevented the malicious users and server from accessing privacy-sensitive data by using homomorphic encryption. Kaur et al. [21] introduced arbitrary distributed data based on two techniques: multi-party random masking and polynomial aggregation, which can improve the efficacy of recommender system and protect users’ privacy. Ma et al. [22] realized a friend recommendation in a way of protecting privacy by utilizing social attributes and trust relationship about online social network users. However, these schemes all cause heavy computational overhead.Besides, to ensure the accuracy of the recommendation items, the current Recommender System will take the similarity as the reference parameter of recommendation. In [23], the similarity between users is calculated to help get more accurate recommendation results. In [24], the similarity between users and items is calculated. To further improve the accuracy of recommendations, asymmetric similarity method was mentioned in [25], where weighted schemes made recommendations more accurate, taking into account the varying degrees of influence of each factor. But that will raise privacy issues. This is due to the similarity calculation in the recommendation process will involve the user’s privacy information, the recommender server may be able to know the users’ personal interests, which contain sensitive information. Some studies have proposed solutions to this problem, such as [12, 13, 26]. Li et al. [26] proposed a privacy-preserving scheme to implement a contextual recommendation for online social communications, which can hide users’ real identities from other users by using pseudonyms. Zhang et al. [12] used BGN Cryptosystem to protect users’ privacy in the recommendation process, which utilized homomorphic property to calculate the similarity between two users in the ciphertext domain. However, the scheme causes heavy computing burden on the user side, in which the computation of bilinear pairs is used. In addition, Xu et al. [13] focused on similarity and evaluation of truth to propose a privacy-preserving recommendation scheme. However, it used a centralized framework so that it is unsuitable for the scenario with multiple recommenders. FL can solve this problem very well. Many existing studies utilize FL to achieve collaboration while protecting data privacy. In [27], a scheme called EPPDA was proposed, which can resist the reverse attack by utilizing secret sharing and an efficient privacy-preserving data aggregation method for FL.In order to address the above privacy problems and improve accuracy, Federated Recommendation System(FedRec) is proposed, the goal of FedRec is to collaborate with multiple parties to complete the more efficient and accurate recommendation process without directly accessing each other’s private data [4]. To perform the recommendation process in multiple data-owners scenarios, Zhou et al. [6] implemented a privacy-preserving contextual recommendation which used Federated Learning framework to protect users’ privacy and increase efficiency of recommendation. However, in the scheme, the center server is set to be fully trusted, which is hard to meet in practice [28], and the center server processes the sensitive data in plaintexts, which raises privacy risk [29, 30]. For instance, some malicious Cloud servers may apply gradient inference attacks or model inversion attacks to damage the client’s sensitive data, as described in [31, 32]. Hence, it is impractical that schemes are under the assumption that the Cloud server is full-trusted.


## 3. Preliminaries

### 3.1. Orthogonal Matrices

Orthogonal matrix is an important type of matrix [33]. When the product of a matrix and its transpose gives the value of the identity matrix, the matrix is called an orthonormal matrix.These matrices are useful in many scientific applications related to vectors.SupposeA and B are n×n orthogonal matrices which can also be represented by A=a1⟶,a2⟶,…,an⟶,B=b1⟶,b2⟶,…,bn⟶, where ai⟶,bi⟶∈ℝn,1≤i≤n. The symbol ℝn represents an infinitely large set of vectors, where each vector has n components. Mathematically, v⟶=v1,v2,…,vn⊤,vi∈ℝ;1≤i≤n, where ⊤ is the transpose symbol. A is a orthogonal matrix, if and only if:(1)ai⟶⊤⋅aj⟶=ai1aj1+ai2aj2+⋯+ainajn=1i=j,0i≠j.Meanwhile, letA⊤ and B⊤ are the transpose matrices of A and B, respectively. Then they have the properties as follows:(i)
A⋅A⊤=E , B⋅B⊤=E ;(ii)
A−1=A⊤ , B−1=B⊤ ;(iii)
AB⊤=B⊤A⊤ ;(iv)
AB−1=B−1A−1;whereE is the identity matrix of the order n×n. ⋅−1 is the inverse of matrix ⋅.Interestingly, the inverse and transpose of an orthogonal matrix are the same that make the inverse operation of the orthogonal matrix simple and fast. In light of this, it is efficient to use orthogonal matrices as cipher keys.


### 3.2. Differential Privacy

Differential privacy (DP) is a promising technology which can solve privacy problems [34]. We have adopted the local version of DP for users, which can protect users’ privacy under untrusted Cloud server and Agents. We introduce several definitions about differential privacy as follows [35]:Definition 1.
(ε-Differential Privacy, ε-DP). A random mechanism ℒ is said ε-indistinguishable if for all pairs X⟶,X′⟶∈Dp which differs in only one entry, for all adversaries A, and for all transcripts t, where Dp is p-dimensional vector data set:(2)lnPrTAX⟶=tPrTAX′⟶=t≤ε.
In the definition, a privacy parameterε is predefined in order to control the privacy budget, which means that if ε is smaller, the privacy protection will be stronger.Definition 2.
(L1-Sensitivity). Assume that f is a numeric query function, and f maps a data set Dp into a p-dimensional real space ℝp such as f:Dp⟶ℝp. For any pair of adjacent data sets Dp and D′p, the sensitivity about f is defined as:(3)Δf=maxDp,D′pfDp−fD′pL1,where ⋅L1 denoted the L1 norm.
Theorem (Random-Laplace Mechanism). Letb∈ℝ+, and f is a numeric query function which maps a p-dimensional domain Dp p-dimensional real space ℝp, such as f:Dp⟶ℝp. The mechanism ℒ randomly selects t elements in vector X⟶, where t satisfies the following condition: t=⌈p/3⌉.(4)ℒX⟶=fX⟶+Lap1b,Lap2b,…,Lappb,provides ε-Differential Privacy, where selected subscript j: Lapjb=0. Other Lapib is drawn from the Laplace distribution with scaling parameter b, where b’s density function is(5)db=12bexp−xb,where b=Δf/ε is bound by the privacy budget ε and the sensitivity of function Δf.


### 3.3. Digital Signature

Digital Signature is used to prevent information from being tampered with [36]. Digital Signature Λ is composed of the algorithms Λ.KeyGen,Λ.Sign,Λ.Verify defined as follows:Λ.KeyGen1λ⟶sk,pk: It takes as input 1λ, and outputs a key pair sk,pk, where λ is a security parameter.Λ.Signsk,m⟶σ: It takes as input the private key sk and the message m, and outputs the signature σ.Λ.Verifypk,m,σ⟶0,1: It takes as input the public pk, the message m, and the signature σ, and it outputs 0 if the signature σ is invalid and 1 otherwise.


### 3.4. Federated Learning

In order to improve the accuracy of predicting users’ next input, Google built a horizontal federated model, and Google first proposed a concept of Federated Learning (FL) in 2017 [37]. FL is a distributed deep learning framework, and it allows multiple clients such as IoT devices and mobile devices to train the model, but the sensitive privacy data in the device remains local, the joint model trained by the server is sent back to each client, and the client continues to learn the new model. The process iterates to get the optimal model [38]. Therefore, the privacy of the client has been protected to a certain extent.


## 3.1. Orthogonal Matrices

Orthogonal matrix is an important type of matrix [33]. When the product of a matrix and its transpose gives the value of the identity matrix, the matrix is called an orthonormal matrix.These matrices are useful in many scientific applications related to vectors.SupposeA and B are n×n orthogonal matrices which can also be represented by A=a1⟶,a2⟶,…,an⟶,B=b1⟶,b2⟶,…,bn⟶, where ai⟶,bi⟶∈ℝn,1≤i≤n. The symbol ℝn represents an infinitely large set of vectors, where each vector has n components. Mathematically, v⟶=v1,v2,…,vn⊤,vi∈ℝ;1≤i≤n, where ⊤ is the transpose symbol. A is a orthogonal matrix, if and only if:(1)ai⟶⊤⋅aj⟶=ai1aj1+ai2aj2+⋯+ainajn=1i=j,0i≠j.Meanwhile, letA⊤ and B⊤ are the transpose matrices of A and B, respectively. Then they have the properties as follows:(i)
A⋅A⊤=E , B⋅B⊤=E ;(ii)
A−1=A⊤ , B−1=B⊤ ;(iii)
AB⊤=B⊤A⊤ ;(iv)
AB−1=B−1A−1;whereE is the identity matrix of the order n×n. ⋅−1 is the inverse of matrix ⋅.Interestingly, the inverse and transpose of an orthogonal matrix are the same that make the inverse operation of the orthogonal matrix simple and fast. In light of this, it is efficient to use orthogonal matrices as cipher keys.


## 3.2. Differential Privacy

Differential privacy (DP) is a promising technology which can solve privacy problems [34]. We have adopted the local version of DP for users, which can protect users’ privacy under untrusted Cloud server and Agents. We introduce several definitions about differential privacy as follows [35]:Definition 1.
(ε-Differential Privacy, ε-DP). A random mechanism ℒ is said ε-indistinguishable if for all pairs X⟶,X′⟶∈Dp which differs in only one entry, for all adversaries A, and for all transcripts t, where Dp is p-dimensional vector data set:(2)lnPrTAX⟶=tPrTAX′⟶=t≤ε.
In the definition, a privacy parameterε is predefined in order to control the privacy budget, which means that if ε is smaller, the privacy protection will be stronger.Definition 2.
(L1-Sensitivity). Assume that f is a numeric query function, and f maps a data set Dp into a p-dimensional real space ℝp such as f:Dp⟶ℝp. For any pair of adjacent data sets Dp and D′p, the sensitivity about f is defined as:(3)Δf=maxDp,D′pfDp−fD′pL1,where ⋅L1 denoted the L1 norm.
Theorem (Random-Laplace Mechanism). Letb∈ℝ+, and f is a numeric query function which maps a p-dimensional domain Dp p-dimensional real space ℝp, such as f:Dp⟶ℝp. The mechanism ℒ randomly selects t elements in vector X⟶, where t satisfies the following condition: t=⌈p/3⌉.(4)ℒX⟶=fX⟶+Lap1b,Lap2b,…,Lappb,provides ε-Differential Privacy, where selected subscript j: Lapjb=0. Other Lapib is drawn from the Laplace distribution with scaling parameter b, where b’s density function is(5)db=12bexp−xb,where b=Δf/ε is bound by the privacy budget ε and the sensitivity of function Δf.


## 3.3. Digital Signature

Digital Signature is used to prevent information from being tampered with [36]. Digital Signature Λ is composed of the algorithms Λ.KeyGen,Λ.Sign,Λ.Verify defined as follows:Λ.KeyGen1λ⟶sk,pk: It takes as input 1λ, and outputs a key pair sk,pk, where λ is a security parameter.Λ.Signsk,m⟶σ: It takes as input the private key sk and the message m, and outputs the signature σ.Λ.Verifypk,m,σ⟶0,1: It takes as input the public pk, the message m, and the signature σ, and it outputs 0 if the signature σ is invalid and 1 otherwise.


## 3.4. Federated Learning

In order to improve the accuracy of predicting users’ next input, Google built a horizontal federated model, and Google first proposed a concept of Federated Learning (FL) in 2017 [37]. FL is a distributed deep learning framework, and it allows multiple clients such as IoT devices and mobile devices to train the model, but the sensitive privacy data in the device remains local, the joint model trained by the server is sent back to each client, and the client continues to learn the new model. The process iterates to get the optimal model [38]. Therefore, the privacy of the client has been protected to a certain extent.


## 4. Design of Proposed Scheme

Before introducing the proposed scheme, we first give the basic symbols involved in the scheme. We defineUi is Ageni’s user group, U is a set of user groups: U=Ui,i=1,2,…,U where U is the size of Agents. Note that here Ui=ui,j,j=1,2,…,Ui is a subgroup of U based on geographic location, in which Ui is a size of users included in Ui. For each user ui,j∈Ui, we define the vector Ai,j⟶=aij,1,aij,2,…,aij,p⊤ as ui,j’s demand vector, where aij,l refers to an attribute about ui,j’s demand.EachUi∈U has a corresponding Ageni, and Ageni holds a Item set ℐi=Ii,i′,i′=1,2,…,ni where ni is the size of Ageni’s Items. We define the vector Bi,i′⟶=bii′,1,bii′,2,…,bii′,p⊤ as Ii,i′’s attribute vector, where bii′,l refers to an attribute about Ii,i′. Besides, Ageni’s recommendation weight matrix consists of p weight parameters wi,rr=1,2,…,p, denoted as Wi=diagwi,1,wi,2,…,wi,p which is a p×p diagonal matrix. Notes: each wi,rr=1,2,…,p represents the impact factor of the r-th attribute on the recommendation item. According to the property of diagonal matrix, we can know Wi⊤=Wi.


### 4.1. System Architecture

As shown in Figure1, our system consists of four components as follows: users, Agent, Cloud server and Trusted authority (TA).(i)
User: Considering our system, the user submits an encrypted demand vector to Agent, and makes the recommendation request. After receiving the recommended Item, the user sends an encrypted feedback score to Agent.(ii)
Agent: Agent has its own user group and Item set. It can recommend appropriate Items to users belonging to its user group, after receiving requests the users send.(iii)
Cloud server: It is considered to be honest but curious. It is responsible to calculate similarity between users’ demand and Items’ attributes, and calculate Agent’s Reliability score after receiving request. It will follow the proposed scheme for executing requests received. But we do not exclude the possibility that it will disclose the privacy of users. Additionally, the server is not allowed to collude with Agents.(iv)
Trusted authority (TA): It is a fully trusted third party and responsible to generate and distribute keys to users, Agents and Cloud server.Figure 1
System model.Specially, all users submit their requests for recommendation to Agents in ciphertext, and the Agents need to cooperate with the Cloud server for recommendation. According to the Agents’ Reliability scores, the server judges whether it needs to select several Agents to form a group for federal recommendation. After recommendation finished, the users will the give encrypted feedback scores to Agents, then the Agents forwards to the Cloud server, and the Cloud server updates the Agents’ Reliability scores.


### 4.2. Similarity Calculation Algorithm Based on Orthogonal Matrix in Ciphertext

In order to improve the accuracy of recommendation items, we need to calculate the similarity between users’ demand and items’ attributes. Meanwhile, to strengthen the privacy preservation of recommendation, users’ demand and items’ information should be compared under ciphertext form. Therefore, we propose an efficient Similarity calculation algorithm based on Orthogonal Matrix in Ciphertext (SOMC), which can protect sensitive information privacy by lightweight encryption. The SOMC comprises the following three algorithmsKeyGen, Enc, and Eval, and detailed as follows.SOMC.KeyGenp⟶KA,Ks,i,Ki,L,Ji: It takes as input p where p is the dimension of the matrix, and outputs the secret keys KA,Ks,i,Ki,L and Ji:(i)
It first takes as inputp, generates p×p orthogonal matrices KA,Ks,i and L as follows:(6)KA=x11…x1p⋮⋱⋮xp1…xppp×p,Ks,i=y11…y1p⋮⋱⋮yp1…yppp×p,L=q11…q1p⋮⋱⋮qp1…qppp×p,wherexll,yll,qll∈ℝ.(ii)
Then, generatingKi and Ji according to the following formula: Ki=KA⋅Ks,i and. Ji=Ki⋅LSOMC.EncSK,M⟶CSK: It takes as input secret key SK and plaintext M, where SK is Ki or Ji, and M is a p×p matrix (weight matrix) or a p-dimensional vector (demand or item vector), and outputs the ciphertext CSK.The encryption process is as follows:(7)CSK=SK⊤⋅M.SOMC.EvalL,Ck,Cj⟶simk,j: On input the secret key L, the ciphertext Ck and Cj, where Ck,Cj are obtained by algorithm SOMC.EncKi,Mk and SOMC.EncJi,Mj, the similarities simk,j between Mk (item vector) and Mj (demand vector) as output. Note that here Mk=mk,1,mk,2,…,mk,p⊤ and Mj=mj,1,mj,2,…,mj,p⊤ are p-dimensional vectors. The calculation process is as follows:(8)simk,j=Cj−L⊤Ck⊤⋅Cj−L⊤Ck=Ji⊤Mj−L⊤Ki⊤Mk⊤⋅Ji⊤Mj−L⊤Ki⊤Mk=Ji⊤Mj−Ji⊤Mk⊤⋅Ji⊤Mj−Ji⊤Mk=Mj−Mk⊤Ji⋅Ji⊤Mj−Mk=Mj−Mk⊤⋅Mj−Mk=∑x=1pmk,x−mj,x2.Therefore, we can calculate the similarity betweenCk and Cj without obtaining the plaintext about them.


### 4.3. Efficient Recommendation Scheme Based on Federated Learning

#### 4.3.1. System Initialization

In this phase, it is divided into two parts, firstly TA generates and distributes key, and then the Agents encrypt attribute information. In order to facilitate description, we takeAgeni and users ui,j∈Ui as an example to illustrate.Firstly, TA uses the algorithmSOMC.KeyGenp described in the previous section to generate keys and system parameters as follows:(i)
Step 1: TA exploits algorithmSOMC.KeyGenp to generate KA,Ks,iKi,L,Ji, and then distributes {KA,Ki,Ks,i} to Ageni; {L,Ks,i} to the Cloud server; {Ji} to each users ui,j∈Ui by secure channel. Note that here for Agena and Agenb, if a≠b, then Ka≠Kb, Ks,a≠Ks,b. Beside, each Ageni has the same KA.(ii)
Step 2: TA generates unique identification for each Agent and each Item. We defineIDi as Ageni’s identification and Iidi,i′ as for Item Ii,i′.(iii)
Step 3: On input1λ where λ is the security parameter, TA runs the signature algorithm Λ.KeyGen1λ to generate pkΛ,i,j,skΛ,i,j,pkΛ,S,skΛ,S. Then, TA distributes skΛ,i,j to ui,j∈Ui; skΛ,S to Cloud server. And then TA public pkΛ,i,j,pkΛ,S.(iv)
Step 4: TA sets eachAgeni’s Reliability score RESi to 0 and its update times counti to 0.Secondly,Ageni has own Item set ℐi=Ii,i′,i′=1,2,…,ni, Ageni generates the encrypted Item information for Bi,i′⟶,i′=1,2,…,ni:(9)Bi,i′′⟶=SOMC.EncKi,Bi,i′⟶i′=1,2,…,ni,and then upload Bi,i′′⟶,i′=1,2,…,ni to the Cloud server for storage.


#### 4.3.2. Item Recommendation

In this subsection, we introduce how to recommend a suitable Item to a user when the Agent cooperates with the Cloud server. The whole process can be divided into three parts: (1) User sends demand; (2) The Cloud chooses Agents; (3) Item choosing and recommendation. The pseudo-code of the Item Recommendation is given in Algorithm1.Algorithm 1: Item Recommendation.
Input:Ai,j′⟶,σi,j⟶, Bi,i′′⟶,i′=1,2,…,ni, Wi, RESi,i=1,2,…,U, pkΛ,i,j, L, ∂ and rOutput:Iopt,Iidopt,σser(1)
The Cloud server does:(2)
ifΛ.VerifypkΛ,i,Ai,j′⟶,σi,j⟶then(3)
ifRESi>rthen(4)
Wrec′=Wi′;(5)
end(6)
else(7)
while(the number of collected ! = j)do(8)
choosej Agents which satisfy: ∑z=1jRESmax−z≤∂∑q=1NRESqcollectingPIDk,Wk′ from Agenk∈ACi;(9)
end(10)
forAgenk∈ACido(11)
calculateWaggr,k′ following equation (13);(12)
end(13)
calculateWrec′=Wfed′ following equation (14);(14)
end(15)
calculatesimAi,j′⟶,Bi,j′′⟶,i′=1,2,..,ni following equation (15)–(17);(16)
chooseIopt: simAi,j′⟶,Bopt′⟶=simAi,j′⟶,Bi,j′′⟶,i′=1,2,..,nimin;(17)
Calculateσser←Λ.SignskΛ,S,Iidopt;(18)
end(19)
The AgentAgenk does:(20)
ifAgenk∈ACithen(21)
Wk′←SOMC.EncKi,Wi;PIDk←HIDk‖Rk;sendPIDk,Wk′ to the Cloud server(22)
end(23)
returnIopt,Iidopt,σser(1) User sends demand. To avoid the disclosure of user needs that contain a large amount of private information, user ui,j will exploit SOMC.Enc to encrypt message Ai,j⟶:(10)Ai,j∗⟶=SOMC.EncJi,Ai,j⟶=a1′,a2′,…,ap′⊤,To resistbrute-force exhausted attack [39], we apply a Laplace mechanism [35] by adding noise to Ai,j∗⟶. Although this noise will cause an error, we will experiment later to prove that the error is in the acceptable range. First, ui,j randomly selects t elements in Ai,j∗⟶ to form a set Sub, where t satisfies the following condition: t=⌈p/3⌉ and then adds a Laplace noise:(11)Ai,j′⟶=aij,1′′,aij,2′′,…,aij,p′′⊤=aij,x′′=aij,x′+Lapbaij,x′∈Sub,aij,x′′=aij,x′aij,x′∉Sub,where b is Laplace parameter. To simplify, we express the noise as a vector Lapbi,j⟶. We can get Ai,j′⟶=Ai,j∗⟶+Lapbi,j⟶. Then ui,j generates a signature σi,j⟶=Λ.SignskΛ,i,Ai,j′⟶.Afterward, userui,j submits Ai,j′⟶,σi,j⟶ to Ageni.After receivingAi,j′⟶,σi,j⟶, Ageni exploits SOMC.Enc to encrypt weight matrix:(12)Wi′=SOMC.EncKi,Wi,and sends Ai,j′⟶,σi,j⟶,Wi′ and a request for collaboration about recommendation to the Cloud server.(2) The Cloud chooses Agents. After receiving Ageni’s request, the Cloud server verifies the signature by performing the algorithm Λ.VerifypkΛ,i,Ai,j′⟶,σi,j⟶ . If it fails, the Cloud server refuses the request; otherwise, should determine whether Ageni is eligible to make a recommendation alone or federated recommendation according to its Reliability score RESi. The higher RESi, the more credible the items Ageni recommends.IfRESi>r, where r is a threshold set by TA, the Cloud server considers that Ageni can recommend credible items to users alone, then go straight to 3) Item choosing and recommendation. Otherwise, the Cloud server needs to choose some other Agents to participate in the federal recommendation. Specific steps are as follows:(i)
Step 1: WhenRESi≤r, the Cloud server sorts all Agents according to their Reliability score by descending order firstly, then selects j Agents with a higher score to form a set ACi with the following threshold condition: ∑z=1jRESmax−z≤∂∑q=1NRESq , where ∂<1 is set by TA. We denote RESmax−z is the z− th max in the Reliability score of Agents.(ii)
Step 2: For eachAgenk∈ACi , the Cloud server calculates PIDk=HIDk‖Rk, where Rk is a random number, then sends PIDk and recommendation request to each Agenk∈ACi.(iii)
Step 3: After receiving the message from the Cloud server,Agenk∈ACi exploits SOMC.Enc to encrypt own weight matrix: Wk′=SOMC.EncKk,Wk, and sends PIDk,Wk′ to the Cloud server.(iv)
Step 4: After receiving all encrypted weight matrices fromAgenk∈ACi, the Cloud server calculates Waggr,k′ for each Agenk∈ACi by shared key between the Cloud server and the Agent:(13)Waggr,k′=Ks,i⋅Ks,k⋅Wk′=Ks,i⋅Ks,k⋅Kk⊤⋅Wk=Ks,i⋅Ks,k⋅KA⋅Ks,k⊤⋅Wk=Ks,i⋅Ks,k⋅Ks,k⊤⋅KA⊤⋅Wk=Ks,i⋅KA⊤⋅Wk=Ki⊤⋅Wk.Notes that if the Cloud server finds some weight matrices missing according to thePIDk during collecting PIDk,Wk′, the Cloud server will select another Agents and repeat the previous step.Then the Cloud server aggregates weight for Federated Recommendation:(14)Wfed′=∑Agenk∈ACiRESk⋅Waggr,k′∑Agenk∈ACiRESk=Ki⊤⋅∑Agenk∈ACiRESk⋅Wk∑Agenk∈ACiRESk,where ∑Agenk∈ACiRESk is denoted as the sum of all Reliability scores of Agenk∈ACi.We defineWfed=∑Agenk∈ACiRESk⋅Wk/∑Agenk∈ACiRESk, then we can get Wfed′=Ki⊤⋅Wfed.(3) Item choosing and recommendation. The process of recommending alone by Ageni and federal recommendation is the same in this step, therefore we use Wrec′ to represent both Wfed′ and Wi′ which are weight matrices in ciphertext form. According to Wfed′=Ki⊤⋅Wfed, Wi′=Ki⊤⋅Wi, we define Wrec:Wrec′=Ki⊤⋅Wrec.For more accurate recommendation, the Cloud server findsBi,j′′⟶ and computes the similarities simAi,j⟶,Bi,i′⟶,i′=1,2,…,ni as follows:(15)Ai,j′′⟶=Wrec′⊤⋅L⋅Ai,j′⟶,(16)Bi,i′′′⟶=L⋅Wrec′⊤⋅Bi,j′′⟶i′=1,2,…,ni,(17)simAi,j⟶,Bi,i′⟶=SOMC.EvalL,Bi,i′′′⟶,Ai,j′′⟶i′=1,2,…,ni=Ai,j′′⟶−L⊤Bi,i′′′⟶⊤⋅Ai,j′′⟶−L⊤Bi,i′′′⟶=Wrec⊤⋅Ki⋅L⋅Ji⊤⋅Ai,j⟶−L⊤L⋅Wrec⊤Ki⋅Ki⊤Bi,i′⟶⊤⋅Wrec⊤⋅Ki⋅L⋅Ji⊤⋅Ai,j⟶−L⊤L⋅Wrec⊤Ki⋅Ki⊤Bi,i′⟶=Wrec⋅Ai,j⟶−WrecBi,i′⟶⊤⋅Wrec⋅Ai,j⟶−WrecBi,i′⟶=WrecAi,j⟶−Bi,i′⟶⊤⋅WrecAi,j⟶−Bi,i′⟶=∑x=1pwrec,x2aij,x−bii′,x2.Then according tosimAi,j⟶,Bi,i′⟶,i′=1,2,…,ni, the cloud selects the Item Iopt with the best similarity, and calculates: σser=Λ.SignskΛ,S,Iidopt where Iidopt is the unique identifier of the Iopt . Then send Iopt,Iidopt,σser to Ageni, Ageni will forward the recommendation to the user ui,j.


#### 4.3.3. Update Reliability Score

After receiving the recommendation, the userui,j sets scores according to the recommended items and sends it to the Cloud server as feedback, then the Cloud server updates the Ageni’s Reliability score according to the feedback score. The whole process can be divided into two parts: (1) User scores for recommendation; (2) The Cloud calculates Reliability score. The pseudo-code of the Item Recommendation is given in Algorithm 2.(1) User scores for recommendation. First, the user ui,j verifies the signature by performing the algorithm Λ. VerifypkΛ,S,Iidopt,σser . If it fails, ui,j refuses the request; otherwise, generates a feedback score matrix by calculating the square root of the scores: Ri,j=diagrj,1,rj,2,…,rj,p, where rj,l represents to a score about l-th attribute of demand. The value of rj,l is 1 to 5.To keep the Cloud server from knowingui,j’s scores, ui,j adds noise to the feedback score matrix Ri,j: We define a set Rsubi,j contains p−t scores which is selected by ui,j in the set rj,x,x=1,2,…,p, where t satisfies the following condition: t=⌈p/3⌉.And thenui,j adds noise to the feedback scoring matrix Ri,j to get Ri,j∗:(18)Ri,j∗=diagrj,1′,rj,2′,…,rj,p′=rj,x′=0+r1rj,x∉Rsubi,j,rj,x′=rj,xrj,x∈Rsubi,j,where r1 is a random number. Then ui,j generates an indicator vector Rj,0⟶:(19)Rj,0⟶=r0,1,r0,2,…,r0,p⊤=r0,x=0rj,x∉Rsubi,j,r0,x=1rj,x∈Rsubi,j.Then We can getRi,jture⟶=Ri,j∗⋅Rj,0⟶=Ri,j⋅Rj,0⟶, where(20)Ri,jture⟶=rj,1′′,rj,2′′,…,rj,p′′⊤=rj,x′′=0rj,x∉Rsubi,j,rj,x′′=rj,xrj,x∈Rsubi,j.To preventAgeni tampering, ui,j calculates as follows:(21)Ri,j′=SOMC.EncJi,Ri,j∗,Rj,0′⟶=Ji⋅Rj,0⟶,σr.i,j⟶=Λ.SignskΛ,i,j,Ri,j′⋅Rj,0⟶.And then ui,j sends Ri,j′,Rj,0′⟶,σr.i,j⟶ to Ageni.(2) The Cloud calculates Reliability score. After receiving a number of Ri,j′,Rj,0′⟶,σr.i,j⟶ from ui,j∈Ui, Ageni calculates(22)Rj,0⟶′′=Ki⊤⋅Rj,0′⟶for each ui,j∈Fi, where Fi is defined as a set contains users who send feedback to Ageni. When the amount of feedback exceeds μ that is set by TA, Ageni sends Ri,j′,Rj,0⟶″,σr.i,j⟶,ui,j∈Fi to the Cloud server.After receivingRi,j′,Rj,0⟶″,σr.i,j⟶,ui,j∈Fi, the Cloud server calculates to get Rj,0⟶,ui,j∈Fi:(23)Rj,0⟶=L⊤⋅Rj,0⟶′′=L⊤⋅Ki⊤⋅Rj,0′⟶=Ji⊤⋅Ji⋅Rj,0⟶.Then the Cloud server verifies each the signature by performing the algorithmΛ.VerifypkΛ,i,j,Ri,j′⋅Rj,0⟶,σr.i,j⟶ . If it fails, the Cloud server will punish Ageni by giving it a low Reliability score; otherwise, calculates and updates Reliability score RESi for each Ageni as follows:(24)scoreui,j=Ri,j′⋅Rj,0⟶⊤⋅Ri,j′⋅Rj,0⟶(25)=Rj,0⟶⊤⋅Ri,j∗Ji⋅Ji⊤Ri,j∗⋅Rj,0⟶=Rj,0⟶⊤⋅Ri,j∗⋅Ri,j∗⋅Rj,0⟶=Ri,j⟶⊤⋅Ri,j⟶=∑rj,x∈Rsubi,jrj,x2=∑rj,x∈Rsubi,jrj,x,RESinew=counti×RESi+1/Fi∑ui,j∈Fiscoreui,jcounti+1,(26)countinew=counti+1,where Fi is defined as the number of users which send feedback to Ageni, and counti is the number of times RESi has been updated.Algorithm 2: Update Reliability score.
Input:Ri,j′,Rj,0′⟶,σr.i,j⟶,ui,j∈Fi, RESi,i=1,2,…,U, counti,i=1,2,…,U, pkΛ,i,jOutput:RESinew,i=1,2,…,U(24)
EachAgenidoes:(25)
countnum=0;forui,j∈Fido(26)
calculateRj,0⟶″ following equation (22);(27)
countnum++;(28)
ifcountnum>μthen(29)
sendRi,j′,Rj,0′⟶,σr.i,j⟶,ui,j∈Fi to the Cloud server;(30)
countnum=0;(31)
end(32)
end(33)
The Cloud server does:(34)
foreachAgeni do(35)
forui,j∈Fido(36)
calculateRj,0⟶ following equation (23);ifΛ.VerifypkΛ,i,j,Ri,j′⋅Rj,0⟶,σr.i,j⟶then(37)
calculatescoreui,j following equation (24);(38)
end(39)
end(40)
calculateRESinew following equation (25);(41)
counti++;(42)
end(43)
returnRESinew,i=1,2,…,U


## 4.1. System Architecture

As shown in Figure1, our system consists of four components as follows: users, Agent, Cloud server and Trusted authority (TA).(i)
User: Considering our system, the user submits an encrypted demand vector to Agent, and makes the recommendation request. After receiving the recommended Item, the user sends an encrypted feedback score to Agent.(ii)
Agent: Agent has its own user group and Item set. It can recommend appropriate Items to users belonging to its user group, after receiving requests the users send.(iii)
Cloud server: It is considered to be honest but curious. It is responsible to calculate similarity between users’ demand and Items’ attributes, and calculate Agent’s Reliability score after receiving request. It will follow the proposed scheme for executing requests received. But we do not exclude the possibility that it will disclose the privacy of users. Additionally, the server is not allowed to collude with Agents.(iv)
Trusted authority (TA): It is a fully trusted third party and responsible to generate and distribute keys to users, Agents and Cloud server.Figure 1
System model.Specially, all users submit their requests for recommendation to Agents in ciphertext, and the Agents need to cooperate with the Cloud server for recommendation. According to the Agents’ Reliability scores, the server judges whether it needs to select several Agents to form a group for federal recommendation. After recommendation finished, the users will the give encrypted feedback scores to Agents, then the Agents forwards to the Cloud server, and the Cloud server updates the Agents’ Reliability scores.


## 4.2. Similarity Calculation Algorithm Based on Orthogonal Matrix in Ciphertext

In order to improve the accuracy of recommendation items, we need to calculate the similarity between users’ demand and items’ attributes. Meanwhile, to strengthen the privacy preservation of recommendation, users’ demand and items’ information should be compared under ciphertext form. Therefore, we propose an efficient Similarity calculation algorithm based on Orthogonal Matrix in Ciphertext (SOMC), which can protect sensitive information privacy by lightweight encryption. The SOMC comprises the following three algorithmsKeyGen, Enc, and Eval, and detailed as follows.SOMC.KeyGenp⟶KA,Ks,i,Ki,L,Ji: It takes as input p where p is the dimension of the matrix, and outputs the secret keys KA,Ks,i,Ki,L and Ji:(i)
It first takes as inputp, generates p×p orthogonal matrices KA,Ks,i and L as follows:(6)KA=x11…x1p⋮⋱⋮xp1…xppp×p,Ks,i=y11…y1p⋮⋱⋮yp1…yppp×p,L=q11…q1p⋮⋱⋮qp1…qppp×p,wherexll,yll,qll∈ℝ.(ii)
Then, generatingKi and Ji according to the following formula: Ki=KA⋅Ks,i and. Ji=Ki⋅LSOMC.EncSK,M⟶CSK: It takes as input secret key SK and plaintext M, where SK is Ki or Ji, and M is a p×p matrix (weight matrix) or a p-dimensional vector (demand or item vector), and outputs the ciphertext CSK.The encryption process is as follows:(7)CSK=SK⊤⋅M.SOMC.EvalL,Ck,Cj⟶simk,j: On input the secret key L, the ciphertext Ck and Cj, where Ck,Cj are obtained by algorithm SOMC.EncKi,Mk and SOMC.EncJi,Mj, the similarities simk,j between Mk (item vector) and Mj (demand vector) as output. Note that here Mk=mk,1,mk,2,…,mk,p⊤ and Mj=mj,1,mj,2,…,mj,p⊤ are p-dimensional vectors. The calculation process is as follows:(8)simk,j=Cj−L⊤Ck⊤⋅Cj−L⊤Ck=Ji⊤Mj−L⊤Ki⊤Mk⊤⋅Ji⊤Mj−L⊤Ki⊤Mk=Ji⊤Mj−Ji⊤Mk⊤⋅Ji⊤Mj−Ji⊤Mk=Mj−Mk⊤Ji⋅Ji⊤Mj−Mk=Mj−Mk⊤⋅Mj−Mk=∑x=1pmk,x−mj,x2.Therefore, we can calculate the similarity betweenCk and Cj without obtaining the plaintext about them.


## 4.3. Efficient Recommendation Scheme Based on Federated Learning

### 4.3.1. System Initialization

In this phase, it is divided into two parts, firstly TA generates and distributes key, and then the Agents encrypt attribute information. In order to facilitate description, we takeAgeni and users ui,j∈Ui as an example to illustrate.Firstly, TA uses the algorithmSOMC.KeyGenp described in the previous section to generate keys and system parameters as follows:(i)
Step 1: TA exploits algorithmSOMC.KeyGenp to generate KA,Ks,iKi,L,Ji, and then distributes {KA,Ki,Ks,i} to Ageni; {L,Ks,i} to the Cloud server; {Ji} to each users ui,j∈Ui by secure channel. Note that here for Agena and Agenb, if a≠b, then Ka≠Kb, Ks,a≠Ks,b. Beside, each Ageni has the same KA.(ii)
Step 2: TA generates unique identification for each Agent and each Item. We defineIDi as Ageni’s identification and Iidi,i′ as for Item Ii,i′.(iii)
Step 3: On input1λ where λ is the security parameter, TA runs the signature algorithm Λ.KeyGen1λ to generate pkΛ,i,j,skΛ,i,j,pkΛ,S,skΛ,S. Then, TA distributes skΛ,i,j to ui,j∈Ui; skΛ,S to Cloud server. And then TA public pkΛ,i,j,pkΛ,S.(iv)
Step 4: TA sets eachAgeni’s Reliability score RESi to 0 and its update times counti to 0.Secondly,Ageni has own Item set ℐi=Ii,i′,i′=1,2,…,ni, Ageni generates the encrypted Item information for Bi,i′⟶,i′=1,2,…,ni:(9)Bi,i′′⟶=SOMC.EncKi,Bi,i′⟶i′=1,2,…,ni,and then upload Bi,i′′⟶,i′=1,2,…,ni to the Cloud server for storage.


### 4.3.2. Item Recommendation

In this subsection, we introduce how to recommend a suitable Item to a user when the Agent cooperates with the Cloud server. The whole process can be divided into three parts: (1) User sends demand; (2) The Cloud chooses Agents; (3) Item choosing and recommendation. The pseudo-code of the Item Recommendation is given in Algorithm1.Algorithm 1: Item Recommendation.
Input:Ai,j′⟶,σi,j⟶, Bi,i′′⟶,i′=1,2,…,ni, Wi, RESi,i=1,2,…,U, pkΛ,i,j, L, ∂ and rOutput:Iopt,Iidopt,σser(1)
The Cloud server does:(2)
ifΛ.VerifypkΛ,i,Ai,j′⟶,σi,j⟶then(3)
ifRESi>rthen(4)
Wrec′=Wi′;(5)
end(6)
else(7)
while(the number of collected ! = j)do(8)
choosej Agents which satisfy: ∑z=1jRESmax−z≤∂∑q=1NRESqcollectingPIDk,Wk′ from Agenk∈ACi;(9)
end(10)
forAgenk∈ACido(11)
calculateWaggr,k′ following equation (13);(12)
end(13)
calculateWrec′=Wfed′ following equation (14);(14)
end(15)
calculatesimAi,j′⟶,Bi,j′′⟶,i′=1,2,..,ni following equation (15)–(17);(16)
chooseIopt: simAi,j′⟶,Bopt′⟶=simAi,j′⟶,Bi,j′′⟶,i′=1,2,..,nimin;(17)
Calculateσser←Λ.SignskΛ,S,Iidopt;(18)
end(19)
The AgentAgenk does:(20)
ifAgenk∈ACithen(21)
Wk′←SOMC.EncKi,Wi;PIDk←HIDk‖Rk;sendPIDk,Wk′ to the Cloud server(22)
end(23)
returnIopt,Iidopt,σser(1) User sends demand. To avoid the disclosure of user needs that contain a large amount of private information, user ui,j will exploit SOMC.Enc to encrypt message Ai,j⟶:(10)Ai,j∗⟶=SOMC.EncJi,Ai,j⟶=a1′,a2′,…,ap′⊤,To resistbrute-force exhausted attack [39], we apply a Laplace mechanism [35] by adding noise to Ai,j∗⟶. Although this noise will cause an error, we will experiment later to prove that the error is in the acceptable range. First, ui,j randomly selects t elements in Ai,j∗⟶ to form a set Sub, where t satisfies the following condition: t=⌈p/3⌉ and then adds a Laplace noise:(11)Ai,j′⟶=aij,1′′,aij,2′′,…,aij,p′′⊤=aij,x′′=aij,x′+Lapbaij,x′∈Sub,aij,x′′=aij,x′aij,x′∉Sub,where b is Laplace parameter. To simplify, we express the noise as a vector Lapbi,j⟶. We can get Ai,j′⟶=Ai,j∗⟶+Lapbi,j⟶. Then ui,j generates a signature σi,j⟶=Λ.SignskΛ,i,Ai,j′⟶.Afterward, userui,j submits Ai,j′⟶,σi,j⟶ to Ageni.After receivingAi,j′⟶,σi,j⟶, Ageni exploits SOMC.Enc to encrypt weight matrix:(12)Wi′=SOMC.EncKi,Wi,and sends Ai,j′⟶,σi,j⟶,Wi′ and a request for collaboration about recommendation to the Cloud server.(2) The Cloud chooses Agents. After receiving Ageni’s request, the Cloud server verifies the signature by performing the algorithm Λ.VerifypkΛ,i,Ai,j′⟶,σi,j⟶ . If it fails, the Cloud server refuses the request; otherwise, should determine whether Ageni is eligible to make a recommendation alone or federated recommendation according to its Reliability score RESi. The higher RESi, the more credible the items Ageni recommends.IfRESi>r, where r is a threshold set by TA, the Cloud server considers that Ageni can recommend credible items to users alone, then go straight to 3) Item choosing and recommendation. Otherwise, the Cloud server needs to choose some other Agents to participate in the federal recommendation. Specific steps are as follows:(i)
Step 1: WhenRESi≤r, the Cloud server sorts all Agents according to their Reliability score by descending order firstly, then selects j Agents with a higher score to form a set ACi with the following threshold condition: ∑z=1jRESmax−z≤∂∑q=1NRESq , where ∂<1 is set by TA. We denote RESmax−z is the z− th max in the Reliability score of Agents.(ii)
Step 2: For eachAgenk∈ACi , the Cloud server calculates PIDk=HIDk‖Rk, where Rk is a random number, then sends PIDk and recommendation request to each Agenk∈ACi.(iii)
Step 3: After receiving the message from the Cloud server,Agenk∈ACi exploits SOMC.Enc to encrypt own weight matrix: Wk′=SOMC.EncKk,Wk, and sends PIDk,Wk′ to the Cloud server.(iv)
Step 4: After receiving all encrypted weight matrices fromAgenk∈ACi, the Cloud server calculates Waggr,k′ for each Agenk∈ACi by shared key between the Cloud server and the Agent:(13)Waggr,k′=Ks,i⋅Ks,k⋅Wk′=Ks,i⋅Ks,k⋅Kk⊤⋅Wk=Ks,i⋅Ks,k⋅KA⋅Ks,k⊤⋅Wk=Ks,i⋅Ks,k⋅Ks,k⊤⋅KA⊤⋅Wk=Ks,i⋅KA⊤⋅Wk=Ki⊤⋅Wk.Notes that if the Cloud server finds some weight matrices missing according to thePIDk during collecting PIDk,Wk′, the Cloud server will select another Agents and repeat the previous step.Then the Cloud server aggregates weight for Federated Recommendation:(14)Wfed′=∑Agenk∈ACiRESk⋅Waggr,k′∑Agenk∈ACiRESk=Ki⊤⋅∑Agenk∈ACiRESk⋅Wk∑Agenk∈ACiRESk,where ∑Agenk∈ACiRESk is denoted as the sum of all Reliability scores of Agenk∈ACi.We defineWfed=∑Agenk∈ACiRESk⋅Wk/∑Agenk∈ACiRESk, then we can get Wfed′=Ki⊤⋅Wfed.(3) Item choosing and recommendation. The process of recommending alone by Ageni and federal recommendation is the same in this step, therefore we use Wrec′ to represent both Wfed′ and Wi′ which are weight matrices in ciphertext form. According to Wfed′=Ki⊤⋅Wfed, Wi′=Ki⊤⋅Wi, we define Wrec:Wrec′=Ki⊤⋅Wrec.For more accurate recommendation, the Cloud server findsBi,j′′⟶ and computes the similarities simAi,j⟶,Bi,i′⟶,i′=1,2,…,ni as follows:(15)Ai,j′′⟶=Wrec′⊤⋅L⋅Ai,j′⟶,(16)Bi,i′′′⟶=L⋅Wrec′⊤⋅Bi,j′′⟶i′=1,2,…,ni,(17)simAi,j⟶,Bi,i′⟶=SOMC.EvalL,Bi,i′′′⟶,Ai,j′′⟶i′=1,2,…,ni=Ai,j′′⟶−L⊤Bi,i′′′⟶⊤⋅Ai,j′′⟶−L⊤Bi,i′′′⟶=Wrec⊤⋅Ki⋅L⋅Ji⊤⋅Ai,j⟶−L⊤L⋅Wrec⊤Ki⋅Ki⊤Bi,i′⟶⊤⋅Wrec⊤⋅Ki⋅L⋅Ji⊤⋅Ai,j⟶−L⊤L⋅Wrec⊤Ki⋅Ki⊤Bi,i′⟶=Wrec⋅Ai,j⟶−WrecBi,i′⟶⊤⋅Wrec⋅Ai,j⟶−WrecBi,i′⟶=WrecAi,j⟶−Bi,i′⟶⊤⋅WrecAi,j⟶−Bi,i′⟶=∑x=1pwrec,x2aij,x−bii′,x2.Then according tosimAi,j⟶,Bi,i′⟶,i′=1,2,…,ni, the cloud selects the Item Iopt with the best similarity, and calculates: σser=Λ.SignskΛ,S,Iidopt where Iidopt is the unique identifier of the Iopt . Then send Iopt,Iidopt,σser to Ageni, Ageni will forward the recommendation to the user ui,j.


### 4.3.3. Update Reliability Score

After receiving the recommendation, the userui,j sets scores according to the recommended items and sends it to the Cloud server as feedback, then the Cloud server updates the Ageni’s Reliability score according to the feedback score. The whole process can be divided into two parts: (1) User scores for recommendation; (2) The Cloud calculates Reliability score. The pseudo-code of the Item Recommendation is given in Algorithm 2.(1) User scores for recommendation. First, the user ui,j verifies the signature by performing the algorithm Λ. VerifypkΛ,S,Iidopt,σser . If it fails, ui,j refuses the request; otherwise, generates a feedback score matrix by calculating the square root of the scores: Ri,j=diagrj,1,rj,2,…,rj,p, where rj,l represents to a score about l-th attribute of demand. The value of rj,l is 1 to 5.To keep the Cloud server from knowingui,j’s scores, ui,j adds noise to the feedback score matrix Ri,j: We define a set Rsubi,j contains p−t scores which is selected by ui,j in the set rj,x,x=1,2,…,p, where t satisfies the following condition: t=⌈p/3⌉.And thenui,j adds noise to the feedback scoring matrix Ri,j to get Ri,j∗:(18)Ri,j∗=diagrj,1′,rj,2′,…,rj,p′=rj,x′=0+r1rj,x∉Rsubi,j,rj,x′=rj,xrj,x∈Rsubi,j,where r1 is a random number. Then ui,j generates an indicator vector Rj,0⟶:(19)Rj,0⟶=r0,1,r0,2,…,r0,p⊤=r0,x=0rj,x∉Rsubi,j,r0,x=1rj,x∈Rsubi,j.Then We can getRi,jture⟶=Ri,j∗⋅Rj,0⟶=Ri,j⋅Rj,0⟶, where(20)Ri,jture⟶=rj,1′′,rj,2′′,…,rj,p′′⊤=rj,x′′=0rj,x∉Rsubi,j,rj,x′′=rj,xrj,x∈Rsubi,j.To preventAgeni tampering, ui,j calculates as follows:(21)Ri,j′=SOMC.EncJi,Ri,j∗,Rj,0′⟶=Ji⋅Rj,0⟶,σr.i,j⟶=Λ.SignskΛ,i,j,Ri,j′⋅Rj,0⟶.And then ui,j sends Ri,j′,Rj,0′⟶,σr.i,j⟶ to Ageni.(2) The Cloud calculates Reliability score. After receiving a number of Ri,j′,Rj,0′⟶,σr.i,j⟶ from ui,j∈Ui, Ageni calculates(22)Rj,0⟶′′=Ki⊤⋅Rj,0′⟶for each ui,j∈Fi, where Fi is defined as a set contains users who send feedback to Ageni. When the amount of feedback exceeds μ that is set by TA, Ageni sends Ri,j′,Rj,0⟶″,σr.i,j⟶,ui,j∈Fi to the Cloud server.After receivingRi,j′,Rj,0⟶″,σr.i,j⟶,ui,j∈Fi, the Cloud server calculates to get Rj,0⟶,ui,j∈Fi:(23)Rj,0⟶=L⊤⋅Rj,0⟶′′=L⊤⋅Ki⊤⋅Rj,0′⟶=Ji⊤⋅Ji⋅Rj,0⟶.Then the Cloud server verifies each the signature by performing the algorithmΛ.VerifypkΛ,i,j,Ri,j′⋅Rj,0⟶,σr.i,j⟶ . If it fails, the Cloud server will punish Ageni by giving it a low Reliability score; otherwise, calculates and updates Reliability score RESi for each Ageni as follows:(24)scoreui,j=Ri,j′⋅Rj,0⟶⊤⋅Ri,j′⋅Rj,0⟶(25)=Rj,0⟶⊤⋅Ri,j∗Ji⋅Ji⊤Ri,j∗⋅Rj,0⟶=Rj,0⟶⊤⋅Ri,j∗⋅Ri,j∗⋅Rj,0⟶=Ri,j⟶⊤⋅Ri,j⟶=∑rj,x∈Rsubi,jrj,x2=∑rj,x∈Rsubi,jrj,x,RESinew=counti×RESi+1/Fi∑ui,j∈Fiscoreui,jcounti+1,(26)countinew=counti+1,where Fi is defined as the number of users which send feedback to Ageni, and counti is the number of times RESi has been updated.Algorithm 2: Update Reliability score.
Input:Ri,j′,Rj,0′⟶,σr.i,j⟶,ui,j∈Fi, RESi,i=1,2,…,U, counti,i=1,2,…,U, pkΛ,i,jOutput:RESinew,i=1,2,…,U(24)
EachAgenidoes:(25)
countnum=0;forui,j∈Fido(26)
calculateRj,0⟶″ following equation (22);(27)
countnum++;(28)
ifcountnum>μthen(29)
sendRi,j′,Rj,0′⟶,σr.i,j⟶,ui,j∈Fi to the Cloud server;(30)
countnum=0;(31)
end(32)
end(33)
The Cloud server does:(34)
foreachAgeni do(35)
forui,j∈Fido(36)
calculateRj,0⟶ following equation (23);ifΛ.VerifypkΛ,i,j,Ri,j′⋅Rj,0⟶,σr.i,j⟶then(37)
calculatescoreui,j following equation (24);(38)
end(39)
end(40)
calculateRESinew following equation (25);(41)
counti++;(42)
end(43)
returnRESinew,i=1,2,…,U


## 4.3.1. System Initialization

In this phase, it is divided into two parts, firstly TA generates and distributes key, and then the Agents encrypt attribute information. In order to facilitate description, we takeAgeni and users ui,j∈Ui as an example to illustrate.Firstly, TA uses the algorithmSOMC.KeyGenp described in the previous section to generate keys and system parameters as follows:(i)
Step 1: TA exploits algorithmSOMC.KeyGenp to generate KA,Ks,iKi,L,Ji, and then distributes {KA,Ki,Ks,i} to Ageni; {L,Ks,i} to the Cloud server; {Ji} to each users ui,j∈Ui by secure channel. Note that here for Agena and Agenb, if a≠b, then Ka≠Kb, Ks,a≠Ks,b. Beside, each Ageni has the same KA.(ii)
Step 2: TA generates unique identification for each Agent and each Item. We defineIDi as Ageni’s identification and Iidi,i′ as for Item Ii,i′.(iii)
Step 3: On input1λ where λ is the security parameter, TA runs the signature algorithm Λ.KeyGen1λ to generate pkΛ,i,j,skΛ,i,j,pkΛ,S,skΛ,S. Then, TA distributes skΛ,i,j to ui,j∈Ui; skΛ,S to Cloud server. And then TA public pkΛ,i,j,pkΛ,S.(iv)
Step 4: TA sets eachAgeni’s Reliability score RESi to 0 and its update times counti to 0.Secondly,Ageni has own Item set ℐi=Ii,i′,i′=1,2,…,ni, Ageni generates the encrypted Item information for Bi,i′⟶,i′=1,2,…,ni:(9)Bi,i′′⟶=SOMC.EncKi,Bi,i′⟶i′=1,2,…,ni,and then upload Bi,i′′⟶,i′=1,2,…,ni to the Cloud server for storage.


## 4.3.2. Item Recommendation

In this subsection, we introduce how to recommend a suitable Item to a user when the Agent cooperates with the Cloud server. The whole process can be divided into three parts: (1) User sends demand; (2) The Cloud chooses Agents; (3) Item choosing and recommendation. The pseudo-code of the Item Recommendation is given in Algorithm1.Algorithm 1: Item Recommendation.
Input:Ai,j′⟶,σi,j⟶, Bi,i′′⟶,i′=1,2,…,ni, Wi, RESi,i=1,2,…,U, pkΛ,i,j, L, ∂ and rOutput:Iopt,Iidopt,σser(1)
The Cloud server does:(2)
ifΛ.VerifypkΛ,i,Ai,j′⟶,σi,j⟶then(3)
ifRESi>rthen(4)
Wrec′=Wi′;(5)
end(6)
else(7)
while(the number of collected ! = j)do(8)
choosej Agents which satisfy: ∑z=1jRESmax−z≤∂∑q=1NRESqcollectingPIDk,Wk′ from Agenk∈ACi;(9)
end(10)
forAgenk∈ACido(11)
calculateWaggr,k′ following equation (13);(12)
end(13)
calculateWrec′=Wfed′ following equation (14);(14)
end(15)
calculatesimAi,j′⟶,Bi,j′′⟶,i′=1,2,..,ni following equation (15)–(17);(16)
chooseIopt: simAi,j′⟶,Bopt′⟶=simAi,j′⟶,Bi,j′′⟶,i′=1,2,..,nimin;(17)
Calculateσser←Λ.SignskΛ,S,Iidopt;(18)
end(19)
The AgentAgenk does:(20)
ifAgenk∈ACithen(21)
Wk′←SOMC.EncKi,Wi;PIDk←HIDk‖Rk;sendPIDk,Wk′ to the Cloud server(22)
end(23)
returnIopt,Iidopt,σser(1) User sends demand. To avoid the disclosure of user needs that contain a large amount of private information, user ui,j will exploit SOMC.Enc to encrypt message Ai,j⟶:(10)Ai,j∗⟶=SOMC.EncJi,Ai,j⟶=a1′,a2′,…,ap′⊤,To resistbrute-force exhausted attack [39], we apply a Laplace mechanism [35] by adding noise to Ai,j∗⟶. Although this noise will cause an error, we will experiment later to prove that the error is in the acceptable range. First, ui,j randomly selects t elements in Ai,j∗⟶ to form a set Sub, where t satisfies the following condition: t=⌈p/3⌉ and then adds a Laplace noise:(11)Ai,j′⟶=aij,1′′,aij,2′′,…,aij,p′′⊤=aij,x′′=aij,x′+Lapbaij,x′∈Sub,aij,x′′=aij,x′aij,x′∉Sub,where b is Laplace parameter. To simplify, we express the noise as a vector Lapbi,j⟶. We can get Ai,j′⟶=Ai,j∗⟶+Lapbi,j⟶. Then ui,j generates a signature σi,j⟶=Λ.SignskΛ,i,Ai,j′⟶.Afterward, userui,j submits Ai,j′⟶,σi,j⟶ to Ageni.After receivingAi,j′⟶,σi,j⟶, Ageni exploits SOMC.Enc to encrypt weight matrix:(12)Wi′=SOMC.EncKi,Wi,and sends Ai,j′⟶,σi,j⟶,Wi′ and a request for collaboration about recommendation to the Cloud server.(2) The Cloud chooses Agents. After receiving Ageni’s request, the Cloud server verifies the signature by performing the algorithm Λ.VerifypkΛ,i,Ai,j′⟶,σi,j⟶ . If it fails, the Cloud server refuses the request; otherwise, should determine whether Ageni is eligible to make a recommendation alone or federated recommendation according to its Reliability score RESi. The higher RESi, the more credible the items Ageni recommends.IfRESi>r, where r is a threshold set by TA, the Cloud server considers that Ageni can recommend credible items to users alone, then go straight to 3) Item choosing and recommendation. Otherwise, the Cloud server needs to choose some other Agents to participate in the federal recommendation. Specific steps are as follows:(i)
Step 1: WhenRESi≤r, the Cloud server sorts all Agents according to their Reliability score by descending order firstly, then selects j Agents with a higher score to form a set ACi with the following threshold condition: ∑z=1jRESmax−z≤∂∑q=1NRESq , where ∂<1 is set by TA. We denote RESmax−z is the z− th max in the Reliability score of Agents.(ii)
Step 2: For eachAgenk∈ACi , the Cloud server calculates PIDk=HIDk‖Rk, where Rk is a random number, then sends PIDk and recommendation request to each Agenk∈ACi.(iii)
Step 3: After receiving the message from the Cloud server,Agenk∈ACi exploits SOMC.Enc to encrypt own weight matrix: Wk′=SOMC.EncKk,Wk, and sends PIDk,Wk′ to the Cloud server.(iv)
Step 4: After receiving all encrypted weight matrices fromAgenk∈ACi, the Cloud server calculates Waggr,k′ for each Agenk∈ACi by shared key between the Cloud server and the Agent:(13)Waggr,k′=Ks,i⋅Ks,k⋅Wk′=Ks,i⋅Ks,k⋅Kk⊤⋅Wk=Ks,i⋅Ks,k⋅KA⋅Ks,k⊤⋅Wk=Ks,i⋅Ks,k⋅Ks,k⊤⋅KA⊤⋅Wk=Ks,i⋅KA⊤⋅Wk=Ki⊤⋅Wk.Notes that if the Cloud server finds some weight matrices missing according to thePIDk during collecting PIDk,Wk′, the Cloud server will select another Agents and repeat the previous step.Then the Cloud server aggregates weight for Federated Recommendation:(14)Wfed′=∑Agenk∈ACiRESk⋅Waggr,k′∑Agenk∈ACiRESk=Ki⊤⋅∑Agenk∈ACiRESk⋅Wk∑Agenk∈ACiRESk,where ∑Agenk∈ACiRESk is denoted as the sum of all Reliability scores of Agenk∈ACi.We defineWfed=∑Agenk∈ACiRESk⋅Wk/∑Agenk∈ACiRESk, then we can get Wfed′=Ki⊤⋅Wfed.(3) Item choosing and recommendation. The process of recommending alone by Ageni and federal recommendation is the same in this step, therefore we use Wrec′ to represent both Wfed′ and Wi′ which are weight matrices in ciphertext form. According to Wfed′=Ki⊤⋅Wfed, Wi′=Ki⊤⋅Wi, we define Wrec:Wrec′=Ki⊤⋅Wrec.For more accurate recommendation, the Cloud server findsBi,j′′⟶ and computes the similarities simAi,j⟶,Bi,i′⟶,i′=1,2,…,ni as follows:(15)Ai,j′′⟶=Wrec′⊤⋅L⋅Ai,j′⟶,(16)Bi,i′′′⟶=L⋅Wrec′⊤⋅Bi,j′′⟶i′=1,2,…,ni,(17)simAi,j⟶,Bi,i′⟶=SOMC.EvalL,Bi,i′′′⟶,Ai,j′′⟶i′=1,2,…,ni=Ai,j′′⟶−L⊤Bi,i′′′⟶⊤⋅Ai,j′′⟶−L⊤Bi,i′′′⟶=Wrec⊤⋅Ki⋅L⋅Ji⊤⋅Ai,j⟶−L⊤L⋅Wrec⊤Ki⋅Ki⊤Bi,i′⟶⊤⋅Wrec⊤⋅Ki⋅L⋅Ji⊤⋅Ai,j⟶−L⊤L⋅Wrec⊤Ki⋅Ki⊤Bi,i′⟶=Wrec⋅Ai,j⟶−WrecBi,i′⟶⊤⋅Wrec⋅Ai,j⟶−WrecBi,i′⟶=WrecAi,j⟶−Bi,i′⟶⊤⋅WrecAi,j⟶−Bi,i′⟶=∑x=1pwrec,x2aij,x−bii′,x2.Then according tosimAi,j⟶,Bi,i′⟶,i′=1,2,…,ni, the cloud selects the Item Iopt with the best similarity, and calculates: σser=Λ.SignskΛ,S,Iidopt where Iidopt is the unique identifier of the Iopt . Then send Iopt,Iidopt,σser to Ageni, Ageni will forward the recommendation to the user ui,j.


## 4.3.3. Update Reliability Score

After receiving the recommendation, the userui,j sets scores according to the recommended items and sends it to the Cloud server as feedback, then the Cloud server updates the Ageni’s Reliability score according to the feedback score. The whole process can be divided into two parts: (1) User scores for recommendation; (2) The Cloud calculates Reliability score. The pseudo-code of the Item Recommendation is given in Algorithm 2.(1) User scores for recommendation. First, the user ui,j verifies the signature by performing the algorithm Λ. VerifypkΛ,S,Iidopt,σser . If it fails, ui,j refuses the request; otherwise, generates a feedback score matrix by calculating the square root of the scores: Ri,j=diagrj,1,rj,2,…,rj,p, where rj,l represents to a score about l-th attribute of demand. The value of rj,l is 1 to 5.To keep the Cloud server from knowingui,j’s scores, ui,j adds noise to the feedback score matrix Ri,j: We define a set Rsubi,j contains p−t scores which is selected by ui,j in the set rj,x,x=1,2,…,p, where t satisfies the following condition: t=⌈p/3⌉.And thenui,j adds noise to the feedback scoring matrix Ri,j to get Ri,j∗:(18)Ri,j∗=diagrj,1′,rj,2′,…,rj,p′=rj,x′=0+r1rj,x∉Rsubi,j,rj,x′=rj,xrj,x∈Rsubi,j,where r1 is a random number. Then ui,j generates an indicator vector Rj,0⟶:(19)Rj,0⟶=r0,1,r0,2,…,r0,p⊤=r0,x=0rj,x∉Rsubi,j,r0,x=1rj,x∈Rsubi,j.Then We can getRi,jture⟶=Ri,j∗⋅Rj,0⟶=Ri,j⋅Rj,0⟶, where(20)Ri,jture⟶=rj,1′′,rj,2′′,…,rj,p′′⊤=rj,x′′=0rj,x∉Rsubi,j,rj,x′′=rj,xrj,x∈Rsubi,j.To preventAgeni tampering, ui,j calculates as follows:(21)Ri,j′=SOMC.EncJi,Ri,j∗,Rj,0′⟶=Ji⋅Rj,0⟶,σr.i,j⟶=Λ.SignskΛ,i,j,Ri,j′⋅Rj,0⟶.And then ui,j sends Ri,j′,Rj,0′⟶,σr.i,j⟶ to Ageni.(2) The Cloud calculates Reliability score. After receiving a number of Ri,j′,Rj,0′⟶,σr.i,j⟶ from ui,j∈Ui, Ageni calculates(22)Rj,0⟶′′=Ki⊤⋅Rj,0′⟶for each ui,j∈Fi, where Fi is defined as a set contains users who send feedback to Ageni. When the amount of feedback exceeds μ that is set by TA, Ageni sends Ri,j′,Rj,0⟶″,σr.i,j⟶,ui,j∈Fi to the Cloud server.After receivingRi,j′,Rj,0⟶″,σr.i,j⟶,ui,j∈Fi, the Cloud server calculates to get Rj,0⟶,ui,j∈Fi:(23)Rj,0⟶=L⊤⋅Rj,0⟶′′=L⊤⋅Ki⊤⋅Rj,0′⟶=Ji⊤⋅Ji⋅Rj,0⟶.Then the Cloud server verifies each the signature by performing the algorithmΛ.VerifypkΛ,i,j,Ri,j′⋅Rj,0⟶,σr.i,j⟶ . If it fails, the Cloud server will punish Ageni by giving it a low Reliability score; otherwise, calculates and updates Reliability score RESi for each Ageni as follows:(24)scoreui,j=Ri,j′⋅Rj,0⟶⊤⋅Ri,j′⋅Rj,0⟶(25)=Rj,0⟶⊤⋅Ri,j∗Ji⋅Ji⊤Ri,j∗⋅Rj,0⟶=Rj,0⟶⊤⋅Ri,j∗⋅Ri,j∗⋅Rj,0⟶=Ri,j⟶⊤⋅Ri,j⟶=∑rj,x∈Rsubi,jrj,x2=∑rj,x∈Rsubi,jrj,x,RESinew=counti×RESi+1/Fi∑ui,j∈Fiscoreui,jcounti+1,(26)countinew=counti+1,where Fi is defined as the number of users which send feedback to Ageni, and counti is the number of times RESi has been updated.Algorithm 2: Update Reliability score.
Input:Ri,j′,Rj,0′⟶,σr.i,j⟶,ui,j∈Fi, RESi,i=1,2,…,U, counti,i=1,2,…,U, pkΛ,i,jOutput:RESinew,i=1,2,…,U(24)
EachAgenidoes:(25)
countnum=0;forui,j∈Fido(26)
calculateRj,0⟶″ following equation (22);(27)
countnum++;(28)
ifcountnum>μthen(29)
sendRi,j′,Rj,0′⟶,σr.i,j⟶,ui,j∈Fi to the Cloud server;(30)
countnum=0;(31)
end(32)
end(33)
The Cloud server does:(34)
foreachAgeni do(35)
forui,j∈Fido(36)
calculateRj,0⟶ following equation (23);ifΛ.VerifypkΛ,i,j,Ri,j′⋅Rj,0⟶,σr.i,j⟶then(37)
calculatescoreui,j following equation (24);(38)
end(39)
end(40)
calculateRESinew following equation (25);(41)
counti++;(42)
end(43)
returnRESinew,i=1,2,…,U


## 5. Security Analysis

In this section, we give the formal security proof of our proposed scheme, and security requirements of our scheme include verifiability and privacy. We have used the digital signature so that the verifiability is guaranteed, which has proven to be safe in [36]. The privacy of our proposed scheme is proved under the following threat model:(i)
The Cloud server and Agents are honest-but-curious: we assume that Agents and the Cloud server will follow the protocol, but may be curious about users’ sensitive information.(ii)
Agents does not collude with the Cloud server.For privacy, it includes users’ data privacy and Agents’ parameter privacy. We give the proof of users’ data privacy in Theorem1, and Agents’ parameter privacy in Theorem 2.Theorem 1.
Under the above threat model, our scheme meets the requirement of users’ data privacy.Proof.
Depending on our scheme, users’ privacy is reflected in Item Recommendation and Update Reliability score. So, our proof is divided into two parts as follows:(i)
According to the Item Recommendation process in Algorithm1, no additional information about the user (we use ui,j as an example) is sent except for the encrypted demand vector Ai,j′⟶.
If the attacker wants to reveal users’ demand privacy informationAi,j⟶ from Ai,j′⟶=Ji⊤⋅Ai,j⟶+Lapbi,j⟶, he needs to get Ji and Lapbi,j⟶. So we can set up the following equation to solve: Ai,j′⟶=Ji⊤⋅Ai,j⟶+Lapbi,j⟶.
However,Ji=Ki⋅L, if attacker is Ageni, he has Ki, but no L. Similarly, if the attacker is the Cloud server, he has L, but no Ki. That means Agent and the Cloud server cannot get Ki and L at the same time. So, they cannot reveal Ji and Ai,j⟶.
Then we consider the known-sample attack [40] and brute-force exhausted attack [39]:
If the purpose of the attacker is to recover plains from encrypted demanding vectors, and the attacker gets a set of plain demanding vectorsZ=Ai,zx⟶,x=1,2,…,Z, but he does not know Ai,zx′⟶,x=1,2,…,Z which is the corresponding ciphertext of Z.
The attacker can usebrute-force exhausted attack: trying every possible Ji and Lapbi,j⟶ to recover Ai,j⟶. We can simplify the problem a little bit by setting all the elements of Lapbi,j⟶ to zero, then we can get Ai,j⟶=Ji⋅Ai,j′⟶, and then attacker just needs to recover Ji.
Then we assume the worst-case scenario forZ: there are at least p linearly independent vectors in Z, and |Z|=n≥p+1. The attacker can solve Ji by setting up the following equations: Ai,zx⟶=Ji⋅Ai,zx′⟶ for x=1 to p. If the cloud server who has L as attacker needs to try every possible X to recover Ji: Ji=X⋅L, then the attacker chooses p vectors from Z to form a p×p matrix C such that C=Ai,z1⟶,Ai,z2⟶,…,Ai,zp⟶. He has to try every possible linearly independent Ai,zx′⟶ permutations from the encrypted demanding vectors which he has received to form a p×p matrices D such that D=Ai,∗1′⟶,Ai,∗2′⟶,…,Ai,∗p′⟶. Then the attacker has Ji⊤⋅C=D. Note that C is invertible since Ai,z1⟶,Ai,z2⟶,…,Ai,zp⟶ are linearly independent. He picks a set of p encrypted demanding vectors D randomly and sets up a hypothesis that D contains the corresponding encrypted demanding vectors in C. Then he can set up equation Ji⊤=C−1⋅D to solve for Ji and choose some vectors A∗⟶|A∗⟶∈ZΛA∗⟶∉C to verify the hypothesis: if A∗⟶∉C, the hypothesis cannot be correct; otherwise, the hypothesis may be true.
However, it is for the attacker that the attack is exponentially expensive. That’s because there arePnp=Onp possible candidates of D. For each candidate, the attacker performs to verify whether recovered key Ji is true which takes On validations. For example, if n=5K,p=4 and the attacker is capable to perform 2M validations in a second, then if the attacker wants to try all hypotheses, he must spend more than 460 years. Therefore, our simplified scheme (Lapbi,j⟶=0 ) can also resist this the known-sample brute-force exhausted attack. Noteworthy, in our scheme, Lapbi,j⟶ is a random vector, which the number of non-zero is random and non-zero elements are also random. The blindness of the demanding vector is increased, which makes his calculation aboved more difficult. There’s another scenario: Agenk as attacker wants to recover ui,j’s demanding vector, but it is more difficult since he does not have Ki.
Similarly, theAgeni who has Ki as attacker needs to try every possible Y to recover Ji: Ji=Ki⋅Y, the proof process is similar to the above.
Therefore, in the Item Recommendation phase, the demanding privacy of users is guaranteed.(ii)
According to the Update Reliability score process in Algorithm2, no additional information about ui,j is sent except for the encrypted feedback vector Rj,0′⟶ and matrix Ri,j′.
If the attaker wants to reveal users’ preference informationRi,jture⟶=Ri,j⋅Rj,0⟶ and the total score of the feedback from Rj,0′⟶=Ji⋅Rj,0⟶ and Ri,j′=Ji⊤⋅Ri,j, where the non-zero elements in Ri,jture⟶ represent that each true score in Ri,j, Rj,0⟶ is used to mark which scores in the feedback Ri,j are true, and the sum of elements in Ri,jture⟶ represents the total score of the feedback, he needs to get Ji, Ri,j and Rj,0⟶. So we can set up the following equation to solve: Ri,j=Ji⋅Ri,j′, Rj,0⟶=Ji⊤⋅Rj,0′⟶.
However,Ageni who has Ki as attacker only knows the ciphertext Ri,j′,Rj,0′⟶ and the semi-decrypted result Rj,0′′⟶=Ki⊤⋅Rj,0′⟶. He cannot know Ri,jture⟶ and the sum of elements in Ri,jture⟶. That’s because Ri,jture⟶=Ri,j⋅Rj,0⟶, and he cannot get Rj,0⟶ without L. Meanwhile, the encryption method for Ri,j is the same as the demand vector in Algorithm 1 so that he cannot recover Ri,j. Therefore, he cannot recover Ri,jture⟶ from Rj,0′⟶ and Ri,j′. For the total score of the feedback, we define a p-dimensiona vector V⟶ with the elements being all 1, he can get the sum of Ri,j by calculating Ri,j′⋅V⟶⊤⋅Ri,j′⋅V⟶=V⟶⊤⋅Ri,j⋅Ri,j⋅V⟶, but the result is not the total score of the feedback, because Ri,j contains random numbers. The total score of the feedback can only be obtained by calculating scoreui,j=Ri,j′⋅Rj,0⟶⊤⋅Ri,j′⋅Rj,0⟶=Ji⊤⋅Ri,j⋅Rj,0⟶⊤⋅Ji⊤⋅Ri,j⋅Rj,0⟶=Ri,jture⊤⟶⋅Ri,jture′⟶, where Ri,jture′⟶=SOMC.EncJi,Ri,jture⟶. However, he cannot know Rj,0⟶ so that he cannot get the total score of the feedback. This means that he cannot know the ui,j’s preference information and the total score of the feedback.
Similarly, the Cloud server who hasL as attacker only knows the ciphertext Ri,j′ and the semi-decrypted result Rj,0′′⟶. He cannot know Ri,jture⟶, but can get the sum of elements in Ri,jture⟶ to update Reliability score for Ageni. This because Ri,jture⟶=Ri,j⋅Rj,0⟶, he can recover Rj,0⟶=L⊤⋅Rj,0′′⟶, but he cannot recover Ri,j that is encrypted by the same method in Algorithm 1. He only get Ri,jture′⟶=Ri,j′⋅Rj,0⟶=Ji⊤⋅Ri,j∗⋅Rj,0⟶=Ji⊤⋅Ri,jture⟶=SOMC.EncJi,Ri,jture⟶. The encryption method is the same as the demand vector in Algorithm 1. Therefore, he cannot recover Ri,jture⟶ that includes ui,j’s preference information. But he can get the total score of the feedback: scoreui,j=Ri,j′⋅Rj,0⟶⊤⋅Ri,j′⋅Rj,0⟶=Ri,jture′⊤⟶⋅Ri,jture′⟶. This means that he can know the total score of the feedback but he cannot know the ui,j’s preference information.
Therefore, in the Update Reliability score phase, the preference privacy of users is guaranteed.(iii)
To sum up, our scheme meets the requirement of users’ data privacy.Theorem 2.
Under the above threat model, our scheme meets the requirement of Agents’ parameter privacy.Proof.
Depending on our scheme, Agents’ parameter privacy is reflected in Item Recommendation.
According to the Item Recommendation process in Algorithm1, no additional information about the Agent (we use Ageni as an example) is sent except for the encrypted weight matrix Wi′. We consider that the attacker is the Cloud server or other Agents, and he wants to recover Wi. The encryption method is the same as mentioned in Theorem 1. so that the attacker cannot recover Wi. The proof procedure is the same as Theorem 1. Here is not described again.
Thus, our scheme meets the requirement of Agents’ parameter privacy.


## 6. Evaluation

In this section, we conduct simulation experiments to compare the performance of the proposed SOMC and ERBFL scheme with the existing schemes. We conduct all the experiments on the server with an Intel(R) Core(TM) i7-10700 CPU @ 2.90 GHz 2.90 GHz and 16 GB of RAM and uses TensorFlow to simulate the SOMC and ERBFL algorithm in Python.For experimental parameters, we choose appropriate and security parameters with the given initial parameterp=5 and λ=128. We can get t=⌈p/3⌉=2. So that the full Reliability score is 15. To facilitate the test, we choose the parameter r=9, U=10 and Ui=50.


### 6.1. Efficiency Comparison

In order to show the computation costs about encryption (SOMC) in ERBFL, we compare our scheme with PPO-NBR [12] and EPRT [10], which use homomorphic encryption. We compare the running time of encrypting vectors against varying number of Items. As shown in Figure 2, it can be observed that as the number of Items increasing, all of them increase. But we can see that our scheme takes the least time no matter how many Items. This is because the encryption form in PRO-NBR can only deal with a bit message per encryption, and EPRT can deal with an integer message, whereas our scheme can deal with p integer messages. Thus, our encryption scheme runs faster and more efficiently.Figure 2
Comparison of the efficiency of encryption methods.Next, we conduct experiments to compare the running time of recommendation phase in our scheme with PPO-NBR [12] and EPRT [10] as shown in Figure 3. As the number of items increases, the running time increases. However, the running time of our scheme is always the least.Figure 3
Comparison of the total time of recommendation phase.


### 6.2. Impact of Laplace Noise on Similarity Accuracy

To achieve better privacy protection, we use differential privacy Laplace noise encryption, which makes us consider the impact on the recommendation items. In fact, the accuracy of the recommended items can be known from equation (17), which is equivalent to the impact on the similarity calculation items. Therefore, we conduct the following experiments by setting three scenarios: noise added after encryption, noise added before encryption and nosieless encryption, as shown in Figure 4. It is easy to see that the effect of putting noise after encryption is almost equal to that of no noise, so the effect of our ERBFL scheme on similarity calculation is negligible, therefore, this noise will not affect the accuracy of recommendations in our scheme.Figure 4
Influence of noise on similarity calculation.


### 6.3. Recommendation Accuracy Comparison

We use users to score the recommended items to indicate the accuracy of the recommended items. Because if the recommendation items are more accurate, the users will be more satisfied and the feedback score will be higher. Then we use a data set MovieLens-100k [41], which includes 100000 movie ratings from about 900 users on over 1600 movies, where the value of all scores is 1 to 5. Since the data does not include all users’ scores for all movies, we fill in the missing scores with the mean of two known values, where one of two known values is the average of the corresponding user has scored, another value is the average of the corresponding item has been scored. We use the data as the users’ scores, the more satisfied with the recommended items, the higher the score. We repeat the recommendation process many times, find the corresponding score from the data for each time, and compare different schemes of average score. In addition, an evaluation indicator called accuracy is also used. Accuracy is defined as the fraction of correct recommendations in the total number of recommendations, and accuracy is generally considered to evaluate whether a Recommender System can recommend accurate items. Higher accuracy means that the Recommender System can recommend more comfortable items. Then, due to the scores in data set MovieLens-100k [41] are all real users scoring, we assume that an item with a score above 4 is the correct recommendation. We repeat the recommendation process many times, count the number of correct recommendations, and compare the accuracy of different schemes.As shown in Figure5, it can be seen that the items recommended by our scheme always has a higher feedback score. And as shown in Figure 6, it also can be seen that our scheme always has the best performance in terms of accuracy. On the one hand, our scheme is designed based on a federal learning framework, which is different from EPRT [10] and PPO-NBR [12] used centralized recommendation. On the other hand, our scheme uses similarity as a recommended criterion, which is different from PPO-NBR [12]. Therefore, our scheme can recommend the item that makes users more satisfactory.Figure 5
Comparison of Feedback score about recommendation.Figure 6
Comparison of Accuracy about recommendation.


## 6.1. Efficiency Comparison

In order to show the computation costs about encryption (SOMC) in ERBFL, we compare our scheme with PPO-NBR [12] and EPRT [10], which use homomorphic encryption. We compare the running time of encrypting vectors against varying number of Items. As shown in Figure 2, it can be observed that as the number of Items increasing, all of them increase. But we can see that our scheme takes the least time no matter how many Items. This is because the encryption form in PRO-NBR can only deal with a bit message per encryption, and EPRT can deal with an integer message, whereas our scheme can deal with p integer messages. Thus, our encryption scheme runs faster and more efficiently.Figure 2
Comparison of the efficiency of encryption methods.Next, we conduct experiments to compare the running time of recommendation phase in our scheme with PPO-NBR [12] and EPRT [10] as shown in Figure 3. As the number of items increases, the running time increases. However, the running time of our scheme is always the least.Figure 3
Comparison of the total time of recommendation phase.


## 6.2. Impact of Laplace Noise on Similarity Accuracy

To achieve better privacy protection, we use differential privacy Laplace noise encryption, which makes us consider the impact on the recommendation items. In fact, the accuracy of the recommended items can be known from equation (17), which is equivalent to the impact on the similarity calculation items. Therefore, we conduct the following experiments by setting three scenarios: noise added after encryption, noise added before encryption and nosieless encryption, as shown in Figure 4. It is easy to see that the effect of putting noise after encryption is almost equal to that of no noise, so the effect of our ERBFL scheme on similarity calculation is negligible, therefore, this noise will not affect the accuracy of recommendations in our scheme.Figure 4
Influence of noise on similarity calculation.


## 6.3. Recommendation Accuracy Comparison

We use users to score the recommended items to indicate the accuracy of the recommended items. Because if the recommendation items are more accurate, the users will be more satisfied and the feedback score will be higher. Then we use a data set MovieLens-100k [41], which includes 100000 movie ratings from about 900 users on over 1600 movies, where the value of all scores is 1 to 5. Since the data does not include all users’ scores for all movies, we fill in the missing scores with the mean of two known values, where one of two known values is the average of the corresponding user has scored, another value is the average of the corresponding item has been scored. We use the data as the users’ scores, the more satisfied with the recommended items, the higher the score. We repeat the recommendation process many times, find the corresponding score from the data for each time, and compare different schemes of average score. In addition, an evaluation indicator called accuracy is also used. Accuracy is defined as the fraction of correct recommendations in the total number of recommendations, and accuracy is generally considered to evaluate whether a Recommender System can recommend accurate items. Higher accuracy means that the Recommender System can recommend more comfortable items. Then, due to the scores in data set MovieLens-100k [41] are all real users scoring, we assume that an item with a score above 4 is the correct recommendation. We repeat the recommendation process many times, count the number of correct recommendations, and compare the accuracy of different schemes.As shown in Figure5, it can be seen that the items recommended by our scheme always has a higher feedback score. And as shown in Figure 6, it also can be seen that our scheme always has the best performance in terms of accuracy. On the one hand, our scheme is designed based on a federal learning framework, which is different from EPRT [10] and PPO-NBR [12] used centralized recommendation. On the other hand, our scheme uses similarity as a recommended criterion, which is different from PPO-NBR [12]. Therefore, our scheme can recommend the item that makes users more satisfactory.Figure 5
Comparison of Feedback score about recommendation.Figure 6
Comparison of Accuracy about recommendation.


## 7. Conclusion

In this paper, we propose ERBFL—an Efficient Recommendation Based on Federated Learning for helping users find an appropriate item. To protect privacy and improve accuracy of recommendation, we design a privacy-preserving ciphertext calculation for similarity calculation, and by employing the Federated Learning framework. We analyze the security of our scheme for achieving the design secure goals and ensuring the accuracy of the recommended items. In addition, the experiment proves that ERBFL is more efficient than the existing scheme. The primary constraint we faced was the high dimension of user or item information, which can affect the execution time, and the performance of our scheme. Furthermore, in our scheme, we assume that the Cloud and agents cannot collude. Therefore, our future plans are to extend our scheme to be applicable more complex scenarios and to be able to resist collusive attacks.



---

*Source: 8607234-2022-09-16.xml*