# Improved Cloud-Assisted Privacy-Preserving Profile-Matching Scheme in Mobile Social Networks

Authors: Ying Zou; Yanting Chai; Sha Shi; Lei Wang; Yunfeng Peng; Yuan Ping; Baocang Wang
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Due to the transparency of the wireless channel, users in multiple-key environment are vulnerable to eavesdropping during the process of uploading personal data and re-encryption keys. Besides, there is additional burden of key management arising from multiple keys of users. In addition, profile matching using inner product between vectors cannot effectively filter out users with ulterior motives. To tackle the above challenges, we first improve a homomorphic re-encryption system (HRES) to support a single homomorphic multiplication and arbitrarily many homomorphic additions. The public key negotiated by the clouds is used to encrypt the users’ data, thereby avoiding the issues of key leakage and key management, and the privacy of users’ data is also protected. Furthermore, our scheme utilizes the homomorphic multiplication property of the improved HRES algorithm to compute the cosine result between the normalized vectors as the standard for measuring the users’ proximity. Thus, we can effectively improve the social experience of users.


---

## Body

## 1. Introduction

With the rapid development of Internet technology, mobile devices such as mobile phones and tablets have gradually become popular in people’s daily life in recent years. Some social networks such as WeChat, Twitter, and Facebook are gradually integrated into people’s life, and people would like to share some opinions, pictures, and videos with others. Therefore, people are more willing to find potential friends with similar interests in mobile social networks.Profile-matching is the most effective way to measure the proximity between users’ personal profiles. The user’s personal profile is often defined as a vector in practical applications, and each dimension of the vector represents an attribute corresponding to a hobby, such as football, photography, and religion. Each attribute value is represented by an integer between 0 and 10 or a larger range. The attribute value indicates the degree of the interest. The value 0 means that the user has no interest in the item, and value 10 represents that the user is particularly fond of it. Moreover, social proximity is often defined as the inner product of two users’ vectors [1–3]. Since the inner product is the sum of the products of the corresponding attributes between the two vectors, it cannot accurately show the proximity between users. For example, the vector of user A is uA=3,4,7,8, user B is uB=10,10,10,10, and user C is uC=4,3,8,7. User A wants to find a person with a higher proximity between user B and user C. If the inner product of two vectors is chosen as a measurement, it is surprising that user B meets higher requirements than user C. To get more accurate social proximity results, it is preferred to adopt cosine proximity result between the two normalized vectors as the standard.In addition, users’ profiles often contain sensitive data and they do not want to expose their personal information. One way to protect the users’ privacy is to encrypt the data by cryptographic technologies, but the structure of raw data will be essentially damaged after encryption, causing difficulties in reprocessing the data. The homomorphic encryption technology [4–7] has its unique advantages in encrypted data processing. In particular, partial homomorphic encryption technique [8] is more suitable for many realistic applications [9].In many existing profile-matching works [1, 10, 11], a large amount of interactions are often required between user mobile terminals to obtain matching results, which will bring heavy computational costs and communication overhead to users. In addition, users also need to stay online during the matching process. Fortunately, with the development of cloud computing technology [12, 13], the cloud platform can provide users with huge storage space and abundant computing resources. Outsourcing computing and storage to the cloud can effectively reduce the burden on the users’ mobile terminals. Gao et al. [2] transfer users’ work to the cloud with the help of two cooperative but noncollusive clouds, and users can go offline after uploading their profiles to the cloud. Gao et al.’s scheme utilizes an ElGamal-like proxy re-encryption [14] algorithm with additive homomorphic property, which leads to the issues of key management and the leakage of re-encryption keys. Furthermore, the ElGamal-like algorithm requires that the size of the plaintext cannot exceed 40 bits in order to ensure the decryption efficiency; thus it cannot be applied to the scenarios requiring high data accuracy.The main contributions of our work are as follows:(i)
We improve the HRES algorithm [15] in order to avoid the drawbacks in [2]. The improved algorithm supports one homomorphic multiplication and arbitrarily many homomorphic additions, which can effectively avoid the key leakage and the key management issues caused during users’ uploading re-encryption keys.(ii)
This paper utilizes the homomorphic multiplication property of the improved HRES algorithm to compute the cosine result between the normalized vectors as the standard for measuring proximity. Our proposal can effectively ensure the accuracy of the matching results and improve the social experience of the users. Furthermore, the improved HRES algorithm can prove to be semantically secure, and the profile-matching protocol is also secure in the sense that both clouds cannot get useful information about users’ data under the non-collusion security model.


### 1.1. Related Work

The research on privacy-preserving profile matching can be mainly divided into two categories, coarse-grained [16–19] and fine-grained [1, 2, 10] profile-matching schemes.


#### 1.1.1. Coarse-Grained Scheme

In the coarse-grained profile-matching schemes, the matching proximity is often defined as a set intersection or the cardinality of intersections of user’s attribute sets, but this solution cannot further distinguish the specific relevance between users. In 2011, Li et al. [16] proposed two distributed privacy-preserving profile-matching protocols, which deploy the homomorphic property of Shamir secret sharing scheme [20] to calculate the intersections of users’ private sets without relying on a trusted third party. However, the coarse-grained profile matching cannot accurately measure the proximity of users.


#### 1.1.2. Fine-Grained Scheme

For the fine-grained profile-matching schemes [1, 2, 10], user’s preference or behavior pattern is usually regarded as a multidimensional vector, and the social proximity is usually measured by the inner product between two users’ vectors. For example, Zhang et al. [1] designed a fine-grained profile-matching protocol with three security levels. A user can initiate a matching query for their encrypted data with other users and finally obtains the proximity result by utilizing the homomorphic addition property of the Paillier cryptosystem [21]. However, it is required that both users stay online to perform multiple interactions during the execution of protocols, thus imposing a heavy communication and computational burden on mobile terminals. To tackle the above issues, Gao et al. [2] introduced a novel cloud-assisted profile-matching scheme under multiple keys. The cloud environment is composed of two cooperative but non-collusive clouds, and users in the social application could go offline after uploading their encrypted data. A friend finder can designate a target and initiate a matching query to the cloud; then, the two cloud servers return the matching result to the user through interactions. In their scheme, the clouds perform most of the computations, which effectively reduces the burden of users. And the data providers do not have to stay online all the time. However, the scheme [2] utilizes a secure ElGamal-like [14] proxy re-encryption algorithm to encrypt data, so each user needs to generate their secret keys and re-encryption keys. Although schemes in a multiple-key environment could benefit from some existing technologies [22] that could create secure communicating groups within a secure group with exchange of small information, multiple keys increase additional burden of key management in our consideration. Moreover, it seems impossible to guarantee users’ privacy once the user’s re-encryption key is leaked in the process of uploading to the cloud. What is worse, Gao et al.’s scheme uses the inner product of two vectors to measure the matching degree. However, the ElGamal-like algorithm requires the size of the plaintext to be less than 40 bits to make sure that the ciphertext can be efficiently decrypted using Pollard’s kangaroo algorithm [23] to solve the discrete logarithm problem for a relatively smaller integer. Therefore, the scheme fails to provide high precision computations on the users’ data.


### 1.2. Organization

The rest of the paper is organized as follows. Section2 gives some notations and the main part of the HRES algorithm [15]. Section 3 introduces the system and adversary models. Section 4 provides the construction of the improved algorithm and the profile-matching scheme. Section 5 presents the security proof of the improved HRES algorithm and the security analysis of the profile-matching protocol. Section 6 draws conclusions.


## 1.1. Related Work

The research on privacy-preserving profile matching can be mainly divided into two categories, coarse-grained [16–19] and fine-grained [1, 2, 10] profile-matching schemes.


### 1.1.1. Coarse-Grained Scheme

In the coarse-grained profile-matching schemes, the matching proximity is often defined as a set intersection or the cardinality of intersections of user’s attribute sets, but this solution cannot further distinguish the specific relevance between users. In 2011, Li et al. [16] proposed two distributed privacy-preserving profile-matching protocols, which deploy the homomorphic property of Shamir secret sharing scheme [20] to calculate the intersections of users’ private sets without relying on a trusted third party. However, the coarse-grained profile matching cannot accurately measure the proximity of users.


### 1.1.2. Fine-Grained Scheme

For the fine-grained profile-matching schemes [1, 2, 10], user’s preference or behavior pattern is usually regarded as a multidimensional vector, and the social proximity is usually measured by the inner product between two users’ vectors. For example, Zhang et al. [1] designed a fine-grained profile-matching protocol with three security levels. A user can initiate a matching query for their encrypted data with other users and finally obtains the proximity result by utilizing the homomorphic addition property of the Paillier cryptosystem [21]. However, it is required that both users stay online to perform multiple interactions during the execution of protocols, thus imposing a heavy communication and computational burden on mobile terminals. To tackle the above issues, Gao et al. [2] introduced a novel cloud-assisted profile-matching scheme under multiple keys. The cloud environment is composed of two cooperative but non-collusive clouds, and users in the social application could go offline after uploading their encrypted data. A friend finder can designate a target and initiate a matching query to the cloud; then, the two cloud servers return the matching result to the user through interactions. In their scheme, the clouds perform most of the computations, which effectively reduces the burden of users. And the data providers do not have to stay online all the time. However, the scheme [2] utilizes a secure ElGamal-like [14] proxy re-encryption algorithm to encrypt data, so each user needs to generate their secret keys and re-encryption keys. Although schemes in a multiple-key environment could benefit from some existing technologies [22] that could create secure communicating groups within a secure group with exchange of small information, multiple keys increase additional burden of key management in our consideration. Moreover, it seems impossible to guarantee users’ privacy once the user’s re-encryption key is leaked in the process of uploading to the cloud. What is worse, Gao et al.’s scheme uses the inner product of two vectors to measure the matching degree. However, the ElGamal-like algorithm requires the size of the plaintext to be less than 40 bits to make sure that the ciphertext can be efficiently decrypted using Pollard’s kangaroo algorithm [23] to solve the discrete logarithm problem for a relatively smaller integer. Therefore, the scheme fails to provide high precision computations on the users’ data.


