1 Introduction

Given the popularity of smart phones, mobile terminals and other mobile devices, the use of mobile devices to access social networks has become mainstream [1]. Some social networks for instance, LinkedIn, Facebook and MySpace have been very prominent and are now the preferred way of communication for many people [2]. Mobile social networks (MSNs) allow mobile users to discover and interact with potential friends. Increasingly more people are beginning to pay attention to the task of looking for a potential new friend with similar interests. Profile matching is the most cost-effective method of measuring the proximity to users’ personal profiles. However, one’s personal profile may contain sensitive information, and users do not want to reveal their private data. In addition, current profile-matching schemes [3,4,5,6] have high computational overhead and are not suitable for mobile devices, which have low computational resources.

One way to address the issue of high computational overhead is to take advantage of cloud computing. The cloud promises to provide massively scalable data storage and powerful computation services to society at a reduced cost [7]. With the rapid development of cloud computing [8], outsourcing computing and storage to the cloud is an effective way to relieve the heavy burden on users of managing and processing data. However, trivially moving the computation to the cloud will lead to privacy leakage [9]. To prevent privacy leakage, data owners tend to encrypt their private data before outsourcing. However, current solutions either have heavy interactions or require users to encrypt private data under a single key. In this paper, we propose a novel cloud-assisted privacy-preserving profile-matching scheme under multiple keys based on a proxy re-encryption scheme with additive homomorphism. The cloud environment is composed of two cloud servers. Our scheme does not require users to be online at the same time. Users only need to encrypt their personal profiles and send them to one cloud server and receive matching results. The two cloud servers perform most of the computations in our scheme, effectively reducing the user’s computational burden and ensuring that the user’s private information is not leaked to the clouds. Our scheme is secure under the honest-but-curious (HBC) model assuming that two cloud servers do not collude.

1.1 Related work

With the fast development of cloud computing, Internet of things and smart grids, more and more data are being produced and analyzed, leading to a new big data era [10, 11]. However, the risk of the data being revealed or disclosed makes it urgent to enhance the security and privacy of users’ data. In the literature, privacy protection issues have been studied in various fields, such as Internet of things [12, 13], online social networks [14], smart grids [15], and cloud computing [16]. Negi et al. [16] proposed a modification to the confidence based filtering method (CBF) which is investigated for cloud computing environment based on correlation pattern to mitigate distributed denial of service attacks on cloud. In [12], Stergiou et al. combined the cloud computing and Internet of things in order to examine the common features, and in order to discover the benefits of their integration.

A number of research works have been conducted on protecting a user’s privacy during the process of profile matching. Previous work focusing on privacy-preserving profile matching can be broadly divided into two categories. The first approach is the coarse-grained private matching approach. In this approach, social proximity is defined as a set intersection or the cardinality of a set intersection of two users’ attribute sets, [4,5,6, 17] are coarse-grained private matching schemes; they cannot further differentiate users with different degrees of attributes. The other approach is the fine-grained private matching approach. In this approach, social proximity is defined as the dot product between two users’ vectors, [3, 18, 19] are fine-grained private matching schemes; they enable finer differentiation among users having different degrees of interest in the same attribute.

With the rapidly increasing ability to store and handle personal data, the problem of protecting privacy in cloud computing has become more important in recent years. To achieve secure data processing in the cloud, many schemes based on various techniques have been proposed, including partially homomorphic encryption (PHE) [20], fully homomorphic encryption (FHE) [21,22,23,24] and secure multiparty computation [25]. Fully homomorphic encryption has high computational overhead. Although it supports homomorphic computations over ciphertext, which are encrypted with a single key, it is not suitable for multi-user systems. Secure multiparty computation always requires heavy interactions and is not suitable for outsourcing situations. Compared with schemes employing FHE, PHE has lower computational overhead. To meet certain special security requirements, many schemes based on encryption schemes with certain properties have been proposed such as deduplication schemes [20, 26, 27], identity-based encryption schemes [28], and attribute-based encryption schemes [29].

