# Privacy-Preservingk-Means Clustering under Multiowner Setting in Distributed Cloud Environments

Authors: Hong Rong; Huimei Wang; Jian Liu; Jialu Hao; Ming Xian
Journal: Security and Communication Networks
 (2017)

---

## Abstract

With the advent of big data era, clients who lack computational and storage resources tend to outsource data mining tasks to cloud service providers in order to improve efficiency and reduce costs. It is also increasingly common for clients to perform collaborative mining to maximize profits. However, due to the rise of privacy leakage issues, the data contributed by clients should be encrypted using their own keys. This paper focuses on privacy-preservingk-means clustering over the joint datasets encrypted under multiple keys. Unfortunately, existing outsourcing k-means protocols are impractical because not only are they restricted to a single key setting, but also they are inefficient and nonscalable for distributed cloud computing. To address these issues, we propose a set of privacy-preserving building blocks and outsourced k-means clustering protocol under Spark framework. Theoretical analysis shows that our scheme protects the confidentiality of the joint database and mining results, as well as access patterns under the standard semihonest model with relatively small computational overhead. Experimental evaluations on real datasets also demonstrate its efficiency improvements compared with existing approaches.


---

## Body

## 1. Introduction

With tremendous amount of data collected each day, it is increasingly difficult for resource-constrained clients to perform computationally intensive tasks locally. There are numerous cases regarding this, such as mobile phones or sensors in the IoT system with limited battery and small companies that lack hardware and software infrastructures. Thus, it is a viable option to outsource data mining tasks to Cloud Service Provider (CSP) which provides massive storage and computation power in a cost-efficient way [1]. By leveraging the cloud platforms, a great many giant IT companies have offered machine learning services to help clients to train and deploy their own models, for example, Amazon Machine Learning [2], Google Cloud Machine Learning Engine [3], and IBM Watson [4]. Despite the advantages, privacy issues are the critical concerns for cloud users to employ these services. For many data records may contain sensitive information, such as health condition, financial records, and location information, outsourcing them in plain form inevitably reveals personal privacy to CSP which may be untrustworthy or even malicious. For instance, it is favorable to improve the diagnosis accuracy by utilizing data mining techniques over medical records gathered from multiple patients [5], while releasing such information to public directly is prohibited by laws in many countries, for example, HIPAA [6]. Thereby, appropriate mechanisms should be designed to guarantee that the outsourced mining tasks are executed in a privacy-preserving manner.In this paper, we focus on privacy protection techniques on outsourcedk-means clustering, which is a widely used data mining algorithm in the fields of image analysis, information retrieval, pattern recognition, and so on. The outsourcing datasets are contributed by multiple data owners who are willing to collaborate in outsourced clustering in order to obtain more accurate results. Normally, the data records are encrypted via cryptographic tools to prevent them from being disclosed to other parties. The goal of our solution is to let cloud servers perform clustering over the encrypted data.Traditional privacy-preserving clustering schemes cannot be directly adopted to address the privacy issues for outsourcing. They aim at computing clusters through interactions among different data holders without revealing respective data to others [7–9], whereas, in our case, the data are stored and processed by the cloud rather than clients themselves.Most existing works on outsourced privacy-preserving clustering require cloud clients to utilize the same key for data encryption [10–15]. In practice, sharing the same encryption key has some disadvantages: (1) for symmetric encryption scheme, compromised data owners can easily decrypt other owners’ encrypted data if they launch eavesdropping attacks, which suites the case in [10–14]; (2) for asymmetric encryption, if the datasets are encrypted under cloud’s public key, data owners cannot decrypt their uploaded data due to not knowing the private key [15]. One way to solve this is allowing data owners to encrypt their data by their own keys, but this calls for computation over encrypted data under multiple keys (denoted by multikey). The only work [16] concerning multikey clustering was constructed on the multiplicative transformation method proposed in [17], whereas their proposed solutions expose all owners’ keys to the query user, which causes security risks if the user is compromised.Another issue of current research is that their threat models do not suffice higher level attacks. The essence of underlying schemes in [10, 14, 16] is to apply random matrix to encrypt data. These are secure against known-sample attack [17] (namely, attacker only knows some instances). But if attacker also knows the corresponding encrypted values of some data (i.e., chosen plaintext attack), the remaining instances may be recovered by setting up enough equations. In addition, the fully homomorphic encryption (FHE) used in [12, 13] is not secure according to [18]. Furthermore, access patterns (assignment of data objects, etc.) are disclosed to cloud servers [14, 16]. They may be used to derive sensitive information regardless of data encryption, as indicated by [19, 20]. Last but not least, few works consider combining their privacy-preserving techniques with large-scale data processing frameworks for boosting efficiency.To address these challenges, we propose a novel solution for Privacy-Preservingk-means Clustering Outsourcing under Multikeys (PPCOM), which enables distributed cloud servers to perform clustering collaboratively over the aggregated datasets with no privacy leakage. Specifically, the major contributions of this paper are fourfold:(i)
Firstly, our solution allows the cloud to perform arithmetic computations over encrypted data under multiple keys. It is achieved by transforming ciphertexts under different keys into ones under the unified key through the double decryption cryptosystem. Since the encryption scheme is only partially homomorphic, we propose a secure addition subprotocol under the noncolluding two-server model, which does not reveal anything about input or output, including the input ratio. Based on these, the cloud can compute Euclidean distances between records and cluster centers.(ii)
Secondly, we propose two secure primitives to evaluate equality test and compare ciphertexts, addressing the problem that encrypted data are incomparable because of probabilistically random distribution. These two are further utilized in other privacy-preserving building blocks, including minimum Euclidean distance computing and encrypted bitmap converting, as well as cluster center updating.(iii)
Thirdly, on the basis of those privacy-preserving building blocks, we design PPCOM protocol by integrating Spark framework to accelerate the outsourcing process, which works in distributed cloud environments. Moreover, PPCOM requires no clients’ participation after they upload their encrypted datasets under their own private keys.(iv)
Fourthly, theoretical analysis demonstrates that the proposed protocol not only protects the privacy of aggregated data records and clustering centers, but also hides access patterns under the semihonest model. Experimental results on real dataset shows that PPCOM is much more efficient than existing methods in terms of computational overhead.The rest of the paper is organized as follows. Section2 reviews the related works. In Section 3, we describe the preliminaries required in the understanding of our proposed PPCOM. In Section 4, we formalize the system model, threat model, and design objectives. The design details of the proposed privacy-preserving building blocks as well as outsourcing protocol are presented in Section 5. We provide security analysis in Section 6. Section 7 shows the theoretical and experimental evaluation results. Finally, we conclude the paper and outline future work in Section 8.


## 2. Related Work

There have been a lot of works on privacy-preserving distributedk-means clustering [7–9]. These works have different security requirements and design goals compared with our work. In the distributed setting where data are partitioned among multiple parties, the clustering task is undertaken by data holders instead of centralized servers. Generally, their schemes exploit secure multiparty computation (SMC) techniques so as to preclude one’s data from being disclosed to the others except the final results. Whereas, in terms of clustering outsourcing, data owners intend to transfer the major workloads to cloud servers for the sake of reducing costs and improving efficiency. During the entire outsourcing process, all the inputs and outputs, as well as intermediate results, are supposed to be encrypted to ensure confidentiality.As for outsourcedk-means clustering, Liu et al. [12] first leveraged FHE technique to perform outsourced clustering. To compare encrypted distances, their approach requires data owner to provide trapdoor information during each iteration, which entails heavy overhead on clients. To reduce the amount of data owner participation, Almutairi et al. [13] presented an efficient mechanism by using the concept of an Updatable Distance Matrix (UDM). Nevertheless, both works reveal partial privacy to cloud servers, such as the size of each cluster and the distance between data object and centroid. Moreover, the encryption scheme adopted in [12, 13] is not secure according to [18].Another line of research for outsourced clustering is to use distance-preserving data perturbation or transformation techniques to encrypt dataset [21]. Keeping the distance after encryption enables the cloud to update clusters independently without data owner’s involvement, which achieves approximate efficiency compared with unencrypted data. However, as [17, 22] pointed out, these solutions are weak in security. Specifically, if attackers obtain some original instances (i.e., known-sample attack (KSA) [17]), the rest may be recovered by identifying corresponding encrypted ones and setting up enough equations. The work by Lin [11] focused on kernel k-means instead of standard k-means to avoid the preserving-distance vulnerability of random transformation. For outsourced collaborative data mining, Huang et al. [16] utilized asymmetric scalar-product-preserving encryption (ASPE) proposed in [17] that is resilient to KSA to compare distances. However, Yao et al. [23] demonstrated that ASPE is vulnerable to the linear analysis attack (LAA) [23]. To accelerate clustering efficiency, much research [24, 25] has been done to integrate MapReduce into k-means algorithm and optimize its performance, while few of them take privacy protection into account. Most recently, a secure scheme based on MapReduce to support large-scale dataset was proposed by Yuan and Tian [14]. By preserving the sign of encrypted distance difference like ASPE, their approach enables the cloud to assign data object to its closest cluster. It is resistant against both KSA and LAA. Unfortunately, none of the previously mentioned encryption schemes were formally proved to be secure against chosen plaintext attack (CPA); meanwhile some sensitive information, such as assignment of data objects and size of clusters, is directly disclosed to cloud servers.To further reenforce security, Rao et al. [15] proposed a semantic secure scheme for outsourced distributed clustering over the aggregated encrypted data from multiple users. Based on Paillier cryptosystem, their solution protects not only confidentiality of data contents, but also access patterns from cloud servers and other users. In addition, participation of users is no longer required during outsourcing. Their design objective is similar to ours, except that their protocol does not support computation under multikeys and Spark framework. Besides, the cost of secure comparison is too heavy since each input has to be decomposed into encrypted bits by calling SBD subroutine [26]. This will be demonstrated in the experimental evaluations in Section 7. In regard to computation under multikey setting, López et al. [27] proposed a new FHE; however its efficiency suffers from complex key-switching and heavy interactions among users. There are other works that utilize double decryption mechanism [28] or proxy reencryption technique [29] to convert ciphertext keys, allowing two servers to conduct addition and multiplication operations under multikeys. Nevertheless, these basic operations still cannot fulfill the need to perform more sophisticated data mining computations, for example, similarity measurement.


## 3. Preliminaries

In this section, we briefly introduce the typicalk-means clustering algorithm and public key cryptosystem with double decryption mechanism, serving as the basis of our solution.


### 3.1.k-Means Clustering

Given recordst1,…,tl, the k-means clustering algorithm partitions them into k disjoint clusters, denoted by c1,…,ck. Let μi be the centroid value of ci. Record tj assigned to ci has the shortest distance to μi compared with its distances to other centroids, where i∈[1,k] and j∈[1,l]. Let Vl×k be the matrix defining the membership of records, in which Vi,j∈{0,1}, for 1≤i≤l, 1≤j≤k. Note that the ith record belongs to cj if Vi,j=1; otherwise, Vi,j=0.Initialk records are selected randomly as cluster centers μ1,…,μk. Then the algorithm executes in an iterative fashion. For ti, the algorithm computes Euclidean distance between ti and every centroid μj for 1≤j≤k and updates V according to argminjti-μj2, that is, assigns ti to the closest cluster cj. Later, the centroid μj is derived by computing the mean values of attributes of records belonging to cj. With the updated c1,…,ck, the clustering algorithm begins the next iteration. Finally, the algorithm terminates if the matrix V does not vary any more or if a predefined maximum count of iterations is reached [10].


### 3.2. Public Key Cryptosystem with Double Decryption

Public key cryptosystem with double decryption mechanism (denoted by PKC-DD) allows an authority to decrypt any ciphertext by using the master secret key without consent of corresponding owner. In this paper, we use the scheme proposed by Youn et al. [30] as our secure primitive, which is more efficient than the scheme in [31] in that Youn et al.’s approach applies smaller modulus in cryptographic operations. The major steps are shown in the following.(i)
Key generation (KeyGen(κ)→N,g,msk,pk,sk): given a security parameter k, the master authority chooses two primes p and q (p=q=κ) and defines N=p2q. Then it chooses a random number g in ZN∗ such that the order of gp=gp-1modp2 is p. The master secret key msk=(p,q) is known only to the authority. The public parameters are N,g. A cloud user picks a random integer sk∈{0,1,…,2κ-1-1} as secret key and computes pk=gskmodN as public key.(ii)
Encryption (Enc(pk,m)→C): the encryption algorithm takes the message m∈ZN and pk as inputs and outputs C=(A,B), where A=grmodN, B=pkr·mmodN, and r is a random κ-1 bit integer.(iii)
Decryption with user key (uDec(sk,C)→m): the decryption algorithm takes ciphertext C and sk as inputs, and outputs the message m by computing m←B/AskmodN.(iv)
Decryption with master key (mDec(msk,pk,C)→m): given msk, pk, and C, the authority decrypts C by factorizing N. The secret key of C can be obtained by computing sk←Lpkp-1/Lgp, where function L is defined as L(x)=x-1/p. Then, m is recovered by computing m←B/AskmodN.By applying the general conversion method in [32], the scheme was claimed to be IND-CCA2 secure under the hardness of solving the p-DH Problem [30]. However, Galindo and Herranz [33] have constructed an attack by generating invalid public keys and querying for the master decryption, which may lead to factorization of N. To solve this, we adopt a slight modification of the scheme by checking the validity of the secret key, as proposed in [33]. If sk≥2κ-1, the master entity outputs a rejection message; otherwise, the decryption proceeds as usual.


## 3.1.k-Means Clustering

Given recordst1,…,tl, the k-means clustering algorithm partitions them into k disjoint clusters, denoted by c1,…,ck. Let μi be the centroid value of ci. Record tj assigned to ci has the shortest distance to μi compared with its distances to other centroids, where i∈[1,k] and j∈[1,l]. Let Vl×k be the matrix defining the membership of records, in which Vi,j∈{0,1}, for 1≤i≤l, 1≤j≤k. Note that the ith record belongs to cj if Vi,j=1; otherwise, Vi,j=0.Initialk records are selected randomly as cluster centers μ1,…,μk. Then the algorithm executes in an iterative fashion. For ti, the algorithm computes Euclidean distance between ti and every centroid μj for 1≤j≤k and updates V according to argminjti-μj2, that is, assigns ti to the closest cluster cj. Later, the centroid μj is derived by computing the mean values of attributes of records belonging to cj. With the updated c1,…,ck, the clustering algorithm begins the next iteration. Finally, the algorithm terminates if the matrix V does not vary any more or if a predefined maximum count of iterations is reached [10].


## 3.2. Public Key Cryptosystem with Double Decryption

Public key cryptosystem with double decryption mechanism (denoted by PKC-DD) allows an authority to decrypt any ciphertext by using the master secret key without consent of corresponding owner. In this paper, we use the scheme proposed by Youn et al. [30] as our secure primitive, which is more efficient than the scheme in [31] in that Youn et al.’s approach applies smaller modulus in cryptographic operations. The major steps are shown in the following.(i)
Key generation (KeyGen(κ)→N,g,msk,pk,sk): given a security parameter k, the master authority chooses two primes p and q (p=q=κ) and defines N=p2q. Then it chooses a random number g in ZN∗ such that the order of gp=gp-1modp2 is p. The master secret key msk=(p,q) is known only to the authority. The public parameters are N,g. A cloud user picks a random integer sk∈{0,1,…,2κ-1-1} as secret key and computes pk=gskmodN as public key.(ii)
Encryption (Enc(pk,m)→C): the encryption algorithm takes the message m∈ZN and pk as inputs and outputs C=(A,B), where A=grmodN, B=pkr·mmodN, and r is a random κ-1 bit integer.(iii)
Decryption with user key (uDec(sk,C)→m): the decryption algorithm takes ciphertext C and sk as inputs, and outputs the message m by computing m←B/AskmodN.(iv)
Decryption with master key (mDec(msk,pk,C)→m): given msk, pk, and C, the authority decrypts C by factorizing N. The secret key of C can be obtained by computing sk←Lpkp-1/Lgp, where function L is defined as L(x)=x-1/p. Then, m is recovered by computing m←B/AskmodN.By applying the general conversion method in [32], the scheme was claimed to be IND-CCA2 secure under the hardness of solving the p-DH Problem [30]. However, Galindo and Herranz [33] have constructed an attack by generating invalid public keys and querying for the master decryption, which may lead to factorization of N. To solve this, we adopt a slight modification of the scheme by checking the validity of the secret key, as proposed in [33]. If sk≥2κ-1, the master entity outputs a rejection message; otherwise, the decryption proceeds as usual.


## 4. Problem Statement

In this section, we formally describe our system model, threat model, and design objectives.


### 4.1. System Model

In our system model depicted in Figure1, there are two types of entities, that is, Cloud Users and Cloud Service Provider. Cloud Users consist of Data Owners and Query Client. The Cloud Service Provider can be divided into Storage and Computation Provider and Cryptographic Service Provider. Storage and Computation Provider is composed of dozens of Executing Servers, whereas Cryptographic Service Provider comprises a Key Authority Server and a group of Assistant Servers. The description of each party is given as follows.(1)
Data owner (DO): DO is the proprietor of a large dataset. Due to lack of hardware and software resources, DO prefers to outsource his data to the cloud for storage and collaborative data mining. There areDO1,…,DOn in the system. DOi has dataset Di which contains m attributes and li records, for i∈[1,n]. The total number of records is L=∑inli.(2)
Query client (QC): QC is an authorized party requestingk-means clustering tasks over the federate datasets. QC should not be involved in outsourced computation and should be able to decrypt the result with his own secret key.(3)
Executing worker (EW): EW server is a cluster node within Storage and Computation Provider, which is responsible for storing DO’s dataset and performing computation over them. There areEW1,…,EWθ in the system. They together constitute a parallel Spark cluster, working on the same distributed file system like HDFS and providing cloud users with massive storage and computing power.(4)
Key authority (KA): KA belongs to Cryptographic Service Provider, which is assigned with distribution and management of public parameters and public/private keys, as well as the master key of the cryptosystem.(5)
Assistant worker (AW): AW is also part of Cryptographic Service Provider. AW server holds the public/private keys generated by KA, with which AW is able to assist EW to execute a series of privacy-preserving building blocks. We assume that there areϑ AWs, that is, AW1,…,AWϑ. All AWs and KA constitute the cluster of Cryptographic Service Provider. Note that they offer sufficient computing power for temporal tasks, while they do not store the combined database.Figure 1
System model.Previous study has shown that it is impossible to implement a noninteractive protocol in the single server setting under the partially homomorphic encryption scheme [34]. So at least two servers are required to complete the outsourced computation [35]. In design of the system model, we take into account the situation that there are usually a large number of servers in one CSP. Moreover, it is feasible to propose secure outsourcing protocols through the cooperation between cloud servers from different CSPs. ∀i∈[1,n], DOi generates its own key pair pki/ski using the parameters produced by KA and encrypts Di with pki before uploading it to EW. With the joint datasets as inputs, the distributed cloud servers are scheduled to perform k-means clustering algorithm in a privacy-preserving manner.


### 4.2. Threat Model