## 1.1.1. Coarse-Grained Scheme

In the coarse-grained profile-matching schemes, the matching proximity is often defined as a set intersection or the cardinality of intersections of user’s attribute sets, but this solution cannot further distinguish the specific relevance between users. In 2011, Li et al. [16] proposed two distributed privacy-preserving profile-matching protocols, which deploy the homomorphic property of Shamir secret sharing scheme [20] to calculate the intersections of users’ private sets without relying on a trusted third party. However, the coarse-grained profile matching cannot accurately measure the proximity of users.


## 1.1.2. Fine-Grained Scheme

For the fine-grained profile-matching schemes [1, 2, 10], user’s preference or behavior pattern is usually regarded as a multidimensional vector, and the social proximity is usually measured by the inner product between two users’ vectors. For example, Zhang et al. [1] designed a fine-grained profile-matching protocol with three security levels. A user can initiate a matching query for their encrypted data with other users and finally obtains the proximity result by utilizing the homomorphic addition property of the Paillier cryptosystem [21]. However, it is required that both users stay online to perform multiple interactions during the execution of protocols, thus imposing a heavy communication and computational burden on mobile terminals. To tackle the above issues, Gao et al. [2] introduced a novel cloud-assisted profile-matching scheme under multiple keys. The cloud environment is composed of two cooperative but non-collusive clouds, and users in the social application could go offline after uploading their encrypted data. A friend finder can designate a target and initiate a matching query to the cloud; then, the two cloud servers return the matching result to the user through interactions. In their scheme, the clouds perform most of the computations, which effectively reduces the burden of users. And the data providers do not have to stay online all the time. However, the scheme [2] utilizes a secure ElGamal-like [14] proxy re-encryption algorithm to encrypt data, so each user needs to generate their secret keys and re-encryption keys. Although schemes in a multiple-key environment could benefit from some existing technologies [22] that could create secure communicating groups within a secure group with exchange of small information, multiple keys increase additional burden of key management in our consideration. Moreover, it seems impossible to guarantee users’ privacy once the user’s re-encryption key is leaked in the process of uploading to the cloud. What is worse, Gao et al.’s scheme uses the inner product of two vectors to measure the matching degree. However, the ElGamal-like algorithm requires the size of the plaintext to be less than 40 bits to make sure that the ciphertext can be efficiently decrypted using Pollard’s kangaroo algorithm [23] to solve the discrete logarithm problem for a relatively smaller integer. Therefore, the scheme fails to provide high precision computations on the users’ data.


## 1.2. Organization

The rest of the paper is organized as follows. Section2 gives some notations and the main part of the HRES algorithm [15]. Section 3 introduces the system and adversary models. Section 4 provides the construction of the improved algorithm and the profile-matching scheme. Section 5 presents the security proof of the improved HRES algorithm and the security analysis of the profile-matching protocol. Section 6 draws conclusions.


## 2. Preliminaries

In this section, we briefly introduce some notations appearing in this paper. We also introduce a fundamental HRES algorithm with two cooperative and non-collusive clouds and a data normalization method.


### 2.1. Notation

In this paper, we writex←X for assigning x a value X and denote the integer set 1,...,n as n. In addition, a⟶bindicates that b is calculated by the algorithm a. We use ϕ⋅ and λ⋅ to denote the Euler and the Carmichael function, respectively. The ring ℤn means the residue class ring of integers modulo n, i.e., 0,…,n−1. We use bold lowercase letters to represent vectors, and the Euclidean norm for a vector u is denoted as u. In addition, the bit length of an integer a is denoted as a. We use the symbol ⌈⋅⌉ to denote the ceiling function. Besides, u⋅v means the inner product of the two vectors u and v, and we use EPK⋅ to denote the encryption function with the public key PK of the improved HRES algorithm that will be introduced in the next section.


### 2.2. Homomorphic Re-Encryption

Re-encryption technology supports a proxy transferring decryption authority without decrypting ciphertext [24]. On this basis, homomorphic re-encryption supports homomorphic operation on ciphertext, which is more suitable for data dissemination in networks with special needs. In 2017, Ding et al. proposed a HRES homomorphic re-encryption scheme [15], which includes two non-collusive cloud servers, CA and CB, that jointly manage the ciphertext data. The data owner encrypts his data with the public key generated by negotiation between the two cloud servers, and the ciphertexts can be correctly decrypted only if the two cloud servers cooperate with each other. The HRES consists of the following algorithms.(i)
KeyGen. Given a security parameter κ, let n=pq be a safe RSA modulus, where p and q are primes of the form of p=2p′+1 and q=2q′+1, and p′ and q′ are primes of equal bit length. Let g be an element of the maximal order λn2=lcmϕp2,q2=2np′q′ in ℤn2. The two cloud servers CA and CB, respectively, generate their own key pairs: skCA=a∈ℤλn2,pkCA=gamodn2 and skCB=b∈ℤλn2,pkCB=gbmodn2. Therefore, CA negotiates with CB to generate their Diffie–Hellman key PK=pkCAskCB=pkCBskCA=gabmodn2.(ii)
Enc. Given the Diffie–Hellman key PK and a message m∈ℤn, output the ciphertext as follows: c=EPKm=ξ,ζ=1+mnPKrmodn2,grmodn2, where EPKm indicates the ciphertext encrypted with PK and r is a random integer selected from ℤλn2.(iii)
Partial Dec1. Given skCA=a and a ciphertext c=EPKm∈ℤn22, the cloud CA can transfer the above ciphertext into another ciphertext as EpkCBm=ξ2,ζ2=ξ,ζamodn2 where EpkCBm indicates that the ciphertext can be decrypted with skCB.(iv)
Partial Dec2. Given skCB=b and a ciphertext EpkCBm, the cloud CB can decrypt the plaintext as follows:(1)η=ζ2b=ζab=grab=PKrmodn2,m=Lnξηmodn2=Ln1+mn,where the function Ln⋅ is defined as Lnx=x−1/n.


### 2.3. Normalization Method

This section mainly introduces a common data standardization method:Z-score standardization method, which standardizes data based on the mean and variance of the original data. The processed data obeys the normal distribution; that is, the mean value of the data is 0 and the standard deviation is 1. The conversion formula is as follows:(2)x∗=x−x¯σ,where x∗ represents the processed data, x¯ is the mean of the samples and σ denotes the standard deviation of the samples.In the proposed scheme, the raw data need to be normalized before processing. The reason for this operation is that the values of data from different sources are quite different. In order to eliminate the influence of different numerical range and make the data comparable, data need to be normalized. Hence,Z-score method is adopted to make the data at the same level, which is convenient for analyzing the data.


## 2.1. Notation

In this paper, we writex←X for assigning x a value X and denote the integer set 1,...,n as n. In addition, a⟶bindicates that b is calculated by the algorithm a. We use ϕ⋅ and λ⋅ to denote the Euler and the Carmichael function, respectively. The ring ℤn means the residue class ring of integers modulo n, i.e., 0,…,n−1. We use bold lowercase letters to represent vectors, and the Euclidean norm for a vector u is denoted as u. In addition, the bit length of an integer a is denoted as a. We use the symbol ⌈⋅⌉ to denote the ceiling function. Besides, u⋅v means the inner product of the two vectors u and v, and we use EPK⋅ to denote the encryption function with the public key PK of the improved HRES algorithm that will be introduced in the next section.


## 2.2. Homomorphic Re-Encryption

Re-encryption technology supports a proxy transferring decryption authority without decrypting ciphertext [24]. On this basis, homomorphic re-encryption supports homomorphic operation on ciphertext, which is more suitable for data dissemination in networks with special needs. In 2017, Ding et al. proposed a HRES homomorphic re-encryption scheme [15], which includes two non-collusive cloud servers, CA and CB, that jointly manage the ciphertext data. The data owner encrypts his data with the public key generated by negotiation between the two cloud servers, and the ciphertexts can be correctly decrypted only if the two cloud servers cooperate with each other. The HRES consists of the following algorithms.(i)
KeyGen. Given a security parameter κ, let n=pq be a safe RSA modulus, where p and q are primes of the form of p=2p′+1 and q=2q′+1, and p′ and q′ are primes of equal bit length. Let g be an element of the maximal order λn2=lcmϕp2,q2=2np′q′ in ℤn2. The two cloud servers CA and CB, respectively, generate their own key pairs: skCA=a∈ℤλn2,pkCA=gamodn2 and skCB=b∈ℤλn2,pkCB=gbmodn2. Therefore, CA negotiates with CB to generate their Diffie–Hellman key PK=pkCAskCB=pkCBskCA=gabmodn2.(ii)
Enc. Given the Diffie–Hellman key PK and a message m∈ℤn, output the ciphertext as follows: c=EPKm=ξ,ζ=1+mnPKrmodn2,grmodn2, where EPKm indicates the ciphertext encrypted with PK and r is a random integer selected from ℤλn2.(iii)
Partial Dec1. Given skCA=a and a ciphertext c=EPKm∈ℤn22, the cloud CA can transfer the above ciphertext into another ciphertext as EpkCBm=ξ2,ζ2=ξ,ζamodn2 where EpkCBm indicates that the ciphertext can be decrypted with skCB.(iv)
Partial Dec2. Given skCB=b and a ciphertext EpkCBm, the cloud CB can decrypt the plaintext as follows:(1)η=ζ2b=ζab=grab=PKrmodn2,m=Lnξηmodn2=Ln1+mn,where the function Ln⋅ is defined as Lnx=x−1/n.