Recently, secure data processing in the cloud under multiple keys has become an important area of research. López et al. [30] proposed an FHE under multiple keys, but a large amount of interaction between users is required during the decryption of the final result. Liu et al. [31] presented a distributed public-key cryptosystem with double trapdoors (DT-PKC) to realize privacy-preserving outsourced calculation. DT-PKC is deployed to split a strong private key into different shares. This scheme requires many interactions between the cloud and the server, who provides the computing service. Peter et al. [32] proposed a novel technique based on additively homomorphic encryption. They extensively utilized the BCP cryptosystem [33], which is additively homomorphic and offers two independent decryption mechanisms. However, this scheme requires heavy interactions between servers when transforming the ciphertexts of multiple keys into a single key. In addition, an efficient and secure data sharing framework has been proposed [34] using homomorphic encryption and proxy re-encryption schemes. Rong et al. [35] proposed an outsourced privacy-preserving scalar product protocol that leverages the multiplicatively homomorphic property of a bidirectional proxy re-encryption scheme Wang et al. [36] proposed two privacy-preserving schemes for outsourcing computation over ciphertexts under multiple keys. To the best of our knowledge, there are very few studies [35] on outsourced privacy-preserving dot product computing under multiple keys.

1.2 Our contribution

We present a cloud-assisted privacy-preserving profile-matching scheme under multiple keys to efficiently compute the social proximity between two users to discover potential friends while ensuring personal privacy. There are three main contributions of our scheme.

  • Non-interactive for users Our scheme does not require the friend finder and the data provider to be online simultaneously. Before receiving the matching result, users only need to encrypt their personal profiles and send the ciphertext to one cloud server.

  • Efficient The clouds perform most of the computation in our scheme, thereby effectively reducing the user’s computational load and ensuring that the user’s personal information is not leaked to the clouds.

  • Allow user and cloud collusion Our scheme is secure under the HBC model assuming that the two cloud servers do not collude. Even if the participating parties collude with one of the cloud servers, our scheme will still not reveal any private information about either the inputs, intermediate results or final results.

1.3 Organization

The remainder of this paper is organized as follows. In Sect. 2, we describe our system model and adversary model. In Sect. 3, we give some preliminaries, including the additively homomorphic encryption, proxy re-encryption and additively homomorphic proxy re-encryption schemes. Section 4 presents the cloud-assisted privacy-preserving profile-matching scheme. Section 5 analyses the correctness and security of our scheme. Section 6 compares our scheme with some known privacy-preserving profile-matching or dot product computation schemes. Section 7 concludes this paper.

2 Problem statement

2.1 System model

Figure 1 shows our system model. In our work, we denote Alice as the friend finder, and she wants to find a friend with similar interests from the other users in the mobile social network. The cloud environment consists of two cloud servers: cloud A (CA) and cloud B (CB). The two clouds provide large-scale data storage and computation services to reduce total cost. There are many users (data provider), and they encrypt their own private profile and outsource the computation to the cloud.

Fig. 1
figure 1

System Model

Full size image

Each person in the mobile social network has a profile that is used to measure their personal preference. Every personal profile is defined as a vector \(\mathbf {U}\,=\,<u_1, u_2, \cdots , u_n>\). The n represents the dimension of the vector. Every attribute corresponds to an interest, such as dancing and traveling, and every attribute value is an integer in [0, 10]. The attribute value represents the degree of the interest and indicates the level of interest, from no interest (0) to extremely high interest (10). In addition, social proximity is defined as the dot product of two users’ vectors. Taking the dot product is a popular similarity criterion [3, 18]. Before profile matching, we should normalize the dot products to have unit length. To perform the following encryption, every attribute value should be integerized as a member of some mathematic group. To ensure accuracy, we should keep H digits after the binary point. We can multiply every attribute value of users’ vectors by \(2^H\) and then integerize the result.

2.2 Adversary model

The adversary model considered in this paper is under the honest-but-curious (HBC) framework [37]. In this framework, all participating parties faithfully follow the scheme, but they can collect and infer private information from the protocol and even collude with one of the cloud servers. However, the two cloud servers will never collude with each other. In the HBC model, the users perform the protocol faithfully and do not deliberately attempt to guess the dot product by adjusting the vector multiple times.

Fig. 2
figure 2

Protocol 1

Full size image

3 Preliminaries

3.1 Additive homomorphic