In our threat model, all cloud servers and clients are assumed to be semihonest, which means that they strictly follow the prescribed protocol but try to infer private information using the messages they receive during the protocol execution. This assumption is consistent with existing works [11–16] on privacy-preserving clustering in cloud environment. Furthermore, the cloud servers have some prior knowledge regarding distribution of owners’ datasets that may be used to launch inference attacks by analyzing access patterns [19]. DOs, QCs, EWs, AWs, and KA are also interested in learning plain data belonging to other parities. Therefore, a CPA adversary A is introduced in the threat model. The target of A is to decrypt the ciphertexts from the challenge DO and challenge QC with the following abilities:(i)
A may compromise all the EWs to guess the plaintexts of received ciphertexts from DOs and AWs during the execution of the protocol.(ii)
A may compromise all the AWs and KA to guess the plaintext values of ciphertexts sent from EWs during the protocol interactions.(iii)
A may compromise one or more DOs and QCs except the challenge DO and the challenge QC to decrypt the ciphertexts belonging to the challenge party.Nevertheless, we assume that the adversaryA cannot compromise EWs and AWs and KA simultaneously; otherwise, A is able to decrypt any ciphertext stored on Storage and Computation Provider with the keys from Cryptographic Service Provider. In other words, there is no collusion between these two cloud providers, whereas servers within the provider itself may collude with each other. We remark that such assumptions are typical in adversary models used in cryptographic protocols (e.g., [15, 28, 36]), in that cloud providers are mostly competitors and economically driven by different business models.


### 4.3. Design Objectives

Given the aforementioned system model and threat model, our design should achieve the following objectives:(i)
Correctness: if the cloud users and servers both follow the protocol, the final decrypted result should be the same as in the standard k-means algorithm.(ii)
Data confidentiality: nothing regarding the contents of datasets D1,…,Dn and cluster centers μ1,…,μk, as well as the size of each cluster, should be revealed to the semihonest cloud servers.(iii)
Access pattern hidden: access patterns of clustering process, such as which records are assigned to which clusters, should not be revealed to the cloud to prevent any inference attacks [37].(iv)
Efficiency: most computation should be processed by cloud in an efficient way, while DOs and QCs are not required to be involved in the outsourced clustering.


## 4.1. System Model

In our system model depicted in Figure1, there are two types of entities, that is, Cloud Users and Cloud Service Provider. Cloud Users consist of Data Owners and Query Client. The Cloud Service Provider can be divided into Storage and Computation Provider and Cryptographic Service Provider. Storage and Computation Provider is composed of dozens of Executing Servers, whereas Cryptographic Service Provider comprises a Key Authority Server and a group of Assistant Servers. The description of each party is given as follows.(1)
Data owner (DO): DO is the proprietor of a large dataset. Due to lack of hardware and software resources, DO prefers to outsource his data to the cloud for storage and collaborative data mining. There areDO1,…,DOn in the system. DOi has dataset Di which contains m attributes and li records, for i∈[1,n]. The total number of records is L=∑inli.(2)
Query client (QC): QC is an authorized party requestingk-means clustering tasks over the federate datasets. QC should not be involved in outsourced computation and should be able to decrypt the result with his own secret key.(3)
Executing worker (EW): EW server is a cluster node within Storage and Computation Provider, which is responsible for storing DO’s dataset and performing computation over them. There areEW1,…,EWθ in the system. They together constitute a parallel Spark cluster, working on the same distributed file system like HDFS and providing cloud users with massive storage and computing power.(4)
Key authority (KA): KA belongs to Cryptographic Service Provider, which is assigned with distribution and management of public parameters and public/private keys, as well as the master key of the cryptosystem.(5)
Assistant worker (AW): AW is also part of Cryptographic Service Provider. AW server holds the public/private keys generated by KA, with which AW is able to assist EW to execute a series of privacy-preserving building blocks. We assume that there areϑ AWs, that is, AW1,…,AWϑ. All AWs and KA constitute the cluster of Cryptographic Service Provider. Note that they offer sufficient computing power for temporal tasks, while they do not store the combined database.Figure 1
System model.Previous study has shown that it is impossible to implement a noninteractive protocol in the single server setting under the partially homomorphic encryption scheme [34]. So at least two servers are required to complete the outsourced computation [35]. In design of the system model, we take into account the situation that there are usually a large number of servers in one CSP. Moreover, it is feasible to propose secure outsourcing protocols through the cooperation between cloud servers from different CSPs. ∀i∈[1,n], DOi generates its own key pair pki/ski using the parameters produced by KA and encrypts Di with pki before uploading it to EW. With the joint datasets as inputs, the distributed cloud servers are scheduled to perform k-means clustering algorithm in a privacy-preserving manner.


## 4.2. Threat Model

In our threat model, all cloud servers and clients are assumed to be semihonest, which means that they strictly follow the prescribed protocol but try to infer private information using the messages they receive during the protocol execution. This assumption is consistent with existing works [11–16] on privacy-preserving clustering in cloud environment. Furthermore, the cloud servers have some prior knowledge regarding distribution of owners’ datasets that may be used to launch inference attacks by analyzing access patterns [19]. DOs, QCs, EWs, AWs, and KA are also interested in learning plain data belonging to other parities. Therefore, a CPA adversary A is introduced in the threat model. The target of A is to decrypt the ciphertexts from the challenge DO and challenge QC with the following abilities:(i)
A may compromise all the EWs to guess the plaintexts of received ciphertexts from DOs and AWs during the execution of the protocol.(ii)
A may compromise all the AWs and KA to guess the plaintext values of ciphertexts sent from EWs during the protocol interactions.(iii)
A may compromise one or more DOs and QCs except the challenge DO and the challenge QC to decrypt the ciphertexts belonging to the challenge party.Nevertheless, we assume that the adversaryA cannot compromise EWs and AWs and KA simultaneously; otherwise, A is able to decrypt any ciphertext stored on Storage and Computation Provider with the keys from Cryptographic Service Provider. In other words, there is no collusion between these two cloud providers, whereas servers within the provider itself may collude with each other. We remark that such assumptions are typical in adversary models used in cryptographic protocols (e.g., [15, 28, 36]), in that cloud providers are mostly competitors and economically driven by different business models.


## 4.3. Design Objectives

Given the aforementioned system model and threat model, our design should achieve the following objectives:(i)
Correctness: if the cloud users and servers both follow the protocol, the final decrypted result should be the same as in the standard k-means algorithm.(ii)
Data confidentiality: nothing regarding the contents of datasets D1,…,Dn and cluster centers μ1,…,μk, as well as the size of each cluster, should be revealed to the semihonest cloud servers.(iii)
Access pattern hidden: access patterns of clustering process, such as which records are assigned to which clusters, should not be revealed to the cloud to prevent any inference attacks [37].(iv)
Efficiency: most computation should be processed by cloud in an efficient way, while DOs and QCs are not required to be involved in the outsourced clustering.


## 5. The PPCOM Solution

In this section, we first discuss a set of privacy-preserving building blocks. Then the complete protocol of PPCOM is presented.Recall that, in Section3.1, the semihonest but noncolluding cloud servers need to cooperate to perform computation over encrypted data under PKC-DD scheme. At first, KA takes a security parameter κ as input and generates public parameter (N,g) and master secret key msk by executing KeyGen(κ). Also, KA generates a key pair pku/sku used to unify ciphertext encryption key. After that, pku/sku and msk are sent to AWs, while (N,g) is distributed to DOs and QC, which are used to produce their own key pair pki/ski for i∈[1,n]. Their generated public keys are sent back to KA for management. Hereafter, let Encpk(·) denote the underlying encryption and uDecsk(·) and mDecsk(·) denote user-side decryption and master-side decryption, respectively. x represents the bit length of x.


### 5.1. Privacy-Preserving Building Blocks

We present eight privacy-preserving building blocks under multikeys. Five of them aim at solving basic operations over ciphertexts, including ciphertext transformation, multiplication, addition, equality test, and minimum, while the rest are especially designed for outsourced clustering.It can be apparently observed that the underlying encryption scheme is multiplicatively homomorphic due to the following equation:(1)gr1,pkr1·m1×gr2,pkr2·m2=gr1+r2,pkr1+r2·m1·m2=Encpkm1·m2,where Encpk(mi)=(gri,pkri·mi), for i=1,2. This property is so critical that multiplication over ciphertexts can be evaluated by one EW server independently, as long as the encryptions are under the same public key. Hereafter, “×” denotes multiplication operation in the encrypted domain while “·” represents multiplication in the plaintext domain.


#### 5.1.1. Secure Ciphertext Transformation (SCT) Protocol

Given that EW holdsEncpkx(m), and AW holds (msk,pky), the goal of theSCT protocol is to transform encrypted message m under public key pkx into another ciphertext under public key pky. During execution ofSCT, the plaintext m should not be revealed to EW or AW; meanwhile the output Encpky(m) is only known to EW. The complete steps are shown in Algorithm 1.Algorithm 1:SCT(Encpkx(m),pky)→Encpky(m).
Require:  EW has Encpkx(m), pkx, and pky; AW has msk, pkx, and pky.
(1) EW:
(a) Generate a random number:r∈RZN, s.t., r<κ-1;
(b) ComputeEncpkx(r⋅m)←Encpkx(m)×Encpkx(r);
(c) SendEncpkx(r⋅m) to AW;
(2) AW:
(a) Decryptr⋅m←mDec(msk,pkx,Encpkx(r⋅m));
(b) EncryptEncpky(r⋅m)←Enc(pky,r⋅m);
(c) SendEncpky(r⋅m) to EW;
(3) EW:
(a) ComputeEncpky(m)←Encpky(r⋅m)×Encpky(r-1);To start with, EW generates a numberr∈RZN, which means that r is randomly picked in ZN. Note that r<κ-1 ensures that r is invertible in ZN due to GCD(r,N)=1. Then we exploit multiplicative homomorphic property of PKC-DD to blind m from AW, even if it is able to decrypt Encpkx(r·m) via using msk. Finally, EW removes the randomness by multiplying the encrypted inverse of r due to Encpky(m)=Encpky(r·m·r-1modN).SCT protocol is especially useful for converting data under different encryption keys into ones under the same key so that EW can perform homomorphic operation.


#### 5.1.2. Secure Addition (SA) Protocol

It takesEncpku(m1) and Encpku(m2) held by EW and sku held by AW as inputs. The output is the encrypted addition of m1 and m2, that is, Encpku(m1+m2), which is only known to EW. As the encryption scheme is not additively homomorphic, it requires interactions between EW and AW.To preclude AW from obtainingm1 and m2, a straightforward solution for EW is to blind the inputs with a random value r by multiplying Encpku(r), where r∈RZN and GCD(r,N)=1. Then the encrypted randomized data are sent to AW. Since AW holds the secret key, it is able to get r·m1, r·m2 through decryption. The randomized addition (denoted by ω) is computed by r·m1+r·m2modN. After that, AW encrypts ω and sends it back to EW who can get the desired output by running Encpku(ω)×Encpku(r-1). Nevertheless, it is very possible that partial privacy is revealed to AW. This is because the ratio of inputs can be calculated via m1/m2←m1·r/m2·r, which may be utilized to distinguish inputs. As our threat model assumes the semihonest servers have some background knowledge of dataset distribution, it is effortless for AW to find correlations between encrypted records and known samples. Therefore, to achieve the privacy-preserving guarantees, disclosing input ratio should be prohibited duringSA execution.We propose an enhancedSA protocol still under two-server model, which protects confidentiality of inputs and outputs as well as intermediate results. There are five steps inSA, the details of which are presented in Algorithm 2.Algorithm 2:SA(Encpku(m1),Encpku(m2))→Encpku(m1+m2).
Require:  EW has Encpku(m1) and Encpku(m2); AW has the secret key sku.
(1) EW:
(a) Generate random numbers:r1,r2,r3∈RZN, s.t., ri<κ-1 for 1≤i≤3;
(b) ComputeS1←Encpku(m1)3, and α1←S1×Encpku(r1);
(c) ComputeS2←Encpku(m2)3, and α2←S2×Encpku(r2);
(d) Generate random numbers:ρ1,ρ2,ρ3,ρ4∈RZ, s.t., ρ1+ρ2≡3modN, ρ3+ρ4≡3modN;
(e) ComputeH1←Encpku(m1)2×Encpku(m2), and α3←H1×Encpku(ρ1)×Encpku(r1);
(f) ComputeH2←Encpku(m1)×Encpku(m2)2, and α4←H2×Encpku(ρ3)×Encpku(r2);
(g) Computeα5←H1×Encpku(ρ2)×Encpku(r3), and α6←H2×Encpku(ρ4)×Encpku(r3);
(h) Send{αi∣i=1,…,6} to AW;
(2) AW:
(a) Receive{αi∣i=1,…,6} from AW;
(b) DecryptFi←uDec(sku,αi), for 1≤i≤6;
(c) Computeβ1←F1+F3modN, β2←F2+F4modN, and β3←F5+F6modN;
(d) Encryptβi′←Enc(pku,βi), for 1≤i≤3;
(e) Send{β1′,β2′,β3′} to EW;
(3) EW:
(a) Receive{β1′,β2′,β3′} from EW;
(b) Generate a random number:r4∈RZN, s.t., r4<κ-1;
(c)fori=1 to 3do
(i) ComputeKi←βi′×Encpku(ri-1);
(ii) ComputeKi′←Ki×Encpku(r4);
(d) Send{K1′,K2′,K3′} to AW;
(4) AW:
(a) Receive{K1′,K2′,K3′} from AW;
(b) DecryptLi←uDec(sku,Ki′), for 1≤i≤3;
(c) Computeγ←L1+L2+L3modN;
(d) Encryptγ′←Enc(pku,γ); Send γ′ to EW;
(5) EW:
(a) Receiveγ′ from EW;
(b) Computeχ←γ′×Encpku(r4-1);
(c) Computed←3-1modord(G);
(d) ComputeEncpku(m1+m2)←χdmodN;During Step (1), the cloud EW generates a set of random numbers, namely,{ri∈ZN,ρj∈ZN∣i=1,…,3,j=1,…,4}, and calculates their corresponding encryptions under pku. By exploiting (1), EW computes several intermediate results, such as S1,S2,H1,H2, and outputs α1,…,α6. It can be easily verified that S1=Encpku(m13), S2=Encpku(m23), H1=Encpku(m12·m2), H2=Encpku(m1·m22), α1=Encpku(m13·r1), α2=Encpku(m23·r2), α3=Encpku(m12·m2·ρ1·r1), α4=Encpku(m1·m22·ρ3·r2), α5=Encpku(m12·m2·ρ2·r3), α6=Encpku(m1·m22·ρ4·r3).During Step (2), AW decryptsαi using sku, for 1≤i≤6. It then computes additions: β1,β2,β3 and their corresponding encryptions. It can be verified that β1′=Encpku(m13·r1+m12·m2·ρ1·r1), β2′=Encpku(m23·r2+m1·m22·ρ3·r2), β3′=Encpku(m12·m2·ρ2·r3+m1·m22·ρ4·r3).During Step (3), the blinding factors inβ1′,β2′,β3′ are removed by multiplying the encrypted values of r1-1,r2-1,r3-1. Then, EW generates a random number r4, which is used to blind K1,K2,K3. At Step (4), AW decrypts K1′,K2′,K3′ as L1,L2,L3, and calculates their addition γ. It can be verified that γ′=Encpku(m13·r4+m12·m2·ρ1·r4+m23·r4+m1·m22·ρ3·r4+m12·m2·ρ2·r4+m1·m22·ρ4·r4).In the end of Step (5), EW gets rid of randomness byχ←γ′×Encpku(r4-1). So we can verify that(2)χ=γ′×Encpkur4-1=Encpkum13+ρ1·m12·m2+ρ2·m12·m2+ρ3·m1·m22+ρ4·m1·m22+m23.After that, EW computes the inverse of 3 modulo ord(G). Note that ord(G) can be obtained due to ϕ(N)=p(p-1)(q-1). We have GCD(3,ϕ(N))=1, if p and q are primes of the forms p=2p′+1 and q=2q′+1, where p′ and q′ are also primes, which means that 3-1 exists in the degree domain. The desired output is calculated by Encpku(m1+m2)←χ3-1. The correctness of SA protocol can be proven by the following equation:(3)χ3-1=Encpkum13+ρ1·m12·m2+ρ2·m12·m2+ρ3·m1·m22+ρ4·m1·m22+m233-1=Encpkum13+ρ1+ρ2·m12·m2+ρ3+ρ4·m1·m22+m233-1=Encpkum13+3·m12·m2+3·m1·m22+m233-1=Encpkum1+m233-1=Encpkum1+m2.Executing Algorithm2 requires two rounds of interactions between EW and AW, which incurs more computational and communication overhead than the simple solution. However, it reveals no privacy to both cloud servers. The formal security analysis ofSA is given in Section 6.


#### 5.1.3. Secure Equality Test (SET) Protocol

Given that EW holds two encrypted valuesEncpku(m1) and Encpku(m2) while AW holds the secret key sku, the goal ofSET is to test whether m1 and m2 are equal without revealing them to cloud servers. The detailed steps are presented in Algorithm 3.Algorithm 3:SET(Encpku(m1),Encpku(m2))→Tor  F.
Require:  EW holds two encrypted values Encpku(m1) and Encpku(m2); AW holds the secret key sku.
(1) EW:
(a) ComputeA′←A1⋅A2-1modN, B′←B1⋅B2-1modN, where Encpku(m1)=(A1,B1),
Encpku(m2)=(A2,B2);
(b) Generate a random numberr∈RZN that r≠0;
(c) Computeξ′←ξr, where ξ=(A′,B′); Send ξ′ to AW;
(2) AW:
(a) Decryptζ←Dec(sku,ξ′);
(b)ifζ==1thenρ←T;elseρ←F;
(3)returnρ;At the first step, EW computes the fractions of two input ciphertexts. Supposing that(A1,B1)=(gr1,m1·pkr1) and (A2,B2)=(gr2,m2·pkr2), it can be verified that ξ′=(gr·(r1-r2),(m1·m2-1)r·pkr·(r1-r2)), where r,r1,r2∈RZN. During Step (2), AW decrypts ξ′ using sku as follows:(4)ζ=m1·m2-1r·pkr·r1-r2gsku·r·r1-r2modN=m1·m2-1rmodN.Since r is randomly selected in ZN, ζ is a random value if and only if m1≠m2. For m1=m2, it is obvious to infer that ζ=1. Thus, if AW obtains ζ=1, the returned value ρ is set to be true (denoted by T); otherwise, ρ is false (denoted by F). It is worth noting that neither m1,m2 nor the intermediate result m1/m2 is revealed to the cloud during execution ofSET.


#### 5.1.4. Secure Squared Euclidean Distance (SSED) Protocol

Fork-means algorithm, we use squared Euclidean distance to measure the distance between the data record and cluster centroid, denoted by ti-μj2, supposing that EW holds the ciphertext of ith data record ti, and the ciphertext of jth cluster centroid μj, while AW holds the secret key sku, for 1≤i≤L and 1≤j≤k.Note thatμj is a vector composed of m attributes which may be rational numbers. However, the ring ZN does not support rational division operation, so a new form of expression is required to represent the cluster center. Let sj,cj¯ denote the new form of cluster center, where sj and cj¯ represent the sum vector and the total number of records belonging to cj, respectively. It is easily observed that sj=Σh=1L(Vh,j·th)∈ZNm and cj¯=Σh=1LVh,j∈ZN. Furthermore, Ωi,j is defined as the scaled squared distance between ti and μj, which satisfies ti-μj=Ωi,j/cj¯. Thus, Ωi,j can be calculated as follows:(5)Ωi,j=ti-μj·cj¯2=∑h=1mtih-sjhcj2·cj¯2=∑h=1mcj¯·tih-sjh2,where i∈[1,L], j∈[1,k], and m is the dimension size.Taking encrypted record[ti] and encrypted center [μj] as inputs, EW and AW jointly executeSSED by invokingSA and output encryption of squared Euclidean distance [d(i,j)], in which [ti]=Encpku(ti), [μj]=Encpku(sj),Encpku(cj¯), and [d(i,j)]=Encpku(Ωi,j),Encpku(cj¯). TheSSED protocol should reveal neither the contents of ti and μj nor the Euclidean distance d(i,j) between them to cloud servers. Since implementation ofSSED is straightforward bySA scheme, the design details are omitted.


#### 5.1.5. Secure Squared Distance Comparison (SSDC) Protocol

