Privacy Preserving Inner Product of Vectors in Cloud Computing

Abstract

The problem of privacy preserving inner product of vectors has been widely studied. Much work has been done on the scenario of two parties involved in the computation. In this paper, we consider the scenario where three parties are involved in the computing process of cloud computing. We propose a new privacy preserving scheme for inner product of two vectors in the cloud and give the correctness analysis and performance analysis for the scheme. The proposed scheme is based on homomorphic encryption, and the security can be guaranteed. Experiments show the efficiency of the scheme.

1. Introduction

The computation of inner product of vectors is a fundamental mathematical operation. The inner product of vectors has found wide application in the research field of computer science, such as cooperative statistical analysis [1], data mining [2], and similarity computation [3]. The model depicted in Figure 1 is adopted in much work, where two parties, that is, the server and the client, are involved. The server owns a large amount of data, and the client may issue query to the server. In Model 1, the problem of data privacy preservation is one of the most important security issues. The problem of privacy preserving inner product of vectors has gained thorough research, and much work has been done on it, such as [1–7].

Figure 1

Model 1.

When the server possesses particularly large amounts of data or the amount of query from the clients is considerably abundant, the server may be overburdened. Now, the cloud computing has gained wide research and many applications have been deployed in the cloud. Three parties are generally involved in the cloud computing model [8]. The existing work on privacy preserving inner product of vectors between two parties cannot work well any longer.

A secure privacy preserving scheme was presented for inner product of vectors in cloud computing in [9]. The scheme is effective and achieves the goal of data privacy preservation. However, it is the array that acts as the shared secret key between the data owner and the client. The array may be large when the vector has big size of dimensionality. It is inconvenient for the data owner to update the secret key when there are many clients.

We propose a new scheme on the basis of homomorphic encryption, which aims at the problem of privacy preserving inner product of vectors in cloud computing. Our proposed scheme can work seamlessly with the other secure scheme of inner product of vectors, such as correctness verification of inner product of vectors [10].

The rest of this paper is organized as follows. Section 2 describes the background knowledge, including the inner product of vectors, homomorphic encryption, and the system model and threat model. Section 3 summarizes the existing works on privacy preserving inner product of vectors. Section 4 introduces our proposed scheme for privacy preserving inner product of vectors in the cloud. Following that, experimental results are given in Section 5. Finally, Section 6 concludes the paper.

2. Background

2.1. Inner Product of Vectors

Let $u=(u_1,u_2,\dots ,u_n)$ and $v=(v_1,v_2,\dots ,v_n)$ be two vectors, where n is a positive integer and denotes the dimensionality of the vectors, and $u_i$ and $v_i\hspace{0.17em}\hspace{0.17em}(1\le i\le n)$ are vector elements. The inner product of u and v is the sum of the products of the corresponding elements; that is, $u·v=u_1{v}_1+u_2{v}_2+\cdots +u_n{v}_n={\sum }_{i=1}^n‍u_i{v}_i$ , where the symbol “·” denotes the mathematical operation of computing the inner product between two vectors.

2.2. Homomorphic Encryption

Let $(\text{pk},\text{sk})$ be a key pair for a public key encryption scheme, where $\text{pk}$ is the public key for encrypting data and $\text{sk}$ is the secret key for decrypting. An encryption scheme is called homomorphic if it holds the following two properties simultaneously:

$$\begin{array}{cc}& \mathrm{\hspace{0.17em}\hspace{0.17em}}{E}_{\text{pk}}\left(x_1\right)\oplus E_{\text{pk}}\left(x_2\right)=E_{\text{pk}}\left(x_1+x_2\right),\\ {\left(E_{\text{pk}}\right(x\left)\right)}^c=E_{\text{pk}}\left(cx\right),\end{array}$$

(1)

where $x_1,x_2$ ,  and x are plain data, $E_{\text{pk}}(x_1),E_{\text{pk}}(x_2)$ , and $E_{\text{pk}}(x)$ are the ciphertext of $x_1,x_2$ ,  and  x with $\text{pk}$ as the encryption key, respectively, and ⊕ is an operation on the ciphertext and c is a positive integer.

For convenience, we introduce a symbol $\text{Sum}$ , which denotes the result of operation ⊕ on multiple homomorphic ciphertexts. $\text{Sum}$ is defined as

$$\begin{array}{cc}& \text{Su}{\text{m}}_{i=1}^n{x}_i=E_{\text{pk}}\left(x_1\right)\oplus E_{\text{pk}}\left(x_2\right)\oplus \cdots \oplus E_{\text{pk}}\left(x_n\right).\end{array}$$

(2)