Suppose that \({E}_{pk}(m_1) \) and \( {E}_{pk}(m_2) \) are two additively homomorphic ciphertexts under the same public key pk. The additively homomorphic cryptosystem has a key property.

  • Homomorphic.

    1. 1).

      \({E}_{pk}(m_1){E}_{pk}(m_2) = {E}_{pk}(m_1+m_2)\).

    2. 2).

      \({E}_{pk}(m_1)^{m_2} = {E}_{pk}(m_1\cdot m_2)\).

3.2 Proxy re-encryption

Proxy re-encryption (PRE) [38] allows a semi-trusted proxy to transform the ciphertext from Alice’s public key \(pk_\text {A}\) into a ciphertext under CB’s public key \(pk_\text {CB}\). Furthermore, a key pair can be generated to allow the encrypted data to be delivered in a re-encrypted form such that CB can decrypt the data but the proxy cannot. Ultimately, the proxy learns nothing about the corresponding plaintext.

3.3 Additive homomorphic proxy re-encryption

In this work, we adopt the ElGamal-like encryption scheme (EL) in [34]. The EL scheme is a semantically secure proxy re-encryption scheme under the Decisional Bilinear Diffie-Hellman assumption [39, 40], which supports additive homomorphism. The EL scheme is based on bilinear mapping and works as follows:

Suppose that \(G_1\) and \(G_2\) are two cyclic groups of prime order q with a bilinear map \(e: G_1 \times G_1 \rightarrow G_2\). g is a generator of \(G_1\). The mapping e has three properties. (1) Bilinearity: For any \(g \in G_1\) and \(a,b \in Z_q\), \(e(g^a,g^b)=e(g,g)^{ab}\) is efficiently computable. (2) Non-degeneracy: \(e(g,g) \ne 1\). (3) Computability: e can be efficiently computed. Here, \(G_1, G_2, q, e, g \) and \(Z=e(g,g) \in G_2 \) are public parameters.

  • Key generation: Given parameters, output the public key \(pk_\text {a}= (Z^{a_1},g^{a_2})\) and the corresponding private key \(sk_\text {a}=(a_1,a_2)\), where \(a_1,a_2 \xleftarrow {R} Z_q\).

  • Re-encryption key generation: Given \(pk_\text {b}=(Z^{b_1},g^{b_2})\) and \(sk_\text {a}=(a_1,a_2)\), output the proxy re-encryption key using the private key \(sk_\text {a}\) and public key \(pk_\text {b}\). Specifically, \(rk_{pk_\text {a} \rightarrow pk_\text {b}}=(g^{b_2})^{a_1} = g^{a_1b_2}\).

  • Encryption: Given \(pk_\text {a}\) and the message \(m \in Z_q\), output \( E_{pk_\text {a}}(m) =(\beta ,\gamma )=(g^r,Z^mZ^{a_1r})\), where r is a random number from \(Z_q\).

  • Decryption: Given \((\beta ,\gamma )\) and \(sk_\text {a}\), the ciphertext \((\beta ,\gamma )\) can be decrypted using \(sk_\text {a}\) by computing \(\frac{ \gamma }{ e(g,\beta )^{a_1}}=\frac{ Z^mZ^{a_1r} }{ e(g,g^r)^{a_1} }=\frac{ Z^mZ^{a_1r} }{ Z^{a_1r} }=Z^m\).

  • Re-encryption: Given the ciphertext \((\beta ,\gamma )\) and \(rk_{pk_\text {a} \rightarrow pk_\text {b}}\), compute \(\beta ^*=e(rk_{{pk_\text {a}} \rightarrow {pk_\text {b}}},\beta ) =e(g^{a_1b_2},\)\(g^r)=Z^{a_1rb_2}, (\beta ^*,\gamma )=(Z^{a_1rb_2},Z^mZ^{a_1r}),\) and output re-encrypted ciphertext \((\beta ^*,\gamma )\).

  • Re-decryption: Given the re-encrypted ciphertext \((\beta ^*,\gamma )\) and \(sk_\text {b}\), decrypt the re-encrypted ciphertext as \(\frac{\gamma }{{\beta ^*}^{1/b_2}}=\frac{ Z^mZ^{a_1r}}{ Z^{a_1r} }=Z^m.\) The EL scheme requires computing the discrete logarithm of \(Z^m\) in base Z to obtain the plaintext m. If the plaintext size is less than 40 bits, it is efficient to compute the discrete logarithm using Pollard’s kangaroo method [41]. The time complexity of Pollard’s kangaroo method is \(O(\sqrt{M})\), where M is the number of possible values of m.