Suppose that EW holds[d(i,a),d(i,b)] and AW holds sku, where i∈[1,L], a,b∈[1,k], a≠b. Apart from these, EW also has encrypted secrets associated with the distances, that is, sa′,sb′. The output ofSSDC is the encrypted minimum squared distance and its corresponding secret. Since our encryption scheme is probabilistic and does not preserve the order of messages, EW and AW should jointly compute the minimum without revealing Encpku(Ωi,a),Encpku(ca¯), Encpku(Ωi,b),Encpku(cb¯), and sa, as well as sb, to both servers.Our key idea is to compute the fraction value between the two squared Euclidean distances, based on which AW is able to judge its relationship and returns EW as an encrypted identifier that indicates the minimum value. The fraction between the two squared Euclidean distances can be calculated as follows:(6)ti-μa2ti-μb2=Ωi,aca¯2·Ωi,bcb¯2-1=Ωi,a·ca¯2Ωi,b·ca¯2=λ.Since Ωi,a·cb¯2 and Ωi,b·ca¯2 are integers within ZN, the ratio λ may be a rational value in Q, according to (6). It can be observed that if ⌊λ⌋<1 (· truncates the decimal fraction while keeping the integer part), we deduce that ti-μa2<ti-μb2; otherwise, ti-μa2≥ti-μb2. The overall steps ofSSDC are given in Algorithm 4.Algorithm 4:SSDC({[d(i,a)],sa′},{[d(i,b)],sb′})→{[dmin],smin′}.
Require:  EW has two encrypted squared distances along with their corresponding encrypted secrets, i.e., ([d(i,a)],sa′)
([d(i,b)],sb′), while AW holds secret key sku, where [d(i,a)]=Encpku(Ωi,a),Encpku(ca¯),
[d(i,b)]=Encpku(Ωi,b),Encpku(cb¯), sa′=Encpku(sa), sb′=Encpku(sb).
(1) EW:
(a) Generate a random numbers∈RZ, two non-zero random numbers r1,r2∈RZN;
(b) ComputeE1←Encpku(Ωi,a)×Encpku(cb¯)×Encpku(r1);
(c) ComputeE2←Encpku(Ωi,a)×Encpku(ca¯)×Encpku(r1);
(d)ifsmod2==1then
(i) Computeτ1←E1r2modN;
(ii) Computeτ2←E2r2modN;
(e)else
(i) Computeτ1←E2r2modN;
(ii) Computeτ2←E1r2modN;
(f) Sendτ1,τ2 to AW;
(2) AW:
(a) Decryptηi←uDec(sku,τi), for i=1,2;
(b) Computeδ←η1/η2;
(c)ifδ==0then
(i) Computeσ←2;
(d)else ifδ>=1then
(i) Computeσ←1;
(e) Encryptσ′←Enc(pku,σ); Send σ′ to EW;
(3) EW:
(a)ifsmod2==1then
(i) ComputeEncpku(Ωmin)←ComputeMin(Encpku(Ωi,a),Encpku(Ωi,b),σ′);
(ii) ComputeEncpku(cmin¯)←ComputeMin(Encpku(ca¯),Encpku(cb¯),σ′);
(iii) ComputeEncpku(smin)←ComputeMin(Encpku(sa),Encpku(sb),σ′);
(b)else
(i) ComputeEncpku(Ωmin)←ComputeMin(Encpku(Ωi,b),Encpku(Ωi,a),σ′);
(ii) ComputeEncpku(cmin¯)←ComputeMin(Encpku(cb¯),Encpku(ca¯),σ′);
(iii) ComputeEncpku(smin)←ComputeMin(Encpku(sb),Encpku(sa),σ′);
(4)return([dmin],smin′)←(Encpku(Ωmin),Encpku(cmin¯),Encpku(smin));To begin with, EW computes encryptions of randomized distances, that is,τ1,τ2. It can be verified that τ1=Encpkur1·Ωi,a·cb¯r2 and τ2=Encpkur1·Ωi,b·ca¯r2. During Step (2), AW obtains η1,η2 through decrypting τ1,τ2 with sku. Next, it calculates η1/η2 in the rational field.(7)η1η2=r1·Ωi,a·cb¯2r2r1·Ωi,b·ca¯2r2=Ωi,a·cb¯2Ωi,b·ca¯2r2=λr2.From (7), it is easy to infer that AW locates the minimum value by δ=(λ)r2, for the blinding factor r2 does not alter the relationship between ti-μa2 and ti-μb2. If ⌊δ⌋=0, it means η1<η2 and AW assigns the indicator σ′ to be Encpku(2); otherwise, η1≥η2 and σ′=Encpku(1). One may prefer to use Encpku(1) and Encpku(0) to represent the indicator, which is more straightforward, whereas it is not secure to utilize encryption of “0”, because C2=0·pkrmodN=0, in which Encpku(0)=(C1,C2). In that case, EW can obviously infer that the encrypted message is zero by observing the ciphertext part.During Step (3), EW takes the receivedσ and encrypted squared distances as well as secrets as inputs and computes the target minimum values. It invokes a secure subroutine calledComputeMin, as shown in Algorithm 5. The correctness ofSSDC protocol is proven as follows. Let us take Encpku(Ωmin) as an example; if smod2=1, EW and AW jointly executeComputeMin and get the following:(8)EncpkuΩmin=Encpkuσ·Ωi,a+2·Ωi,b-Ωi,a-σ·Ωi,b=Encpkuσ-1·Ωi,a+2-σ·Ωi,b.Apparently, it can be observed that if σ=2, then we have Encpku(Ωmin)=Encpku(Ωi,a); otherwise, Encpku(Ωmin)=Encpku(Ωi,b). Likewise, Encpku(cmin¯) and Encpku(smin) are calculated in a similar way.Algorithm 5:ComputeMin(v′,w′,φ′)→min(u′,v′).
Require:  EW holds two encrypted values v′,w′, and an encrypted identifier φ′, where v′=Encpku(v), w′=Encpku(w),
φ′=Encpku(φ); AW has sku;
(1) EW computes Encpku(v⋅φ)←Encpku(v)×Encpku(φ);
(2) EW computes Encpku(2⋅w)←Encpku(2)×Encpku(w);
(3) EW computes Encpku(w⋅φ)←Encpku(w)×Encpku(φ);
(4) EW and AW jointly compute Encpku(v⋅φ+2⋅w)←SA(Encpku(v⋅φ),Encpku(2⋅w));
(5) EW and AW jointly compute Encpku(v+w⋅φ)←SA(Encpku(v),Encpku(w⋅φ));
(6) EW computes Encpku(-v-w⋅φ)←Encpku(v+w⋅φ)×Encpku(-1);
(7) EW and AW jointly compute Encpku(v⋅φ+2⋅w-v-w⋅φ)←SA(Encpku(v⋅φ+2⋅w),Encpku(-v-w⋅φ));
(8)returnmin(u′,v′)←Encpku(v⋅φ+2⋅w-v-w⋅φ);


#### 5.1.6. Secure Minimum amongk Squared Distances (SMkSD) Protocol

We assume that EW holds a set of encrypted squared Euclidean distances[d(i,1)],…,[d(i,k)], where [d(i,j)]=Encpku(Ωi,j),μj¯, i∈[1,L], j∈[1,k], and AW holds the secret key sku. Besides, EW also has the encryptions of secrets corresponding to their distances, that is, s1′,…,sk′. The goal ofSMkSD is to compute the encryption of the shortest squared distance along with its encrypted secret, denoted by [dmin],smin′, respectively. To executeSMkSD, we compute the minimum by utilizingSSDC with two inputs each time in a sequential fashion. The computation complexity of this algorithm is O(k). Also, it can be executed in a binary tree hierarchy like SMINn in [15], which takes at most ⌈log2⁡k⌉ iterations.


#### 5.1.7. Secure Index to Bitmap Conversion (SIBC) Protocol

Given that EW has the encrypted index of the closest cluster denoted byEncpku(ν) (ν∈[1,k]), and AW holds the private key sku, the output ofSIBC is a bitmap vector Λ composed of k encrypted elements. During execution ofSIBC, neither the index nor the bitmap should be revealed to both servers. If i=ν∧i∈[1,k],SIBC denotes Λ[i]=Encpku(2); otherwise, Λ[i]=Encpku(1). This indicates that the position of Encpku(2) in Λ is the index of the nearest cluster. The typical form of Λ is as follows: (9)Λ=Encpku1,…,Encpku1︷1⇀ν-1,Encpku2︷ν,Encpku1,…,Encpku1︷ν+1⇀k. The complete steps are presented in Algorithm 6.Algorithm 6:SIBC(Encpku(ν))→Λ.
Require:  EW holds encrypted index Encpku(ν); AW has secret key sku.
(1) EW:
(a)fori=1 to kdo
(i) Generate non-zero random numbersαi,β∈RZN;
(ii) ComputeAi←Encpku(αi)×Enc(pku,i)β;
(iii) ComputeBi←Encpku(αi)×Encpku(ν)β;
(b) Generate a random permutation functionπ;
(c) ComputeΓ′←π(Γ), where Γ={Ai,Bi∣i=1,…,k};
(d) SendΓ′ to AW;
(2) AW:
(a)fori=1 to kdo
(i) DecryptEi←Dec(sku,Ai′), Fi←Dec(sku,Bi′), where Γ′={Ai′,Bi′∣i=1,…,k};
(ii) Computeηi←Ei/Fi;
(iii)ifηi==1then
(A) ComputeW[i]←Encpku(2);
(iv)else
(A) ComputeW[i]←Encpku(1);
(b) SendW to EW;
(3) EW:
(a) ComputeΛ←π-1(W);During Step (1), EW generates nonzero random numbers and uses them to blindi and ν, for 1≤i≤k. It can be verified that Ai=Encpku(αi·(i)β) and Bi=Encpku(αi·(ν)β). For i=1,…,k, Ai,Bi constitutes an ordered set Γ, which is further permutated by a random permutation function π.During Step (2), AW decrypts the permutated setΓ′ and computes the fraction for each part. It is easy to infer the following equation:(10)ηj=EjFj=αi·iβαi·νβ=iνβ,where i,j∈[1,k] and i,j may not be the same. Regardless of β, if i=ν, then we have ηj=1; otherwise, ηj is a random number in Q. Note that AW cannot know the relationship between Ei and Ej for i≠j, since they are randomized by blinding factors. Besides, the ratio Ei/Ej=(αi/αj)·(i/j)β is also a random number. Thus, as long as π is kept confidential, the index of closest cluster is not revealed to AW. In the end, EW recovers the true sequence of Λ by running the inverse permutation π-1(W).Furthermore, it should be emphasized that the method based on (10) can also be used in other scenarios where equality test is required.


#### 5.1.8. Secure New Cluster Computation (SNCC) Protocol

Given that EW holds the assignment membership matrixV, the encrypted dataset D′, and target cluster ci, the goal ofSNCC is to calculate the new cluster centroid denoted by [μi], where [μi]=Encpku(si),Encpku(ci¯). During execution ofSNCC, nothing regarding the data record, sum of attributes, and cluster size should be disclosed to cloud servers. The complete steps are shown in Algorithm 7.Algorithm 7:SNCC(V,D′,i)→[μi].
Require:  EW holds the assignment matrix V, the encrypted dataset D′, the cluster id i, while AW has the secret key sku,
whereV=Λ1T,…,ΛLT, D′={Encpkutj,h∣j∈[1,L],h∈[1,m]}, i∈[1,k].
(1) EW:
(a)forh=1 to mdo
(i)forj=1 to Ldo
(A) ComputeHj←Encpku(tj,h)×V[j,i];
(B) ComputeHh′←SA(Hj,Hh′) with AW;
(ii) ComputeSh′←Sh×Encpku(-1), where Sh=∑j=1Ltj,h;
(iii) ComputeEncpku(si,h)←SA(Hh′,Sh′) with AW;
(2) EW:
(a)forj=1 to Ldo
(i) ComputeC←SA(V[j,i],C) with AW;
(b) ComputeEncpku(ci¯)←SA(C,Encpku(-L)) with AW;
(3)return[μi]←〈Encpku(si),Encpku(ci¯)〉;During Step (1), EW computes the encryption of summation for each attribute, that is,Encpku(si,h) for 1≤i≤k and 1≤h≤m. Supposing that V[j,i]=Encpku(vj,i), where vj,i∈{1,2} and j∈[1,L], EW obtains Hj=Encpku(tj,h·vj,i). After L rounds of iterations, the important observation is(11)Encpkusi,h=Encpku∑j=1Ltj,h·vj,i-∑j=1Ltj,h=Encpku∑j=1Ltj,h·vj,i-1.Recall that vj,i=2 means that tj belongs to the cluster ci, while vj,i=1 denotes tj∉cj. Therefore, (11) adds all the records that are assigned to the target cluster. Moreover, Sh only needs to be calculated only once during the entire outsourcing period, for 1≤h≤m.During Step (2), EW and AW jointly compute the encryption of cluster sizeEncpku(ci¯) by invokingSA subprotocol. It can be verified that(12)Encpkuci¯=Encpku∑j=1Lvj,i-L=Encpku∑j=1Lvj,i-1.Obviously, (12) sums up those whose vj,i equals 2 and discards those with vj,i=1, through which the final result is the size of the cluster ci.


### 5.2. The Complete PPCOM Protocol

In this subsection, we present our proposed PPCOM protocol for the standardk-means algorithm which works in the distributed cloud environments.The primary goal of PPCOM is to schedule a group of cloud servers to perform clustering task over the joint datasets encrypted under multiple keys, meanwhile no privacy of data records, intermediate results, and final clusters should be revealed to the semihonest servers. In order to improve the overall performance, we leverage a large-scale data processing engine called Spark [38]. It develops a data structure called the resilient distributed dataset (RDD) for data parallelism and fault-tolerance, which facilitates iterative algorithms in machine learning. Though it provides a scalable machine learning library—MLlib—which includes k-means algorithm [39], it does not take privacy protection into account and cannot process encrypted data either. Therefore, it is essential to combine our proposed building blocks in Section 5.1 and Spark computing framework to design PPCOM.PPCOM is composed of four stages, that is, Data Uploading, Ciphertext Transformation, Clustering Computation, and Result Retrieval, the details of which are described in the following.


#### 5.2.1. Data Uploading Stage

We assume that all data records should have been preprocessed by data owners. One essential preprocessing step is to normalize data values, because different attributes have different value domains, which possibly leads to the case that those attribute values whose domain is large have greater impacts on accuracy of distance-based clustering. Normalization enables records to fall into the common range by endowing all attributes with equal weights. In this paper, we adopt Mix-Max Normalization [40]. Suppose that attribute A owns s observed values v1,v2,…,vs and [minA,maxA] is the range of A, while [new_minA,new_maxA] is the target range. Mix-Max Normalization maps vi into vi′ in [new_minA,new_maxA] by calculating the following equation:(13)vi′=vi-minAmaxA-minAnew_maxA-new_minA+new_minA.After the preprocessing step,DOi encrypts its dataset Di with pki by calculating Enc(pki,tj,hi) for i∈[1,n]. Let tj,hi denote the hth attribute value of jth record tji in Di for h∈[1,m] and j∈[1,L]. Di′ denotes the encryption of Di. After all DOs complete uploading their datasets to EWs, the cloud aggregates the distributed datasets into a joint database D′=⋃i=1nDi′. Under this circumstance, DOi is still able to retrieve its data and decrypt it with its private key ski, whereas DOi cannot decrypt Dj without corresponding ski for i≠j.


#### 5.2.2. Ciphertext Transformation Stage

Upon receiving clustering request from QC, EWs initiate ciphertext transformation procedure which aims at converting ciphertexts underpki into encryptions under the unified key pku, for i∈[1,n]. EW first replicates D′ into Dr′ to ensure DOs’ accessibility to their original dataset. ThenSCT subprotocol is executed to output the converted dataset (denoted by Du′). This stage is important for two reasons: (1) EW is able to perform homomorphic operation merely under the same public key; (2) user-decryption is much more efficient than master decryption.


#### 5.2.3. Clustering Computation Stage

With all the converted recordsEncpku(ti,j), for i∈[1,L], j∈[1,m], the objective of this stage is to compute the cluster centroids [μ1],…,[μk] and the membership matrix VL×k without compromising privacy. The outsourcing process is not only protected by the proposed secure building blocks, but also accelerated by Spark framework. The stage includes four steps, namely, Job Assignment, Map Execution, Reduce Execution, and Update Judgement, as shown in Figure 2.Figure 2
PPCOM under Spark framework.Step 1 (Job Assignment).
Firstly, CSPs selectς minimum computing units (denoted by MCUs). Each MCU is composed of one server from {EW1,…,EWθ} and one from {AW1,…,AWϑ}; that is, MCU={EW,AW}. Obviously, MCU is able to perform cryptographic building blocks on its own. Since the workload of AW is relatively light compared to EW, it is preferable to share one AW within several MCUs to maximize resource usage. We assume that every cloud node possesses sufficient storage and computational power for its assigned job. The set {MCU1,…,MCUς} is divided into two disjoint sets, that is, Map set and Reduce set. Without loss of generality, Map consists of MCU1,…,MCUf, while Reduce comprises MCUf+1,…,MCUf+k+1. Then Du′ is divided into f uniformly distributed partitions P1,…,Pf, which are transferred to their corresponding MCU nodes in Map set. In this paper, we assume that the k initial cluster centers are chosen by DOs in advance and they are also encrypted. ∀i∈[1,f], Map[i] is aware of the initial cluster centroid set U={[μ1],…,[μk]}, where [μj]=Encpku(sj),Encpku(cj¯), for 1≤j≤k.Step 2 (Map Execution).
GivenPi and U as inputs, Map[i] (i∈[1,f]) outputs a key-value table Ti, in which the key is the record and the value is the encryption of bitmap that indicates the closest cluster. Suppose that Pi includes z data records [t1],…,[tz]. Here, [tj] (j∈[1,z]) is an m-dimension vector Encpku(tj,1),…,Encpku(tj,m).
As presented in Algorithm8, each MCU in Map executes the following steps in parallel: (1) computes the encryption of squared Euclidean distance between [tj] and cluster center [μh], for 1≤j≤z and 1≤h≤k (Steps (1)–(5)); (2) computes the encrypted index of the minimum among k distances for each record by callingSMkSD (Step (6)); (3) converts the index into an encrypted bitmap viaSIBC scheme (Step (7)). The final output for Map[i] is table Ti with z entries. Each entry consists of a data record as the key and its corresponding assignment bitmap as value.Algorithm 8:Map(P1,…,Pf,U)→{T1,…,Tf}.
Require:  Map MCUs have datasets P1,…,Pf and cluster centroid set U.
(1)  ∀i∈[1,f], Map[i] concurrently executes:
(2)forj=1 to zdo
(3)  forh=1 to kdo
(4)    {ComputethesquaredEuclideandistance}
[d(j,h)]←SSED([tj],[μh]), where [d(j,h)]=Encpku(Ωj,h),ch¯;
(5)   end for
(6)   {Computetheindexofminimumamongkdistances}
{[dmin],smin′}←SMkSD({[d(j,1)],s1′},…,{[d(j,k)],sk′}), where sν′=Encpku(ν), for ν∈[1,k];
(7)   {Converttheindexintoencryptedvector}
Λj←SIBC(smin′);
(8)   keyj←[tj] and valuej←Λj;
(9)end for
(10)returnTi={key1,value1,…,keyz,valuez} for i=1,…,f;Step 3 (Reduce Execution).
Taking{T1,…,Tf} from Map MCUs and the aggregated dataset Du′ as inputs, Reduce[i] computes the cluster center for ci based on the assignment membership matrix V. The major steps are presented in Algorithm 9. It can be observed that each MCU in Reduce concurrently executes the following: (1) converges the assignment vectors in {T1,…,Tf} into the complete membership matrix V (Step (4)); (2) computes the new cluster center for the target cluster by invokingSNCC (Step (7)). The final output for Reduce[i] is the encrypted centroid [μi] for ci and the matrix V.Algorithm 9:Reduce(T1,…,Tf,Du′)→{U,V}.
Require:  Reduce MCUs have T1,…,Tf and the aggregated dataset Du′.
(1) ∀i∈[1,k], Reducer[i] concurrently executes:
(2)forj=1 to fdo
(3) forh=1 to zdo
(4)   {Convergetheassignmentvectorsintomatrix}
V[(j-1)⋅z+h]←Tj.valueh;
(5) end for
(6)end for
(7) {Computethenewclustercenterforci}
[μi]←SNCC(V,Du′,i);
(8)returnU, V, where U={[μ1],…,[μk]};Step 4 (Update Judgement).
This step is to determine whether the predefined termination condition ofk-means algorithm is satisfied. In this paper, we consider that the membership matrix is not changing as the termination condition. Given that EW holds the previous matrix V and the current matrix V′ and AW holds the key sku, our strategy is to find out whether the elements in V and V′ are equal one by one by utilizingSET subprotocol. Once a mismatch is detected, EW replaces V with V′ and goes to Step 2 of Clustering Computation Stage. Otherwise, these servers continue comparing till the end of matrix. If the outcome is V=V′ which means that the assignment of clusters does not vary any more, EW then terminates the iteration and activates Result Retrieval Stage.