The Paillier's homomorphic encryption is adopted in the following [11].

2.3. System and Threat Models

A simplified architecture of cloud computing is given in Figure 2. Three parties are involved in Model 2, that is, the data owner, the service provider, and the client. The data owner holds large quantities of data. The data owner outsources the heavy data management task to the service provider to reduce the total cost. The service provider is a specific cloud service provider, which possesses rich resources, including hardware, software, and network. The service provider provides the users with the services of storage, computation, and so forth. The authorized client may issue a request to the service provider. Here, the user may be a company, an organization, or an individual, who makes use of the cloud service. The data owner and the client are both users. The client is a specific user, which refers to the party that can only issue query to the service provider.

Figure 2

Model 2.

In the above model, the data owner, who is the owner of the data stored on the service provider side, is honest. The service provider and the client are both semihonest. The service provider attempts to obtain the original data of the data owner and the client. The client attempts to get the original data of the data owner. Suppose that the data are transferred between the three parties through secure channel.

3. Related Works

A privacy preserving scheme of inner product of vectors was proposed for privacy preserving data mining between two parties in [2], in which the matrix multiplication operation was adopted. The privacy of the input data and the obtained result was preserved simultaneously. A state-of-the-art overview of the privacy preserving inner product of vectors problem and the properties of some solutions were given in [4], where the scheme proposed in [2] was analyzed and proved to be not secure, and a new scheme was presented based on the homomorphic encryption, which has strong security guarantee.

For the purpose of detecting similar documents as well as preserving data privacy between two parties, two privacy preserving schemes for inner product of vectors, that is, the random array scheme and the homomorphic encryption scheme, were utilized in [3]. Privacy preserving inner product of vectors was applied to determine the relative position of two spatial geometric objects in [12].

An efficient and secure inner product protocol in the presence of malicious adversaries was presented in [6]. The protocol was based on the proof of knowledge of a discrete logarithm and the verifiable encryption.

Secure two-party inner product of vectors was extended to the quantum field in [7]. The given protocol was built upon quantum entanglement and quantum measurement.

The problem of correctness verification of inner product of vectors was studied in the cloud computing scenario in [9], in which the array multiplication operation was adopted to preserve the data privacy.

4. The Proposed Scheme

Suppose the data owner holds a vector $v=(v_1,v_2,\dots ,v_n)$ and the request vector of the client is $u=(u_1,u_2,\dots ,u_n)$ , where n is a positive integer and denotes the dimensionality of the vectors. Our proposed privacy preserving scheme for inner product of vectors in the cloud consists of five algorithms, that is, KeyGen, Encrypt, Request, Compute, and GetResult.

4.1. Overview

In our scheme, three parties are involved in the computation. Data privacy of each party needs to be preserved. The privacy preserving scheme for inner product of vectors in the cloud scenario works as follows.

• (1)

KeyGen. First of all, the data owner and the client generate the necessary keys, respectively, and share the keys with the related party.

(2)

Encrypt. The data owner encrypts the original vector to obtain the ciphertext and sends it to the service provider. The service provider receives the data from the data owner and monitors the query request from the client.

(3)

Request. The client encrypts the original request vector to get the transformed vector and sends it to the service provider.

(4)

Compute. The service provider performs computing on the ciphertext from the data owner and the client and obtains the intermediate results and sends them back to the client.

(5)

GetResult. The client computes the returned results to get the final result.

4.2. Details

In this section, we describe the design details of each algorithm.

( 1) KeyGen. Whatever encryption scheme or data processing algorithm is chosen, the key(s) is (are) necessary. The keys are generated on the data owner side and client side, respectively, which are given as follows.

• (1)

The data owner randomly generates a key pair $(\text{pk},\text{sk})$ for homomorphic encryption scheme, where $\text{pk}$ is the public key and $\text{sk}$ is the secret key. $\text{pk}$ is published publicly and $\text{sk}$ is shared with the client through secure channel.

(2)

The client randomly generates an $n\times n/2$ array A and shares it with the service provider through secure channel, where

$$\begin{array}{cc}& A=\left(\begin{array}{cccc}{a}_{\mathrm{1,1}}& a_{\mathrm{1,2}}& \cdots & a_{1,n/2}\\ ⋮& ⋮& & ⋮\\ a_{n,1}& a_{n,2}& \cdots & a_{n,n/2}\end{array}\right).\end{array}$$

(3)