4 Our construction

In this work, we adopt the EL scheme, which is a semantically secure proxy re-encryption scheme with additive homomorphism. CB and both users in the social network jointly generate the re-encryption keys for transforming the ciphertext from the user’s public key into the ciphertext under the CB’s public key. CA holds all re-encryption keys.

Fig. 3
figure 3

Protocol 2

Full size image

Let \(pk_\text {A}\) denote Alice’s homomorphic public key. Suppose that Alice’s vector is \(\mathbf {U} = <u_1, u_2,\cdots , u_n>\) and that Bob’s vector is \(\mathbf {V} = <v_1, v_2, \cdots , v_n>\). The dot product of the vectors \( \mathbf {U}\) and \(\mathbf {V}\) can be calculated by the following two formulas:

  • \(\mathbf {U} \circ \mathbf {V}=(u_1 \cdot v_1 +u_2 \cdot v_2+\cdots +u_n \cdot v_n)={\sum _{i=1}^{n}u_iv_i}\)

  • \(2 {\sum _{i=1}^{n}u_iv_i}=\sum _{i=1}^{n}u_i^2+\sum _{i=1}^{n}v_i^2-\sum _{i=1}^{n}(u_i-v_i)^2\)

Intuition Users encrypt their vector with their own public key and then outsource the encrypted data to CA. The procedure for the data outsourcing is presented in Fig. 2.

Alice encrypts her vector with her public key \(pk_\text {A}\) and sends the ciphertexts to CA for measuring the proximity to Bob. The EL cryptosystem supports additive homomorphism. However, it can only support additive homomorphism under the same public key. To use the additive homomorphism, CA computes re-encrypted ciphertexts with \(rk_{pk_\text {A} \rightarrow pk_\text {CB}}\) and \(rk_{pk_\text {B} \rightarrow pk_\text {CB}}\). Because EL is an additive homomorphism, the additivity over the two ciphertexts can be performed by CA independently as follows: \({E}_{pk_\text {CB}}(m_1){E}_{pk_\text {CB}}(m_2) = {E}_{pk_\text {CB}}(m_1+m_2 )\). Because \(2 {\sum _{i=1}^{n}u_iv_i}=\sum _{i=1}^{n}u_i^2+\sum _{i=1}^{n}v_i^2-\sum _{i=1}^{n}(u_i-v_i)^2\), we need to compute the product of ciphertexts \((u_i-v_i)\) by the two cloud servers. CA sends a blinded version of \({E}_{pk_\text {CB}}(u_i-v_i)\) to CB. Then, CB decrypts the ciphertexts, performs the multiplication and encrypts the result with \(pk_\text {CB}\). The encrypted result is sent to CA. CA computes \({E}_{pk_\text {CB}}(\mathbf {U} \circ \mathbf {V}) \) and sends the blinded ciphertext \({E}_{pk_\text {CB}}(w\mathbf {U} \circ \mathbf {V})\) to CB. CB decrypts the ciphertext and encrypts it with Alice’s public key. Then, CB sends \(E_{pk_\text {A}}(w\mathbf {U} \circ \mathbf {V})\) to CA. CA removes the blinding value w and sends the final result to Alice. The details of our scheme are given in Fig. 3.

The privacy of our scheme can be further enhanced by only letting Alice get a 1-bit matching result, i.e., a result of whether the dot product is above or below some threshold. We don’t present the details of the improved scheme here but instead include them in the full version of this paper.

5 Correctness and security

5.1 Correctness