#### 5.2.4. Result Retrieval Stage

Since the cluster center setU and assignment matrix V are encrypted under pku, QC cannot decrypt them without sku. Firstly,SCT scheme is invoked to transform the encryption key of U and V from pku to pkQ. After that, QC is able to download them and decrypt the final result with skQ. The final cluster center of ci is recovered by μi←si/ci¯, for i∈[1,k].


## 5.1. Privacy-Preserving Building Blocks

We present eight privacy-preserving building blocks under multikeys. Five of them aim at solving basic operations over ciphertexts, including ciphertext transformation, multiplication, addition, equality test, and minimum, while the rest are especially designed for outsourced clustering.It can be apparently observed that the underlying encryption scheme is multiplicatively homomorphic due to the following equation:(1)gr1,pkr1·m1×gr2,pkr2·m2=gr1+r2,pkr1+r2·m1·m2=Encpkm1·m2,where Encpk(mi)=(gri,pkri·mi), for i=1,2. This property is so critical that multiplication over ciphertexts can be evaluated by one EW server independently, as long as the encryptions are under the same public key. Hereafter, “×” denotes multiplication operation in the encrypted domain while “·” represents multiplication in the plaintext domain.


### 5.1.1. Secure Ciphertext Transformation (SCT) Protocol

Given that EW holdsEncpkx(m), and AW holds (msk,pky), the goal of theSCT protocol is to transform encrypted message m under public key pkx into another ciphertext under public key pky. During execution ofSCT, the plaintext m should not be revealed to EW or AW; meanwhile the output Encpky(m) is only known to EW. The complete steps are shown in Algorithm 1.Algorithm 1:SCT(Encpkx(m),pky)→Encpky(m).
Require:  EW has Encpkx(m), pkx, and pky; AW has msk, pkx, and pky.
(1) EW:
(a) Generate a random number:r∈RZN, s.t., r<κ-1;
(b) ComputeEncpkx(r⋅m)←Encpkx(m)×Encpkx(r);
(c) SendEncpkx(r⋅m) to AW;
(2) AW:
(a) Decryptr⋅m←mDec(msk,pkx,Encpkx(r⋅m));
(b) EncryptEncpky(r⋅m)←Enc(pky,r⋅m);
(c) SendEncpky(r⋅m) to EW;
(3) EW:
(a) ComputeEncpky(m)←Encpky(r⋅m)×Encpky(r-1);To start with, EW generates a numberr∈RZN, which means that r is randomly picked in ZN. Note that r<κ-1 ensures that r is invertible in ZN due to GCD(r,N)=1. Then we exploit multiplicative homomorphic property of PKC-DD to blind m from AW, even if it is able to decrypt Encpkx(r·m) via using msk. Finally, EW removes the randomness by multiplying the encrypted inverse of r due to Encpky(m)=Encpky(r·m·r-1modN).SCT protocol is especially useful for converting data under different encryption keys into ones under the same key so that EW can perform homomorphic operation.


### 5.1.2. Secure Addition (SA) Protocol

It takesEncpku(m1) and Encpku(m2) held by EW and sku held by AW as inputs. The output is the encrypted addition of m1 and m2, that is, Encpku(m1+m2), which is only known to EW. As the encryption scheme is not additively homomorphic, it requires interactions between EW and AW.To preclude AW from obtainingm1 and m2, a straightforward solution for EW is to blind the inputs with a random value r by multiplying Encpku(r), where r∈RZN and GCD(r,N)=1. Then the encrypted randomized data are sent to AW. Since AW holds the secret key, it is able to get r·m1, r·m2 through decryption. The randomized addition (denoted by ω) is computed by r·m1+r·m2modN. After that, AW encrypts ω and sends it back to EW who can get the desired output by running Encpku(ω)×Encpku(r-1). Nevertheless, it is very possible that partial privacy is revealed to AW. This is because the ratio of inputs can be calculated via m1/m2←m1·r/m2·r, which may be utilized to distinguish inputs. As our threat model assumes the semihonest servers have some background knowledge of dataset distribution, it is effortless for AW to find correlations between encrypted records and known samples. Therefore, to achieve the privacy-preserving guarantees, disclosing input ratio should be prohibited duringSA execution.We propose an enhancedSA protocol still under two-server model, which protects confidentiality of inputs and outputs as well as intermediate results. There are five steps inSA, the details of which are presented in Algorithm 2.Algorithm 2:SA(Encpku(m1),Encpku(m2))→Encpku(m1+m2).
Require:  EW has Encpku(m1) and Encpku(m2); AW has the secret key sku.
(1) EW:
(a) Generate random numbers:r1,r2,r3∈RZN, s.t., ri<κ-1 for 1≤i≤3;
(b) ComputeS1←Encpku(m1)3, and α1←S1×Encpku(r1);
(c) ComputeS2←Encpku(m2)3, and α2←S2×Encpku(r2);
(d) Generate random numbers:ρ1,ρ2,ρ3,ρ4∈RZ, s.t., ρ1+ρ2≡3modN, ρ3+ρ4≡3modN;
(e) ComputeH1←Encpku(m1)2×Encpku(m2), and α3←H1×Encpku(ρ1)×Encpku(r1);
(f) ComputeH2←Encpku(m1)×Encpku(m2)2, and α4←H2×Encpku(ρ3)×Encpku(r2);
(g) Computeα5←H1×Encpku(ρ2)×Encpku(r3), and α6←H2×Encpku(ρ4)×Encpku(r3);
(h) Send{αi∣i=1,…,6} to AW;
(2) AW:
(a) Receive{αi∣i=1,…,6} from AW;
(b) DecryptFi←uDec(sku,αi), for 1≤i≤6;
(c) Computeβ1←F1+F3modN, β2←F2+F4modN, and β3←F5+F6modN;
(d) Encryptβi′←Enc(pku,βi), for 1≤i≤3;
(e) Send{β1′,β2′,β3′} to EW;
(3) EW:
(a) Receive{β1′,β2′,β3′} from EW;
(b) Generate a random number:r4∈RZN, s.t., r4<κ-1;
(c)fori=1 to 3do
(i) ComputeKi←βi′×Encpku(ri-1);
(ii) ComputeKi′←Ki×Encpku(r4);
(d) Send{K1′,K2′,K3′} to AW;
(4) AW:
(a) Receive{K1′,K2′,K3′} from AW;
(b) DecryptLi←uDec(sku,Ki′), for 1≤i≤3;
(c) Computeγ←L1+L2+L3modN;
(d) Encryptγ′←Enc(pku,γ); Send γ′ to EW;
(5) EW:
(a) Receiveγ′ from EW;
(b) Computeχ←γ′×Encpku(r4-1);
(c) Computed←3-1modord(G);
(d) ComputeEncpku(m1+m2)←χdmodN;During Step (1), the cloud EW generates a set of random numbers, namely,{ri∈ZN,ρj∈ZN∣i=1,…,3,j=1,…,4}, and calculates their corresponding encryptions under pku. By exploiting (1), EW computes several intermediate results, such as S1,S2,H1,H2, and outputs α1,…,α6. It can be easily verified that S1=Encpku(m13), S2=Encpku(m23), H1=Encpku(m12·m2), H2=Encpku(m1·m22), α1=Encpku(m13·r1), α2=Encpku(m23·r2), α3=Encpku(m12·m2·ρ1·r1), α4=Encpku(m1·m22·ρ3·r2), α5=Encpku(m12·m2·ρ2·r3), α6=Encpku(m1·m22·ρ4·r3).During Step (2), AW decryptsαi using sku, for 1≤i≤6. It then computes additions: β1,β2,β3 and their corresponding encryptions. It can be verified that β1′=Encpku(m13·r1+m12·m2·ρ1·r1), β2′=Encpku(m23·r2+m1·m22·ρ3·r2), β3′=Encpku(m12·m2·ρ2·r3+m1·m22·ρ4·r3).During Step (3), the blinding factors inβ1′,β2′,β3′ are removed by multiplying the encrypted values of r1-1,r2-1,r3-1. Then, EW generates a random number r4, which is used to blind K1,K2,K3. At Step (4), AW decrypts K1′,K2′,K3′ as L1,L2,L3, and calculates their addition γ. It can be verified that γ′=Encpku(m13·r4+m12·m2·ρ1·r4+m23·r4+m1·m22·ρ3·r4+m12·m2·ρ2·r4+m1·m22·ρ4·r4).In the end of Step (5), EW gets rid of randomness byχ←γ′×Encpku(r4-1). So we can verify that(2)χ=γ′×Encpkur4-1=Encpkum13+ρ1·m12·m2+ρ2·m12·m2+ρ3·m1·m22+ρ4·m1·m22+m23.After that, EW computes the inverse of 3 modulo ord(G). Note that ord(G) can be obtained due to ϕ(N)=p(p-1)(q-1). We have GCD(3,ϕ(N))=1, if p and q are primes of the forms p=2p′+1 and q=2q′+1, where p′ and q′ are also primes, which means that 3-1 exists in the degree domain. The desired output is calculated by Encpku(m1+m2)←χ3-1. The correctness of SA protocol can be proven by the following equation:(3)χ3-1=Encpkum13+ρ1·m12·m2+ρ2·m12·m2+ρ3·m1·m22+ρ4·m1·m22+m233-1=Encpkum13+ρ1+ρ2·m12·m2+ρ3+ρ4·m1·m22+m233-1=Encpkum13+3·m12·m2+3·m1·m22+m233-1=Encpkum1+m233-1=Encpkum1+m2.Executing Algorithm2 requires two rounds of interactions between EW and AW, which incurs more computational and communication overhead than the simple solution. However, it reveals no privacy to both cloud servers. The formal security analysis ofSA is given in Section 6.


### 5.1.3. Secure Equality Test (SET) Protocol

Given that EW holds two encrypted valuesEncpku(m1) and Encpku(m2) while AW holds the secret key sku, the goal ofSET is to test whether m1 and m2 are equal without revealing them to cloud servers. The detailed steps are presented in Algorithm 3.Algorithm 3:SET(Encpku(m1),Encpku(m2))→Tor  F.
Require:  EW holds two encrypted values Encpku(m1) and Encpku(m2); AW holds the secret key sku.
(1) EW:
(a) ComputeA′←A1⋅A2-1modN, B′←B1⋅B2-1modN, where Encpku(m1)=(A1,B1),
Encpku(m2)=(A2,B2);
(b) Generate a random numberr∈RZN that r≠0;
(c) Computeξ′←ξr, where ξ=(A′,B′); Send ξ′ to AW;
(2) AW:
(a) Decryptζ←Dec(sku,ξ′);
(b)ifζ==1thenρ←T;elseρ←F;
(3)returnρ;At the first step, EW computes the fractions of two input ciphertexts. Supposing that(A1,B1)=(gr1,m1·pkr1) and (A2,B2)=(gr2,m2·pkr2), it can be verified that ξ′=(gr·(r1-r2),(m1·m2-1)r·pkr·(r1-r2)), where r,r1,r2∈RZN. During Step (2), AW decrypts ξ′ using sku as follows:(4)ζ=m1·m2-1r·pkr·r1-r2gsku·r·r1-r2modN=m1·m2-1rmodN.Since r is randomly selected in ZN, ζ is a random value if and only if m1≠m2. For m1=m2, it is obvious to infer that ζ=1. Thus, if AW obtains ζ=1, the returned value ρ is set to be true (denoted by T); otherwise, ρ is false (denoted by F). It is worth noting that neither m1,m2 nor the intermediate result m1/m2 is revealed to the cloud during execution ofSET.


### 5.1.4. Secure Squared Euclidean Distance (SSED) Protocol

Fork-means algorithm, we use squared Euclidean distance to measure the distance between the data record and cluster centroid, denoted by ti-μj2, supposing that EW holds the ciphertext of ith data record ti, and the ciphertext of jth cluster centroid μj, while AW holds the secret key sku, for 1≤i≤L and 1≤j≤k.Note thatμj is a vector composed of m attributes which may be rational numbers. However, the ring ZN does not support rational division operation, so a new form of expression is required to represent the cluster center. Let sj,cj¯ denote the new form of cluster center, where sj and cj¯ represent the sum vector and the total number of records belonging to cj, respectively. It is easily observed that sj=Σh=1L(Vh,j·th)∈ZNm and cj¯=Σh=1LVh,j∈ZN. Furthermore, Ωi,j is defined as the scaled squared distance between ti and μj, which satisfies ti-μj=Ωi,j/cj¯. Thus, Ωi,j can be calculated as follows:(5)Ωi,j=ti-μj·cj¯2=∑h=1mtih-sjhcj2·cj¯2=∑h=1mcj¯·tih-sjh2,where i∈[1,L], j∈[1,k], and m is the dimension size.Taking encrypted record[ti] and encrypted center [μj] as inputs, EW and AW jointly executeSSED by invokingSA and output encryption of squared Euclidean distance [d(i,j)], in which [ti]=Encpku(ti), [μj]=Encpku(sj),Encpku(cj¯), and [d(i,j)]=Encpku(Ωi,j),Encpku(cj¯). TheSSED protocol should reveal neither the contents of ti and μj nor the Euclidean distance d(i,j) between them to cloud servers. Since implementation ofSSED is straightforward bySA scheme, the design details are omitted.


### 5.1.5. Secure Squared Distance Comparison (SSDC) Protocol

Suppose that EW holds[d(i,a),d(i,b)] and AW holds sku, where i∈[1,L], a,b∈[1,k], a≠b. Apart from these, EW also has encrypted secrets associated with the distances, that is, sa′,sb′. The output ofSSDC is the encrypted minimum squared distance and its corresponding secret. Since our encryption scheme is probabilistic and does not preserve the order of messages, EW and AW should jointly compute the minimum without revealing Encpku(Ωi,a),Encpku(ca¯), Encpku(Ωi,b),Encpku(cb¯), and sa, as well as sb, to both servers.Our key idea is to compute the fraction value between the two squared Euclidean distances, based on which AW is able to judge its relationship and returns EW as an encrypted identifier that indicates the minimum value. The fraction between the two squared Euclidean distances can be calculated as follows:(6)ti-μa2ti-μb2=Ωi,aca¯2·Ωi,bcb¯2-1=Ωi,a·ca¯2Ωi,b·ca¯2=λ.Since Ωi,a·cb¯2 and Ωi,b·ca¯2 are integers within ZN, the ratio λ may be a rational value in Q, according to (6). It can be observed that if ⌊λ⌋<1 (· truncates the decimal fraction while keeping the integer part), we deduce that ti-μa2<ti-μb2; otherwise, ti-μa2≥ti-μb2. The overall steps ofSSDC are given in Algorithm 4.Algorithm 4:SSDC({[d(i,a)],sa′},{[d(i,b)],sb′})→{[dmin],smin′}.
Require:  EW has two encrypted squared distances along with their corresponding encrypted secrets, i.e., ([d(i,a)],sa′)
([d(i,b)],sb′), while AW holds secret key sku, where [d(i,a)]=Encpku(Ωi,a),Encpku(ca¯),
[d(i,b)]=Encpku(Ωi,b),Encpku(cb¯), sa′=Encpku(sa), sb′=Encpku(sb).
(1) EW:
(a) Generate a random numbers∈RZ, two non-zero random numbers r1,r2∈RZN;
(b) ComputeE1←Encpku(Ωi,a)×Encpku(cb¯)×Encpku(r1);
(c) ComputeE2←Encpku(Ωi,a)×Encpku(ca¯)×Encpku(r1);
(d)ifsmod2==1then
(i) Computeτ1←E1r2modN;
(ii) Computeτ2←E2r2modN;
(e)else
(i) Computeτ1←E2r2modN;
(ii) Computeτ2←E1r2modN;
(f) Sendτ1,τ2 to AW;
(2) AW:
(a) Decryptηi←uDec(sku,τi), for i=1,2;
(b) Computeδ←η1/η2;
(c)ifδ==0then
(i) Computeσ←2;
(d)else ifδ>=1then
(i) Computeσ←1;
(e) Encryptσ′←Enc(pku,σ); Send σ′ to EW;
(3) EW:
(a)ifsmod2==1then
(i) ComputeEncpku(Ωmin)←ComputeMin(Encpku(Ωi,a),Encpku(Ωi,b),σ′);
(ii) ComputeEncpku(cmin¯)←ComputeMin(Encpku(ca¯),Encpku(cb¯),σ′);
(iii) ComputeEncpku(smin)←ComputeMin(Encpku(sa),Encpku(sb),σ′);
(b)else
(i) ComputeEncpku(Ωmin)←ComputeMin(Encpku(Ωi,b),Encpku(Ωi,a),σ′);
(ii) ComputeEncpku(cmin¯)←ComputeMin(Encpku(cb¯),Encpku(ca¯),σ′);
(iii) ComputeEncpku(smin)←ComputeMin(Encpku(sb),Encpku(sa),σ′);
(4)return([dmin],smin′)←(Encpku(Ωmin),Encpku(cmin¯),Encpku(smin));To begin with, EW computes encryptions of randomized distances, that is,τ1,τ2. It can be verified that τ1=Encpkur1·Ωi,a·cb¯r2 and τ2=Encpkur1·Ωi,b·ca¯r2. During Step (2), AW obtains η1,η2 through decrypting τ1,τ2 with sku. Next, it calculates η1/η2 in the rational field.(7)η1η2=r1·Ωi,a·cb¯2r2r1·Ωi,b·ca¯2r2=Ωi,a·cb¯2Ωi,b·ca¯2r2=λr2.From (7), it is easy to infer that AW locates the minimum value by δ=(λ)r2, for the blinding factor r2 does not alter the relationship between ti-μa2 and ti-μb2. If ⌊δ⌋=0, it means η1<η2 and AW assigns the indicator σ′ to be Encpku(2); otherwise, η1≥η2 and σ′=Encpku(1). One may prefer to use Encpku(1) and Encpku(0) to represent the indicator, which is more straightforward, whereas it is not secure to utilize encryption of “0”, because C2=0·pkrmodN=0, in which Encpku(0)=(C1,C2). In that case, EW can obviously infer that the encrypted message is zero by observing the ciphertext part.During Step (3), EW takes the receivedσ and encrypted squared distances as well as secrets as inputs and computes the target minimum values. It invokes a secure subroutine calledComputeMin, as shown in Algorithm 5. The correctness ofSSDC protocol is proven as follows. Let us take Encpku(Ωmin) as an example; if smod2=1, EW and AW jointly executeComputeMin and get the following:(8)EncpkuΩmin=Encpkuσ·Ωi,a+2·Ωi,b-Ωi,a-σ·Ωi,b=Encpkuσ-1·Ωi,a+2-σ·Ωi,b.Apparently, it can be observed that if σ=2, then we have Encpku(Ωmin)=Encpku(Ωi,a); otherwise, Encpku(Ωmin)=Encpku(Ωi,b). Likewise, Encpku(cmin¯) and Encpku(smin) are calculated in a similar way.Algorithm 5:ComputeMin(v′,w′,φ′)→min(u′,v′).
Require:  EW holds two encrypted values v′,w′, and an encrypted identifier φ′, where v′=Encpku(v), w′=Encpku(w),
φ′=Encpku(φ); AW has sku;
(1) EW computes Encpku(v⋅φ)←Encpku(v)×Encpku(φ);
(2) EW computes Encpku(2⋅w)←Encpku(2)×Encpku(w);
(3) EW computes Encpku(w⋅φ)←Encpku(w)×Encpku(φ);
(4) EW and AW jointly compute Encpku(v⋅φ+2⋅w)←SA(Encpku(v⋅φ),Encpku(2⋅w));
(5) EW and AW jointly compute Encpku(v+w⋅φ)←SA(Encpku(v),Encpku(w⋅φ));
(6) EW computes Encpku(-v-w⋅φ)←Encpku(v+w⋅φ)×Encpku(-1);
(7) EW and AW jointly compute Encpku(v⋅φ+2⋅w-v-w⋅φ)←SA(Encpku(v⋅φ+2⋅w),Encpku(-v-w⋅φ));
(8)returnmin(u′,v′)←Encpku(v⋅φ+2⋅w-v-w⋅φ);