( 2) Encrypt. Aiming at privacy preservation of the data, the data owner encrypts each element $v_i\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1,2}\dots ,n)$ of vector v in turn using the homomorphic encryption scheme with public key $\text{pk}$ . The obtained ciphertext of v is denoted as $E_{\text{pk}}(v)$ , where $E_{\text{pk}}(v)=(E_{\text{pk}}(v_1),E_{\text{pk}}(v_2),\dots ,E_{\text{pk}}(v_n))$ . Then $E_{\text{pk}}(v)$ is sent to the service provider.

( 3) Request. Before issuing the request to the service provider, it is necessary for the client to transform the request data to preserve privacy. The data transformation on the client side works as follows.

• (1)

The client randomly generates a vector r with dimensionality of $n/2$ , where $r=(r_1,r_2,\dots ,r_{n/2})$ ;

(2)

compute z, where

$$\begin{array}{cc}& z=u+r{A}^T,\end{array}$$

(4)

and send it to the service provider, where $A^T$ denotes the transpose of array A.

Let z be denoted as $z=(z_1,z_2,\dots ,z_n)$ . Then, we have

$$\begin{array}{cc}& z_i=u_i+{\displaystyle \sum }_{j=1}^{n/2}‍r_j{a}_{i,j},\hspace{1em}i=\mathrm{1,2},\dots ,n.\end{array}$$

(5)

It is vector z that is sent to the service provider, which cannot reveal the value of u. Though the service provider holds A and z, it cannot detect u and r via solving the system of linear equations. Thus, the data privacy of the client is preserved through mathematical transformation.

( 4) Compute. Upon receiving the request z from the client, the service provider starts to compute S and y. S is an intermediate result and contains the final result, where

$$\begin{array}{l}S={\left(E_{\text{pk}}\left(v_1\right)\right)}^{z_1}\oplus {\left(E_{\text{pk}}\left(v_2\right)\right)}^{z_2}\oplus \cdots \oplus {\left(E_{\text{pk}}\left(v_n\right)\right)}^{z_n}\hfill \\ =\text{Su}{\text{m}}_{i=1}^n{\left(E_{\text{pk}}\left(v_i\right)\right)}^{z_i}.\hfill \end{array}$$

(6)

y is a vector with dimensionality of $n/2$ , which is used to compute the final result on the client side. Let $y=(y_1,y_2,\dots ,y_{n/2})$ , where, for $i=\mathrm{1,2},\dots ,n/2$ ,

$$\begin{array}{l}{y}_i={\left(E_{\text{pk}}\left(v_1\right)\right)}^{a_{1,i}}\oplus {\left(E_{\text{pk}}\left(v_2\right)\right)}^{a_{2,i}}\oplus \cdots \oplus {\left(E_{\text{pk}}\left(v_n\right)\right)}^{a_{n,i}}\hfill \\ =\text{Su}{\text{m}}_{j=1}^n{\left(E_{\text{pk}}\left(v_j\right)\right)}^{a_{j,i}}.\hfill \end{array}$$

(7)

Then, the service provider responds to the client with S and y.

( 5) GetResult. Based on the returned results S and y from the service provider, the client first computes

$$\begin{array}{cc}& S^{\prime }=y_1^{r_1}\oplus y_2^{r_2}\oplus \cdots \oplus y_{n/2}^{r_{n/2}}=\text{Su}{\text{m}}_{i=1}^{n/2}{\left(y_i\right)}^{r_i}.\end{array}$$

(8)

Then, the client computes

$$\begin{array}{cc}& D_{\text{pr}}\left(S\right)-D_{\text{pr}}\left(S^{\prime }\right),\end{array}$$

(9)

which is just the inner product of u and v, where $D_{\text{pr}}(S)$ denotes decrypting S with secret key $\text{sk}$ .

Thus, the final result is obtained; that is,

$$\begin{array}{cc}& u·v=D_{\text{pr}}\left(S\right)-D_{\text{pr}}\left(S^{\prime }\right).\end{array}$$

(10)

4.3. Correctness Analysis

In this section, we illustrate the correctness of our proposed scheme.

In the algorithm Compute, the service provider obtains S as the intermediate result. By (1) and (6), we have

$$\begin{array}{l}\mathrm{\hspace{0.17em}\hspace{0.17em}}S=\text{Su}{\text{m}}_{i=1}^n{\left(E_{\text{pk}}\left(v_i\right)\right)}^{z_i}=\text{Su}{\text{m}}_{i=1}^n{E}_{\text{pk}}\left(v_i{z}_i\right)\hfill \\ =E_{\text{pk}}\left({\displaystyle \sum }_{i=1}^n‍v_i{z}_i\right).\hfill \end{array}$$

(11)

By (5) and (11), we have