In our scheme, CA possesses \(E_{pk_\text {A}}(u_i)\), \(E_{pk_\text {B}}(v_i)\), \(E_{pk_\text {A}}(\sum _{i=1}^{n}u_i^2)\), \(E_{pk_\text {B}}(\sum _{i=1}^{n}v_i^2)\), \(rk_{pk_\text {A} \rightarrow pk_\text {CB}}\), and \(rk_{pk_\text {B} \rightarrow pk_\text {CB}}\); CB possesses \(sk_\text {CB}\). Recall that CA computes re-encrypted ciphertexts with \(rk_{pk_\text {A} \rightarrow pk_\text {CB}}\) and \(rk_{pk_\text {B} \rightarrow pk_\text {CB}}\). Then, CA generates random integers \(\delta _i\), and using additive homomorphism and blinding with \(\delta _i\), CA obtains \(E_{pk_\text {CB}}(\delta _i(u_i-v_i))\). Then, CB decrypts \(E_{pk_\text {CB}}(\delta _i(u_i-v_i))\) and computes the products \((\delta _i(u_i-v_i))^2\). The products are later encrypted under \(pk_\text {CB}\) by CB. After that, CA removes the blinding value \(\delta _i^2\) by

$$\begin{aligned} E_{pk_\text {CB}}\left( \delta _i^2(u_i-v_i)^2\right) ^{\delta _i^{-2}} =E_{pk_\text {CB}}\left( (u_i-v_i)^2\right) , \end{aligned}$$

and computes

$$\begin{aligned}&E_{pk_\text {CB}}\left( (u_1-v_1)^2\right) \cdot E_{pk_\text {CB}}\left( (u_2-v_2)^2\right) \dots \cdot \\&\quad E_{pk_\text {CB}}\left( (u_n-v_n)^2\right) \\&\quad =E_{pk_\text {CB}}\left( \sum \nolimits _{i=1}^{n}\left( u_i-v_i\right) ^2\right) ,\\&\quad E_{pk_\text {CB}}\left( \sum \nolimits _{i=1}^{n}v_i^2\right) {\!\cdot } E_{pk_\text {CB}}\left( \sum \nolimits _{i=1}^{n}u_i^2\right) \left( E_{pk_\text {CB}}\left( \sum \nolimits _{i=1}^{n}(u_i-v_i)^2\right) \right) ^{-1}\\&\quad =E_{pk_\text {CB}}\left( \sum \nolimits _{i=1}^{n}v_i^2 +\sum \nolimits _{i=1}^{n}u_i^2-\sum \nolimits _{i=1}^{n}(u_i-v_i)^2\right) \\&\quad =E_{pk_\text {CB}}(2\mathbf {U}\circ \mathbf {V}), \end{aligned}$$

and

$$\begin{aligned} E_{pk_\text {CB}}(2\mathbf {U} \circ \mathbf {V})^{2^{-1}}=E_{pk_\text {CB}}(\mathbf {U} \circ \mathbf {V}). \end{aligned}$$

Then, CA obtains \(E_{pk_\text {CB}}(w\mathbf {U} \circ \mathbf {V})\) via blinding with w. CB decrypts the ciphertext and encrypts it with Alice’s public key. Finally, Alice removes the blinding value w and decrypts \(E_{pk_\text {A}}(\mathbf {U} \circ \mathbf {V})\) to yield the desired output \(\mathbf {U} \circ \mathbf {V}\).

5.2 Security

We now analyse the security of our scheme under the semi-honest model using a real and ideal paradigm [42]. For any adversary attacking a real protocol execution, there exists an adversary attacking an idea execution (with a trusted party) such that the input/output distributions of the adversary and the participating parties in the real and ideal executions are essentially the same.

Theorem 1

Our scheme described in Sect. 4 can securely obtain the matching result via computations on ciphertexts in the presence of semi-honest (non-colluding) adversaries.

Proof

Our scheme involves four types of parties: Alice, Bob, CA and CB. We construct four simulators \(Sim=(Sim_\text {A}, Sim_\text {B}, Sim_\text {CA}, Sim_\text {CB})\) against four types of adversaries \((\mathcal {A}_\text {A}, \mathcal {A}_\text {B}, \mathcal {A}_\text {CA}, \mathcal {A}_\text {CB})\) that corrupt Alice, Bob, CA, and CB, respectively.