## 2.3. Normalization Method

This section mainly introduces a common data standardization method:Z-score standardization method, which standardizes data based on the mean and variance of the original data. The processed data obeys the normal distribution; that is, the mean value of the data is 0 and the standard deviation is 1. The conversion formula is as follows:(2)x∗=x−x¯σ,where x∗ represents the processed data, x¯ is the mean of the samples and σ denotes the standard deviation of the samples.In the proposed scheme, the raw data need to be normalized before processing. The reason for this operation is that the values of data from different sources are quite different. In order to eliminate the influence of different numerical range and make the data comparable, data need to be normalized. Hence,Z-score method is adopted to make the data at the same level, which is convenient for analyzing the data.


## 3. System and Threat Model

### 3.1. System Model

As shown in Figure1, our system model contains three entities: a friend finder (Alice), the cloud environment, and other users. Each entity is described as follows: Alice is marked as a friend finder who wants to find friends that have similar interests with her in the social network. The cloud environment includes two cloud servers, CA and CB, which can provide users with enormous storage space for storing personal profiles and a large amount of computing resources. Through cooperating, CA and CB can help Alice calculate the proximities with other users, and the privacy of the two users will be not compromised. There are many other users in social networks who prefer to outsource the encrypted data representing their preferences to the cloud CA.Figure 1
System model.Each user registers a personal account in the mobile social network and then fills in the personal information. The personal information contains user’s preferences that can be used as a measurement for profile matching. However, the user does not want to reveal his private data in order to avoid illegal use [25]. Personal profile is often defined as a multidimensional vector u=u1,u2,…,un, and each dimension represents an attribute corresponding to a hobby, such as cooking and tourism. Each attribute value may be represented by an integer ranging from 0 to 10, or a larger range. The bigger the number is, the more the users like the item will be, and vice versa. To better measure the proximity between users, the cosine value of normalized vectors with Z-score method is taken in this paper.


### 3.2. Threat Model

In the honest-but-curious model, an external adversary and an internal adversary are considered. An external adversary mainly refers to an eavesdropper who can get some information (e.g., encrypted data) through the transparent channel by eavesdropping. An internal adversary is an honest-but-curious entity such that he faithfully follow the agreement but attempt to collect and reveal private information during the execution of the agreement. The friend finder may want to expose other users’ profiles, while the two clouds may want to reveal the users’ personal data in the social networks. Moreover, it is assumed that the two clouds will never collude with each other and the users will not deliberately attempt to guess the cosine result by adjusting the vector multiple times.


## 3.1. System Model

As shown in Figure1, our system model contains three entities: a friend finder (Alice), the cloud environment, and other users. Each entity is described as follows: Alice is marked as a friend finder who wants to find friends that have similar interests with her in the social network. The cloud environment includes two cloud servers, CA and CB, which can provide users with enormous storage space for storing personal profiles and a large amount of computing resources. Through cooperating, CA and CB can help Alice calculate the proximities with other users, and the privacy of the two users will be not compromised. There are many other users in social networks who prefer to outsource the encrypted data representing their preferences to the cloud CA.Figure 1
System model.Each user registers a personal account in the mobile social network and then fills in the personal information. The personal information contains user’s preferences that can be used as a measurement for profile matching. However, the user does not want to reveal his private data in order to avoid illegal use [25]. Personal profile is often defined as a multidimensional vector u=u1,u2,…,un, and each dimension represents an attribute corresponding to a hobby, such as cooking and tourism. Each attribute value may be represented by an integer ranging from 0 to 10, or a larger range. The bigger the number is, the more the users like the item will be, and vice versa. To better measure the proximity between users, the cosine value of normalized vectors with Z-score method is taken in this paper.


## 3.2. Threat Model

In the honest-but-curious model, an external adversary and an internal adversary are considered. An external adversary mainly refers to an eavesdropper who can get some information (e.g., encrypted data) through the transparent channel by eavesdropping. An internal adversary is an honest-but-curious entity such that he faithfully follow the agreement but attempt to collect and reveal private information during the execution of the agreement. The friend finder may want to expose other users’ profiles, while the two clouds may want to reveal the users’ personal data in the social networks. Moreover, it is assumed that the two clouds will never collude with each other and the users will not deliberately attempt to guess the cosine result by adjusting the vector multiple times.


## 4. Our Construction

In this section, we give the improved HRES algorithm and our privacy-preserving profile-matching scheme.


### 4.1. Improved HRES Algorithm

In order to support homomorphic multiplication computations, a slight modification has been made on the original HRES algorithm. Here it is required that the two clouds CA and CB will not collude with each other and cooperate to perform decryption operations. The improved algorithm includes the following algorithms:KeyGen, Enc, Partial Dec1, Partial Dec2, and Evaluation.(i)
KeyGen. Choose a large prime integer p. Note that the multiplicative group ℤp3∗ has primitive roots of order ϕp3=p2p−1, and hence the algorithm can randomly choose a generator g with order ϕp3=p2p−1 from ℤp3∗. Then the two cloud servers CA and CB, respectively, generate their own key pairs: skCA=a∈ℤϕp3,pkCA=gamodp3 and skCB=b∈ℤϕp3,pkCB=gbmodp3. Therefore, CA negotiates with CB to generate their Diffie–Hellman key PK=gabmodp3.(ii)
Enc. Given the Diffie–Hellman key PK and a plaintext message m, where m∈ℤp, output the ciphertext as follows: c=EPKm=ξ,ζ=1+mpPKrmodp3,grmodp3, where EPKm indicates the ciphertext encrypted with PK and r is a random integer selected from ℤϕp3.(iii)
Partial Dec1. Given skCA and a ciphertext EPKm∈ℤp32, the cloud CA can transfer the above ciphertext into another ciphertext as EpkCBm=ξ2,ζ2=ξ,ζamodp3, where EpkCBm indicates that the ciphertext can be decrypted with skCB.(iv)
Partial Dec2. Given skCB and a ciphertext EpkCBm∈ℤp32, the cloud CB can output the plaintext as follows:(3)η=ζ2b=ζab=grab=PKrmodp3,m=Lpξ2ηmodp3=Lp1+mp,where the functionLp⋅ is defined as Lpx=x−1/p.(v)
Homomorphic evaluation. We first show that the improved scheme supports k+1 homomorphic additions. Given any k+1 ciphertexts, namely, for i=1,…,k+1, ci=EPKmi=ξi,ζi=1+mipPKrimodp3,grimodp3with the underlying plaintext being mi for i=1,…,k+1, we firstly show that our improved algorithm supports k+1 homomorphic additions.Specifically, we computec=ξ,ζ=∏i=1k+1ξimodp3,∏i=1k+1ζimodp3. Note that(4)ξ=∏i=1k+1ξi=∏i=1k+11+mipPKri=1+p∑i=1k+1mi+p2∑i≠jmimjgab∑i=1k+1rimodp3,ζ=∏i=1k+1ζi=∏i=1k+1gri=g∑i=1k+1rimodp3.From the refreshed ciphertextc=ξ,ζ, the cloud CA can use his secret key skCA=a to partially decrypt the ciphertext as c2=ξ2,ζ2=ξ,ζamodp3, where(5)ξ2=ξ=1+p∑i=1k+1mi+p2∑i≠jmimjgab∑i=1k+1rimodp3,ζ2=ζa=ga∑i=1k+1rimodp3.The cloud CB can further decrypt the ciphertextc2=ξ2,ζ2 using his secret key skCB=b as follows. The cloud CB first computes(6)η=ζ2b=ζab=gab∑i=1k+1ri=PK∑i=1k+1rimodp3.Accordingly, it is easy to verify(7)ξ2η=1+p∑i=1k+1mi+p2∑i≠jmimjmodp3,where the cloud CB can obtain the plaintext(8)Lpξ2ηmodp3modp=Lp1+p∑i=1k+1mi+p2∑i≠jmimj+tp3modp=∑i=1k+1mi+p∑i≠jmimj+tp2modp=∑i=1k+1mimodp.Note thatm+1<p−k should hold, i.e., ∑i=1k+1mi<p, if ∑i=1k+1mimodp=∑i=1k+1mi is needed. Therefore, our scheme supports k+1 homomorphic additions on ciphertexts.Now we show that the proposal can perform a homomorphic multiplication on two ciphertexts,c1 and c2, where ci=EPKmi=ξi,ζi with ξi=1+mipPKrimodp3 and ζi=grimodp3 for i=1,2. Specially, we compute c=ξ,ζ=ξ1ξ2modp3,ζ1ζ2modp3. Note that(9)ξ=ξ1ξ2=1+m1p1+m2pPKr1+r2=1+pm1+m2+p2m1m2gabr1+r2modp3,and ζ=ζ1ζ2=gr1+r2modp3. The cloud CA can partially decrypt the ciphertext as c2=ξ2,ζ2=ξ,ζamodp3, where ξ2=ξ=1+pm1+m2+p2m1m2gabr1+r2modp3 and ζ2=ζa=gar1+r2modp3. The cloud CB first computes(10)η=ζ2b=ζab=gabr1+r2=PKr1+r2modp3.Noting that(11)ξη=1+pm1+m2+p2m1m2modp3.The cloud CB computes(12)Lpξηmodp3modp=Lp1+pm1+m2+p2m1m2modp3modp=Lp1+pm1+m2+p2m1m2+tp3modp=m1+m2+pm1m2+tp2modp=m1+m2modp.CB could obtainm1+m2 when m+1<p. Then, CB calculates(13)ξ/ηmodp3−1−pm1+m2p2modp=1+pm1+m2+p2m1m2+tp3−1−pm1+m2p2modp=p2m1m2+tp3p2modp=m1m2+tpmodp=m1m2modp,where the cloud CB obtains the results m1m2modp. Thus, our scheme supports a homomorphic multiplication operation on ciphertexts when m<p/2.