### 5.1.6. Secure Minimum amongk Squared Distances (SMkSD) Protocol

We assume that EW holds a set of encrypted squared Euclidean distances[d(i,1)],…,[d(i,k)], where [d(i,j)]=Encpku(Ωi,j),μj¯, i∈[1,L], j∈[1,k], and AW holds the secret key sku. Besides, EW also has the encryptions of secrets corresponding to their distances, that is, s1′,…,sk′. The goal ofSMkSD is to compute the encryption of the shortest squared distance along with its encrypted secret, denoted by [dmin],smin′, respectively. To executeSMkSD, we compute the minimum by utilizingSSDC with two inputs each time in a sequential fashion. The computation complexity of this algorithm is O(k). Also, it can be executed in a binary tree hierarchy like SMINn in [15], which takes at most ⌈log2⁡k⌉ iterations.


### 5.1.7. Secure Index to Bitmap Conversion (SIBC) Protocol

Given that EW has the encrypted index of the closest cluster denoted byEncpku(ν) (ν∈[1,k]), and AW holds the private key sku, the output ofSIBC is a bitmap vector Λ composed of k encrypted elements. During execution ofSIBC, neither the index nor the bitmap should be revealed to both servers. If i=ν∧i∈[1,k],SIBC denotes Λ[i]=Encpku(2); otherwise, Λ[i]=Encpku(1). This indicates that the position of Encpku(2) in Λ is the index of the nearest cluster. The typical form of Λ is as follows: (9)Λ=Encpku1,…,Encpku1︷1⇀ν-1,Encpku2︷ν,Encpku1,…,Encpku1︷ν+1⇀k. The complete steps are presented in Algorithm 6.Algorithm 6:SIBC(Encpku(ν))→Λ.
Require:  EW holds encrypted index Encpku(ν); AW has secret key sku.
(1) EW:
(a)fori=1 to kdo
(i) Generate non-zero random numbersαi,β∈RZN;
(ii) ComputeAi←Encpku(αi)×Enc(pku,i)β;
(iii) ComputeBi←Encpku(αi)×Encpku(ν)β;
(b) Generate a random permutation functionπ;
(c) ComputeΓ′←π(Γ), where Γ={Ai,Bi∣i=1,…,k};
(d) SendΓ′ to AW;
(2) AW:
(a)fori=1 to kdo
(i) DecryptEi←Dec(sku,Ai′), Fi←Dec(sku,Bi′), where Γ′={Ai′,Bi′∣i=1,…,k};
(ii) Computeηi←Ei/Fi;
(iii)ifηi==1then
(A) ComputeW[i]←Encpku(2);
(iv)else
(A) ComputeW[i]←Encpku(1);
(b) SendW to EW;
(3) EW:
(a) ComputeΛ←π-1(W);During Step (1), EW generates nonzero random numbers and uses them to blindi and ν, for 1≤i≤k. It can be verified that Ai=Encpku(αi·(i)β) and Bi=Encpku(αi·(ν)β). For i=1,…,k, Ai,Bi constitutes an ordered set Γ, which is further permutated by a random permutation function π.During Step (2), AW decrypts the permutated setΓ′ and computes the fraction for each part. It is easy to infer the following equation:(10)ηj=EjFj=αi·iβαi·νβ=iνβ,where i,j∈[1,k] and i,j may not be the same. Regardless of β, if i=ν, then we have ηj=1; otherwise, ηj is a random number in Q. Note that AW cannot know the relationship between Ei and Ej for i≠j, since they are randomized by blinding factors. Besides, the ratio Ei/Ej=(αi/αj)·(i/j)β is also a random number. Thus, as long as π is kept confidential, the index of closest cluster is not revealed to AW. In the end, EW recovers the true sequence of Λ by running the inverse permutation π-1(W).Furthermore, it should be emphasized that the method based on (10) can also be used in other scenarios where equality test is required.


### 5.1.8. Secure New Cluster Computation (SNCC) Protocol

Given that EW holds the assignment membership matrixV, the encrypted dataset D′, and target cluster ci, the goal ofSNCC is to calculate the new cluster centroid denoted by [μi], where [μi]=Encpku(si),Encpku(ci¯). During execution ofSNCC, nothing regarding the data record, sum of attributes, and cluster size should be disclosed to cloud servers. The complete steps are shown in Algorithm 7.Algorithm 7:SNCC(V,D′,i)→[μi].
Require:  EW holds the assignment matrix V, the encrypted dataset D′, the cluster id i, while AW has the secret key sku,
whereV=Λ1T,…,ΛLT, D′={Encpkutj,h∣j∈[1,L],h∈[1,m]}, i∈[1,k].
(1) EW:
(a)forh=1 to mdo
(i)forj=1 to Ldo
(A) ComputeHj←Encpku(tj,h)×V[j,i];
(B) ComputeHh′←SA(Hj,Hh′) with AW;
(ii) ComputeSh′←Sh×Encpku(-1), where Sh=∑j=1Ltj,h;
(iii) ComputeEncpku(si,h)←SA(Hh′,Sh′) with AW;
(2) EW:
(a)forj=1 to Ldo
(i) ComputeC←SA(V[j,i],C) with AW;
(b) ComputeEncpku(ci¯)←SA(C,Encpku(-L)) with AW;
(3)return[μi]←〈Encpku(si),Encpku(ci¯)〉;During Step (1), EW computes the encryption of summation for each attribute, that is,Encpku(si,h) for 1≤i≤k and 1≤h≤m. Supposing that V[j,i]=Encpku(vj,i), where vj,i∈{1,2} and j∈[1,L], EW obtains Hj=Encpku(tj,h·vj,i). After L rounds of iterations, the important observation is(11)Encpkusi,h=Encpku∑j=1Ltj,h·vj,i-∑j=1Ltj,h=Encpku∑j=1Ltj,h·vj,i-1.Recall that vj,i=2 means that tj belongs to the cluster ci, while vj,i=1 denotes tj∉cj. Therefore, (11) adds all the records that are assigned to the target cluster. Moreover, Sh only needs to be calculated only once during the entire outsourcing period, for 1≤h≤m.During Step (2), EW and AW jointly compute the encryption of cluster sizeEncpku(ci¯) by invokingSA subprotocol. It can be verified that(12)Encpkuci¯=Encpku∑j=1Lvj,i-L=Encpku∑j=1Lvj,i-1.Obviously, (12) sums up those whose vj,i equals 2 and discards those with vj,i=1, through which the final result is the size of the cluster ci.


## 5.1.1. Secure Ciphertext Transformation (SCT) Protocol

Given that EW holdsEncpkx(m), and AW holds (msk,pky), the goal of theSCT protocol is to transform encrypted message m under public key pkx into another ciphertext under public key pky. During execution ofSCT, the plaintext m should not be revealed to EW or AW; meanwhile the output Encpky(m) is only known to EW. The complete steps are shown in Algorithm 1.Algorithm 1:SCT(Encpkx(m),pky)→Encpky(m).
Require:  EW has Encpkx(m), pkx, and pky; AW has msk, pkx, and pky.
(1) EW:
(a) Generate a random number:r∈RZN, s.t., r<κ-1;
(b) ComputeEncpkx(r⋅m)←Encpkx(m)×Encpkx(r);
(c) SendEncpkx(r⋅m) to AW;
(2) AW:
(a) Decryptr⋅m←mDec(msk,pkx,Encpkx(r⋅m));
(b) EncryptEncpky(r⋅m)←Enc(pky,r⋅m);
(c) SendEncpky(r⋅m) to EW;
(3) EW:
(a) ComputeEncpky(m)←Encpky(r⋅m)×Encpky(r-1);To start with, EW generates a numberr∈RZN, which means that r is randomly picked in ZN. Note that r<κ-1 ensures that r is invertible in ZN due to GCD(r,N)=1. Then we exploit multiplicative homomorphic property of PKC-DD to blind m from AW, even if it is able to decrypt Encpkx(r·m) via using msk. Finally, EW removes the randomness by multiplying the encrypted inverse of r due to Encpky(m)=Encpky(r·m·r-1modN).SCT protocol is especially useful for converting data under different encryption keys into ones under the same key so that EW can perform homomorphic operation.


## 5.1.2. Secure Addition (SA) Protocol

It takesEncpku(m1) and Encpku(m2) held by EW and sku held by AW as inputs. The output is the encrypted addition of m1 and m2, that is, Encpku(m1+m2), which is only known to EW. As the encryption scheme is not additively homomorphic, it requires interactions between EW and AW.To preclude AW from obtainingm1 and m2, a straightforward solution for EW is to blind the inputs with a random value r by multiplying Encpku(r), where r∈RZN and GCD(r,N)=1. Then the encrypted randomized data are sent to AW. Since AW holds the secret key, it is able to get r·m1, r·m2 through decryption. The randomized addition (denoted by ω) is computed by r·m1+r·m2modN. After that, AW encrypts ω and sends it back to EW who can get the desired output by running Encpku(ω)×Encpku(r-1). Nevertheless, it is very possible that partial privacy is revealed to AW. This is because the ratio of inputs can be calculated via m1/m2←m1·r/m2·r, which may be utilized to distinguish inputs. As our threat model assumes the semihonest servers have some background knowledge of dataset distribution, it is effortless for AW to find correlations between encrypted records and known samples. Therefore, to achieve the privacy-preserving guarantees, disclosing input ratio should be prohibited duringSA execution.We propose an enhancedSA protocol still under two-server model, which protects confidentiality of inputs and outputs as well as intermediate results. There are five steps inSA, the details of which are presented in Algorithm 2.Algorithm 2:SA(Encpku(m1),Encpku(m2))→Encpku(m1+m2).
Require:  EW has Encpku(m1) and Encpku(m2); AW has the secret key sku.
(1) EW:
(a) Generate random numbers:r1,r2,r3∈RZN, s.t., ri<κ-1 for 1≤i≤3;
(b) ComputeS1←Encpku(m1)3, and α1←S1×Encpku(r1);
(c) ComputeS2←Encpku(m2)3, and α2←S2×Encpku(r2);
(d) Generate random numbers:ρ1,ρ2,ρ3,ρ4∈RZ, s.t., ρ1+ρ2≡3modN, ρ3+ρ4≡3modN;
(e) ComputeH1←Encpku(m1)2×Encpku(m2), and α3←H1×Encpku(ρ1)×Encpku(r1);
(f) ComputeH2←Encpku(m1)×Encpku(m2)2, and α4←H2×Encpku(ρ3)×Encpku(r2);
(g) Computeα5←H1×Encpku(ρ2)×Encpku(r3), and α6←H2×Encpku(ρ4)×Encpku(r3);
(h) Send{αi∣i=1,…,6} to AW;
(2) AW:
(a) Receive{αi∣i=1,…,6} from AW;
(b) DecryptFi←uDec(sku,αi), for 1≤i≤6;
(c) Computeβ1←F1+F3modN, β2←F2+F4modN, and β3←F5+F6modN;
(d) Encryptβi′←Enc(pku,βi), for 1≤i≤3;
(e) Send{β1′,β2′,β3′} to EW;
(3) EW:
(a) Receive{β1′,β2′,β3′} from EW;
(b) Generate a random number:r4∈RZN, s.t., r4<κ-1;
(c)fori=1 to 3do
(i) ComputeKi←βi′×Encpku(ri-1);
(ii) ComputeKi′←Ki×Encpku(r4);
(d) Send{K1′,K2′,K3′} to AW;
(4) AW:
(a) Receive{K1′,K2′,K3′} from AW;
(b) DecryptLi←uDec(sku,Ki′), for 1≤i≤3;
(c) Computeγ←L1+L2+L3modN;
(d) Encryptγ′←Enc(pku,γ); Send γ′ to EW;
(5) EW:
(a) Receiveγ′ from EW;
(b) Computeχ←γ′×Encpku(r4-1);
(c) Computed←3-1modord(G);
(d) ComputeEncpku(m1+m2)←χdmodN;During Step (1), the cloud EW generates a set of random numbers, namely,{ri∈ZN,ρj∈ZN∣i=1,…,3,j=1,…,4}, and calculates their corresponding encryptions under pku. By exploiting (1), EW computes several intermediate results, such as S1,S2,H1,H2, and outputs α1,…,α6. It can be easily verified that S1=Encpku(m13), S2=Encpku(m23), H1=Encpku(m12·m2), H2=Encpku(m1·m22), α1=Encpku(m13·r1), α2=Encpku(m23·r2), α3=Encpku(m12·m2·ρ1·r1), α4=Encpku(m1·m22·ρ3·r2), α5=Encpku(m12·m2·ρ2·r3), α6=Encpku(m1·m22·ρ4·r3).During Step (2), AW decryptsαi using sku, for 1≤i≤6. It then computes additions: β1,β2,β3 and their corresponding encryptions. It can be verified that β1′=Encpku(m13·r1+m12·m2·ρ1·r1), β2′=Encpku(m23·r2+m1·m22·ρ3·r2), β3′=Encpku(m12·m2·ρ2·r3+m1·m22·ρ4·r3).During Step (3), the blinding factors inβ1′,β2′,β3′ are removed by multiplying the encrypted values of r1-1,r2-1,r3-1. Then, EW generates a random number r4, which is used to blind K1,K2,K3. At Step (4), AW decrypts K1′,K2′,K3′ as L1,L2,L3, and calculates their addition γ. It can be verified that γ′=Encpku(m13·r4+m12·m2·ρ1·r4+m23·r4+m1·m22·ρ3·r4+m12·m2·ρ2·r4+m1·m22·ρ4·r4).In the end of Step (5), EW gets rid of randomness byχ←γ′×Encpku(r4-1). So we can verify that(2)χ=γ′×Encpkur4-1=Encpkum13+ρ1·m12·m2+ρ2·m12·m2+ρ3·m1·m22+ρ4·m1·m22+m23.After that, EW computes the inverse of 3 modulo ord(G). Note that ord(G) can be obtained due to ϕ(N)=p(p-1)(q-1). We have GCD(3,ϕ(N))=1, if p and q are primes of the forms p=2p′+1 and q=2q′+1, where p′ and q′ are also primes, which means that 3-1 exists in the degree domain. The desired output is calculated by Encpku(m1+m2)←χ3-1. The correctness of SA protocol can be proven by the following equation:(3)χ3-1=Encpkum13+ρ1·m12·m2+ρ2·m12·m2+ρ3·m1·m22+ρ4·m1·m22+m233-1=Encpkum13+ρ1+ρ2·m12·m2+ρ3+ρ4·m1·m22+m233-1=Encpkum13+3·m12·m2+3·m1·m22+m233-1=Encpkum1+m233-1=Encpkum1+m2.Executing Algorithm2 requires two rounds of interactions between EW and AW, which incurs more computational and communication overhead than the simple solution. However, it reveals no privacy to both cloud servers. The formal security analysis ofSA is given in Section 6.


## 5.1.3. Secure Equality Test (SET) Protocol

Given that EW holds two encrypted valuesEncpku(m1) and Encpku(m2) while AW holds the secret key sku, the goal ofSET is to test whether m1 and m2 are equal without revealing them to cloud servers. The detailed steps are presented in Algorithm 3.Algorithm 3:SET(Encpku(m1),Encpku(m2))→Tor  F.
Require:  EW holds two encrypted values Encpku(m1) and Encpku(m2); AW holds the secret key sku.
(1) EW:
(a) ComputeA′←A1⋅A2-1modN, B′←B1⋅B2-1modN, where Encpku(m1)=(A1,B1),
Encpku(m2)=(A2,B2);
(b) Generate a random numberr∈RZN that r≠0;
(c) Computeξ′←ξr, where ξ=(A′,B′); Send ξ′ to AW;
(2) AW:
(a) Decryptζ←Dec(sku,ξ′);
(b)ifζ==1thenρ←T;elseρ←F;
(3)returnρ;At the first step, EW computes the fractions of two input ciphertexts. Supposing that(A1,B1)=(gr1,m1·pkr1) and (A2,B2)=(gr2,m2·pkr2), it can be verified that ξ′=(gr·(r1-r2),(m1·m2-1)r·pkr·(r1-r2)), where r,r1,r2∈RZN. During Step (2), AW decrypts ξ′ using sku as follows:(4)ζ=m1·m2-1r·pkr·r1-r2gsku·r·r1-r2modN=m1·m2-1rmodN.Since r is randomly selected in ZN, ζ is a random value if and only if m1≠m2. For m1=m2, it is obvious to infer that ζ=1. Thus, if AW obtains ζ=1, the returned value ρ is set to be true (denoted by T); otherwise, ρ is false (denoted by F). It is worth noting that neither m1,m2 nor the intermediate result m1/m2 is revealed to the cloud during execution ofSET.


## 5.1.4. Secure Squared Euclidean Distance (SSED) Protocol

Fork-means algorithm, we use squared Euclidean distance to measure the distance between the data record and cluster centroid, denoted by ti-μj2, supposing that EW holds the ciphertext of ith data record ti, and the ciphertext of jth cluster centroid μj, while AW holds the secret key sku, for 1≤i≤L and 1≤j≤k.Note thatμj is a vector composed of m attributes which may be rational numbers. However, the ring ZN does not support rational division operation, so a new form of expression is required to represent the cluster center. Let sj,cj¯ denote the new form of cluster center, where sj and cj¯ represent the sum vector and the total number of records belonging to cj, respectively. It is easily observed that sj=Σh=1L(Vh,j·th)∈ZNm and cj¯=Σh=1LVh,j∈ZN. Furthermore, Ωi,j is defined as the scaled squared distance between ti and μj, which satisfies ti-μj=Ωi,j/cj¯. Thus, Ωi,j can be calculated as follows:(5)Ωi,j=ti-μj·cj¯2=∑h=1mtih-sjhcj2·cj¯2=∑h=1mcj¯·tih-sjh2,where i∈[1,L], j∈[1,k], and m is the dimension size.Taking encrypted record[ti] and encrypted center [μj] as inputs, EW and AW jointly executeSSED by invokingSA and output encryption of squared Euclidean distance [d(i,j)], in which [ti]=Encpku(ti), [μj]=Encpku(sj),Encpku(cj¯), and [d(i,j)]=Encpku(Ωi,j),Encpku(cj¯). TheSSED protocol should reveal neither the contents of ti and μj nor the Euclidean distance d(i,j) between them to cloud servers. Since implementation ofSSED is straightforward bySA scheme, the design details are omitted.