$$\begin{array}{l}S=E_{\text{pk}}\left({\displaystyle \sum }_{i=1}^n‍v_i{z}_i\right)\hfill \\ =E_{\text{pk}}\left({\displaystyle \sum }_{i=1}^n‍v_i\left(u_i+{\displaystyle \sum }_{j=1}^{n/2}‍r_j{a}_{i,j}\right)\right)\hfill \\ =E_{\text{pk}}\left({\displaystyle \sum }_{i=1}^n‍\left(v_i{u}_i+v_i{\displaystyle \sum }_{j=1}^{n/2}‍r_j{a}_{i,j}\right)\right)\hfill \\ =E_{\text{pk}}\left({\displaystyle \sum }_{i=1}^n‍\left(v_i{u}_i+{\displaystyle \sum }_{j=1}^{n/2}‍v_i{r}_j{a}_{i,j}\right)\right)\hfill \\ =E_{\text{pk}}\left({\displaystyle \sum }_{i=1}^n‍v_i{u}_i+{\displaystyle \sum }_{i=1}^n\hspace{0.17em}{\displaystyle \sum }_{j=1}^{n/2}‍v_i{r}_j{a}_{i,j}\right).\hfill \end{array}$$

(12)

Along with S, the service provider obtains a vector $y=(y_1,y_2,\dots ,y_{n/2})$ in the algorithm Compute. By (1) and (7), for $i=\mathrm{1,2},\dots ,n/2$ , we have

$$\begin{array}{cc}& y_i=\text{Su}{\text{m}}_{j=1}^n{\left(E_{\text{pk}}\left(v_j\right)\right)}^{a_{j,i}}=E_{\text{pk}}\left({\displaystyle \sum }_{j=1}^n‍v_j{a}_{j,i}\right).\end{array}$$

(13)

In the algorithm GetResult, the client computes and gets $S^{\prime }=\text{Su}{\text{m}}_{i=1}^{n/2}{(y_i)}^{r_i}$ . Then, by (13), we have

$$\begin{array}{l}{S}^{\prime }=\text{Su}{\text{m}}_{i=1}^{n/2}{\left(y_i\right)}^{r_i}\hfill \\ =\text{Su}{\text{m}}_{i=1}^{n/2}{\left(E_{\text{pk}}\left({\displaystyle \sum }_{j=1}^n‍v_j{a}_{j,i}\right)\right)}^{r_i}\hfill \\ =\text{Su}{\text{m}}_{i=1}^{n/2}\left(E_{\text{pk}}\left(r_i{\displaystyle \sum }_{j=1}^n‍v_j{a}_{j,i}\right)\right)\hfill \\ =\text{Su}{\text{m}}_{i=1}^{n/2}\left(E_{\text{pk}}\left({\displaystyle \sum }_{j=1}^n‍r_i{v}_j{a}_{j,i}\right)\right)\hfill \\ =E_{\text{pk}}\left({\displaystyle \sum }_{i=1}^{n/2}\hspace{0.17em}{\displaystyle \sum }_{j=1}^n‍r_i{v}_j{a}_{j,i}\right).\hfill \end{array}$$

(14)

Thus, in the algorithm GetResult, when the client computes $D_{\text{pr}}(S)-D_{\text{pr}}(S^{\prime })$ , by (12) and (14), we have

$$\begin{array}{l}{D}_{\text{pr}}\left(S\right)-D_{\text{pr}}\left(S^{\prime }\right)\hfill \\ \hspace{1em}={\displaystyle \sum }_{i=1}^n‍v_i{u}_i+{\displaystyle \sum }_{i=1}^n\hspace{0.17em}{\displaystyle \sum }_{j=1}^{n/2}‍v_i{r}_j{a}_{ij}-{\displaystyle \sum }_{i=1}^{n/2}\hspace{0.17em}{\displaystyle \sum }_{j=1}^n‍r_i{v}_j{a}_{j,i}\hfill \\ \hspace{1em}={\displaystyle \sum }_{i=1}^n‍v_i{u}_i=u·v.\hfill \end{array}$$

(15)

In the end, the client obtains the deserved result $u·v$ , which is the inner product of u and v.

4.4. Performance Analysis

In this section, we give the performance analysis of each algorithm.

• (1)

In the algorithm Encrypt, each vector element $v_i\hspace{0.17em}\hspace{0.17em}(1\le i\le n)$ is encrypted in turn on the data owner side. The time complexity of algorithm Encrypt is $O(n)$ .

(2)

In the algorithm Request, the original user request vector u is transformed into z on the client side, where matrix multiplication is used. The time complexity of algorithm Request is $O(n^2)$ .

(3)