\(Sim_\mathbf A \)simulates\(\mathcal {A}_\mathbf A \)as follows: After receiving the input of \(\mathbf {U} = <u_1,\)\(u_2,\cdots ,\)\(u_n>\), it encrypts data \(u_i\) as \( E_{pk_\text {A}}( u_i )\) and encrypts data \(\sum _{i=1}^{n}u_i^2\) as \( E_{pk_\text {A}}(\sum _{i=1}^{n}u_i^2)\). Then, it randomly chooses data \(\hat{\mathbf {V}} = <\hat{v}_1, \hat{v}_2,\cdots , \hat{v}_n>\), encrypts \(E_{pk_\text {A}}(\mathbf {U} \circ \hat{\mathbf {V}})\) and sends it to \(\mathcal {A}_\text {A}\). The view of \(\mathcal {A}_\text {A}\) includes the input {\(u_i\)}, where \(i \in [1,n]\), the encrypted data {\( E_{pk_\text {A}}( u_i ), E_{pk_\text {A}}(\sum _{i=1}^{n}u_i^2)), E_{pk_\text {A}}(\mathbf {U} \circ \hat{\mathbf {V}})\)} and the decrypted result {\(\mathbf {U} \circ \hat{\mathbf {V}}\)}. The views of \(\mathcal {A}_\text {A}\) in the real and ideal executions are indistinguishable because of the security of the EL scheme mentioned above.

\(Sim_\mathbf B \)simulates\(\mathcal {A}_\mathbf B \)as follows: After receiving the input of \(\mathbf {V} = <v_1,\)\( v_2,\cdots ,\)\( v_n>\), it encrypts data \(v_i\) as \( E_{pk_\text {B}}( v_i ) \) and encrypts data \(\sum _{i=1}^{n}v_i^2\) as \(E_{pk_\text {B}}(\sum _{i=1}^{n}v_i^2)\). Finally, it returns \( E_{pk_\text {B}}( v_i )\) and \( E_{pk_\text {B}}(\sum _{i=1}^{n}v_i^2)\) to \(\mathcal {A}_\text {B}\) and outputs \(\mathcal {A}_\text {B}\)’s entire view. The view of \(\mathcal {A}_\text {B}\) includes input {\(v_i\)}, where \(i \in [1,n]\), and the encrypted data {\(E_{pk_\text {B}}( v_i ), E_{pk_\text {B}}(\sum _{i=1}^{n}v_i^2)\)}. The views of \(\mathcal {A}_\text {B}\) in the real and ideal executions are indistinguishable because of the security of the EL scheme mentioned above.

\(Sim_\mathbf CA \)simulates\(\mathcal {A}_\mathbf CA \)as follows: It randomly chooses numbers \(\hat{\mathbf {U}} = <\hat{u}_1, \hat{u}_2,\cdots , \hat{u}_n>\), \(\hat{\mathbf {V}} = <\hat{v}_1, \hat{v}_2,\cdots , \hat{v}_n>\) and encrypts them as \(E_{pk_\text {A}}(\hat{u}_i )\), \( E_{pk_\text {B}}(\hat{v}_i ) \), \(E_{pk_\text {A}}(\sum _{i=1}^{n} \hat{u}_i^2)\), and \(E_{pk_\text {B}}(\sum _{i=1}^{n} \hat{v}_i^2)\). It re-encrypts them as \( E_{pk_\text {CB}}(\hat{u}_i )\), \( E_{pk_\text {CB}}(\hat{v}_i)\), \(E_{pk_\text {CB}}(\sum _{i=1}^{n}\hat{u}_i^2)\), and \(E_{pk_\text {CB}}(\sum _{i=1}^{n}\hat{v}_i^2)\). Then, it generates random integers \(\hat{\delta }_i\) and \(\hat{w}\) and computes \(E_{pk_\text {CB}}(\hat{\delta }_i^2(u_i-v_i)^2)^{\delta _i^{-2}}\), \(E_{pk_\text {CB}}(\hat{w}\hat{\mathbf {U}}\ \circ \hat{\mathbf {V}})\) and \(E_{pk_\text {A}}(\hat{\mathbf {U}}\ \circ \hat{\mathbf {V}})\). The view of \(\mathcal {A}_\text {CA}\) is the encrypted data. The views of \(\mathcal {A}_\text {CA}\) in the real and ideal executions are indistinguishable because of the security of the EL scheme mentioned above.