### 4.2. Privacy-Preserving Profile Matching

In this part, the improved HRES algorithm is adopted to implement our privacy-preserving profile-matching scheme. Suppose that Alice’s vector isv=v1,…,vn and that Bob’s vector is u=u1,…,un. The cosine value of the two vectors can be calculated as(14)u⋅v=u1v1+⋯+unvn=∑i=1nuivi,cosu,v=∑i=1nui2+∑i=1nvi2−∑i=1nui−vi2uv.In particular,cosu,v∈0,1 since ui and vi are nonnegative integers. Users can encrypt their vectors with the Diffie–Hellman key PK and then outsource their encrypted data to CA. The procedure for the data outsourcing is presented in Algorithm 1 and the privacy-preserving profile-matching scheme is shown as Algorithm 2.Algorithm 1: Data outsourcing.
Input: A user Bob wants to outsource his personal profile to CA and holds a private vector u=u1,…,un.Output: The encrypted result EPKu′, EPKτ1σB and EPKsB are sent to CA.(1)
CA executesKeyGen algorithm of the improved HRES algorithm with CB to generate their respective key pairs pkCA,skCApkCB,skCB and their Diffie–Hellman key PK2. Thereafter, PK2 is issued to the users in social networks.(2)
Firstly, Bob normalizes his vector withZ-score method and then converts each element of the normalized vector to an integer by multiplying it with a pretreatment public integer l1 and ceiling. Finally, Bob gets his matching vectoru′=u1′,u2′,...,un′ and calculates sB=∑i=1nu′12, σB=⌈u′⌉.(3)
Bob negotiates with the CA to run the Diffie–Hellman key exchange protocol to generate a secret random integerτ1.(4)
After encrypting the following values:EPK2u′←EPK2u1′,EPK2u2′,…,EPK2un′, EPK2sB, and EPK2τ1σB, Bob uploads these encrypted values to CA.Algorithm 2: Privacy-preserving profile-matching scheme.
Input: Alice’s private vector v=v1,…,vn, and the secret keys of CA and CB.Output: Alice gets the cosine result cosu′,v′.(1)
Alice executes theKeyGen algorithm of the improved HRES algorithm with CA to generate their respective key pairs pkA,skA, pkCA′,skCA′ and their Diffie–Hellman key PK1. Then, PK1 is assigned to the cloud CB.(2)
Alice sends her encrypted profile to CA for querying the proximity with Bob in the social networks.(i)
Alice also needs to process her normalized vector with the public numberl1 to get the result v′=v1′,...,vn′, and calculates sA=∑i=1nv′12, σA=⌈v′⌉.(ii)
Alice negotiates with CA to run the Diffie–Hellman key exchange protocol to generate a secret random integerτ2.(iii)
Alice uploads the encrypted valuesEPK2v′, EPK2τ2σA, and EPK2sA to CA.(3)
CA generates random integersσi and works out the following formulas:(i)
EPK2ui′⋅EPK2p−1vi′⟶EPK2ui′−vi′.(ii)
EPK2σiui′−vi′⟶EPK2σiui′−v′i.Next, CA computesEPK2τ1σB⋅EPK2τ2σA; executes the Partial Dec1 algorithm to process EPK2σiui′−vi′ and EPK2τ1σB⋅EPK2τ2σA with its secret key skCA; and then sends the processed results to CB.(4)
CB runs theEvaluation algorithm with its secret key skCB to decrypt EPK2τ1σB⋅EPK2τ2σA and gets β1 where β1=τ1τ2σAσB.(5)
CB runs thePartial Dec2 algorithm with its secret key skCB to decrypt EPK2σiui′−v′i and compute σiui′−vi′⋅σiui′−vi′. Next, CB sends the encrypted values EPK2σi2ui′−v′i2 to CA.(6)
CA computes(i)
EPK2σi−2σi2ui′−vi′2⟶EPK2ui′−vi′2.(ii)
EPK2sA⋅EPK2sB⋅EPK2p−1∑i=1nui′−vi′2⟶EPK22u′∘v′.(iii)
EPK22−12u′∘v′⟶EPK2u′∘v′.After that, CA generates a random integerω and calculates EPK2ωu′∘v′. Finally, CA runs Partial Dec1 algorithm to decrypt EPK2ωu′∘v′ and sends the results to CB.(7)
CB computes the obfuscated proximity result and sends it to CA.(i)
CB runs thePartial Dec2 algorithm to decrypt EPK2ωu′∘v′ and obtains ω⋅u′∘v′.(ii)
CB processes the valueβ1 with a pretreatment public integer l2, computes l2⋅1/β1=l2⋅τ1τ2σAσB−1, and then gets an integer number β2 where β2=⌈l2⋅1/β1⌉.(iii)
CB computesEPK1ωβ2⋅u′∘v′ with the public key PK1 and then sends it to CA.(8)
CA computes the formulaEPK1τ1τ2ω−1ωβ2⋅u′∘v′⟶EPK1τ1τ2β2⋅u′∘v′, runs the Partial Dec1 algorithm with its secret key skCA′ to process EPK1τ1τ2β2⋅u′∘v′, and sends the results to Alice.(9)
Alice runs thePartial Dec2 algorithm with her secret key skA and uses l2 to get τ1τ2β2⋅u′∘v′/l2 which is very close to the matching result u′∘v′/u′v′=cosu′,v′.


## 4.1. Improved HRES Algorithm

In order to support homomorphic multiplication computations, a slight modification has been made on the original HRES algorithm. Here it is required that the two clouds CA and CB will not collude with each other and cooperate to perform decryption operations. The improved algorithm includes the following algorithms:KeyGen, Enc, Partial Dec1, Partial Dec2, and Evaluation.(i)
KeyGen. Choose a large prime integer p. Note that the multiplicative group ℤp3∗ has primitive roots of order ϕp3=p2p−1, and hence the algorithm can randomly choose a generator g with order ϕp3=p2p−1 from ℤp3∗. Then the two cloud servers CA and CB, respectively, generate their own key pairs: skCA=a∈ℤϕp3,pkCA=gamodp3 and skCB=b∈ℤϕp3,pkCB=gbmodp3. Therefore, CA negotiates with CB to generate their Diffie–Hellman key PK=gabmodp3.(ii)
Enc. Given the Diffie–Hellman key PK and a plaintext message m, where m∈ℤp, output the ciphertext as follows: c=EPKm=ξ,ζ=1+mpPKrmodp3,grmodp3, where EPKm indicates the ciphertext encrypted with PK and r is a random integer selected from ℤϕp3.(iii)
Partial Dec1. Given skCA and a ciphertext EPKm∈ℤp32, the cloud CA can transfer the above ciphertext into another ciphertext as EpkCBm=ξ2,ζ2=ξ,ζamodp3, where EpkCBm indicates that the ciphertext can be decrypted with skCB.(iv)
Partial Dec2. Given skCB and a ciphertext EpkCBm∈ℤp32, the cloud CB can output the plaintext as follows:(3)η=ζ2b=ζab=grab=PKrmodp3,m=Lpξ2ηmodp3=Lp1+mp,where the functionLp⋅ is defined as Lpx=x−1/p.(v)
Homomorphic evaluation. We first show that the improved scheme supports k+1 homomorphic additions. Given any k+1 ciphertexts, namely, for i=1,…,k+1, ci=EPKmi=ξi,ζi=1+mipPKrimodp3,grimodp3with the underlying plaintext being mi for i=1,…,k+1, we firstly show that our improved algorithm supports k+1 homomorphic additions.Specifically, we computec=ξ,ζ=∏i=1k+1ξimodp3,∏i=1k+1ζimodp3. Note that(4)ξ=∏i=1k+1ξi=∏i=1k+11+mipPKri=1+p∑i=1k+1mi+p2∑i≠jmimjgab∑i=1k+1rimodp3,ζ=∏i=1k+1ζi=∏i=1k+1gri=g∑i=1k+1rimodp3.From the refreshed ciphertextc=ξ,ζ, the cloud CA can use his secret key skCA=a to partially decrypt the ciphertext as c2=ξ2,ζ2=ξ,ζamodp3, where(5)ξ2=ξ=1+p∑i=1k+1mi+p2∑i≠jmimjgab∑i=1k+1rimodp3,ζ2=ζa=ga∑i=1k+1rimodp3.The cloud CB can further decrypt the ciphertextc2=ξ2,ζ2 using his secret key skCB=b as follows. The cloud CB first computes(6)η=ζ2b=ζab=gab∑i=1k+1ri=PK∑i=1k+1rimodp3.Accordingly, it is easy to verify(7)ξ2η=1+p∑i=1k+1mi+p2∑i≠jmimjmodp3,where the cloud CB can obtain the plaintext(8)Lpξ2ηmodp3modp=Lp1+p∑i=1k+1mi+p2∑i≠jmimj+tp3modp=∑i=1k+1mi+p∑i≠jmimj+tp2modp=∑i=1k+1mimodp.Note thatm+1<p−k should hold, i.e., ∑i=1k+1mi<p, if ∑i=1k+1mimodp=∑i=1k+1mi is needed. Therefore, our scheme supports k+1 homomorphic additions on ciphertexts.Now we show that the proposal can perform a homomorphic multiplication on two ciphertexts,c1 and c2, where ci=EPKmi=ξi,ζi with ξi=1+mipPKrimodp3 and ζi=grimodp3 for i=1,2. Specially, we compute c=ξ,ζ=ξ1ξ2modp3,ζ1ζ2modp3. Note that(9)ξ=ξ1ξ2=1+m1p1+m2pPKr1+r2=1+pm1+m2+p2m1m2gabr1+r2modp3,and ζ=ζ1ζ2=gr1+r2modp3. The cloud CA can partially decrypt the ciphertext as c2=ξ2,ζ2=ξ,ζamodp3, where ξ2=ξ=1+pm1+m2+p2m1m2gabr1+r2modp3 and ζ2=ζa=gar1+r2modp3. The cloud CB first computes(10)η=ζ2b=ζab=gabr1+r2=PKr1+r2modp3.Noting that(11)ξη=1+pm1+m2+p2m1m2modp3.The cloud CB computes(12)Lpξηmodp3modp=Lp1+pm1+m2+p2m1m2modp3modp=Lp1+pm1+m2+p2m1m2+tp3modp=m1+m2+pm1m2+tp2modp=m1+m2modp.CB could obtainm1+m2 when m+1<p. Then, CB calculates(13)ξ/ηmodp3−1−pm1+m2p2modp=1+pm1+m2+p2m1m2+tp3−1−pm1+m2p2modp=p2m1m2+tp3p2modp=m1m2+tpmodp=m1m2modp,where the cloud CB obtains the results m1m2modp. Thus, our scheme supports a homomorphic multiplication operation on ciphertexts when m<p/2.