## 5.1.5. Secure Squared Distance Comparison (SSDC) Protocol

Suppose that EW holds[d(i,a),d(i,b)] and AW holds sku, where i∈[1,L], a,b∈[1,k], a≠b. Apart from these, EW also has encrypted secrets associated with the distances, that is, sa′,sb′. The output ofSSDC is the encrypted minimum squared distance and its corresponding secret. Since our encryption scheme is probabilistic and does not preserve the order of messages, EW and AW should jointly compute the minimum without revealing Encpku(Ωi,a),Encpku(ca¯), Encpku(Ωi,b),Encpku(cb¯), and sa, as well as sb, to both servers.Our key idea is to compute the fraction value between the two squared Euclidean distances, based on which AW is able to judge its relationship and returns EW as an encrypted identifier that indicates the minimum value. The fraction between the two squared Euclidean distances can be calculated as follows:(6)ti-μa2ti-μb2=Ωi,aca¯2·Ωi,bcb¯2-1=Ωi,a·ca¯2Ωi,b·ca¯2=λ.Since Ωi,a·cb¯2 and Ωi,b·ca¯2 are integers within ZN, the ratio λ may be a rational value in Q, according to (6). It can be observed that if ⌊λ⌋<1 (· truncates the decimal fraction while keeping the integer part), we deduce that ti-μa2<ti-μb2; otherwise, ti-μa2≥ti-μb2. The overall steps ofSSDC are given in Algorithm 4.Algorithm 4:SSDC({[d(i,a)],sa′},{[d(i,b)],sb′})→{[dmin],smin′}.
Require:  EW has two encrypted squared distances along with their corresponding encrypted secrets, i.e., ([d(i,a)],sa′)
([d(i,b)],sb′), while AW holds secret key sku, where [d(i,a)]=Encpku(Ωi,a),Encpku(ca¯),
[d(i,b)]=Encpku(Ωi,b),Encpku(cb¯), sa′=Encpku(sa), sb′=Encpku(sb).
(1) EW:
(a) Generate a random numbers∈RZ, two non-zero random numbers r1,r2∈RZN;
(b) ComputeE1←Encpku(Ωi,a)×Encpku(cb¯)×Encpku(r1);
(c) ComputeE2←Encpku(Ωi,a)×Encpku(ca¯)×Encpku(r1);
(d)ifsmod2==1then
(i) Computeτ1←E1r2modN;
(ii) Computeτ2←E2r2modN;
(e)else
(i) Computeτ1←E2r2modN;
(ii) Computeτ2←E1r2modN;
(f) Sendτ1,τ2 to AW;
(2) AW:
(a) Decryptηi←uDec(sku,τi), for i=1,2;
(b) Computeδ←η1/η2;
(c)ifδ==0then
(i) Computeσ←2;
(d)else ifδ>=1then
(i) Computeσ←1;
(e) Encryptσ′←Enc(pku,σ); Send σ′ to EW;
(3) EW:
(a)ifsmod2==1then
(i) ComputeEncpku(Ωmin)←ComputeMin(Encpku(Ωi,a),Encpku(Ωi,b),σ′);
(ii) ComputeEncpku(cmin¯)←ComputeMin(Encpku(ca¯),Encpku(cb¯),σ′);
(iii) ComputeEncpku(smin)←ComputeMin(Encpku(sa),Encpku(sb),σ′);
(b)else
(i) ComputeEncpku(Ωmin)←ComputeMin(Encpku(Ωi,b),Encpku(Ωi,a),σ′);
(ii) ComputeEncpku(cmin¯)←ComputeMin(Encpku(cb¯),Encpku(ca¯),σ′);
(iii) ComputeEncpku(smin)←ComputeMin(Encpku(sb),Encpku(sa),σ′);
(4)return([dmin],smin′)←(Encpku(Ωmin),Encpku(cmin¯),Encpku(smin));To begin with, EW computes encryptions of randomized distances, that is,τ1,τ2. It can be verified that τ1=Encpkur1·Ωi,a·cb¯r2 and τ2=Encpkur1·Ωi,b·ca¯r2. During Step (2), AW obtains η1,η2 through decrypting τ1,τ2 with sku. Next, it calculates η1/η2 in the rational field.(7)η1η2=r1·Ωi,a·cb¯2r2r1·Ωi,b·ca¯2r2=Ωi,a·cb¯2Ωi,b·ca¯2r2=λr2.From (7), it is easy to infer that AW locates the minimum value by δ=(λ)r2, for the blinding factor r2 does not alter the relationship between ti-μa2 and ti-μb2. If ⌊δ⌋=0, it means η1<η2 and AW assigns the indicator σ′ to be Encpku(2); otherwise, η1≥η2 and σ′=Encpku(1). One may prefer to use Encpku(1) and Encpku(0) to represent the indicator, which is more straightforward, whereas it is not secure to utilize encryption of “0”, because C2=0·pkrmodN=0, in which Encpku(0)=(C1,C2). In that case, EW can obviously infer that the encrypted message is zero by observing the ciphertext part.During Step (3), EW takes the receivedσ and encrypted squared distances as well as secrets as inputs and computes the target minimum values. It invokes a secure subroutine calledComputeMin, as shown in Algorithm 5. The correctness ofSSDC protocol is proven as follows. Let us take Encpku(Ωmin) as an example; if smod2=1, EW and AW jointly executeComputeMin and get the following:(8)EncpkuΩmin=Encpkuσ·Ωi,a+2·Ωi,b-Ωi,a-σ·Ωi,b=Encpkuσ-1·Ωi,a+2-σ·Ωi,b.Apparently, it can be observed that if σ=2, then we have Encpku(Ωmin)=Encpku(Ωi,a); otherwise, Encpku(Ωmin)=Encpku(Ωi,b). Likewise, Encpku(cmin¯) and Encpku(smin) are calculated in a similar way.Algorithm 5:ComputeMin(v′,w′,φ′)→min(u′,v′).
Require:  EW holds two encrypted values v′,w′, and an encrypted identifier φ′, where v′=Encpku(v), w′=Encpku(w),
φ′=Encpku(φ); AW has sku;
(1) EW computes Encpku(v⋅φ)←Encpku(v)×Encpku(φ);
(2) EW computes Encpku(2⋅w)←Encpku(2)×Encpku(w);
(3) EW computes Encpku(w⋅φ)←Encpku(w)×Encpku(φ);
(4) EW and AW jointly compute Encpku(v⋅φ+2⋅w)←SA(Encpku(v⋅φ),Encpku(2⋅w));
(5) EW and AW jointly compute Encpku(v+w⋅φ)←SA(Encpku(v),Encpku(w⋅φ));
(6) EW computes Encpku(-v-w⋅φ)←Encpku(v+w⋅φ)×Encpku(-1);
(7) EW and AW jointly compute Encpku(v⋅φ+2⋅w-v-w⋅φ)←SA(Encpku(v⋅φ+2⋅w),Encpku(-v-w⋅φ));
(8)returnmin(u′,v′)←Encpku(v⋅φ+2⋅w-v-w⋅φ);


## 5.1.6. Secure Minimum amongk Squared Distances (SMkSD) Protocol

We assume that EW holds a set of encrypted squared Euclidean distances[d(i,1)],…,[d(i,k)], where [d(i,j)]=Encpku(Ωi,j),μj¯, i∈[1,L], j∈[1,k], and AW holds the secret key sku. Besides, EW also has the encryptions of secrets corresponding to their distances, that is, s1′,…,sk′. The goal ofSMkSD is to compute the encryption of the shortest squared distance along with its encrypted secret, denoted by [dmin],smin′, respectively. To executeSMkSD, we compute the minimum by utilizingSSDC with two inputs each time in a sequential fashion. The computation complexity of this algorithm is O(k). Also, it can be executed in a binary tree hierarchy like SMINn in [15], which takes at most ⌈log2⁡k⌉ iterations.


## 5.1.7. Secure Index to Bitmap Conversion (SIBC) Protocol

Given that EW has the encrypted index of the closest cluster denoted byEncpku(ν) (ν∈[1,k]), and AW holds the private key sku, the output ofSIBC is a bitmap vector Λ composed of k encrypted elements. During execution ofSIBC, neither the index nor the bitmap should be revealed to both servers. If i=ν∧i∈[1,k],SIBC denotes Λ[i]=Encpku(2); otherwise, Λ[i]=Encpku(1). This indicates that the position of Encpku(2) in Λ is the index of the nearest cluster. The typical form of Λ is as follows: (9)Λ=Encpku1,…,Encpku1︷1⇀ν-1,Encpku2︷ν,Encpku1,…,Encpku1︷ν+1⇀k. The complete steps are presented in Algorithm 6.Algorithm 6:SIBC(Encpku(ν))→Λ.
Require:  EW holds encrypted index Encpku(ν); AW has secret key sku.
(1) EW:
(a)fori=1 to kdo
(i) Generate non-zero random numbersαi,β∈RZN;
(ii) ComputeAi←Encpku(αi)×Enc(pku,i)β;
(iii) ComputeBi←Encpku(αi)×Encpku(ν)β;
(b) Generate a random permutation functionπ;
(c) ComputeΓ′←π(Γ), where Γ={Ai,Bi∣i=1,…,k};
(d) SendΓ′ to AW;
(2) AW:
(a)fori=1 to kdo
(i) DecryptEi←Dec(sku,Ai′), Fi←Dec(sku,Bi′), where Γ′={Ai′,Bi′∣i=1,…,k};
(ii) Computeηi←Ei/Fi;
(iii)ifηi==1then
(A) ComputeW[i]←Encpku(2);
(iv)else
(A) ComputeW[i]←Encpku(1);
(b) SendW to EW;
(3) EW:
(a) ComputeΛ←π-1(W);During Step (1), EW generates nonzero random numbers and uses them to blindi and ν, for 1≤i≤k. It can be verified that Ai=Encpku(αi·(i)β) and Bi=Encpku(αi·(ν)β). For i=1,…,k, Ai,Bi constitutes an ordered set Γ, which is further permutated by a random permutation function π.During Step (2), AW decrypts the permutated setΓ′ and computes the fraction for each part. It is easy to infer the following equation:(10)ηj=EjFj=αi·iβαi·νβ=iνβ,where i,j∈[1,k] and i,j may not be the same. Regardless of β, if i=ν, then we have ηj=1; otherwise, ηj is a random number in Q. Note that AW cannot know the relationship between Ei and Ej for i≠j, since they are randomized by blinding factors. Besides, the ratio Ei/Ej=(αi/αj)·(i/j)β is also a random number. Thus, as long as π is kept confidential, the index of closest cluster is not revealed to AW. In the end, EW recovers the true sequence of Λ by running the inverse permutation π-1(W).Furthermore, it should be emphasized that the method based on (10) can also be used in other scenarios where equality test is required.


## 5.1.8. Secure New Cluster Computation (SNCC) Protocol

Given that EW holds the assignment membership matrixV, the encrypted dataset D′, and target cluster ci, the goal ofSNCC is to calculate the new cluster centroid denoted by [μi], where [μi]=Encpku(si),Encpku(ci¯). During execution ofSNCC, nothing regarding the data record, sum of attributes, and cluster size should be disclosed to cloud servers. The complete steps are shown in Algorithm 7.Algorithm 7:SNCC(V,D′,i)→[μi].
Require:  EW holds the assignment matrix V, the encrypted dataset D′, the cluster id i, while AW has the secret key sku,
whereV=Λ1T,…,ΛLT, D′={Encpkutj,h∣j∈[1,L],h∈[1,m]}, i∈[1,k].
(1) EW:
(a)forh=1 to mdo
(i)forj=1 to Ldo
(A) ComputeHj←Encpku(tj,h)×V[j,i];
(B) ComputeHh′←SA(Hj,Hh′) with AW;
(ii) ComputeSh′←Sh×Encpku(-1), where Sh=∑j=1Ltj,h;
(iii) ComputeEncpku(si,h)←SA(Hh′,Sh′) with AW;
(2) EW:
(a)forj=1 to Ldo
(i) ComputeC←SA(V[j,i],C) with AW;
(b) ComputeEncpku(ci¯)←SA(C,Encpku(-L)) with AW;
(3)return[μi]←〈Encpku(si),Encpku(ci¯)〉;During Step (1), EW computes the encryption of summation for each attribute, that is,Encpku(si,h) for 1≤i≤k and 1≤h≤m. Supposing that V[j,i]=Encpku(vj,i), where vj,i∈{1,2} and j∈[1,L], EW obtains Hj=Encpku(tj,h·vj,i). After L rounds of iterations, the important observation is(11)Encpkusi,h=Encpku∑j=1Ltj,h·vj,i-∑j=1Ltj,h=Encpku∑j=1Ltj,h·vj,i-1.Recall that vj,i=2 means that tj belongs to the cluster ci, while vj,i=1 denotes tj∉cj. Therefore, (11) adds all the records that are assigned to the target cluster. Moreover, Sh only needs to be calculated only once during the entire outsourcing period, for 1≤h≤m.During Step (2), EW and AW jointly compute the encryption of cluster sizeEncpku(ci¯) by invokingSA subprotocol. It can be verified that(12)Encpkuci¯=Encpku∑j=1Lvj,i-L=Encpku∑j=1Lvj,i-1.Obviously, (12) sums up those whose vj,i equals 2 and discards those with vj,i=1, through which the final result is the size of the cluster ci.


## 5.2. The Complete PPCOM Protocol

In this subsection, we present our proposed PPCOM protocol for the standardk-means algorithm which works in the distributed cloud environments.The primary goal of PPCOM is to schedule a group of cloud servers to perform clustering task over the joint datasets encrypted under multiple keys, meanwhile no privacy of data records, intermediate results, and final clusters should be revealed to the semihonest servers. In order to improve the overall performance, we leverage a large-scale data processing engine called Spark [38]. It develops a data structure called the resilient distributed dataset (RDD) for data parallelism and fault-tolerance, which facilitates iterative algorithms in machine learning. Though it provides a scalable machine learning library—MLlib—which includes k-means algorithm [39], it does not take privacy protection into account and cannot process encrypted data either. Therefore, it is essential to combine our proposed building blocks in Section 5.1 and Spark computing framework to design PPCOM.PPCOM is composed of four stages, that is, Data Uploading, Ciphertext Transformation, Clustering Computation, and Result Retrieval, the details of which are described in the following.


### 5.2.1. Data Uploading Stage

We assume that all data records should have been preprocessed by data owners. One essential preprocessing step is to normalize data values, because different attributes have different value domains, which possibly leads to the case that those attribute values whose domain is large have greater impacts on accuracy of distance-based clustering. Normalization enables records to fall into the common range by endowing all attributes with equal weights. In this paper, we adopt Mix-Max Normalization [40]. Suppose that attribute A owns s observed values v1,v2,…,vs and [minA,maxA] is the range of A, while [new_minA,new_maxA] is the target range. Mix-Max Normalization maps vi into vi′ in [new_minA,new_maxA] by calculating the following equation:(13)vi′=vi-minAmaxA-minAnew_maxA-new_minA+new_minA.After the preprocessing step,DOi encrypts its dataset Di with pki by calculating Enc(pki,tj,hi) for i∈[1,n]. Let tj,hi denote the hth attribute value of jth record tji in Di for h∈[1,m] and j∈[1,L]. Di′ denotes the encryption of Di. After all DOs complete uploading their datasets to EWs, the cloud aggregates the distributed datasets into a joint database D′=⋃i=1nDi′. Under this circumstance, DOi is still able to retrieve its data and decrypt it with its private key ski, whereas DOi cannot decrypt Dj without corresponding ski for i≠j.


### 5.2.2. Ciphertext Transformation Stage

Upon receiving clustering request from QC, EWs initiate ciphertext transformation procedure which aims at converting ciphertexts underpki into encryptions under the unified key pku, for i∈[1,n]. EW first replicates D′ into Dr′ to ensure DOs’ accessibility to their original dataset. ThenSCT subprotocol is executed to output the converted dataset (denoted by Du′). This stage is important for two reasons: (1) EW is able to perform homomorphic operation merely under the same public key; (2) user-decryption is much more efficient than master decryption.


### 5.2.3. Clustering Computation Stage

With all the converted recordsEncpku(ti,j), for i∈[1,L], j∈[1,m], the objective of this stage is to compute the cluster centroids [μ1],…,[μk] and the membership matrix VL×k without compromising privacy. The outsourcing process is not only protected by the proposed secure building blocks, but also accelerated by Spark framework. The stage includes four steps, namely, Job Assignment, Map Execution, Reduce Execution, and Update Judgement, as shown in Figure 2.Figure 2
PPCOM under Spark framework.Step 1 (Job Assignment).
Firstly, CSPs selectς minimum computing units (denoted by MCUs). Each MCU is composed of one server from {EW1,…,EWθ} and one from {AW1,…,AWϑ}; that is, MCU={EW,AW}. Obviously, MCU is able to perform cryptographic building blocks on its own. Since the workload of AW is relatively light compared to EW, it is preferable to share one AW within several MCUs to maximize resource usage. We assume that every cloud node possesses sufficient storage and computational power for its assigned job. The set {MCU1,…,MCUς} is divided into two disjoint sets, that is, Map set and Reduce set. Without loss of generality, Map consists of MCU1,…,MCUf, while Reduce comprises MCUf+1,…,MCUf+k+1. Then Du′ is divided into f uniformly distributed partitions P1,…,Pf, which are transferred to their corresponding MCU nodes in Map set. In this paper, we assume that the k initial cluster centers are chosen by DOs in advance and they are also encrypted. ∀i∈[1,f], Map[i] is aware of the initial cluster centroid set U={[μ1],…,[μk]}, where [μj]=Encpku(sj),Encpku(cj¯), for 1≤j≤k.Step 2 (Map Execution).
GivenPi and U as inputs, Map[i] (i∈[1,f]) outputs a key-value table Ti, in which the key is the record and the value is the encryption of bitmap that indicates the closest cluster. Suppose that Pi includes z data records [t1],…,[tz]. Here, [tj] (j∈[1,z]) is an m-dimension vector Encpku(tj,1),…,Encpku(tj,m).
As presented in Algorithm8, each MCU in Map executes the following steps in parallel: (1) computes the encryption of squared Euclidean distance between [tj] and cluster center [μh], for 1≤j≤z and 1≤h≤k (Steps (1)–(5)); (2) computes the encrypted index of the minimum among k distances for each record by callingSMkSD (Step (6)); (3) converts the index into an encrypted bitmap viaSIBC scheme (Step (7)). The final output for Map[i] is table Ti with z entries. Each entry consists of a data record as the key and its corresponding assignment bitmap as value.Algorithm 8:Map(P1,…,Pf,U)→{T1,…,Tf}.
Require:  Map MCUs have datasets P1,…,Pf and cluster centroid set U.
(1)  ∀i∈[1,f], Map[i] concurrently executes:
(2)forj=1 to zdo
(3)  forh=1 to kdo
(4)    {ComputethesquaredEuclideandistance}
[d(j,h)]←SSED([tj],[μh]), where [d(j,h)]=Encpku(Ωj,h),ch¯;
(5)   end for
(6)   {Computetheindexofminimumamongkdistances}
{[dmin],smin′}←SMkSD({[d(j,1)],s1′},…,{[d(j,k)],sk′}), where sν′=Encpku(ν), for ν∈[1,k];
(7)   {Converttheindexintoencryptedvector}
Λj←SIBC(smin′);
(8)   keyj←[tj] and valuej←Λj;
(9)end for
(10)returnTi={key1,value1,…,keyz,valuez} for i=1,…,f;Step 3 (Reduce Execution).
Taking{T1,…,Tf} from Map MCUs and the aggregated dataset Du′ as inputs, Reduce[i] computes the cluster center for ci based on the assignment membership matrix V. The major steps are presented in Algorithm 9. It can be observed that each MCU in Reduce concurrently executes the following: (1) converges the assignment vectors in {T1,…,Tf} into the complete membership matrix V (Step (4)); (2) computes the new cluster center for the target cluster by invokingSNCC (Step (7)). The final output for Reduce[i] is the encrypted centroid [μi] for ci and the matrix V.Algorithm 9:Reduce(T1,…,Tf,Du′)→{U,V}.
Require:  Reduce MCUs have T1,…,Tf and the aggregated dataset Du′.
(1) ∀i∈[1,k], Reducer[i] concurrently executes:
(2)forj=1 to fdo
(3) forh=1 to zdo
(4)   {Convergetheassignmentvectorsintomatrix}
V[(j-1)⋅z+h]←Tj.valueh;
(5) end for
(6)end for
(7) {Computethenewclustercenterforci}
[μi]←SNCC(V,Du′,i);
(8)returnU, V, where U={[μ1],…,[μk]};Step 4 (Update Judgement).
This step is to determine whether the predefined termination condition ofk-means algorithm is satisfied. In this paper, we consider that the membership matrix is not changing as the termination condition. Given that EW holds the previous matrix V and the current matrix V′ and AW holds the key sku, our strategy is to find out whether the elements in V and V′ are equal one by one by utilizingSET subprotocol. Once a mismatch is detected, EW replaces V with V′ and goes to Step 2 of Clustering Computation Stage. Otherwise, these servers continue comparing till the end of matrix. If the outcome is V=V′ which means that the assignment of clusters does not vary any more, EW then terminates the iteration and activates Result Retrieval Stage.