\(Sim_\mathbf CB \)simulates\(\mathcal {A}_\mathbf CB \)as follows: It randomly chooses numbers \(\hat{m}_i\) and encrypts them as \(E_{pk_\text {CB}}(\hat{m}_i)\). Then, it computes \(\hat{m}_i \cdot \hat{m}_i\) and encrypts \(\hat{m}_i \cdot \hat{m}_i\) with CB’s public key. Then, it randomly chooses a number \(\hat{s}\), encrypts it as \(E_{pk_\text {CB}}(\hat{s})\) and encrypts \(\hat{s}\) with Alice’s public key. Finally, it returns {\(E_{pk_\text {CB}}(\hat{m}_1)\), \( E_{pk_\text {CB}}(\hat{m}_2)\), \(\dots \), \( E_{pk_\text {CB}}(\hat{m}_n)\), \(\hat{m}_1,\hat{m}_2,\dots ,\hat{m}_n\), \(E_{pk_\text {CB}}(\hat{m}_1^2)\), \(E_{pk_\text {CB}}(\hat{m}_2^2)\), \(\dots \), \(E_{pk_\text {CB}}(\hat{m}_n^2)\), \(E_{pk_\text {CB}}(\hat{s})\), \( E_{pk_\text {A}}(\hat{s}) \)} to \(\mathcal {A}_\text {CB}\). \(\mathcal {A}_\text {CB}\) is able to decrypt the ciphertexts with its private key, but the decrypted messages are all blinded. Because of the random numbers, the decrypted messages are randomly distributed. The view of \(\mathcal {A}_\text {CB}\) is also the encrypted data and blinded data. Security in the real world can be guaranteed by the security of the EL scheme. The views of \(\mathcal {A}_\text {CB}\) in the real and ideal executions are indistinguishable.

For the case of a user colluding with CA or CB, the security can be proven in a similar manner. \(\square \)

6 Comparison

Table 1 Comparison of our scheme with some known privacy-preserving profile-matching schemes
Full size table
Table 2 The comparison of interaction quantities
Full size table

We compare our new scheme with some known privacy-preserving profile-matching schemes in Table 1. In [3, 5, 43], multiple rounds of interactions between users are required to perform the profile matching, which causes high communication and computation cost for users. Our scheme does not require users to be online at the same time. Users only need to encrypt their personal profiles and send them to one cloud server and receive matching results. The two cloud servers perform most of the computations in our scheme, effectively reducing the user’s computational burden and ensuring that the user’s private information is not leaked to the clouds.

The comparison of interaction quantities among some known privacy- preserving schemes for dot product calculation is shown in Table 2. [35, 44, 45] were constructed to achieve secure dot product computation. [32] was constructed to achieve secure addition and multiplication under multi-key. Because schemes [44, 45] do not use multiple servers, there is no interaction between servers. Goethals et al. [46] showed that two of the private scalar product protocols, one of which [45] adopting the matrix multiplication operation was proved to be insecure. The approach of [31] differs from [32] in the sense that [31] randomly separates the strong trapdoor into two shares, and distributes the shares to two different servers. Only when both servers work together can the ciphertext be successfully decrypted. This decreases the risk of privacy leakage caused by single point attack. Current solutions for privacy-preserving profile matching either have heavy interactions or require users to encrypt private data under one key. In our scheme, the computation is non-interactive to users, and the scheme is secure under the honest-but-curious model, assuming that the two cloud servers do not collude. Furthermore, our scheme is collusion resistant, i.e., collusion between a user and a cloud server will not reveal any privacy information.

7 Conclusion

In this paper, we propose a novel cloud-assisted privacy-preserving profile-matching scheme under multiple keys based on a proxy re-encryption scheme with additive homomorphism. Current solutions either have heavy interactions or require users to encrypt private data under one key. In our scheme, the computation is non-interactive to users. Users only need to encrypt their personal profiles and send them to one cloud server and receive matching results. In addition, the two cloud servers perform most of the computations, effectively reducing the user’s computational burden and ensuring that the user’s private information is not leaked to the clouds. Furthermore, our scheme is proven secure under the honest-but-curious model, assuming that the two cloud servers do not collude. Even if participating parties collude with one of the cloud servers, our scheme will still not reveal any user’s private information.