## 4.2. Privacy-Preserving Profile Matching

In this part, the improved HRES algorithm is adopted to implement our privacy-preserving profile-matching scheme. Suppose that Alice’s vector isv=v1,…,vn and that Bob’s vector is u=u1,…,un. The cosine value of the two vectors can be calculated as(14)u⋅v=u1v1+⋯+unvn=∑i=1nuivi,cosu,v=∑i=1nui2+∑i=1nvi2−∑i=1nui−vi2uv.In particular,cosu,v∈0,1 since ui and vi are nonnegative integers. Users can encrypt their vectors with the Diffie–Hellman key PK and then outsource their encrypted data to CA. The procedure for the data outsourcing is presented in Algorithm 1 and the privacy-preserving profile-matching scheme is shown as Algorithm 2.Algorithm 1: Data outsourcing.
Input: A user Bob wants to outsource his personal profile to CA and holds a private vector u=u1,…,un.Output: The encrypted result EPKu′, EPKτ1σB and EPKsB are sent to CA.(1)
CA executesKeyGen algorithm of the improved HRES algorithm with CB to generate their respective key pairs pkCA,skCApkCB,skCB and their Diffie–Hellman key PK2. Thereafter, PK2 is issued to the users in social networks.(2)
Firstly, Bob normalizes his vector withZ-score method and then converts each element of the normalized vector to an integer by multiplying it with a pretreatment public integer l1 and ceiling. Finally, Bob gets his matching vectoru′=u1′,u2′,...,un′ and calculates sB=∑i=1nu′12, σB=⌈u′⌉.(3)
Bob negotiates with the CA to run the Diffie–Hellman key exchange protocol to generate a secret random integerτ1.(4)
After encrypting the following values:EPK2u′←EPK2u1′,EPK2u2′,…,EPK2un′, EPK2sB, and EPK2τ1σB, Bob uploads these encrypted values to CA.Algorithm 2: Privacy-preserving profile-matching scheme.
Input: Alice’s private vector v=v1,…,vn, and the secret keys of CA and CB.Output: Alice gets the cosine result cosu′,v′.(1)
Alice executes theKeyGen algorithm of the improved HRES algorithm with CA to generate their respective key pairs pkA,skA, pkCA′,skCA′ and their Diffie–Hellman key PK1. Then, PK1 is assigned to the cloud CB.(2)
Alice sends her encrypted profile to CA for querying the proximity with Bob in the social networks.(i)
Alice also needs to process her normalized vector with the public numberl1 to get the result v′=v1′,...,vn′, and calculates sA=∑i=1nv′12, σA=⌈v′⌉.(ii)
Alice negotiates with CA to run the Diffie–Hellman key exchange protocol to generate a secret random integerτ2.(iii)
Alice uploads the encrypted valuesEPK2v′, EPK2τ2σA, and EPK2sA to CA.(3)
CA generates random integersσi and works out the following formulas:(i)
EPK2ui′⋅EPK2p−1vi′⟶EPK2ui′−vi′.(ii)
EPK2σiui′−vi′⟶EPK2σiui′−v′i.Next, CA computesEPK2τ1σB⋅EPK2τ2σA; executes the Partial Dec1 algorithm to process EPK2σiui′−vi′ and EPK2τ1σB⋅EPK2τ2σA with its secret key skCA; and then sends the processed results to CB.(4)
CB runs theEvaluation algorithm with its secret key skCB to decrypt EPK2τ1σB⋅EPK2τ2σA and gets β1 where β1=τ1τ2σAσB.(5)
CB runs thePartial Dec2 algorithm with its secret key skCB to decrypt EPK2σiui′−v′i and compute σiui′−vi′⋅σiui′−vi′. Next, CB sends the encrypted values EPK2σi2ui′−v′i2 to CA.(6)
CA computes(i)
EPK2σi−2σi2ui′−vi′2⟶EPK2ui′−vi′2.(ii)
EPK2sA⋅EPK2sB⋅EPK2p−1∑i=1nui′−vi′2⟶EPK22u′∘v′.(iii)
EPK22−12u′∘v′⟶EPK2u′∘v′.After that, CA generates a random integerω and calculates EPK2ωu′∘v′. Finally, CA runs Partial Dec1 algorithm to decrypt EPK2ωu′∘v′ and sends the results to CB.(7)
CB computes the obfuscated proximity result and sends it to CA.(i)
CB runs thePartial Dec2 algorithm to decrypt EPK2ωu′∘v′ and obtains ω⋅u′∘v′.(ii)
CB processes the valueβ1 with a pretreatment public integer l2, computes l2⋅1/β1=l2⋅τ1τ2σAσB−1, and then gets an integer number β2 where β2=⌈l2⋅1/β1⌉.(iii)
CB computesEPK1ωβ2⋅u′∘v′ with the public key PK1 and then sends it to CA.(8)
CA computes the formulaEPK1τ1τ2ω−1ωβ2⋅u′∘v′⟶EPK1τ1τ2β2⋅u′∘v′, runs the Partial Dec1 algorithm with its secret key skCA′ to process EPK1τ1τ2β2⋅u′∘v′, and sends the results to Alice.(9)
Alice runs thePartial Dec2 algorithm with her secret key skA and uses l2 to get τ1τ2β2⋅u′∘v′/l2 which is very close to the matching result u′∘v′/u′v′=cosu′,v′.


## 5. Correctness and Security

In this section, we firstly give the correctness analysis of our protocol and then prove that the improved HRES algorithm is semantically secure with rigorous method. At last, we prove that our profile-matching scheme is secure under the semihonest model.


### 5.1. Correctness

In our scheme, CB can correctly decrypt and obtain the result ofσiui′−vi′ without revealing any useful information. The demonstration is shown as follows. Firstly, CA computes(15)EPK2p−1vi′≡1+vi′pp−1PKp−1ri,gp−1rimodp3≡1+vi′pp−1+Cp−12vi′p2PKp−1ri,gp−1rimodp3.We can verify that(16)EPK2ui′⋅EPK2p−1vi′≡1+ui′pPKri′,gri′⋅1+vi′pp−1+Cp−12vi′p2PKp−1ri,gp−1rimodp3≡1+ui′−vi′p+vi′−ui′vi′+Cp−12vi′2p2PKp−1ri+ri′,gp−1ri+ri′modp3.Then, CA generates the random integersσi to obfuscate EPK2ui′−vi′, and the final result can be obtained through the following formula:(17)EPK2σiui′−vi′≡1+ui′−vi′p+vi′−ui′vi′+Cp−12vi′2p2σiPKσirip−1+σiri′,gσirip−1+σiri′modp3≡1+σiui′−vi′p+XPKσirip−1+σiri′,gσirip−1+σiri′modp3,where X=Cσi2ui′−vi′+σivi′−ui′vi′+Cp−12vi′2p2. Hence, CB can obtain σiui′−vi′modp. Then, CB calculates σi2ui′−vi′2modp=σi2ui′−vi′2 when 2σi+2maxui′,vi′<p, and it cannot reveal information about ui′ and vi′.On the other hand, we will prove that Alice can obtain a more accurate cosine result as follows.Once CA receivesEPK2σi2ui′−vi′2, it can remove the blinding values σi2 by computing EPK2σi−2σi2ui′−vi′2⟶EPK2ui′−vi′2, and then it computes the following formulas:(i)
EPK2ui′−vi′2,…,EPK2un′−vn′2⟶EPK2∑i=1nui′−vi′2.(ii)
EPK2sA⋅EPK2sB⋅EPK2p−1∑i=1nui′−vi′2⟶EPK22u′∘v′.(iii)
EPK22−12u′∘v′⟶EPK2u′∘v′.Then, CA obtainsEPK2ω⋅u′∘v′ with the blinding value ω. CB decrypts the ciphertext, computes l2ω⋅u′∘v′/τ1τ2σAσB, and then encrypts the ceiling result with PK1. Thus, CA can compute and get EPK1τ1τ2ω−1ωβ2⋅u′∘v′⟶EPK1τ1τ2β2⋅u′∘v′. We find that when the pretreatment number l2 is large, τ1τ2β2⋅u′∘v′ is closer to the cosine result cosu′,v′.