In the algorithm Compute, S and y are obtained on the service provider side, where $S=\text{Su}{\text{m}}_{i=1}^n{(E_{\text{pk}}(v_i))}^{z_i}$ , and $y=(y_1,y_2,\dots ,y_{n/2})$ with $y_i=\text{Su}{\text{m}}_{j=1}^n{(E_{\text{pk}}(v_j))}^{a_{j,i}}$ . The time complexity of algorithm Compute is $O(n^2)$ .

(4)

In the algorithm GetResult, $S^{\prime }$ is obtained by y and r, where $S^{\prime }=\text{Su}{\text{m}}_{i=1}^{n/2}{(y_i)}^{r_i}$ . The time complexity of algorithm GetResult is $O(n)$ .

It is worth mentioning especially that magnitude of the time complexity of algorithm Request and that of Compute are different. Homomorphic encryption is performed on exponents in the algorithm Encrypt, and multiplication and addition are performed on integers in the algorithm Request. The actual time cost is quite different, though the time complexity of both Request and Compute is $O(n^2)$ .

4.5. Security Analysis

In this subsection, we give the security analysis, which is presented from three aspects, that is, data privacy preservation of the data owner, the client, and the result.

Data Privacy of the Data Owner. Because the data on the data owner side are encrypted by homomorphic encryption scheme, the service provider can detect nothing about the original data. Then, the data privacy of the data owner is preserved with security guarantee.

Data Privacy of the Client. The query issued by the client is transformed via matrix operation, and the service provider gets $z=u+r{A}^T$ . The service provider holds z and A, and it may attempt to detect u by solving the following system of linear equations:

$$\begin{array}{l}{z}_1=u_1+r_1{a}_{\mathrm{1,1}}+r_2{a}_{\mathrm{1,2}}+\cdots +r_{n/2}{a}_{1,n/2}\hfill \\ z_2=u_2+r_1{a}_{\mathrm{2,1}}+r_2{a}_{\mathrm{2,2}}+\cdots +r_{n/2}{a}_{2,n/2}\hfill \\ \cdots \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\cdots \hspace{1em}\hspace{1em}\hspace{1em}\cdots \hspace{1em}\hspace{1em}\hspace{1em}\cdots \hfill \\ z_n=u_n+r_1{a}_{n,1}+r_2{a}_{n,2}+\cdots +r_{n/2}{a}_{n,n/2}.\hfill \end{array}$$

(16)

In (16), there are n equations and $n+n/2$ unknown variables, and it is impossible for the service provider to solve the system of linear equations to get the value of u. Thus, the data privacy of the client is preserved.

Data Privacy of the Result. In our proposed scheme, the result of inner product of vectors is not given directly. The result is given by the intermediates S and y, which are both encrypted by homomorphic encryption scheme. The security of S and y can be guaranteed by the homomorphic encryption scheme. Thus, the data privacy of the result is preserved.

5. Experiments

We now evaluate the performance overhead of our proposed scheme for privacy preserving inner product of vectors in cloud computing. We use a Pentium Dual E2200 2.20 GHz PC with 1.99 GB RAM. Code is developed in C using the MIRACL library. Synthetic 5-dimensional data are used, which are integers generated randomly within $[1,10000000]$ with even distribution. Four algorithms of Encrypt, Request, Compute, and GetResult are implemented respectively, whose running results on the given data are shown in Figure 3.

Figure 3

Experiment results.

As can be seen in Figure 3, the performance overhead of each algorithm is consistent with the performance analysis in Section 4.4. Homomorphic encryption is utilized in the algorithms of Encrypt, Compute, and GetResult, where the operation is performed on exponents. The actual time cost of the algorithm Compute is the highest, and that of the algorithm Encrypt is the second among the four algorithms, which is shown in Figure 3(a).

In Section 4.4, we have mentioned that the actual time cost of algorithm Request and Compute is quite different, though the time complexity of the two algorithms is $O(n^2)$ . Figure 3(a) demonstrates that is true. The actual time cost of the algorithm Compute is far higher than that of the algorithm Request.

The actual time cost of the algorithms Request and GetResult is so small compared with the algorithms Encrypt and Compute that they cannot be distinguished from each other clearly. The performance of the algorithms Request and GetResult is shown again in Figure 3(b), where it demonstrates that the time cost of the algorithm Request is higher.

6. Conclusion

Aiming at the problem of privacy preservation of inner product of vectors in cloud computing, a new scheme is presented with the homomorphic encryption as the fundamentals. The scheme is applicable for the cloud scenario where three parties are involved in the computation.

In future work, we plan to consider the case where the service provider of the cloud is malicious. Another interesting direction is access control of the client when there are multiple clients with different access permissions.