### 5.2.4. Result Retrieval Stage

Since the cluster center setU and assignment matrix V are encrypted under pku, QC cannot decrypt them without sku. Firstly,SCT scheme is invoked to transform the encryption key of U and V from pku to pkQ. After that, QC is able to download them and decrypt the final result with skQ. The final cluster center of ci is recovered by μi←si/ci¯, for i∈[1,k].


## 5.2.1. Data Uploading Stage

We assume that all data records should have been preprocessed by data owners. One essential preprocessing step is to normalize data values, because different attributes have different value domains, which possibly leads to the case that those attribute values whose domain is large have greater impacts on accuracy of distance-based clustering. Normalization enables records to fall into the common range by endowing all attributes with equal weights. In this paper, we adopt Mix-Max Normalization [40]. Suppose that attribute A owns s observed values v1,v2,…,vs and [minA,maxA] is the range of A, while [new_minA,new_maxA] is the target range. Mix-Max Normalization maps vi into vi′ in [new_minA,new_maxA] by calculating the following equation:(13)vi′=vi-minAmaxA-minAnew_maxA-new_minA+new_minA.After the preprocessing step,DOi encrypts its dataset Di with pki by calculating Enc(pki,tj,hi) for i∈[1,n]. Let tj,hi denote the hth attribute value of jth record tji in Di for h∈[1,m] and j∈[1,L]. Di′ denotes the encryption of Di. After all DOs complete uploading their datasets to EWs, the cloud aggregates the distributed datasets into a joint database D′=⋃i=1nDi′. Under this circumstance, DOi is still able to retrieve its data and decrypt it with its private key ski, whereas DOi cannot decrypt Dj without corresponding ski for i≠j.


## 5.2.2. Ciphertext Transformation Stage

Upon receiving clustering request from QC, EWs initiate ciphertext transformation procedure which aims at converting ciphertexts underpki into encryptions under the unified key pku, for i∈[1,n]. EW first replicates D′ into Dr′ to ensure DOs’ accessibility to their original dataset. ThenSCT subprotocol is executed to output the converted dataset (denoted by Du′). This stage is important for two reasons: (1) EW is able to perform homomorphic operation merely under the same public key; (2) user-decryption is much more efficient than master decryption.


## 5.2.3. Clustering Computation Stage

With all the converted recordsEncpku(ti,j), for i∈[1,L], j∈[1,m], the objective of this stage is to compute the cluster centroids [μ1],…,[μk] and the membership matrix VL×k without compromising privacy. The outsourcing process is not only protected by the proposed secure building blocks, but also accelerated by Spark framework. The stage includes four steps, namely, Job Assignment, Map Execution, Reduce Execution, and Update Judgement, as shown in Figure 2.Figure 2
PPCOM under Spark framework.Step 1 (Job Assignment).
Firstly, CSPs selectς minimum computing units (denoted by MCUs). Each MCU is composed of one server from {EW1,…,EWθ} and one from {AW1,…,AWϑ}; that is, MCU={EW,AW}. Obviously, MCU is able to perform cryptographic building blocks on its own. Since the workload of AW is relatively light compared to EW, it is preferable to share one AW within several MCUs to maximize resource usage. We assume that every cloud node possesses sufficient storage and computational power for its assigned job. The set {MCU1,…,MCUς} is divided into two disjoint sets, that is, Map set and Reduce set. Without loss of generality, Map consists of MCU1,…,MCUf, while Reduce comprises MCUf+1,…,MCUf+k+1. Then Du′ is divided into f uniformly distributed partitions P1,…,Pf, which are transferred to their corresponding MCU nodes in Map set. In this paper, we assume that the k initial cluster centers are chosen by DOs in advance and they are also encrypted. ∀i∈[1,f], Map[i] is aware of the initial cluster centroid set U={[μ1],…,[μk]}, where [μj]=Encpku(sj),Encpku(cj¯), for 1≤j≤k.Step 2 (Map Execution).
GivenPi and U as inputs, Map[i] (i∈[1,f]) outputs a key-value table Ti, in which the key is the record and the value is the encryption of bitmap that indicates the closest cluster. Suppose that Pi includes z data records [t1],…,[tz]. Here, [tj] (j∈[1,z]) is an m-dimension vector Encpku(tj,1),…,Encpku(tj,m).
As presented in Algorithm8, each MCU in Map executes the following steps in parallel: (1) computes the encryption of squared Euclidean distance between [tj] and cluster center [μh], for 1≤j≤z and 1≤h≤k (Steps (1)–(5)); (2) computes the encrypted index of the minimum among k distances for each record by callingSMkSD (Step (6)); (3) converts the index into an encrypted bitmap viaSIBC scheme (Step (7)). The final output for Map[i] is table Ti with z entries. Each entry consists of a data record as the key and its corresponding assignment bitmap as value.Algorithm 8:Map(P1,…,Pf,U)→{T1,…,Tf}.
Require:  Map MCUs have datasets P1,…,Pf and cluster centroid set U.
(1)  ∀i∈[1,f], Map[i] concurrently executes:
(2)forj=1 to zdo
(3)  forh=1 to kdo
(4)    {ComputethesquaredEuclideandistance}
[d(j,h)]←SSED([tj],[μh]), where [d(j,h)]=Encpku(Ωj,h),ch¯;
(5)   end for
(6)   {Computetheindexofminimumamongkdistances}
{[dmin],smin′}←SMkSD({[d(j,1)],s1′},…,{[d(j,k)],sk′}), where sν′=Encpku(ν), for ν∈[1,k];
(7)   {Converttheindexintoencryptedvector}
Λj←SIBC(smin′);
(8)   keyj←[tj] and valuej←Λj;
(9)end for
(10)returnTi={key1,value1,…,keyz,valuez} for i=1,…,f;Step 3 (Reduce Execution).
Taking{T1,…,Tf} from Map MCUs and the aggregated dataset Du′ as inputs, Reduce[i] computes the cluster center for ci based on the assignment membership matrix V. The major steps are presented in Algorithm 9. It can be observed that each MCU in Reduce concurrently executes the following: (1) converges the assignment vectors in {T1,…,Tf} into the complete membership matrix V (Step (4)); (2) computes the new cluster center for the target cluster by invokingSNCC (Step (7)). The final output for Reduce[i] is the encrypted centroid [μi] for ci and the matrix V.Algorithm 9:Reduce(T1,…,Tf,Du′)→{U,V}.
Require:  Reduce MCUs have T1,…,Tf and the aggregated dataset Du′.
(1) ∀i∈[1,k], Reducer[i] concurrently executes:
(2)forj=1 to fdo
(3) forh=1 to zdo
(4)   {Convergetheassignmentvectorsintomatrix}
V[(j-1)⋅z+h]←Tj.valueh;
(5) end for
(6)end for
(7) {Computethenewclustercenterforci}
[μi]←SNCC(V,Du′,i);
(8)returnU, V, where U={[μ1],…,[μk]};Step 4 (Update Judgement).
This step is to determine whether the predefined termination condition ofk-means algorithm is satisfied. In this paper, we consider that the membership matrix is not changing as the termination condition. Given that EW holds the previous matrix V and the current matrix V′ and AW holds the key sku, our strategy is to find out whether the elements in V and V′ are equal one by one by utilizingSET subprotocol. Once a mismatch is detected, EW replaces V with V′ and goes to Step 2 of Clustering Computation Stage. Otherwise, these servers continue comparing till the end of matrix. If the outcome is V=V′ which means that the assignment of clusters does not vary any more, EW then terminates the iteration and activates Result Retrieval Stage.


## 5.2.4. Result Retrieval Stage

Since the cluster center setU and assignment matrix V are encrypted under pku, QC cannot decrypt them without sku. Firstly,SCT scheme is invoked to transform the encryption key of U and V from pku to pkQ. After that, QC is able to download them and decrypt the final result with skQ. The final cluster center of ci is recovered by μi←si/ci¯, for i∈[1,k].


## 6. Security Analysis

We first analyze the security of the privacy-preserving building blocks. Since all parties are semihonest, security in this model can be proven under “Real-versus-Ideal” framework [41]: there is an ideal model where all computations are performed by a trusted third party. The protocol is secure if all adversarial behaviors in the real world can be simulated in the ideal world. Considering that the proofs of the proposed building blocks are basically the same, we just take the formal proof ofSA subprotocol as an example.Theorem 1.
TheSA protocol described in Section 4.1 securely computes the addition over ciphertexts by using the PKC-DD cryptosystem in presence of two semihonest but noncolluding cloud servers.Proof.
Since this algorithm is collaboratively completed by EW and AW, we need to prove thatSA is not only secure against adversary AEW corrupting EW, but also against AAW corrupting AW, respectively.(1)
Security againstAEW: in Step (1), the real world view of AEW inSA includes inputs {Encpku(m1),Encpku(m2)}, random values {r1,r2,r3,ρ1,ρ2,ρ3,ρ4}, and outputs {αi,S1,S2,H1,H2∣1≤i≤6}. In Step (2), the real world view includes inputs {β1,β2,β3}, outputs {K1′,K2′,K3′}, and intermediate results {K1,K2,K3,r4}. In Step (3), the real world view is composed of input γ′, outputs {χ,χd}, and a fixed value d. Without the secret key sku, AEW is unable to decrypt those ciphertexts. Thus, we can build a simulator SEW in the ideal world. It generates encryptions of inputs {m^1,m^2,β^1,β^2,β^3,γ^′} and random numbers {r^i,ρ^i∣i=1,…,4} by randomly selecting from ZN. Then, SEW follows the protocol to compute the corresponding outputs. Due to the semantic security of the PKC-DD, it is computationally difficult for AEW to distinguish the views from the real world and the ideal world. Therefore, we can prove that (14)Idealf,SEWEncpkumi≈cRealSA,AEWEncpkumi,where i∈{1,2}. Herein, ≈c means computationally distinguishable.(2)
Security againstAAW: in Step (2), the real world view of AAW includes inputs {αi∣i≤i≤6} and outputs {Fi,βj,βj′∣1≤i≤6,1≤j≤3}. Note that the output values are blinded by random r1,…,r3,ρ1,…,ρ4. Besides, it is extremely hard for AAW to guess the correct ratio, that is, m1/m2. Suppose that ρ1=3+k1N-ρ2 and ρ3=3+k2N-ρ4, where k1,k2∈RZ. There are 8 unknown factors (r1,…,r3,ρ1,…,ρ4,m1/m2), whereas AAW can only set up 6 equations (α1,…,α6) that are not enough to crack m1/m2. As for Step (4), the real world view includes inputs {Ki′∣1≤i≤3} and outputs {Li,γ,γ′∣1≤i≤3}. Note that the inputs are randomized by r4. Therefore, we can build a simulator SAW in the ideal world, which generates random numbers as inputs, that is, {α^i,K^j′∈RZN∣i≤i≤6,1≤j≤3}. SAW then executes the protocol to produce output {β^j′,γ^′∣1≤i≤3} through uDec(·), Enc(·), and modular addition operations. Due to the semantic security of the PKC-DD and randomness of blinding factors, the views of AAW in the real world and ideal world are computationally distinguishable. Therefore, for i∈{1,2}, we have (15)Idealf,SAWEncpkurimi3≈cRealSA,AAWEncpkurimi3.During outsourcing process, cloud servers invoke the proposed building blocks as subroutines and all transmitted data are encrypted for each step. Note that the data records are held by cloud parties without decryption key. The assistant parties with the key can decrypt the received data, but the real data are randomized. Since PKC-DD is semantically secure and blinding factors are randomly selected, nothing regarding the data contents and computed clusters is revealed to the servers. Moreover, the access patterns of which encrypted input denotes the minimum Euclidean distance (as shown inSSDC, Algorithm 4) and of which record is assigned to which cluster are protected from the cloud due to encryption of V (as shown inSNCC, Algorithm 7). By the Composition Theorem [41], the sequential composition of four stages in PPCOM is secure under the semihonest model.Discussions. Note that the order of computing addition viaSA cannot be altered inComputeMin calledSSDC even though the final outcome is the same. Suppose that the clouds choose to compute Encpku(v·φ-v) or Encpku(2·w-φ·w); if the result is Encpku(0), it will inevitably reveal φ=1 or φ=2 to both servers. Similarly, the order of computation steps in Algorithm 7 inSNCC ought to be kept unchanged.


## 7. Performance Analysis

In this section, we analyze the performance of PPCOM protocol from both theoretical and experimental perspectives.


### 7.1. Theoretical Analysis

LetExp, Mul denote the modular exponentiation and multiplication operations, respectively. Let N represent the key size of the double decryption scheme. The encryption of the underlying cryptosystem incurs 2Exp+1Mul. The cost of normal decryption is 1Exp+1Mul, while that of authority decryption is 2Exp+2Mul. Recall that m is the dimension size of a record, and L is size of the joint dataset. The computational and communication overheads for the major building blocks and clustering algorithms in one iteration are given in Table 1. It can be observed that the addition and comparing operations incur a lot of Exp operations at the cost of hiding access patterns. For Data Uploading Stage, it takes each DO 2lmExp+lmMul computational cost and 2lmN bits. The computational overhead of Ciphertext Transformation Stage is 8LmExp+9LmMul while its communication cost is 4LmN. We stress that Stage 1 and Stage 2 of PPCOM protocol are executed only once. These overheads are amortized through a number of iterations. Furthermore, the number of MCU in Map set is closely related to the costs, while L affects the performance of Reduce more significantly (usually L≫m). It is easy to find that the larger the computing cluster is, the less the tasks (z) are distributed to each unit. This is because the k-means jobs can be parallelized under Spark. As for the Update Judgement step, the worst case is to compare every element of the matrix, the computational and communication costs of which are related to L and m.Table 1
Computational and communication costs of primary algorithms.
Algorithm
Computational cost
Communication cost (in bits)
SCT
8Exp  +  9Mul
4
N
SA
51
Exp
+  55Mul
26
N
SET
3
Exp
+  3Mul
2
N
SSDC
478
Exp
+  572Mul
84
N
SIBC
(
8
k
+
2
)
Exp
+  8kMul
6
k
N
Map
k
z
(
51
m
+
486
)
Exp
+  kz(59m+580)Mul
k
z
26
m
+
90
N
Reduce
(
102
m
L
+
51
m
+
51
L
)
Exp
+  (111mL+55m+55L)Mul
52
m
L
+
26
m
+
26
L
N
Update
3
m
L
Exp
+  3mLMul
2
m
L
N


### 7.2. Experimental Analysis

The experiments are conducted on our local cluster, in which each server running CentOS6.5 has Intel Xeon E5-2620 @ 2.10 GHz with 12 GB memory. We implemented all the outsourcing protocols using the Crypto++ 5.6.3 library and Spark framework. In this paper, key size of similar methods (Paillier used in PPODC [15] and BCP encryption in [28]) is 1024 bits, which is commonly acceptable. To achieve the same security level, N of PKC-DD should be 500~600 bits more than RSA modulus [42]. During all tests, we choose the security parameter κ=512, so the key size N=1536.To facilitate comparisons, we use KEGG Metabolic Reaction Network dataset [43]. The dataset includes 65554 instances and 29 attributes. Before clustering, all records are first normalized into integers in [0,1000] to prevent impacts of large unit values as mentioned in Data Uploading Stage of Section 5.2. Note that the first attribute is excluded from tests, since it is just the identifier of pathway. All of the testing records are randomly selected from KEGG dataset.


#### 7.2.1. Privacy-Preserving Building Blocks’ Performance

We first measure the execution time of each privacy-preserving building block on a single server through 1000 times, the average costs of which are shown in Table2. It can be seen that costs of the compound protocol (made up of basic primitives, e.g.,SSED,SMkSD, andSNCC) are relatively high, since they are made up of severalSA operations, which involve many encryptions and decryptions, as well as rounds of interactions to preserve data privacy. This is consistent with theoretical analysis.Table 2
Performance of each subprotocol (1000 times for average).
Subprotocol
Computation
Communication
SA
40.851ms
4.875KB
SET
5.543ms
0.375KB
SSED  (m=20)
766.154ms
88.860KB
SSDC
267.815ms
33.750KB
SMkSD  (k=4)
1.107s
134.997KB
SIBC  (k=4)
49.509ms
4.500KB
SNCC  (L=100, m=20, k=4)
80.364s
9.997MBWe then evaluate the performance ofSCT scheme. Table 3 shows the ciphertext transformation time for varying dataset size (L) inSCT andKeyProd in [28]. It can be seen that the cloud running time grows with increasing value of L. Our scheme executes about 4 times faster thanKeyProd in that PKC-DD works more efficiently than theirs. Besides, we remark that schemes in [28] are designed for basic arithmetic operations under multikey rather than complex mining tasks like k-means algorithm.Table 3
Cloud running time for ciphertexts transformation (inmin).
Subprotocol
L
=
2000
L
=
4000
L
=
6000
L
=
8000
L=10000
SCT
11.6
23.2
35.3
46.5
57.9
KeyProd [28]
43.9
87.9
138.9
175.3
219.4We also compare the cloud running time forSSED andSMkSD with counterpart methods in PPODC [15], respectively. As shown in Figures 3(a) and 3(b), computation time of both grows with increase of dataset size and our schemes outperform PPODC’s. Let w denote the bit length of plaintext message. In Figure 3(b), it is easy to find that, with growth of w, the computation time of PPODC grows more rapidly. It is because ciphertexts have to be decomposed into encryption of bits before comparison in [15].Figure 3
Performance ofSSED andSMkSD with varying size of datasets (L).
(a)
Cloud running time ofSSED
(b)
Cloud running time ofSMkSD


#### 7.2.2. Factors Affecting PPCOM’s Performance