### 5.2. Security Proof of Improved Algorithm

In this subsection, the semantic security of the improved HRES algorithm is proved through three theorems. We first prove that the DDH problem inG (the cyclic group of modulo p3) is hard to solve. Based on this conclusion, the improved HRES algorithm could be semantically secure.Theorem 1.
LetG be the cyclic group of modulo p3, and g be a generator of G. The discrete logarithm problem (in G) is hard to solve.Proof.
For the sake of contradiction, it is assumed that the discrete logarithm problem (inG) is not difficult; i.e., there exists an oracle that can solve the discrete logarithm problem (in G) in polynomial time. For example, given an input A≡gamodp3, the oracle returns the index a as output.(1)
Note that, ifg is a generator of ℤp and satisfies gp−1≠1modp2, g is also a generator of G. Our strategy is as follows. Let B≡gbmodp, we can assume that there exists an integer b′that satisfies B≡gb′modp, such that the equation b≡b′modϕp holds. Multiply simultaneously both sides of the equation by p2 and the equation bp2≡b′p2modϕp3 can be obtained. Thus, it has gbp2≡gb′p2modp3.SinceB≡gb′modp, B can be denoted as B=gb′+kp where k is an integer. Thus, Bp2 can be written as the following formula:(18)Bp2=gb′+kpp2=gb′p2+Cp21kpgb′p2−1+⋯+kpp2.We can obtainBp2≡gb′p2modp3. Then, we query the oracle for solving the discrete logarithm problem in G to get the result b′p2 with gb′p2modp3 as input. And of course b′ can be solved out. This implies that, if the discrete logarithm problem in G were not difficult, the discrete logarithm problem in ℤp turns out to be easy as well. It is contradictory obviously.(2)
Ifg is a generator of ℤp and satisfies gp−1≡1modp2, g+p is also the generator that belongs to both ℤp and G. The proof process is similar to the above one and we will not describe it here.Theorem 2.
Letp be a large prime. Let G be the cyclic group of modulo p3, and g be a generator of G. The Decisional Diffie–Hellman problem (in G) is difficult.Proof.
For the sake of contradiction, it is assumed that the Decisional Diffie–Hellman (inG) is not difficult. It means that there exists an adversaryADDH who can find a random integer z such that gxy≡gzmodp3. We assume that R is a random quadruple and D is a DH quadruple, where R=g,gx,gy,gz and D=g,gx,gy,gxy.(1)
Note that, ifg is a generator of ℤp and satisfies gp−1≠1modp2, g is also a generator of G. If ADDH can find a random integer z that satisfies gxy≡gzmodp3, xy≡zmodϕp3 can be derived. Hence, equation xy≡zmodp−1 holds. Besides, since g is a generator of ℤp, we can also get the equation gxy≡gzmodp. We thus state that if there exists an adversary ADDH who can distinguish the random quadruple R from DH quadruple D, ADDH can also distinguish R and D in ℤp. However, the DDH assumption in ℤpis difficult, so the original hypothesis does not hold. Thus, we can get a conclusion that DDH assumption (in G) is also difficult.(2)
Ifg is a generator of ℤp and satisfies gp−1≡1modp2, then g+pis also the generator that belongs to both ℤp and G. The proof process is similar to the above one and we will not describe it here.Theorem 3.
If Decisional Diffie–Hellman assumption inℤp3∗ holds, the improved HRES algorithm Π presented in Section 5.1 is semantically secure.Proof.
During the KeyGen phase, the cloud servers CA and CB negotiate with each other to generate their Diffie–Hellman key. Due to the difficulty of discrete logarithm problem inℤp3∗, it is negligible to get any information aboutsk1, sk2, or sk1⋅sk2 for any adversaries.
For the sake of contradiction, it is assumed that the schemeΠ is not semantically secure; i.e., there exists a polynomial time adversary AΠ which can break semantic security with nonnegligible probability ξ. AΠ constructs a distinguisher β that can solve the DDH problem in ℤp3∗. The construction is as follows.
Given a challenge quadrupleζ=g,ga,gb,T, where a,b∈ℤp3∗, the goal of the distinguisher β is to determine T=gab or T=R, where R is a random integer in ℤp3∗. The challenger sends the public key PK=ga to the adversary AΠ. Then, the adversary AΠ submits two challenge messages m0,m1 of equal length to the challenger based on his prior knowledge, and then the challenger returns C=gb,T1+mdpmodp3 as a challenge ciphertext to the adversary AΠ, in which d∈0,1. Finally, the adversary outputs d′ as the guess result. If d=d′, the challenger outputs T=gab; otherwise, it outputs T=R. The discussion is as follows:(1)
IfT=gab, then C is a valid ciphertext and the probability of adversary guessing correctly is equal to 1/2+ξ.(2)
IfT=R, then R1+mp is independent of the encrypted message because the random value R is uniformly and randomly distributed among ℤp3∗. Therefore, the probability that the adversary guesses correctly is 1/2.
As a result, if the distinguisher can break the schemeΠ with a nonnegligible probability ξ, the adversary AΠ can attack the DDH assumption in ℤp3∗ with the same advantage. For the reason that the DDH assumption in ℤp3∗ is difficult, our improved scheme Π is semantically secure.


### 5.3. Security Analysis of Our Protocol

The security analysis of our privacy-preserving profile-matching scheme under the semihonest model will be presented in this subsection with a real and ideal paradigm [2, 26]. For any adversaries who attack a real protocol execution, there exists an adversary who attacks an ideal execution, such that the input and output distributions of the adversary and participants in both the real and the ideal executions are fundamentally the same.Theorem 4.
Our profile-matching scheme described in Section5 can securely obtain the matching result through the calculations on ciphertexts under the semihonest and noncollusive adversaries.Proof.
In this scheme, there are mainly four parties: Alice, Bob, CA, and CB. We can construct four simulatorsSim=SimA,SimB,SimCA,SimCB against four types of adversaries AA,AB,ACA,ACB that will corrupt the privacy of Alice, Bob, CA, and CB, respectively.
SimA simulates AA as follows: After receiving the normalized vector v′=v1′,v2′,…,vn′, SimA encrypts v′ and ∑i=1nv′i2, respectively, to get EPK2v′ and EPK2sA. Then, SimA chooses a random integer τ2 and encrypts τ2⌈∑i=1nv′i2⌉ into EPK2τ2σA. SimA randomly picks a vector U′=u^1,u^2,…,u^n, computes EPK2τ1τ2β2⋅U′∘v′, and sends the partial decryption result EPKAτ1τ2β2⋅U′∘v′ processed by its secret key to AA. The view of AA involves the normalized vector v′=v1′,v2′,…,vn′, the encrypted results set EPK2v′,EPK2sA,EPK2τ2σA,EPKAτ1τ2β2⋅U′∘v′, and the decryption result cosU′,v′. The view of AA in real and ideal executions is indistinguishable owing to the semantic security of the improved HRES scheme mentioned above.
SimB simulates AB as follows: After receiving the normalized vector U′=u1′,u2′,…,un′, SimB encrypts U′ and ∑i=1nu′i2, respectively, to get EPK2U′ and EPK2sB. After that, SimB chooses a random integer τ1 and encrypts τ1⌈∑i=1nu′i2⌉ into EPK2τ1σB. Then SimB sends the encrypted results to AB. The view of AB involves the normalized vector U′=u1′,u2′,…,un′ and the encrypted result set EPK2U′,EPK2sB,EPK2τ1σB. The view of AB in real and ideal executions is indistinguishable owing to the semantic security of the improved HRES scheme mentioned above.
SimCA simulates ACA as follows: SimCA randomly picks two vectors U′=u^1,u^2,…,u^n and v′=v^1,v^2,…,v^n. Then, SimCA encrypts them as EPK2U′, EPK2v′, EPK2sB, and EPK2sA. SimCA generates two random integers τ1, τ2; respectively, obtains the encrypted values EPK2τ1σB⋅EPK2τ2σA; and partially decrypts the above result. Finally, it generates random integers σi, ω and computes EPK2σi2ui′−vi′2σi−2, EPK2ωU′∘v′, and EPK1τ1τ2β2⋅U′∘v′. The view of ACA in the real and ideal executions is indistinguishable owing to the semantic security of the improved HRES scheme mentioned above.
SimCB simulates ACB as follows: SimCB chooses random integers ri, mi, ti, where i∈n, and then encrypts them as EPK2mi⋅EPK2−1tiri, EPK2rimi2. Then, it picks a random number s and encrypts it as EPK1s, EPK2s. SimCB re-encrypts them with the secret key of CA and sends the values EPK2mi⋅EPK2−1tiri, EPK2rimi2, EPK1s, EPK2s, rimi−ti, and rimi2 to ACB. The view of ACB is the above encrypted values and some obfuscated data. Although ACB can decrypt and obtain the obfuscated data, the random numbers selected by the simulator are uniformly and randomly distributed in the message space, so they are the obfuscated messages. The view of ACB in real and ideal executions is indistinguishable owing to the semantic security of the improved HRES scheme mentioned above.


## 5.1. Correctness

In our scheme, CB can correctly decrypt and obtain the result ofσiui′−vi′ without revealing any useful information. The demonstration is shown as follows. Firstly, CA computes(15)EPK2p−1vi′≡1+vi′pp−1PKp−1ri,gp−1rimodp3≡1+vi′pp−1+Cp−12vi′p2PKp−1ri,gp−1rimodp3.We can verify that(16)EPK2ui′⋅EPK2p−1vi′≡1+ui′pPKri′,gri′⋅1+vi′pp−1+Cp−12vi′p2PKp−1ri,gp−1rimodp3≡1+ui′−vi′p+vi′−ui′vi′+Cp−12vi′2p2PKp−1ri+ri′,gp−1ri+ri′modp3.Then, CA generates the random integersσi to obfuscate EPK2ui′−vi′, and the final result can be obtained through the following formula:(17)EPK2σiui′−vi′≡1+ui′−vi′p+vi′−ui′vi′+Cp−12vi′2p2σiPKσirip−1+σiri′,gσirip−1+σiri′modp3≡1+σiui′−vi′p+XPKσirip−1+σiri′,gσirip−1+σiri′modp3,where X=Cσi2ui′−vi′+σivi′−ui′vi′+Cp−12vi′2p2. Hence, CB can obtain σiui′−vi′modp. Then, CB calculates σi2ui′−vi′2modp=σi2ui′−vi′2 when 2σi+2maxui′,vi′<p, and it cannot reveal information about ui′ and vi′.On the other hand, we will prove that Alice can obtain a more accurate cosine result as follows.Once CA receivesEPK2σi2ui′−vi′2, it can remove the blinding values σi2 by computing EPK2σi−2σi2ui′−vi′2⟶EPK2ui′−vi′2, and then it computes the following formulas:(i)
EPK2ui′−vi′2,…,EPK2un′−vn′2⟶EPK2∑i=1nui′−vi′2.(ii)
EPK2sA⋅EPK2sB⋅EPK2p−1∑i=1nui′−vi′2⟶EPK22u′∘v′.(iii)
EPK22−12u′∘v′⟶EPK2u′∘v′.Then, CA obtainsEPK2ω⋅u′∘v′ with the blinding value ω. CB decrypts the ciphertext, computes l2ω⋅u′∘v′/τ1τ2σAσB, and then encrypts the ceiling result with PK1. Thus, CA can compute and get EPK1τ1τ2ω−1ωβ2⋅u′∘v′⟶EPK1τ1τ2β2⋅u′∘v′. We find that when the pretreatment number l2 is large, τ1τ2β2⋅u′∘v′ is closer to the cosine result cosu′,v′.


## 5.2. Security Proof of Improved Algorithm

In this subsection, the semantic security of the improved HRES algorithm is proved through three theorems. We first prove that the DDH problem inG (the cyclic group of modulo p3) is hard to solve. Based on this conclusion, the improved HRES algorithm could be semantically secure.Theorem 1.
LetG be the cyclic group of modulo p3, and g be a generator of G. The discrete logarithm problem (in G) is hard to solve.Proof.
For the sake of contradiction, it is assumed that the discrete logarithm problem (inG) is not difficult; i.e., there exists an oracle that can solve the discrete logarithm problem (in G) in polynomial time. For example, given an input A≡gamodp3, the oracle returns the index a as output.(1)
Note that, ifg is a generator of ℤp and satisfies gp−1≠1modp2, g is also a generator of G. Our strategy is as follows. Let B≡gbmodp, we can assume that there exists an integer b′that satisfies B≡gb′modp, such that the equation b≡b′modϕp holds. Multiply simultaneously both sides of the equation by p2 and the equation bp2≡b′p2modϕp3 can be obtained. Thus, it has gbp2≡gb′p2modp3.SinceB≡gb′modp, B can be denoted as B=gb′+kp where k is an integer. Thus, Bp2 can be written as the following formula:(18)Bp2=gb′+kpp2=gb′p2+Cp21kpgb′p2−1+⋯+kpp2.We can obtainBp2≡gb′p2modp3. Then, we query the oracle for solving the discrete logarithm problem in G to get the result b′p2 with gb′p2modp3 as input. And of course b′ can be solved out. This implies that, if the discrete logarithm problem in G were not difficult, the discrete logarithm problem in ℤp turns out to be easy as well. It is contradictory obviously.(2)
Ifg is a generator of ℤp and satisfies gp−1≡1modp2, g+p is also the generator that belongs to both ℤp and G. The proof process is similar to the above one and we will not describe it here.Theorem 2.
Letp be a large prime. Let G be the cyclic group of modulo p3, and g be a generator of G. The Decisional Diffie–Hellman problem (in G) is difficult.Proof.
For the sake of contradiction, it is assumed that the Decisional Diffie–Hellman (inG) is not difficult. It means that there exists an adversaryADDH who can find a random integer z such that gxy≡gzmodp3. We assume that R is a random quadruple and D is a DH quadruple, where R=g,gx,gy,gz and D=g,gx,gy,gxy.(1)
Note that, ifg is a generator of ℤp and satisfies gp−1≠1modp2, g is also a generator of G. If ADDH can find a random integer z that satisfies gxy≡gzmodp3, xy≡zmodϕp3 can be derived. Hence, equation xy≡zmodp−1 holds. Besides, since g is a generator of ℤp, we can also get the equation gxy≡gzmodp. We thus state that if there exists an adversary ADDH who can distinguish the random quadruple R from DH quadruple D, ADDH can also distinguish R and D in ℤp. However, the DDH assumption in ℤpis difficult, so the original hypothesis does not hold. Thus, we can get a conclusion that DDH assumption (in G) is also difficult.(2)
Ifg is a generator of ℤp and satisfies gp−1≡1modp2, then g+pis also the generator that belongs to both ℤp and G. The proof process is similar to the above one and we will not describe it here.Theorem 3.
If Decisional Diffie–Hellman assumption inℤp3∗ holds, the improved HRES algorithm Π presented in Section 5.1 is semantically secure.Proof.
During the KeyGen phase, the cloud servers CA and CB negotiate with each other to generate their Diffie–Hellman key. Due to the difficulty of discrete logarithm problem inℤp3∗, it is negligible to get any information aboutsk1, sk2, or sk1⋅sk2 for any adversaries.
For the sake of contradiction, it is assumed that the schemeΠ is not semantically secure; i.e., there exists a polynomial time adversary AΠ which can break semantic security with nonnegligible probability ξ. AΠ constructs a distinguisher β that can solve the DDH problem in ℤp3∗. The construction is as follows.
Given a challenge quadrupleζ=g,ga,gb,T, where a,b∈ℤp3∗, the goal of the distinguisher β is to determine T=gab or T=R, where R is a random integer in ℤp3∗. The challenger sends the public key PK=ga to the adversary AΠ. Then, the adversary AΠ submits two challenge messages m0,m1 of equal length to the challenger based on his prior knowledge, and then the challenger returns C=gb,T1+mdpmodp3 as a challenge ciphertext to the adversary AΠ, in which d∈0,1. Finally, the adversary outputs d′ as the guess result. If d=d′, the challenger outputs T=gab; otherwise, it outputs T=R. The discussion is as follows:(1)
IfT=gab, then C is a valid ciphertext and the probability of adversary guessing correctly is equal to 1/2+ξ.(2)
IfT=R, then R1+mp is independent of the encrypted message because the random value R is uniformly and randomly distributed among ℤp3∗. Therefore, the probability that the adversary guesses correctly is 1/2.
As a result, if the distinguisher can break the schemeΠ with a nonnegligible probability ξ, the adversary AΠ can attack the DDH assumption in ℤp3∗ with the same advantage. For the reason that the DDH assumption in ℤp3∗ is difficult, our improved scheme Π is semantically secure.


## 5.3. Security Analysis of Our Protocol