There are three major factors affecting the outsourced performance: (1) the number of clusters (k); (2) the number of parallelized MCUs (f); (3) the size of aggregated dataset (L).First, we evaluate the overhead on cloud servers with varyingk and m when L=2000 and f=8, in comparison with the optimized PPODC with 8 parallelized server pairs. The results are given in Figures 4(a) and 4(b). It can be seen that the computation costs of both protocols grow almost linearly with k and PPCOM protocol outperforms PPODC; for example, when m=10, k=12, the cloud computation time of PPODC is 381.798 min, that is, 4.33 times that of our scheme. The efficiency is gained not only by improved secure primitives, but also by Spark framework. Nevertheless, the communication overhead of PPCOM is relatively high, which is mainly caused by frequent interactions duringSA process. Furthermore, the growth of dimension size also increases the computational and communication overhead of both protocols.Figure 4
Experiment analysis with varying number of clusters (k) in the real dataset.
(a)
Cloud running time
(b)
Cloud communication costNext, we evaluate the overhead on cloud servers with varyingf when k=4,m=20. As shown in Figure 5(a), the computation time decreases with the growth of f. It can be derived that (1) the scaling of parallelized servers can accelerate the outsourced clustering task; (2) it takes PPCOM less computational cost than PPODC to accomplish the same amount of work. Figure 5(b) shows that the communication cost of both schemes remains unchanged regardless of f, because the total amount of clustering task is fixed. However, PPCOM incurs heavier communication overhead to protect privacy and access patterns.Figure 5
Experiment analysis with varying number of parallelized MCUs (f) in the real dataset.
(a)
Cloud running time
(b)
Cloud communication costMoreover, we evaluate the impact ofL on cloud servers’ performance with k=4, m=10. From Figure 6(a), we observe that the running time of both protocols increases with L, as more data need to be clustered. It is obvious that the cost of PPODC grows more sharply than ours. Figure 6(b) shows the computation overhead of Map stage and Reduce stage during execution of PPCOM, respectively. Map stage takes larger proportion of total cost than Reduce, while they scale linearly with L. In addition, the doubled parallelized MCUs save almost 40% of Map execution time.Figure 6
Experiment analysis with varying size of joint datasets (L) from the real dataset.
(a)
Cloud running time
(b)
Running time for Map and Reduce


### 7.3. Comparative Summary

As shown in Table4, we summarize qualitative comparisons with existing outsourced k-means protocols. All protocols are claimed to protect input data privacy. The encryption schemes of first three are constructed on random transformation, such as randomized kernel matrix [11] and random invertible matrices [14, 16]. They were proven to be secure against KSA (known-sample attack) that the attacker knows a set of plain data objects in the dataset, but not the corresponding encrypted values. Yuan and Tian’s work [14] can also defeat LAA (linear analysis attack) introduced by [23]. However, these schemes are weak considering that attacker gets both some data objects and their encryptions. The latter four outsourcing protocols are proposed based on homomorphic encryption techniques, which can resist CPA (chosen plaintext attack). References [12, 13] adopt Liu’s FHE as the underlying encryption scheme, which yet may not be secure enough as illustrated by [18]. Rao et al.’s [15] and our encryption schemes achieve semantic security, relying on hardness of Decisional Composite Residuosity [44] and Diffie-Hellman Problem [30], respectively.Table 4
Comparative summary of existing solutions for outsourcedk-means.
Protocol
Security model
Data privacy protection
Support multikeys
Hide access patterns
No owner involvement
Encrypted distance comparison
Big data engine
Lin’s [11]
KSA
√
×
×
√
√
×
Huang et al.’s [16]
KSA
√
√
×
×
√
×
Yuan and Tian’s [14]
KSA & LAA
√
×
×
×
√
√
Liu et al.’s [12]
CPA
√
×
×
×
√
×
Almutairi et al.’s [13]
CPA
√
×
×
×
×
×
Rao et al.’s [15]
CPA
√
×
√
√
√
×
Ours
CPA
√
√
√
√
√
√From this table, it can be seen that only [16] and ours support computation over encrypted data under multikeys, whereas one drawback in [16] is that they either reveal data owners’ keys to query user or reveal query user’s key to owners. Rao et al.’s [15] and ours hide access patterns by executing clustering in an oblivious way, preventing cloud servers from knowing the assignment membership of encrypted records which may be used to launch inference attack. Several schemes require data owners to participate in the mining process so as to update cluster centroids or to assist similarity comparison, except those from [11, 15] and ours. Almost all works allow the cloud to perform comparison operation between encrypted distances, while approach in [13] adopts a plain updatable matrix to compare. What is more, only Yuan and Tian’s [14] and our researches consider how to integrate big data processing framework into privacy-preserving protocols. As a consequence, our solution achieves the most comprehensive security requirements and feasibility for clustering outsourcing compared with current works.


## 7.1. Theoretical Analysis

LetExp, Mul denote the modular exponentiation and multiplication operations, respectively. Let N represent the key size of the double decryption scheme. The encryption of the underlying cryptosystem incurs 2Exp+1Mul. The cost of normal decryption is 1Exp+1Mul, while that of authority decryption is 2Exp+2Mul. Recall that m is the dimension size of a record, and L is size of the joint dataset. The computational and communication overheads for the major building blocks and clustering algorithms in one iteration are given in Table 1. It can be observed that the addition and comparing operations incur a lot of Exp operations at the cost of hiding access patterns. For Data Uploading Stage, it takes each DO 2lmExp+lmMul computational cost and 2lmN bits. The computational overhead of Ciphertext Transformation Stage is 8LmExp+9LmMul while its communication cost is 4LmN. We stress that Stage 1 and Stage 2 of PPCOM protocol are executed only once. These overheads are amortized through a number of iterations. Furthermore, the number of MCU in Map set is closely related to the costs, while L affects the performance of Reduce more significantly (usually L≫m). It is easy to find that the larger the computing cluster is, the less the tasks (z) are distributed to each unit. This is because the k-means jobs can be parallelized under Spark. As for the Update Judgement step, the worst case is to compare every element of the matrix, the computational and communication costs of which are related to L and m.Table 1
Computational and communication costs of primary algorithms.
Algorithm
Computational cost
Communication cost (in bits)
SCT
8Exp  +  9Mul
4
N
SA
51
Exp
+  55Mul
26
N
SET
3
Exp
+  3Mul
2
N
SSDC
478
Exp
+  572Mul
84
N
SIBC
(
8
k
+
2
)
Exp
+  8kMul
6
k
N
Map
k
z
(
51
m
+
486
)
Exp
+  kz(59m+580)Mul
k
z
26
m
+
90
N
Reduce
(
102
m
L
+
51
m
+
51
L
)
Exp
+  (111mL+55m+55L)Mul
52
m
L
+
26
m
+
26
L
N
Update
3
m
L
Exp
+  3mLMul
2
m
L
N


## 7.2. Experimental Analysis

The experiments are conducted on our local cluster, in which each server running CentOS6.5 has Intel Xeon E5-2620 @ 2.10 GHz with 12 GB memory. We implemented all the outsourcing protocols using the Crypto++ 5.6.3 library and Spark framework. In this paper, key size of similar methods (Paillier used in PPODC [15] and BCP encryption in [28]) is 1024 bits, which is commonly acceptable. To achieve the same security level, N of PKC-DD should be 500~600 bits more than RSA modulus [42]. During all tests, we choose the security parameter κ=512, so the key size N=1536.To facilitate comparisons, we use KEGG Metabolic Reaction Network dataset [43]. The dataset includes 65554 instances and 29 attributes. Before clustering, all records are first normalized into integers in [0,1000] to prevent impacts of large unit values as mentioned in Data Uploading Stage of Section 5.2. Note that the first attribute is excluded from tests, since it is just the identifier of pathway. All of the testing records are randomly selected from KEGG dataset.


### 7.2.1. Privacy-Preserving Building Blocks’ Performance

We first measure the execution time of each privacy-preserving building block on a single server through 1000 times, the average costs of which are shown in Table2. It can be seen that costs of the compound protocol (made up of basic primitives, e.g.,SSED,SMkSD, andSNCC) are relatively high, since they are made up of severalSA operations, which involve many encryptions and decryptions, as well as rounds of interactions to preserve data privacy. This is consistent with theoretical analysis.Table 2
Performance of each subprotocol (1000 times for average).
Subprotocol
Computation
Communication
SA
40.851ms
4.875KB
SET
5.543ms
0.375KB
SSED  (m=20)
766.154ms
88.860KB
SSDC
267.815ms
33.750KB
SMkSD  (k=4)
1.107s
134.997KB
SIBC  (k=4)
49.509ms
4.500KB
SNCC  (L=100, m=20, k=4)
80.364s
9.997MBWe then evaluate the performance ofSCT scheme. Table 3 shows the ciphertext transformation time for varying dataset size (L) inSCT andKeyProd in [28]. It can be seen that the cloud running time grows with increasing value of L. Our scheme executes about 4 times faster thanKeyProd in that PKC-DD works more efficiently than theirs. Besides, we remark that schemes in [28] are designed for basic arithmetic operations under multikey rather than complex mining tasks like k-means algorithm.Table 3
Cloud running time for ciphertexts transformation (inmin).
Subprotocol
L
=
2000
L
=
4000
L
=
6000
L
=
8000
L=10000
SCT
11.6
23.2
35.3
46.5
57.9
KeyProd [28]
43.9
87.9
138.9
175.3
219.4We also compare the cloud running time forSSED andSMkSD with counterpart methods in PPODC [15], respectively. As shown in Figures 3(a) and 3(b), computation time of both grows with increase of dataset size and our schemes outperform PPODC’s. Let w denote the bit length of plaintext message. In Figure 3(b), it is easy to find that, with growth of w, the computation time of PPODC grows more rapidly. It is because ciphertexts have to be decomposed into encryption of bits before comparison in [15].Figure 3
Performance ofSSED andSMkSD with varying size of datasets (L).
(a)
Cloud running time ofSSED
(b)
Cloud running time ofSMkSD


### 7.2.2. Factors Affecting PPCOM’s Performance

There are three major factors affecting the outsourced performance: (1) the number of clusters (k); (2) the number of parallelized MCUs (f); (3) the size of aggregated dataset (L).First, we evaluate the overhead on cloud servers with varyingk and m when L=2000 and f=8, in comparison with the optimized PPODC with 8 parallelized server pairs. The results are given in Figures 4(a) and 4(b). It can be seen that the computation costs of both protocols grow almost linearly with k and PPCOM protocol outperforms PPODC; for example, when m=10, k=12, the cloud computation time of PPODC is 381.798 min, that is, 4.33 times that of our scheme. The efficiency is gained not only by improved secure primitives, but also by Spark framework. Nevertheless, the communication overhead of PPCOM is relatively high, which is mainly caused by frequent interactions duringSA process. Furthermore, the growth of dimension size also increases the computational and communication overhead of both protocols.Figure 4
Experiment analysis with varying number of clusters (k) in the real dataset.
(a)
Cloud running time
(b)
Cloud communication costNext, we evaluate the overhead on cloud servers with varyingf when k=4,m=20. As shown in Figure 5(a), the computation time decreases with the growth of f. It can be derived that (1) the scaling of parallelized servers can accelerate the outsourced clustering task; (2) it takes PPCOM less computational cost than PPODC to accomplish the same amount of work. Figure 5(b) shows that the communication cost of both schemes remains unchanged regardless of f, because the total amount of clustering task is fixed. However, PPCOM incurs heavier communication overhead to protect privacy and access patterns.Figure 5
Experiment analysis with varying number of parallelized MCUs (f) in the real dataset.
(a)
Cloud running time
(b)
Cloud communication costMoreover, we evaluate the impact ofL on cloud servers’ performance with k=4, m=10. From Figure 6(a), we observe that the running time of both protocols increases with L, as more data need to be clustered. It is obvious that the cost of PPODC grows more sharply than ours. Figure 6(b) shows the computation overhead of Map stage and Reduce stage during execution of PPCOM, respectively. Map stage takes larger proportion of total cost than Reduce, while they scale linearly with L. In addition, the doubled parallelized MCUs save almost 40% of Map execution time.Figure 6
Experiment analysis with varying size of joint datasets (L) from the real dataset.
(a)
Cloud running time
(b)
Running time for Map and Reduce


## 7.2.1. Privacy-Preserving Building Blocks’ Performance

We first measure the execution time of each privacy-preserving building block on a single server through 1000 times, the average costs of which are shown in Table2. It can be seen that costs of the compound protocol (made up of basic primitives, e.g.,SSED,SMkSD, andSNCC) are relatively high, since they are made up of severalSA operations, which involve many encryptions and decryptions, as well as rounds of interactions to preserve data privacy. This is consistent with theoretical analysis.Table 2
Performance of each subprotocol (1000 times for average).
Subprotocol
Computation
Communication
SA
40.851ms
4.875KB
SET
5.543ms
0.375KB
SSED  (m=20)
766.154ms
88.860KB
SSDC
267.815ms
33.750KB
SMkSD  (k=4)
1.107s
134.997KB
SIBC  (k=4)
49.509ms
4.500KB
SNCC  (L=100, m=20, k=4)
80.364s
9.997MBWe then evaluate the performance ofSCT scheme. Table 3 shows the ciphertext transformation time for varying dataset size (L) inSCT andKeyProd in [28]. It can be seen that the cloud running time grows with increasing value of L. Our scheme executes about 4 times faster thanKeyProd in that PKC-DD works more efficiently than theirs. Besides, we remark that schemes in [28] are designed for basic arithmetic operations under multikey rather than complex mining tasks like k-means algorithm.Table 3
Cloud running time for ciphertexts transformation (inmin).
Subprotocol
L
=
2000
L
=
4000
L
=
6000
L
=
8000
L=10000
SCT
11.6
23.2
35.3
46.5
57.9
KeyProd [28]
43.9
87.9
138.9
175.3
219.4We also compare the cloud running time forSSED andSMkSD with counterpart methods in PPODC [15], respectively. As shown in Figures 3(a) and 3(b), computation time of both grows with increase of dataset size and our schemes outperform PPODC’s. Let w denote the bit length of plaintext message. In Figure 3(b), it is easy to find that, with growth of w, the computation time of PPODC grows more rapidly. It is because ciphertexts have to be decomposed into encryption of bits before comparison in [15].Figure 3
Performance ofSSED andSMkSD with varying size of datasets (L).
(a)
Cloud running time ofSSED
(b)
Cloud running time ofSMkSD


## 7.2.2. Factors Affecting PPCOM’s Performance

There are three major factors affecting the outsourced performance: (1) the number of clusters (k); (2) the number of parallelized MCUs (f); (3) the size of aggregated dataset (L).First, we evaluate the overhead on cloud servers with varyingk and m when L=2000 and f=8, in comparison with the optimized PPODC with 8 parallelized server pairs. The results are given in Figures 4(a) and 4(b). It can be seen that the computation costs of both protocols grow almost linearly with k and PPCOM protocol outperforms PPODC; for example, when m=10, k=12, the cloud computation time of PPODC is 381.798 min, that is, 4.33 times that of our scheme. The efficiency is gained not only by improved secure primitives, but also by Spark framework. Nevertheless, the communication overhead of PPCOM is relatively high, which is mainly caused by frequent interactions duringSA process. Furthermore, the growth of dimension size also increases the computational and communication overhead of both protocols.Figure 4
Experiment analysis with varying number of clusters (k) in the real dataset.
(a)
Cloud running time
(b)
Cloud communication costNext, we evaluate the overhead on cloud servers with varyingf when k=4,m=20. As shown in Figure 5(a), the computation time decreases with the growth of f. It can be derived that (1) the scaling of parallelized servers can accelerate the outsourced clustering task; (2) it takes PPCOM less computational cost than PPODC to accomplish the same amount of work. Figure 5(b) shows that the communication cost of both schemes remains unchanged regardless of f, because the total amount of clustering task is fixed. However, PPCOM incurs heavier communication overhead to protect privacy and access patterns.Figure 5
Experiment analysis with varying number of parallelized MCUs (f) in the real dataset.
(a)
Cloud running time
(b)
Cloud communication costMoreover, we evaluate the impact ofL on cloud servers’ performance with k=4, m=10. From Figure 6(a), we observe that the running time of both protocols increases with L, as more data need to be clustered. It is obvious that the cost of PPODC grows more sharply than ours. Figure 6(b) shows the computation overhead of Map stage and Reduce stage during execution of PPCOM, respectively. Map stage takes larger proportion of total cost than Reduce, while they scale linearly with L. In addition, the doubled parallelized MCUs save almost 40% of Map execution time.Figure 6
Experiment analysis with varying size of joint datasets (L) from the real dataset.
(a)
Cloud running time
(b)
Running time for Map and Reduce


## 7.3. Comparative Summary

As shown in Table4, we summarize qualitative comparisons with existing outsourced k-means protocols. All protocols are claimed to protect input data privacy. The encryption schemes of first three are constructed on random transformation, such as randomized kernel matrix [11] and random invertible matrices [14, 16]. They were proven to be secure against KSA (known-sample attack) that the attacker knows a set of plain data objects in the dataset, but not the corresponding encrypted values. Yuan and Tian’s work [14] can also defeat LAA (linear analysis attack) introduced by [23]. However, these schemes are weak considering that attacker gets both some data objects and their encryptions. The latter four outsourcing protocols are proposed based on homomorphic encryption techniques, which can resist CPA (chosen plaintext attack). References [12, 13] adopt Liu’s FHE as the underlying encryption scheme, which yet may not be secure enough as illustrated by [18]. Rao et al.’s [15] and our encryption schemes achieve semantic security, relying on hardness of Decisional Composite Residuosity [44] and Diffie-Hellman Problem [30], respectively.Table 4
Comparative summary of existing solutions for outsourcedk-means.
Protocol
Security model
Data privacy protection
Support multikeys
Hide access patterns
No owner involvement
Encrypted distance comparison
Big data engine
Lin’s [11]
KSA
√
×
×
√
√
×
Huang et al.’s [16]
KSA
√
√
×
×
√
×
Yuan and Tian’s [14]
KSA & LAA
√
×
×
×
√
√
Liu et al.’s [12]
CPA
√
×
×
×
√
×
Almutairi et al.’s [13]
CPA
√
×
×
×
×
×
Rao et al.’s [15]
CPA
√
×
√
√
√
×
Ours
CPA
√
√
√
√
√
√From this table, it can be seen that only [16] and ours support computation over encrypted data under multikeys, whereas one drawback in [16] is that they either reveal data owners’ keys to query user or reveal query user’s key to owners. Rao et al.’s [15] and ours hide access patterns by executing clustering in an oblivious way, preventing cloud servers from knowing the assignment membership of encrypted records which may be used to launch inference attack. Several schemes require data owners to participate in the mining process so as to update cluster centroids or to assist similarity comparison, except those from [11, 15] and ours. Almost all works allow the cloud to perform comparison operation between encrypted distances, while approach in [13] adopts a plain updatable matrix to compare. What is more, only Yuan and Tian’s [14] and our researches consider how to integrate big data processing framework into privacy-preserving protocols. As a consequence, our solution achieves the most comprehensive security requirements and feasibility for clustering outsourcing compared with current works.


## 8. Conclusion

In this paper, we proposed an efficient privacy-preserving protocol for outsourcedk-means clustering over joint datasets encrypted under multiple data owners’ keys. By utilizing double decryption cryptosystem, we proposed a series of privacy-preserving building blocks to transform ciphertexts and evaluate addition, multiplication, equality, and comparison, and so on, over encrypted data. Our protocol not only protects privacy of the aggregated database, but also hides access patterns under the semihonest model. Another improvement is that the outsourced clustering works under big data processing framework, which can be scaled to process big data. Experiments on real dataset show that our scheme is more efficient than existing approaches. However, the computation and communication costs of PPCOM are still heavy for large datasets. Our future work will focus on improving the efficiency of outsourced protocols while protecting data privacy to withstand advanced attacks, for example, collusion attack between two CSPs.



---

*Source: 3910126-2017-11-13.xml*