The security analysis of our privacy-preserving profile-matching scheme under the semihonest model will be presented in this subsection with a real and ideal paradigm [2, 26]. For any adversaries who attack a real protocol execution, there exists an adversary who attacks an ideal execution, such that the input and output distributions of the adversary and participants in both the real and the ideal executions are fundamentally the same.Theorem 4.
Our profile-matching scheme described in Section5 can securely obtain the matching result through the calculations on ciphertexts under the semihonest and noncollusive adversaries.Proof.
In this scheme, there are mainly four parties: Alice, Bob, CA, and CB. We can construct four simulatorsSim=SimA,SimB,SimCA,SimCB against four types of adversaries AA,AB,ACA,ACB that will corrupt the privacy of Alice, Bob, CA, and CB, respectively.
SimA simulates AA as follows: After receiving the normalized vector v′=v1′,v2′,…,vn′, SimA encrypts v′ and ∑i=1nv′i2, respectively, to get EPK2v′ and EPK2sA. Then, SimA chooses a random integer τ2 and encrypts τ2⌈∑i=1nv′i2⌉ into EPK2τ2σA. SimA randomly picks a vector U′=u^1,u^2,…,u^n, computes EPK2τ1τ2β2⋅U′∘v′, and sends the partial decryption result EPKAτ1τ2β2⋅U′∘v′ processed by its secret key to AA. The view of AA involves the normalized vector v′=v1′,v2′,…,vn′, the encrypted results set EPK2v′,EPK2sA,EPK2τ2σA,EPKAτ1τ2β2⋅U′∘v′, and the decryption result cosU′,v′. The view of AA in real and ideal executions is indistinguishable owing to the semantic security of the improved HRES scheme mentioned above.
SimB simulates AB as follows: After receiving the normalized vector U′=u1′,u2′,…,un′, SimB encrypts U′ and ∑i=1nu′i2, respectively, to get EPK2U′ and EPK2sB. After that, SimB chooses a random integer τ1 and encrypts τ1⌈∑i=1nu′i2⌉ into EPK2τ1σB. Then SimB sends the encrypted results to AB. The view of AB involves the normalized vector U′=u1′,u2′,…,un′ and the encrypted result set EPK2U′,EPK2sB,EPK2τ1σB. The view of AB in real and ideal executions is indistinguishable owing to the semantic security of the improved HRES scheme mentioned above.
SimCA simulates ACA as follows: SimCA randomly picks two vectors U′=u^1,u^2,…,u^n and v′=v^1,v^2,…,v^n. Then, SimCA encrypts them as EPK2U′, EPK2v′, EPK2sB, and EPK2sA. SimCA generates two random integers τ1, τ2; respectively, obtains the encrypted values EPK2τ1σB⋅EPK2τ2σA; and partially decrypts the above result. Finally, it generates random integers σi, ω and computes EPK2σi2ui′−vi′2σi−2, EPK2ωU′∘v′, and EPK1τ1τ2β2⋅U′∘v′. The view of ACA in the real and ideal executions is indistinguishable owing to the semantic security of the improved HRES scheme mentioned above.
SimCB simulates ACB as follows: SimCB chooses random integers ri, mi, ti, where i∈n, and then encrypts them as EPK2mi⋅EPK2−1tiri, EPK2rimi2. Then, it picks a random number s and encrypts it as EPK1s, EPK2s. SimCB re-encrypts them with the secret key of CA and sends the values EPK2mi⋅EPK2−1tiri, EPK2rimi2, EPK1s, EPK2s, rimi−ti, and rimi2 to ACB. The view of ACB is the above encrypted values and some obfuscated data. Although ACB can decrypt and obtain the obfuscated data, the random numbers selected by the simulator are uniformly and randomly distributed in the message space, so they are the obfuscated messages. The view of ACB in real and ideal executions is indistinguishable owing to the semantic security of the improved HRES scheme mentioned above.


## 6. Evaluation

### 6.1. Comparison

In this subsection, we mainly discuss the advantages of our scheme compared with the existing privacy-preserving profile-matching schemes [1, 2, 11, 27] in Table 1. These schemes [1, 11, 27] require users to stay online simultaneously to obtain matching results through multiple interactions, resulting in additional computational costs and communication overheads on mobile devices of users. In our scheme, users only need to encrypt their personal profiles and upload them to the cloud, and then they can go offline. For a Friend finder, he can designate a target to initiate a matching query and ultimately get the matching result. Most computations are undertaken by the two cloud servers, which can greatly reduce the burden of users. Compared with the scheme in [2], the users do not need to upload the re-encryption keys when uploading their encrypted data, thereby avoiding the risk of the users’ personal data leakage due to the re-encryption key leakage and reducing the burden of the key management. We use the cosine scores of two vectors as the matching result instead of the intersection of two sets or the inner product of two vectors. In particular, the proposed scheme supports processing larger data. Therefore, the proposed scheme is fine-grained, and the precision of matching result is high.Table 1
Comparison with other profile-matching schemes.
SchemeNoninteractiveHigh precisionFine-grainedSingle keyOur schemeYesYesYesYesScheme [1]NoNoYesYesScheme [2]YesNoYesNoScheme [11]NoNoYesYesScheme [27]NoYesYesYes


### 6.2. Simulation

In order to better demonstrate the performance of our scheme and compare it with Gao’s scheme [2], we simulated two profile-matching protocols separately. Simulations are conducted using the PBC library on a computer equipped with a 2.5 GHz Intel core i5-3210 processor with 4 GB of RAM. The dimension n of users’ vector is set as 20, and we compared the two system performances with the increase in the number of the data bits. The results are shown in Figures 2 and 3. More intuitive comparison results are shown in Figure 4. As the number of data bits increases, the decryption time of Gao’s scheme will increase exponentially, and the time spent by cloud servers and users increases. Specifically, our scheme has no limit on the length of the data. And as the length increases, the time consumed does not change significantly.Figure 2
Computational costs of Gao’s scheme with the increase in data bits.Figure 3
Computational costs of the proposed scheme with the increase in data bits.Figure 4
Efficiency comparison between the proposed scheme and Gao’s scheme.


### 6.3. Complexity Analysis

In this subsection, we review some existing conclusions before analyzing the computational complexity of our scheme. The complexity of calculating modular multiplication and modular exponentiation isOlog2p and Olog3p, respectively, where p is the modulus.First, we analyze the computational complexity of the improved HRES algorithm. TheEnc involves two modular multiplications, a modular addition and two modular exponentiations. Hence, the computational complexity of this part is Olog3p. The Partial Dec1 only needs a modular exponentiation, so the computational complexity is Olog3p. Similarly, the Partial Dec2 involves a modular exponentiation, a modular inversion, a modular multiplication, a subtraction, and a division. Hence, the corresponding computational complexity is Olog3p. On this basis, we could deduce that the computational complexity of the procedure executed by Alice is Olog3p, and the same for Bob, CA, and CB.


## 6.1. Comparison

In this subsection, we mainly discuss the advantages of our scheme compared with the existing privacy-preserving profile-matching schemes [1, 2, 11, 27] in Table 1. These schemes [1, 11, 27] require users to stay online simultaneously to obtain matching results through multiple interactions, resulting in additional computational costs and communication overheads on mobile devices of users. In our scheme, users only need to encrypt their personal profiles and upload them to the cloud, and then they can go offline. For a Friend finder, he can designate a target to initiate a matching query and ultimately get the matching result. Most computations are undertaken by the two cloud servers, which can greatly reduce the burden of users. Compared with the scheme in [2], the users do not need to upload the re-encryption keys when uploading their encrypted data, thereby avoiding the risk of the users’ personal data leakage due to the re-encryption key leakage and reducing the burden of the key management. We use the cosine scores of two vectors as the matching result instead of the intersection of two sets or the inner product of two vectors. In particular, the proposed scheme supports processing larger data. Therefore, the proposed scheme is fine-grained, and the precision of matching result is high.Table 1
Comparison with other profile-matching schemes.
SchemeNoninteractiveHigh precisionFine-grainedSingle keyOur schemeYesYesYesYesScheme [1]NoNoYesYesScheme [2]YesNoYesNoScheme [11]NoNoYesYesScheme [27]NoYesYesYes


## 6.2. Simulation

In order to better demonstrate the performance of our scheme and compare it with Gao’s scheme [2], we simulated two profile-matching protocols separately. Simulations are conducted using the PBC library on a computer equipped with a 2.5 GHz Intel core i5-3210 processor with 4 GB of RAM. The dimension n of users’ vector is set as 20, and we compared the two system performances with the increase in the number of the data bits. The results are shown in Figures 2 and 3. More intuitive comparison results are shown in Figure 4. As the number of data bits increases, the decryption time of Gao’s scheme will increase exponentially, and the time spent by cloud servers and users increases. Specifically, our scheme has no limit on the length of the data. And as the length increases, the time consumed does not change significantly.Figure 2
Computational costs of Gao’s scheme with the increase in data bits.Figure 3
Computational costs of the proposed scheme with the increase in data bits.Figure 4
Efficiency comparison between the proposed scheme and Gao’s scheme.


## 6.3. Complexity Analysis

In this subsection, we review some existing conclusions before analyzing the computational complexity of our scheme. The complexity of calculating modular multiplication and modular exponentiation isOlog2p and Olog3p, respectively, where p is the modulus.First, we analyze the computational complexity of the improved HRES algorithm. TheEnc involves two modular multiplications, a modular addition and two modular exponentiations. Hence, the computational complexity of this part is Olog3p. The Partial Dec1 only needs a modular exponentiation, so the computational complexity is Olog3p. Similarly, the Partial Dec2 involves a modular exponentiation, a modular inversion, a modular multiplication, a subtraction, and a division. Hence, the corresponding computational complexity is Olog3p. On this basis, we could deduce that the computational complexity of the procedure executed by Alice is Olog3p, and the same for Bob, CA, and CB.


## 7. Conclusion

In this paper, we propose a privacy-preserving profile-matching scheme over improved HRES algorithm in mobile social networks. The improved algorithm can support one-time homomorphic multiplication and arbitrarily many homomorphic additions. Compared with the original scheme [2], the key management burden can be reduced, and the privacy problem of users caused by the re-encryption keys leakage can be effectively solved. In addition, our scheme utilizes the cosine result between two normalized vectors as the standard for measuring the users’ proximity, which can effectively improve the social experience of the users. Even if users with ulterior motives collude with one of the clouds, the personal data of other users will not be revealed. At last, we prove that our scheme is secure under the semihonest model through strict security analysis.



---

*Source: 4938736-2020-09-21.xml*