# Highly Secure Privacy-Preserving Outsourcedk-Means Clustering under Multiple Keys in Cloud Computing

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

---

## Abstract

Data clustering is the unsupervised classification of data records into groups. As one of the steps in data analysis, it has been widely researched and applied in practical life, such as pattern recognition, image processing, information retrieval, geography, and marketing. In addition, the rapid increase of data volume in recent years poses a huge challenge for resource-constrained data owners to perform computation on their data. This leads to a trend that users authorize the cloud to perform computation on stored data, such as keyword search, equality test, and outsourced data clustering. In outsourced data clustering, the cloud classifies users’ data into groups according to their similarities. Considering the sensitive information in outsourced data and multiple data owners in practical application, it is necessary to develop a privacy-preserving outsourced clustering scheme under multiple keys. Recently, Rong et al. proposed a privacy-preserving outsourcedk-means clustering scheme under multiple keys. However, in their scheme, the assistant server (AS) is able to extract the ratio of two underlying data records, and key management server (KMS) can decrypt the ciphertexts of owners’ data records, which break the privacy security. AS can even reduce all data records if it knows one of the data records. To solve the aforementioned problem, we propose a highly secure privacy-preserving outsourced k-means clustering scheme under multiple keys in cloud computing. In this paper, noncolluded cloud computing service (CCS) and KMS jointly perform clustering over the encrypted data records without exposing data privacy. Specifically, we use BCP encryption which has additive homomorphic property and AES encryption to double encrypt data records, where the former cryptosystem prevents CCS from obtaining any useful information from received ciphertexts and the latter one protects data records from being decrypted by KMS. We first define five protocols to realize different functions and then present our scheme based on these protocols. Finally, we give the security and performance analyses which show that our scheme is comparable with the existing schemes on functionality and security.


---

## Body

## 1. Introduction

Data clustering [1, 2] enables data records to be classified into groups according to their features, attributes, or similarities. This property leads to its significance in many fields related to data analysis, such as pattern recognition, image processing, information retrieval, geography, and marketing. Furthermore, with the explosive data received nowadays in the information era, it has been a challenge for our digital devices not only to storage but also to perform computation on such massive data. Cloud computing relieves this problem by providing a platform with high storage capacity and strong computing power. Users tend to outsource their data on the cloud and authorize the cloud server computing ability on data. The cloud server therefore can replace users to perform some computation on the outsourced data, such as keyword search [3], equality test [4], and outsourced data clustering [5]. It is worth noting that, in these applications, the cloud server will send the final result to the data owner. This gives a security issue of data integrity which has been further researched in [6–11].By outsourced data clustering which means the cloud classifies data into different groups according to their similarities, it is possible to efficiently detect abnormalities, segment images, and predict diseases. As a widely applied clustering method,k-means clustering [1] classifies data into k-clusters based on their distances from cluster centers. However, the sensitive information of data on the cloud platform cannot be protected by simply using k-means clustering. This calls for privacy-preserving outsourced k-means clustering, where data is classified without exposing the sensitive information of data.The traditional privacy-preservingk-means clustering schemes [12–15] protect the data privacy by adding noises with the sacrifice of clustering accuracy. Subsequently, some symmetric and asymmetric constructions [16–18] have been proposed to improve it with the tradeoff of computing cost and communication overhead. The literature of outsourced privacy-preserving clustering schemes fall into two categories, i.e., single-key and multikey clustering, where the former one refers to that all of the outsourced data of owners are encrypted with one same key while that are with different keys in multikey clustering. Taking into account the practical application, it is necessary to consider the privacy-preserving clustering under multiple keys.Recently, Rong et al. proposed an outsourcedk-means clustering scheme [19] under multiple keys. Nevertheless, their scheme is not secure against semihonest assistant server (AS) and key management server (KMS), where AS can extract the ratio of messages and KMS can even extract all data records of users with its master secret key. In addition, as long as AS obtains one of the data records, it can recover all data records. The privacy leakage may incur a huge economic loss to the user in practice. To solve this problem, we present a highly secure outsourced k-means clustering scheme under multiple keys in cloud computing.


### 1.1. Our Contribution

In this paper, we propose a highly secure privacy-preserving outsourcedk-means clustering under multiple keys in cloud computing.We first introduce our system model and threat models. Specifically, the system model includes four entities, i.e., data owners (DOs), query client (QC), cloud computing service (CCS), and key management service (KMS), and threat model denotes the models against semihonest CCS and KMS. Subsequently, based on [19] and BCP homomorphic encryption, we construct five protocols to realize different functions. It is worth noting that the secure multiplication (SM) protocol is defined to achieve the multiplicative homomorphic property using BCP encryption which only has additive homomorphic property. We then present a highly secure outsourced k-means clustering scheme under multiple keys in cloud computing, which achieves privacy security against semihonest CCS and KMS. In particular, we use BCP encryption to realize the security against privacy leakage to CCS such that semihonest CCS cannot extract any useful information from ciphertexts of data records. We then utilize AES encryption to protect privacy security against semihonest KMS. KMS, therefore, cannot extract any data records of data owners although KMS possesses the master secret key which can be used to decrypt ciphertexts encrypted using BCP encryption.


### 1.2. Related Work

#### 1.2.1. Privacy-Preservingk-Means Clustering

Zhang et al. [20] proposed a high-order possibilistic c-means algorithm for big data in cloud computing based on the BGV cryptosystem [21]. However, their scheme is not practical because of its low efficiency. Subsequently, Almutairi et al. [22] improved it and developed a privacy-preserving k-means clustering scheme based on homomorphic encryption but failed to protect the plaintext information in the update of clustering centers. For this, Yuan and Tian [23] put forward a privacy-preserving clustering scheme using a novel lightweight cryptosystem basing on the hardness of learning with error (LWE) [24]. Their scheme can complete the sum of ciphertexts and compare the distance using ciphertexts of multidimensional data. Nevertheless, this scheme is not fully outsourced.


#### 1.2.2. Outsourced Single-Key Clustering

Lin [25] constructed a privacy-preserving kernel k-means clustering scheme based on linear transformation and kernel matrix with random perturbation, but this scheme cannot realize ciphertext comparison. Based on Paillier cryptosystem, Rao et al. [26] proposed a privacy-preserving outsourcing distributed clustering protocol in the union cloud environment, which includes a new protocol to construct the function of Euclidean distance and evaluate the termination condition over the encrypted data. The problem of this scheme lies in the heavy computing load and lack of support to encrypted datasets under multiple keys. Liu et al. [27] constructed a secure KNN multilabel data classification scheme based on Paillier cryptosystem.


#### 1.2.3. Multikey Clustering

Gheid and Challal [28] presented a novel privacy-preserving k-means clustering scheme with the multiparty of Clifton security [29]. Peter et al. [30] further proposed a scheme to outsource multiparty computation to cloud under multiple keys, while it does not support ciphertext comparison. Li et al. [31] applied the BCP homomorphic encryption [32] to multiparty horizontal partitioned databases and then set up the ciphertext comparison for the outsourced privacy-preserving random decision tree algorithm. Rong et al. [19] improved it by presenting an efficient privacy-preserving protocol for outsourced k-means clustering under multiple keys based on the double decryption cryptosystem [33].


### 1.3. Organization

The rest of this paper is organized as follows. In Section2, we recall the definitions for k-means clustering, BCP encryption, and AES encryption. The system model and threat models are proposed in Section 3. In Section 4, five basic protocols are constructed, and we present our scheme in which the defined protocols are invoked thoroughly. The security proof and performance analysis are given in Section 5. Finally, we conclude this paper in Section 6.


## 1.1. Our Contribution

In this paper, we propose a highly secure privacy-preserving outsourcedk-means clustering under multiple keys in cloud computing.We first introduce our system model and threat models. Specifically, the system model includes four entities, i.e., data owners (DOs), query client (QC), cloud computing service (CCS), and key management service (KMS), and threat model denotes the models against semihonest CCS and KMS. Subsequently, based on [19] and BCP homomorphic encryption, we construct five protocols to realize different functions. It is worth noting that the secure multiplication (SM) protocol is defined to achieve the multiplicative homomorphic property using BCP encryption which only has additive homomorphic property. We then present a highly secure outsourced k-means clustering scheme under multiple keys in cloud computing, which achieves privacy security against semihonest CCS and KMS. In particular, we use BCP encryption to realize the security against privacy leakage to CCS such that semihonest CCS cannot extract any useful information from ciphertexts of data records. We then utilize AES encryption to protect privacy security against semihonest KMS. KMS, therefore, cannot extract any data records of data owners although KMS possesses the master secret key which can be used to decrypt ciphertexts encrypted using BCP encryption.


## 1.2. Related Work

### 1.2.1. Privacy-Preservingk-Means Clustering

Zhang et al. [20] proposed a high-order possibilistic c-means algorithm for big data in cloud computing based on the BGV cryptosystem [21]. However, their scheme is not practical because of its low efficiency. Subsequently, Almutairi et al. [22] improved it and developed a privacy-preserving k-means clustering scheme based on homomorphic encryption but failed to protect the plaintext information in the update of clustering centers. For this, Yuan and Tian [23] put forward a privacy-preserving clustering scheme using a novel lightweight cryptosystem basing on the hardness of learning with error (LWE) [24]. Their scheme can complete the sum of ciphertexts and compare the distance using ciphertexts of multidimensional data. Nevertheless, this scheme is not fully outsourced.


### 1.2.2. Outsourced Single-Key Clustering

Lin [25] constructed a privacy-preserving kernel k-means clustering scheme based on linear transformation and kernel matrix with random perturbation, but this scheme cannot realize ciphertext comparison. Based on Paillier cryptosystem, Rao et al. [26] proposed a privacy-preserving outsourcing distributed clustering protocol in the union cloud environment, which includes a new protocol to construct the function of Euclidean distance and evaluate the termination condition over the encrypted data. The problem of this scheme lies in the heavy computing load and lack of support to encrypted datasets under multiple keys. Liu et al. [27] constructed a secure KNN multilabel data classification scheme based on Paillier cryptosystem.


### 1.2.3. Multikey Clustering

Gheid and Challal [28] presented a novel privacy-preserving k-means clustering scheme with the multiparty of Clifton security [29]. Peter et al. [30] further proposed a scheme to outsource multiparty computation to cloud under multiple keys, while it does not support ciphertext comparison. Li et al. [31] applied the BCP homomorphic encryption [32] to multiparty horizontal partitioned databases and then set up the ciphertext comparison for the outsourced privacy-preserving random decision tree algorithm. Rong et al. [19] improved it by presenting an efficient privacy-preserving protocol for outsourced k-means clustering under multiple keys based on the double decryption cryptosystem [33].


## 1.2.1. Privacy-Preservingk-Means Clustering

Zhang et al. [20] proposed a high-order possibilistic c-means algorithm for big data in cloud computing based on the BGV cryptosystem [21]. However, their scheme is not practical because of its low efficiency. Subsequently, Almutairi et al. [22] improved it and developed a privacy-preserving k-means clustering scheme based on homomorphic encryption but failed to protect the plaintext information in the update of clustering centers. For this, Yuan and Tian [23] put forward a privacy-preserving clustering scheme using a novel lightweight cryptosystem basing on the hardness of learning with error (LWE) [24]. Their scheme can complete the sum of ciphertexts and compare the distance using ciphertexts of multidimensional data. Nevertheless, this scheme is not fully outsourced.


## 1.2.2. Outsourced Single-Key Clustering

Lin [25] constructed a privacy-preserving kernel k-means clustering scheme based on linear transformation and kernel matrix with random perturbation, but this scheme cannot realize ciphertext comparison. Based on Paillier cryptosystem, Rao et al. [26] proposed a privacy-preserving outsourcing distributed clustering protocol in the union cloud environment, which includes a new protocol to construct the function of Euclidean distance and evaluate the termination condition over the encrypted data. The problem of this scheme lies in the heavy computing load and lack of support to encrypted datasets under multiple keys. Liu et al. [27] constructed a secure KNN multilabel data classification scheme based on Paillier cryptosystem.


## 1.2.3. Multikey Clustering

Gheid and Challal [28] presented a novel privacy-preserving k-means clustering scheme with the multiparty of Clifton security [29]. Peter et al. [30] further proposed a scheme to outsource multiparty computation to cloud under multiple keys, while it does not support ciphertext comparison. Li et al. [31] applied the BCP homomorphic encryption [32] to multiparty horizontal partitioned databases and then set up the ciphertext comparison for the outsourced privacy-preserving random decision tree algorithm. Rong et al. [19] improved it by presenting an efficient privacy-preserving protocol for outsourced k-means clustering under multiple keys based on the double decryption cryptosystem [33].


## 1.3. Organization

The rest of this paper is organized as follows. In Section2, we recall the definitions for k-means clustering, BCP encryption, and AES encryption. The system model and threat models are proposed in Section 3. In Section 4, five basic protocols are constructed, and we present our scheme in which the defined protocols are invoked thoroughly. The security proof and performance analysis are given in Section 5. Finally, we conclude this paper in Section 6.


## 2. Preliminaries

### 2.1. Notations

We summarize the notations used in this paper in Table1.Table 1
Notations.
Symbol
Meaning
K
Number of clusters
L
Number of total data records
m
Dimension of data records
I
Maximum number of iterations
n
Number of data owners
n
i
Number of data records ofi-th owner
d
⟶
i
i-th data record d⟶i=di,1,di,2,…,di,m with i∈1,l
c
i
i-th cluster with i∈1,k
c
i
Number of data records in clusterci
μ
⟶
i
Cluster center ofi-th cluster
Dist
a
⟶
,
b
⟶
Euclidean distance between vectorsa⟶ and b⟶
DOi
i-th data owner with i∈1,n
QC
Query client
CCS
Cloud computing service
KMS
Key management server
λ
The security parameter
p
,
q
Two primes of the formp=2p′+1,q=2q′+1
N
,
λ
N
N
=
p
q
,
λ
N
=
2
p
′
q
′
G
The cyclic group of quadratic residue modoloN2
g
g
∈
G and its order is NλN/2
msk
Master secret key in BCP encryption
pk
,
sk
Public key and secret key in BCP encryption
ask
Symmetric key used in AES encryption
Λ
Λ
=
M
1
+
r
1
M
2
+
r
2
Ω
i
,
j
Scaled squared distance betweend⟶i and μ⟶j
V
n
×
k
Location matrix ofn records in k clusters


### 2.2.k-Means Clustering

k-means clustering is an iterative algorithm that allocates l data records into k disjoint clusters, each of which has a center. Let l m-dimensional data records be d⟶1,d⟶2,…,d⟶l and k clusters be c1,c2,…,ck, where μ⟶1,μ⟶2,…,μ⟶k are the centers of k clusters separately. The data record d⟶i will be categorized into the cluster cj if d⟶i and μ⟶j has the minimum Euclidean distance among that of d⟶i and all of cluster centers. In particular, the Euclidean distance of an m-dimensional data record d⟶i=di,1,di,2,…,di,m and a cluster center μ⟶j=μj,1,μj,2,…,μj,m can be expressed as(1)Distd⟶i,μ⟶j=∑h=1mdi,h−μj,h2.The detailed process ofk-means clustering is depicted as Algorithm 1. The algorithm takes as input l m-dimensional data records d⟶1,d⟶2,…,d⟶l, a predefined number of clusters k, and a predefined max number of iterations I. k-cluster centers are firstly picked to compute the Euclidean distance with data records. Each data record is distributed to the cluster which has the minimum Euclidean distance with it. After one iteration, the cluster center μ⟶j is reassigned as the average value of all data records in cj for j∈1,2,…,k. If the max number of iterations is reached or the output clusters does not change any more, terminate the algorithm and output the k-clusters.Algorithm 1: k-means clustering.
Input:d⟶1,d⟶2,…,d⟶l: m-dimensional data records, where d⟶i=di,1,di,2,…,di,m;
k: predefined number of clusters;
I: predefined max number of iterations;
Begin: Pickk cluster centers μ⟶j, j∈1,2,…,k,
for α=1 to Ido
if {different k clusters compared with the case α−1}
(1) Distribute each data recordd⟶i to the cluster cj with the minimum Distd⟶i,μ⟶j among Distd⟶i,μ⟶h for h∈ 1,2,…,k
(2) Update the cluster centerμ⟶j to the average values of data records in cj for i∈1,2,…,k, α=α+1
end if
end for
Output:k clusters


### 2.3. BCP Encryption

In this paper, we utilize the BCP encryption proposed by Bresson et al. [32] which has the additive homomorphic property and provides double decryption mechanisms. The BCP encryption consists of five algorithms as follows:(i)
Setupλ. Taking as input a security parameter λ, the setup algorithm picks two primes p,q of the form p=2p′+1,q=2q′+1 and computes N=pq, where p′,q′ are also primes. Consider G=QRN2, the cyclic group of quadratic residues modulo N2, and we have ord G=NλN/2 with λN=2p′q′. It chooses g∈G, the order of which is NλN/2, and we have gλNmodN2=1+αNmodN2, α∈1,2,…,N−1. The public parameter pp and the master secret key msk are denoted as(2)pp=N,g,msk=p′,q′.(ii)
KeyGenpp. Taking as input the public parameter pp, the key generation algorithm randomly chooses a∈1,ordG and computes h=gamodN2. Note that h is of maximal order with high probability. It sets the output public and secret key pair pk,sk as(3)pk=h=ga,sk=a.(iii)
Encpk,M. Taking as input a public key pk and a message M, the encryption algorithm randomly chooses r∈ℤN and generates the ciphertext CT=A,B as(4)A=grmodN2,B=hr1+mNmodN2.Specifically, we denoteEncpkM as the encryption of message M under the public key pk.(iv)
Decsk,CT. Taking as input a secrete key sk and a ciphertext CT=A,B, the decryption algorithm output the message as(5)M=B/Aa−1modN2N.Specifically, we denoteDecskCT as the decryption of ciphertext CT under the secret key sk.(v)
sDecmsk,CT. Taking as input the master secret key msk and a ciphertext CT=A,B, the system decryption algorithm computes(6)amodN=hλN−1modN2N⋅α−1modN,rmodN=AλN−1modN2N⋅α−1modN.LetarordG=γ1+γ2N; thus, ar=γ1modN is efficiently computable. Let π be the inverse of λN. It generates the message as(7)M=B/gγ1λN−1modN2N⋅πmodN.Specifically, we denotesDecmskCT as the decryption of ciphertext CT under the master secret key msk.Specifically, BCP encryption has additive homomorphic property, which means(8)EncM1⋅EncM2=EncM1+M2.This property will be utilized in the whole system.


### 2.4. AES Encryption

AES encryption is an efficient symmetric encryption system widely used in practical application, where the symmetric means encryption and decryption require the same key. We give the simplified definition of AES as follows:(i)
AKeyGen. The sender and receiver consult the secret key sk of the AES encryption system.(ii)
AEnc. The sender generates the ciphertext CT of message M under the secret key ask following the AES encryption algorithm. We denote it as(9)CT=AEncaskM.(iii)
ADec. The receiver decrypts the ciphertext CT with the secret key sk. We denote it as(10)M=DecaskCT.


## 2.1. Notations

We summarize the notations used in this paper in Table1.Table 1
Notations.
Symbol
Meaning
K
Number of clusters
L
Number of total data records
m
Dimension of data records
I
Maximum number of iterations
n
Number of data owners
n
i
Number of data records ofi-th owner
d
⟶
i
i-th data record d⟶i=di,1,di,2,…,di,m with i∈1,l
c
i
i-th cluster with i∈1,k
c
i
Number of data records in clusterci
μ
⟶
i
Cluster center ofi-th cluster
Dist
a
⟶
,
b
⟶
Euclidean distance between vectorsa⟶ and b⟶
DOi
i-th data owner with i∈1,n
QC
Query client
CCS
Cloud computing service
KMS
Key management server
λ
The security parameter
p
,
q
Two primes of the formp=2p′+1,q=2q′+1
N
,
λ
N
N
=
p
q
,
λ
N
=
2
p
′
q
′
G
The cyclic group of quadratic residue modoloN2
g
g
∈
G and its order is NλN/2
msk
Master secret key in BCP encryption
pk
,
sk
Public key and secret key in BCP encryption
ask
Symmetric key used in AES encryption
Λ
Λ
=
M
1
+
r
1
M
2
+
r
2
Ω
i
,
j
Scaled squared distance betweend⟶i and μ⟶j
V
n
×
k
Location matrix ofn records in k clusters


## 2.2.k-Means Clustering

k-means clustering is an iterative algorithm that allocates l data records into k disjoint clusters, each of which has a center. Let l m-dimensional data records be d⟶1,d⟶2,…,d⟶l and k clusters be c1,c2,…,ck, where μ⟶1,μ⟶2,…,μ⟶k are the centers of k clusters separately. The data record d⟶i will be categorized into the cluster cj if d⟶i and μ⟶j has the minimum Euclidean distance among that of d⟶i and all of cluster centers. In particular, the Euclidean distance of an m-dimensional data record d⟶i=di,1,di,2,…,di,m and a cluster center μ⟶j=μj,1,μj,2,…,μj,m can be expressed as(1)Distd⟶i,μ⟶j=∑h=1mdi,h−μj,h2.The detailed process ofk-means clustering is depicted as Algorithm 1. The algorithm takes as input l m-dimensional data records d⟶1,d⟶2,…,d⟶l, a predefined number of clusters k, and a predefined max number of iterations I. k-cluster centers are firstly picked to compute the Euclidean distance with data records. Each data record is distributed to the cluster which has the minimum Euclidean distance with it. After one iteration, the cluster center μ⟶j is reassigned as the average value of all data records in cj for j∈1,2,…,k. If the max number of iterations is reached or the output clusters does not change any more, terminate the algorithm and output the k-clusters.Algorithm 1: k-means clustering.
Input:d⟶1,d⟶2,…,d⟶l: m-dimensional data records, where d⟶i=di,1,di,2,…,di,m;
k: predefined number of clusters;
I: predefined max number of iterations;
Begin: Pickk cluster centers μ⟶j, j∈1,2,…,k,
for α=1 to Ido
if {different k clusters compared with the case α−1}
(1) Distribute each data recordd⟶i to the cluster cj with the minimum Distd⟶i,μ⟶j among Distd⟶i,μ⟶h for h∈ 1,2,…,k
(2) Update the cluster centerμ⟶j to the average values of data records in cj for i∈1,2,…,k, α=α+1
end if
end for
Output:k clusters


## 2.3. BCP Encryption

In this paper, we utilize the BCP encryption proposed by Bresson et al. [32] which has the additive homomorphic property and provides double decryption mechanisms. The BCP encryption consists of five algorithms as follows:(i)
Setupλ. Taking as input a security parameter λ, the setup algorithm picks two primes p,q of the form p=2p′+1,q=2q′+1 and computes N=pq, where p′,q′ are also primes. Consider G=QRN2, the cyclic group of quadratic residues modulo N2, and we have ord G=NλN/2 with λN=2p′q′. It chooses g∈G, the order of which is NλN/2, and we have gλNmodN2=1+αNmodN2, α∈1,2,…,N−1. The public parameter pp and the master secret key msk are denoted as(2)pp=N,g,msk=p′,q′.(ii)
KeyGenpp. Taking as input the public parameter pp, the key generation algorithm randomly chooses a∈1,ordG and computes h=gamodN2. Note that h is of maximal order with high probability. It sets the output public and secret key pair pk,sk as(3)pk=h=ga,sk=a.(iii)
Encpk,M. Taking as input a public key pk and a message M, the encryption algorithm randomly chooses r∈ℤN and generates the ciphertext CT=A,B as(4)A=grmodN2,B=hr1+mNmodN2.Specifically, we denoteEncpkM as the encryption of message M under the public key pk.(iv)
Decsk,CT. Taking as input a secrete key sk and a ciphertext CT=A,B, the decryption algorithm output the message as(5)M=B/Aa−1modN2N.Specifically, we denoteDecskCT as the decryption of ciphertext CT under the secret key sk.(v)
sDecmsk,CT. Taking as input the master secret key msk and a ciphertext CT=A,B, the system decryption algorithm computes(6)amodN=hλN−1modN2N⋅α−1modN,rmodN=AλN−1modN2N⋅α−1modN.LetarordG=γ1+γ2N; thus, ar=γ1modN is efficiently computable. Let π be the inverse of λN. It generates the message as(7)M=B/gγ1λN−1modN2N⋅πmodN.Specifically, we denotesDecmskCT as the decryption of ciphertext CT under the master secret key msk.Specifically, BCP encryption has additive homomorphic property, which means(8)EncM1⋅EncM2=EncM1+M2.This property will be utilized in the whole system.


## 2.4. AES Encryption

AES encryption is an efficient symmetric encryption system widely used in practical application, where the symmetric means encryption and decryption require the same key. We give the simplified definition of AES as follows:(i)
AKeyGen. The sender and receiver consult the secret key sk of the AES encryption system.(ii)
AEnc. The sender generates the ciphertext CT of message M under the secret key ask following the AES encryption algorithm. We denote it as(9)CT=AEncaskM.(iii)
ADec. The receiver decrypts the ciphertext CT with the secret key sk. We denote it as(10)M=DecaskCT.


## 3. Models

### 3.1. System Model

As shown in Figure1, our scheme considers four types of entities, i.e., data owner (DO), cloud computing service (CCS), key management server (KMS), and query client (QC).(i)
DO: DO has limited computing power and therefore outsources its encrypted data to the cloud. Our system involvesn DOs, denoted as DO1,DO2,…,DOn. For i∈1,n, each DOi has ni data records, and each data record has m attributes. Data owners are assumed not to collude with the cloud servers.(ii)
QC: QC is authorized to query and receive the clustering results and does not involve in any clustering calculation.(iii)
CCS: CCS stores the datasets of multiple DOs, takes part in the clustering process, and sends the clustering results to the QC.(iv)
KMS: KMS generates system parameters and performs ciphertext transformation with the master secret key. It also participates in the clustering process.Figure 1
System architecture.


### 3.2. Threat Models

In our system, we suppose that CCS and KMS are semihonest. This means they will honestly perform what the protocol requires but will be curious about the messages under ciphertexts they received. Upon this assumption, we define three thread models as follows, where an adversaryA acting as different roles in different models attempts to decrypt the ciphertexts sent from DOs and CCS.(i)
Acting as a “malicious” CCS,A tries to obtain the message under ciphertexts sent from DOs and KMS(ii)
Acting as a “malicious” KMS,A tries to obtain the real message under ciphertexts sent from CCS(iii)
Acting as a “malicious” KMS,A tries to obtain the message under the ciphertexts that sent from DOs to CCSIt is worth noting that CCS and KMS are assumed not to collude with each other.


## 3.1. System Model

As shown in Figure1, our scheme considers four types of entities, i.e., data owner (DO), cloud computing service (CCS), key management server (KMS), and query client (QC).(i)
DO: DO has limited computing power and therefore outsources its encrypted data to the cloud. Our system involvesn DOs, denoted as DO1,DO2,…,DOn. For i∈1,n, each DOi has ni data records, and each data record has m attributes. Data owners are assumed not to collude with the cloud servers.(ii)
QC: QC is authorized to query and receive the clustering results and does not involve in any clustering calculation.(iii)
CCS: CCS stores the datasets of multiple DOs, takes part in the clustering process, and sends the clustering results to the QC.(iv)
KMS: KMS generates system parameters and performs ciphertext transformation with the master secret key. It also participates in the clustering process.Figure 1
System architecture.


## 3.2. Threat Models

In our system, we suppose that CCS and KMS are semihonest. This means they will honestly perform what the protocol requires but will be curious about the messages under ciphertexts they received. Upon this assumption, we define three thread models as follows, where an adversaryA acting as different roles in different models attempts to decrypt the ciphertexts sent from DOs and CCS.(i)
Acting as a “malicious” CCS,A tries to obtain the message under ciphertexts sent from DOs and KMS(ii)
Acting as a “malicious” KMS,A tries to obtain the real message under ciphertexts sent from CCS(iii)
Acting as a “malicious” KMS,A tries to obtain the message under the ciphertexts that sent from DOs to CCSIt is worth noting that CCS and KMS are assumed not to collude with each other.


## 4. Our Construction

Based on the scheme proposed by Rong et al. in [19], we construct a more secure clustering scheme. In our construction, we utilize BCP homomorphic encryption to protect the privacy security of data owners such that adversaries cannot extract any useful information about underlying data records of data owners, while AS can easily extract M1/M2 in [19]. Furthermore, AES encryption is also used to double-encrypt the data records to prevent KMS from directly extracting data records from ciphertexts sent from DO to CCS.


### 4.1. Protocols

We first define five underlying protocols to satisfy different requirements in the clustering process. To securely transfer the data records of DO to CCS, we define secure ciphertext transformation (SCT) protocol. Since the BCP encryption used in our scheme only has additive property, we build a secure multiplication (SM) protocol to realize the multiplicative property. Finally, aiming to classify the similar data records using the ciphertexts, we construct three protocols, namely, secure distance measurement (SDM) protocol, secure distance comparison (SDC) protocol, and secure minimum distance measurement (SMDM) protocol. These protocols will be invoked through our scheme.


#### 4.1.1. Secure Ciphertext Transformation Protocol

Secure ciphertext transformation (SCT) protocol aims to transfer the ciphertext of messageM encrypted under public key pkx to a ciphertext of M encrypted under public key pky without revealing M. Suppose two entities in SCT protocol, i.e., Alice and Bob, Alice interacts with Bob following SCT protocol to convert EncpkxM to EncpkyM. To prevent Bob from extracting the message M, a random number is used to blind the message from Bob. The detailed process is listed in Algorithm 2.Algorithm 2:SCT protocol.
Input: Alice:pkx,pky,EncpkxM
Bob:msk,pky
Begin: Alice:
(a) Pick a random numberr∈ℤN
(b) ComputeEncpkxM+r⟵EncpkxM⋅Encpkyr
(c) SendEncpkxM+r to Bob
Bob:
(a) DecryptM+r⟵sDecmskEncpkxM+r
(b) ComputeEncpkyM+r
(c) SendEncpkyM+r to Alice
Alice
(a) ComputeEncpkyM=EncpkyM+r⋅Encpky−r
Output:EncpkyMTaking as the input the public keyspkxand pky and the ciphertext EncpkxM, Alice randomly chooses r∈ℤN and encrypts r using pkx to Encpkxr. It then computes the encryption of M+r under pkx, which can be realized by EncpkxM+Encpkxr because of the additive homomorphic property of BCP encryption. Alice then sends the output sfEncpkxM+r to Bob. Taking as the input the public key pky, its master secret key msk, and received EncpkxM+r, Bob decrypts this ciphertext using its master secret key msk following the system decryption algorithm sDec and obtains M+r. It then encrypts M+r with pky and sends the output EncpkyM+r to Alice. Alice eliminates r in the ciphertext by computing EncpkyM+r⋅Encpky−r and obtains EncpkyM as the final output.


#### 4.1.2. Secure Multiplication Protocol

Secure multiplication (SM) protocol is used to obtain the ciphertext of messages’ multiplication with corresponding messages’ ciphertexts using the BCP homomorphic cryptosystem. It is required in this process that the messages should not be exposed. The same as SCT protocol, we also assume two entities in SM protocol, i.e., Alice and Bob. Alice attempts to obtainEncpkxM1⋅M2 from EncpkxM1,EncpkxM2 without revealing M1,M2 to Bob who is the owner of the corresponding secret key sk. We define SM protocol in Algorithm 3.Algorithm 3:SM protocol.
Input: Alice:EncpkxM1,EncpkxM2
Bob:skx.
Begin: Alice:
(a) Pick random numbersr1,r2∈ℤN
(b) ComputeEncpkxM1+r1⟵EncpkxM1⋅Encpkxr1
(c) ComputeEncpkxM2+r2⟵EncpkxM2⋅Encpkxr2
(d) SendEncpkxM1+r1,EncpkxM2+r2 to Bob
Bob:
(a) DecryptM1+r1⟵DecskxEncpkxM1+r1
(b) DecryptM2+r2⟵DecskxEncpkxM1+r1
(c) ComputeΛ=M1+r1M2+r2
(d) ComputeEncpkxΛ
(e) SendEncpkxΛ to Alice
Alice:
(a) ComputeEncpkxM1⋅M2=EncpkxM1N−r2
EncpkxM2N−r1⋅Encpkxr1r2N−1⋅EncpkxΛ
Output:EncpkxM1⋅M2Taking as the input the ciphertextEncpkxM1 and EncpkyM2, Alice randomly chooses numbers r1,r2∈ℤN and computes the ciphertext of M1+r1,M2+r2 by computing EncpkxM1⋅Encpkxr1 and EncpkxM2⋅Encpkxr2 respectively. This utilizes the additive homomorphic property of BCP encryption. It then sends the output EncpkxM1+r1,EncpkxM2+r2 to Bob. Taking as the input the corresponding secret key skx of pkx, Bob decrypts the received ciphertexts with skx and obtains M1+r1,M2+r2. It computes the multiplication of M1+r1,M2+r2 as Λ=M1+r1⋅M2+r2=M1⋅M2+r2M1+r1M2+r1r2 and encrypts Λ with pkx as EncpkxΛ which is used to divide M1⋅M2 in the underlying message. Bob sends EncpkxΛ to Alice. Finally, Alice computes EncpkxM1⋅M2 with EncpkxΛ,r1,r2,EncpkxM1,EncpkxM2 using the additive homomorphic property of BCP encryption.


#### 4.1.3. Secure Distance Measurement Protocol

We define the secure distance measurement (SDM) protocol to measure the distance between data records and cluster centers using Euclidean distance. Assume there aren data records and k clusters. Let s⟶j=sj,1,sj,2,…,sj,m be the sum of data records in cluster cj and cj be the number of data records in cluster cj, respectively. Given a data record d⟶i=di,1,di,2,…,di,m and a cluster center μ⟶j=μi,1,μi,2,…,μi,m, Ωi,j is denoted as the scaled squared distance between d⟶i and μ⟶j satisfying Distd⟶i,μ⟶j=Ωi,j/cj. Therefore, Ωi,j is denoted and computed as in the following equation:(11)Ωi,j=Distd→i,μ→j⋅cj2.=∑α=1mcj,di,α−sj,α2The process is depicted as Algorithm4.Algorithm 4:SDM protocol.
Input:Encpkxd⟶i,Encpkxsj⟶,cj
Begin:EncpkxΩi,j=0
for α=1 to m
1. Run SM protocol onEncpkxdi,α and Encpkxcj to obtain Γ=Encpkxcj⋅di,α
2. ComputeEncpkxΩi,j=Γ⋅Encpkxsj,αN−12+EncpkxΩi,j
end for
Output:EncpkxΩi,j,cj


#### 4.1.4. Secure Distance Comparison Protocol

Secure distance comparison (SDC) protocol is to determine the shorter distance between two output distances from SDM protocol. Taking as the input two distances, i.e.,EncpkxΩi,a,ca and EncpkxΩi,b,cb, Alice interacts with Bob to obtain the shorter one. As in [19], the difference between two differences can be expressed as(12)EncpkxDistd⟶i,μ⟶a⋅EncpkxDistd⟶i,μ⟶bN−1=EncpkxDistd⟶i,μ⟶a−Distd⟶i,μ⟶b=EncpkxΩ/ca2−Ωi,b/cb2=Encpkxcb2Ωi,a−ca2Ωi,bca2cb2.Since we only need to know whethercb2Ωi,a−ca2Ωi,b/ca2cb2>0 or not, it is equal to judge whether cb2Ωi,a−ca2Ωi,b>0 or not. This means, the comparison can be related to(13)Encpkxcb2Ωi,a−ca2Ωi,b.Letβ be the maximum size of messages. We have M∈−2β+1,2β−1, which means MmodN∈1,2β−1 if M>0 and MmodN∈N−2β+1,N−1. Let η be the threshold for sign judgement chosen from 2β−1,N+2β−1. To prevent Bob from obtaining distance-related information, Alice blinds the message with a random r∈1,minN−η,N−ϕN/2β−1 with ϕ∈ℤ and satisfying(14)2β−1⋅rmodN<ηN−1⋅rmodN>ηN+1−2β⋅rmodN>η..We illustrate the detailed realization in Algorithm5.Algorithm 5:SDC protocol..
Input: Alice:EncpkxΩi,a,ca,EncpkxΩi,b,cb,sky
Bob:skx,pky
Begin: Alice interacts with Bob to compute:
(a)EncpkxΩi,a′⟵SMEncpkxΩi,a,Encpkxb2
(b)EncpkxΩi,b′⟵SMEncpkxΩi,b,Encpkxa2
Alice:
(a) ComputeEncpkxΩi,b′=EncpkxΩi,b′N−1
(b) ComputeEncpkxΔa,b=EncpkxΩi,a′⋅EncpkxΩi,b″
(c) Pick a random numberr∈ℤN
Alice interacts with Bob to compute:
(a)EncpkxrΔa,b⟵SMEncpkxr,EncpkxΔa,b
Alice:
(a) SendEncpkxrΔa,b to Bob
Bob:
(a) DecryptrΔa,b⟵DecEncpkxrΔa,b
(b) IfrΔa,b>η, sn⟵Encpky1; otherwise, randomly choose r′∈ℤN satisfying r≠1, sn⟵Encpkyr′
(c) Sendsn to Alice
Alice:
(a) IfDecskysn=1, let EncpkxΩi,min=EncpkxΩi,a, cmin=ca; Otherwise, we have Decskysn≠1, let EncpkxΩi,min=EncpkxΩi,b,ci,min=cb
Output:EncpkxΩi,min,ci,minIn the process, Bob cannot obtainΩi,a,Ωi,b.


#### 4.1.5. Secure Minimum Distance Measurement Protocol

Finally, we define the secure minimum distance measurement (SMDM) protocol as Algorithm6 to choose the shortest one among given distances.Algorithm 6:SMDM protocol.
Input:Encpkxd⟶i,Encpkxμ⟶1,Encpkxμ⟶2,…,Encpkxμ⟶k
Begin:for α=1 to k
(a) RunSDMEncpkxd⟶i,Encpkxμ⟶α and obtain the output EncpkxΩi,α,cα
end for
LetEncpkxΩi,min,ci,min=EncpkxΩi,1,c1
for α=2 to k
(a) RunSDCEncpkxΩi,min,ci,min,EncpkxΩi,2,c2 and obtain the output EncpkxΩi,min,ci,min
(b) SetEncpkxΩi,min,ci,min≔EncpkxΩi,min,ci,min
end for
Output:EncpkxΩi,min,ci,min


### 4.2. Our Scheme

At the beginning, the four entities in the system, i.e., data owners DOs, query client QC, cloud computing service CCS, and key management server KMS, setup the system by running the algorithms,Setup, KeyGen, and AKeyGen. DOs then run Enc and AEnc on their data records and upload to CCS separately. CCS decrypts the received ciphertexts using ADec. After receiving the clustering request from QC, CCS interacts with KMS to transform the ciphertexts encrypted under different public keys to ciphertexts encrypted under the same public key. Subsequently, CCS performs the clustering computation. Finally, CCS interacts with KMS to transfer the clustering result to QC. It is worth noting that the defined protocols are invoked through the process.


#### 4.2.1. System Setup

As the setting in the system model (see Section 4.1), we haven data owners DOi1≤i≤n, cloud computing servers (CCS), key management server (KMS), and query client (QC). Before running the protocols, related entities in the system model generate their keys as follows:(1)
Taking as the input a security parameter λ, KMS runs the setup algorithmSetupλ of the BCP homomorphic cryptosystem and generate the public parameter pp and master secret key msk, where msk is kept secret(2)
Each data ownerDOi runs KeyGenpp to generate its own public/secret key pair pki,ski, 1≤i≤n(3)
EachDOi consults with CCS a symmetric key aski through Diffie–Hellman key exchange protocol or other methods for 1≤i≤n(4)
CCS runs the key generation algorithmKeyGenpp to generate its public/secret key pair as pkc,skc(5)
QC runsKeyGenpp to generate its own public/secret key pair pkq,skq


#### 4.2.2. Data Uploading

Following the setting in Section 4.1, assume that each data ownerDOi has a dataset Di which contains ni data records, and each record has m attributes, and DOi encrypts Di with BCP cryptosystem first and then AES encryption, 1≤i≤n. Finally, DOi sends the output to CCS.(1)
DOi then runs the encryption algorithm on each record dji⟶=dj,1i,dj,2i,…,dj,mi,j∈1,ni and obtains the encrypted result as(15)Encpkid⟶ji1≤j≤ni.(2)
To prevent the privacy disclosure from KMS, data owners double-encrypt the output ciphertext with AES encryption. EachDOi computes(16)aEncaskiEncpkid⟶ji1≤j≤ni,and sends the output results to CCS.(3)
After receivingaEncaskiEncpkid⟶ji1≤j≤ni from DOi, CCS runs the decryption algorithm aDEC with the consulted symmetric key aski on each ciphertext to obtain(17)aDECaskaEncaskEncpkid⟶ji1≤i≤ni=Encpkid⟶ji1≤i≤ni.In our setting for data uploading, each data ownerDOi sends their double-encrypted ciphertext to CCS such that the KMS cannot obtain the original message of the data owner although the KMS has the master secret key msk which can be used to decrypt the ciphertext encrypted under the BCP homomorphic cryptosystem.


#### 4.2.3. Ciphertext Transformation

This phase is to transfer “multiuser” to “single-user” by re-encrypting the ciphertext encrypted under the public key ofpki to the ciphertext encrypted under pkc, 1≤i≤n.(1)
QC sends a clustering request to CCS.(2)
For a ciphertextEncpkid⟶ji from DOi, CCS interacts with KMS to run the SCT protocol by setting pkx=pki,pky=pkc,EncpkxM=Encpkid⟶ji,msk=msk. Finally, CCS obtains Encpkcd⟶ji.(3)
By performing the SCT protocol on all the ciphertexts received fromDOi1≤i≤n, CCS finally obtains(18)Encpkcd⟶ji1≤i≤n,1≤j≤ni.Letn=n1+n2+⋯+nl, and denote these n ciphertexts as(19)Encpkcd⟶i1≤i≤n.For simplicity, we denoteEncpkcd⟶i as Encd⟶i in the following.It is worth noting that the final ciphertexts are unknown to the KMS since they are blinded in the SCT protocol.


#### 4.2.4. Clustering Computation

In this phase, CCS computes the clustering results withk randomly chosen cluster centers Encμ⟶1,Encμ⟶2,…,Encμ⟶k from Encpkcd⟶i1≤i≤n. Let Encμ⟶i=Encs⟶j=Encsj,1,Encsj,2,…,Encsj,m and ci=1. CCS also outputs a matrix Vn×k which refers to the location in k clusters of n records, where Vi,j=1 means d⟶i is allocated to j-th cluster. In addition, there is a maximum iteration time ϕmax. Let ϕ=0.(1)
For a data recordEncd⟶i, CCS runs the SMDM protocol on it and k-cluster centers with the setting pkx=pkc. Finally, CCS obtains the output(20)EncΩi,min,ci,min,whereci,min=cα. Let Vi,j=0 for j≠α.(2)
For each data recordEncd⟶i where d⟶i≠μ⟶j,1≤i≤n,1≤j≤k, CCS runs step 1 and obtains(21)EncΩi,min,ci,min,1≤i≤n,and the matrixVn×k.(3)
With the matrixVn×k and data records Encd⟶i=Encdi,1,di,2,…,di,m, if Vi,j=1, CCS updates cj=cj+1 and Encsj,α as(22)Encdi,α⋅Encsj,α=Encdi,α+sj,α,for1≤α≤m. Finally, CCS obtains new cj and Encs⟶j=Encsj,1,Encsj,2,…,Encsj,m for 1≤j≤k. Let ϕ=ϕ+1.(4)
Ifϕ<ϕmax and the output matrix Vn×k is different from that in the last iteration, CCS starts a new iteration by running steps (1), (2), and (3). Otherwise, CCS outputs the final(23)Encs⟶j,cj1≤j≤k.


#### 4.2.5. Result Retrieval

(1)
CCS interacts with KMS to run the SCT protocol onEncpkcs⟶j1≤j≤k with the setting pkx=pkc,pky=pkq,EncpkxM=Encpkcs⟶j. CCS obtains
(24)
Enc
pk
q
s
⟶
j
1
≤
j
≤
k
and sends it andVn×k to QC.
(2)
QC decrypts the receivedEncpkqs⟶j with its secret key skq by computing
(25)
Dec
sk
q
Enc
pk
q
s
⟶
j
=
s
⟶
j
1
≤
j
≤
k
.
QC then computes the cluster centers as
(26)
s
⟶
j
c
j
1
≤
j
≤
k
,
wherecj=∑i=1nVi,j.


## 4.1. Protocols

We first define five underlying protocols to satisfy different requirements in the clustering process. To securely transfer the data records of DO to CCS, we define secure ciphertext transformation (SCT) protocol. Since the BCP encryption used in our scheme only has additive property, we build a secure multiplication (SM) protocol to realize the multiplicative property. Finally, aiming to classify the similar data records using the ciphertexts, we construct three protocols, namely, secure distance measurement (SDM) protocol, secure distance comparison (SDC) protocol, and secure minimum distance measurement (SMDM) protocol. These protocols will be invoked through our scheme.


### 4.1.1. Secure Ciphertext Transformation Protocol

Secure ciphertext transformation (SCT) protocol aims to transfer the ciphertext of messageM encrypted under public key pkx to a ciphertext of M encrypted under public key pky without revealing M. Suppose two entities in SCT protocol, i.e., Alice and Bob, Alice interacts with Bob following SCT protocol to convert EncpkxM to EncpkyM. To prevent Bob from extracting the message M, a random number is used to blind the message from Bob. The detailed process is listed in Algorithm 2.Algorithm 2:SCT protocol.
Input: Alice:pkx,pky,EncpkxM
Bob:msk,pky
Begin: Alice:
(a) Pick a random numberr∈ℤN
(b) ComputeEncpkxM+r⟵EncpkxM⋅Encpkyr
(c) SendEncpkxM+r to Bob
Bob:
(a) DecryptM+r⟵sDecmskEncpkxM+r
(b) ComputeEncpkyM+r
(c) SendEncpkyM+r to Alice
Alice
(a) ComputeEncpkyM=EncpkyM+r⋅Encpky−r
Output:EncpkyMTaking as the input the public keyspkxand pky and the ciphertext EncpkxM, Alice randomly chooses r∈ℤN and encrypts r using pkx to Encpkxr. It then computes the encryption of M+r under pkx, which can be realized by EncpkxM+Encpkxr because of the additive homomorphic property of BCP encryption. Alice then sends the output sfEncpkxM+r to Bob. Taking as the input the public key pky, its master secret key msk, and received EncpkxM+r, Bob decrypts this ciphertext using its master secret key msk following the system decryption algorithm sDec and obtains M+r. It then encrypts M+r with pky and sends the output EncpkyM+r to Alice. Alice eliminates r in the ciphertext by computing EncpkyM+r⋅Encpky−r and obtains EncpkyM as the final output.


### 4.1.2. Secure Multiplication Protocol

Secure multiplication (SM) protocol is used to obtain the ciphertext of messages’ multiplication with corresponding messages’ ciphertexts using the BCP homomorphic cryptosystem. It is required in this process that the messages should not be exposed. The same as SCT protocol, we also assume two entities in SM protocol, i.e., Alice and Bob. Alice attempts to obtainEncpkxM1⋅M2 from EncpkxM1,EncpkxM2 without revealing M1,M2 to Bob who is the owner of the corresponding secret key sk. We define SM protocol in Algorithm 3.Algorithm 3:SM protocol.
Input: Alice:EncpkxM1,EncpkxM2
Bob:skx.
Begin: Alice:
(a) Pick random numbersr1,r2∈ℤN
(b) ComputeEncpkxM1+r1⟵EncpkxM1⋅Encpkxr1
(c) ComputeEncpkxM2+r2⟵EncpkxM2⋅Encpkxr2
(d) SendEncpkxM1+r1,EncpkxM2+r2 to Bob
Bob:
(a) DecryptM1+r1⟵DecskxEncpkxM1+r1
(b) DecryptM2+r2⟵DecskxEncpkxM1+r1
(c) ComputeΛ=M1+r1M2+r2
(d) ComputeEncpkxΛ
(e) SendEncpkxΛ to Alice
Alice:
(a) ComputeEncpkxM1⋅M2=EncpkxM1N−r2
EncpkxM2N−r1⋅Encpkxr1r2N−1⋅EncpkxΛ
Output:EncpkxM1⋅M2Taking as the input the ciphertextEncpkxM1 and EncpkyM2, Alice randomly chooses numbers r1,r2∈ℤN and computes the ciphertext of M1+r1,M2+r2 by computing EncpkxM1⋅Encpkxr1 and EncpkxM2⋅Encpkxr2 respectively. This utilizes the additive homomorphic property of BCP encryption. It then sends the output EncpkxM1+r1,EncpkxM2+r2 to Bob. Taking as the input the corresponding secret key skx of pkx, Bob decrypts the received ciphertexts with skx and obtains M1+r1,M2+r2. It computes the multiplication of M1+r1,M2+r2 as Λ=M1+r1⋅M2+r2=M1⋅M2+r2M1+r1M2+r1r2 and encrypts Λ with pkx as EncpkxΛ which is used to divide M1⋅M2 in the underlying message. Bob sends EncpkxΛ to Alice. Finally, Alice computes EncpkxM1⋅M2 with EncpkxΛ,r1,r2,EncpkxM1,EncpkxM2 using the additive homomorphic property of BCP encryption.


### 4.1.3. Secure Distance Measurement Protocol

We define the secure distance measurement (SDM) protocol to measure the distance between data records and cluster centers using Euclidean distance. Assume there aren data records and k clusters. Let s⟶j=sj,1,sj,2,…,sj,m be the sum of data records in cluster cj and cj be the number of data records in cluster cj, respectively. Given a data record d⟶i=di,1,di,2,…,di,m and a cluster center μ⟶j=μi,1,μi,2,…,μi,m, Ωi,j is denoted as the scaled squared distance between d⟶i and μ⟶j satisfying Distd⟶i,μ⟶j=Ωi,j/cj. Therefore, Ωi,j is denoted and computed as in the following equation:(11)Ωi,j=Distd→i,μ→j⋅cj2.=∑α=1mcj,di,α−sj,α2The process is depicted as Algorithm4.Algorithm 4:SDM protocol.
Input:Encpkxd⟶i,Encpkxsj⟶,cj
Begin:EncpkxΩi,j=0
for α=1 to m
1. Run SM protocol onEncpkxdi,α and Encpkxcj to obtain Γ=Encpkxcj⋅di,α
2. ComputeEncpkxΩi,j=Γ⋅Encpkxsj,αN−12+EncpkxΩi,j
end for
Output:EncpkxΩi,j,cj


### 4.1.4. Secure Distance Comparison Protocol

Secure distance comparison (SDC) protocol is to determine the shorter distance between two output distances from SDM protocol. Taking as the input two distances, i.e.,EncpkxΩi,a,ca and EncpkxΩi,b,cb, Alice interacts with Bob to obtain the shorter one. As in [19], the difference between two differences can be expressed as(12)EncpkxDistd⟶i,μ⟶a⋅EncpkxDistd⟶i,μ⟶bN−1=EncpkxDistd⟶i,μ⟶a−Distd⟶i,μ⟶b=EncpkxΩ/ca2−Ωi,b/cb2=Encpkxcb2Ωi,a−ca2Ωi,bca2cb2.Since we only need to know whethercb2Ωi,a−ca2Ωi,b/ca2cb2>0 or not, it is equal to judge whether cb2Ωi,a−ca2Ωi,b>0 or not. This means, the comparison can be related to(13)Encpkxcb2Ωi,a−ca2Ωi,b.Letβ be the maximum size of messages. We have M∈−2β+1,2β−1, which means MmodN∈1,2β−1 if M>0 and MmodN∈N−2β+1,N−1. Let η be the threshold for sign judgement chosen from 2β−1,N+2β−1. To prevent Bob from obtaining distance-related information, Alice blinds the message with a random r∈1,minN−η,N−ϕN/2β−1 with ϕ∈ℤ and satisfying(14)2β−1⋅rmodN<ηN−1⋅rmodN>ηN+1−2β⋅rmodN>η..We illustrate the detailed realization in Algorithm5.Algorithm 5:SDC protocol..
Input: Alice:EncpkxΩi,a,ca,EncpkxΩi,b,cb,sky
Bob:skx,pky
Begin: Alice interacts with Bob to compute:
(a)EncpkxΩi,a′⟵SMEncpkxΩi,a,Encpkxb2
(b)EncpkxΩi,b′⟵SMEncpkxΩi,b,Encpkxa2
Alice:
(a) ComputeEncpkxΩi,b′=EncpkxΩi,b′N−1
(b) ComputeEncpkxΔa,b=EncpkxΩi,a′⋅EncpkxΩi,b″
(c) Pick a random numberr∈ℤN
Alice interacts with Bob to compute:
(a)EncpkxrΔa,b⟵SMEncpkxr,EncpkxΔa,b
Alice:
(a) SendEncpkxrΔa,b to Bob
Bob:
(a) DecryptrΔa,b⟵DecEncpkxrΔa,b
(b) IfrΔa,b>η, sn⟵Encpky1; otherwise, randomly choose r′∈ℤN satisfying r≠1, sn⟵Encpkyr′
(c) Sendsn to Alice
Alice:
(a) IfDecskysn=1, let EncpkxΩi,min=EncpkxΩi,a, cmin=ca; Otherwise, we have Decskysn≠1, let EncpkxΩi,min=EncpkxΩi,b,ci,min=cb
Output:EncpkxΩi,min,ci,minIn the process, Bob cannot obtainΩi,a,Ωi,b.


### 4.1.5. Secure Minimum Distance Measurement Protocol

Finally, we define the secure minimum distance measurement (SMDM) protocol as Algorithm6 to choose the shortest one among given distances.Algorithm 6:SMDM protocol.
Input:Encpkxd⟶i,Encpkxμ⟶1,Encpkxμ⟶2,…,Encpkxμ⟶k
Begin:for α=1 to k
(a) RunSDMEncpkxd⟶i,Encpkxμ⟶α and obtain the output EncpkxΩi,α,cα
end for
LetEncpkxΩi,min,ci,min=EncpkxΩi,1,c1
for α=2 to k
(a) RunSDCEncpkxΩi,min,ci,min,EncpkxΩi,2,c2 and obtain the output EncpkxΩi,min,ci,min
(b) SetEncpkxΩi,min,ci,min≔EncpkxΩi,min,ci,min
end for
Output:EncpkxΩi,min,ci,min


## 4.1.1. Secure Ciphertext Transformation Protocol

Secure ciphertext transformation (SCT) protocol aims to transfer the ciphertext of messageM encrypted under public key pkx to a ciphertext of M encrypted under public key pky without revealing M. Suppose two entities in SCT protocol, i.e., Alice and Bob, Alice interacts with Bob following SCT protocol to convert EncpkxM to EncpkyM. To prevent Bob from extracting the message M, a random number is used to blind the message from Bob. The detailed process is listed in Algorithm 2.Algorithm 2:SCT protocol.
Input: Alice:pkx,pky,EncpkxM
Bob:msk,pky
Begin: Alice:
(a) Pick a random numberr∈ℤN
(b) ComputeEncpkxM+r⟵EncpkxM⋅Encpkyr
(c) SendEncpkxM+r to Bob
Bob:
(a) DecryptM+r⟵sDecmskEncpkxM+r
(b) ComputeEncpkyM+r
(c) SendEncpkyM+r to Alice
Alice
(a) ComputeEncpkyM=EncpkyM+r⋅Encpky−r
Output:EncpkyMTaking as the input the public keyspkxand pky and the ciphertext EncpkxM, Alice randomly chooses r∈ℤN and encrypts r using pkx to Encpkxr. It then computes the encryption of M+r under pkx, which can be realized by EncpkxM+Encpkxr because of the additive homomorphic property of BCP encryption. Alice then sends the output sfEncpkxM+r to Bob. Taking as the input the public key pky, its master secret key msk, and received EncpkxM+r, Bob decrypts this ciphertext using its master secret key msk following the system decryption algorithm sDec and obtains M+r. It then encrypts M+r with pky and sends the output EncpkyM+r to Alice. Alice eliminates r in the ciphertext by computing EncpkyM+r⋅Encpky−r and obtains EncpkyM as the final output.


## 4.1.2. Secure Multiplication Protocol

Secure multiplication (SM) protocol is used to obtain the ciphertext of messages’ multiplication with corresponding messages’ ciphertexts using the BCP homomorphic cryptosystem. It is required in this process that the messages should not be exposed. The same as SCT protocol, we also assume two entities in SM protocol, i.e., Alice and Bob. Alice attempts to obtainEncpkxM1⋅M2 from EncpkxM1,EncpkxM2 without revealing M1,M2 to Bob who is the owner of the corresponding secret key sk. We define SM protocol in Algorithm 3.Algorithm 3:SM protocol.
Input: Alice:EncpkxM1,EncpkxM2
Bob:skx.
Begin: Alice:
(a) Pick random numbersr1,r2∈ℤN
(b) ComputeEncpkxM1+r1⟵EncpkxM1⋅Encpkxr1
(c) ComputeEncpkxM2+r2⟵EncpkxM2⋅Encpkxr2
(d) SendEncpkxM1+r1,EncpkxM2+r2 to Bob
Bob:
(a) DecryptM1+r1⟵DecskxEncpkxM1+r1
(b) DecryptM2+r2⟵DecskxEncpkxM1+r1
(c) ComputeΛ=M1+r1M2+r2
(d) ComputeEncpkxΛ
(e) SendEncpkxΛ to Alice
Alice:
(a) ComputeEncpkxM1⋅M2=EncpkxM1N−r2
EncpkxM2N−r1⋅Encpkxr1r2N−1⋅EncpkxΛ
Output:EncpkxM1⋅M2Taking as the input the ciphertextEncpkxM1 and EncpkyM2, Alice randomly chooses numbers r1,r2∈ℤN and computes the ciphertext of M1+r1,M2+r2 by computing EncpkxM1⋅Encpkxr1 and EncpkxM2⋅Encpkxr2 respectively. This utilizes the additive homomorphic property of BCP encryption. It then sends the output EncpkxM1+r1,EncpkxM2+r2 to Bob. Taking as the input the corresponding secret key skx of pkx, Bob decrypts the received ciphertexts with skx and obtains M1+r1,M2+r2. It computes the multiplication of M1+r1,M2+r2 as Λ=M1+r1⋅M2+r2=M1⋅M2+r2M1+r1M2+r1r2 and encrypts Λ with pkx as EncpkxΛ which is used to divide M1⋅M2 in the underlying message. Bob sends EncpkxΛ to Alice. Finally, Alice computes EncpkxM1⋅M2 with EncpkxΛ,r1,r2,EncpkxM1,EncpkxM2 using the additive homomorphic property of BCP encryption.


## 4.1.3. Secure Distance Measurement Protocol

We define the secure distance measurement (SDM) protocol to measure the distance between data records and cluster centers using Euclidean distance. Assume there aren data records and k clusters. Let s⟶j=sj,1,sj,2,…,sj,m be the sum of data records in cluster cj and cj be the number of data records in cluster cj, respectively. Given a data record d⟶i=di,1,di,2,…,di,m and a cluster center μ⟶j=μi,1,μi,2,…,μi,m, Ωi,j is denoted as the scaled squared distance between d⟶i and μ⟶j satisfying Distd⟶i,μ⟶j=Ωi,j/cj. Therefore, Ωi,j is denoted and computed as in the following equation:(11)Ωi,j=Distd→i,μ→j⋅cj2.=∑α=1mcj,di,α−sj,α2The process is depicted as Algorithm4.Algorithm 4:SDM protocol.
Input:Encpkxd⟶i,Encpkxsj⟶,cj
Begin:EncpkxΩi,j=0
for α=1 to m
1. Run SM protocol onEncpkxdi,α and Encpkxcj to obtain Γ=Encpkxcj⋅di,α
2. ComputeEncpkxΩi,j=Γ⋅Encpkxsj,αN−12+EncpkxΩi,j
end for
Output:EncpkxΩi,j,cj


## 4.1.4. Secure Distance Comparison Protocol

Secure distance comparison (SDC) protocol is to determine the shorter distance between two output distances from SDM protocol. Taking as the input two distances, i.e.,EncpkxΩi,a,ca and EncpkxΩi,b,cb, Alice interacts with Bob to obtain the shorter one. As in [19], the difference between two differences can be expressed as(12)EncpkxDistd⟶i,μ⟶a⋅EncpkxDistd⟶i,μ⟶bN−1=EncpkxDistd⟶i,μ⟶a−Distd⟶i,μ⟶b=EncpkxΩ/ca2−Ωi,b/cb2=Encpkxcb2Ωi,a−ca2Ωi,bca2cb2.Since we only need to know whethercb2Ωi,a−ca2Ωi,b/ca2cb2>0 or not, it is equal to judge whether cb2Ωi,a−ca2Ωi,b>0 or not. This means, the comparison can be related to(13)Encpkxcb2Ωi,a−ca2Ωi,b.Letβ be the maximum size of messages. We have M∈−2β+1,2β−1, which means MmodN∈1,2β−1 if M>0 and MmodN∈N−2β+1,N−1. Let η be the threshold for sign judgement chosen from 2β−1,N+2β−1. To prevent Bob from obtaining distance-related information, Alice blinds the message with a random r∈1,minN−η,N−ϕN/2β−1 with ϕ∈ℤ and satisfying(14)2β−1⋅rmodN<ηN−1⋅rmodN>ηN+1−2β⋅rmodN>η..We illustrate the detailed realization in Algorithm5.Algorithm 5:SDC protocol..
Input: Alice:EncpkxΩi,a,ca,EncpkxΩi,b,cb,sky
Bob:skx,pky
Begin: Alice interacts with Bob to compute:
(a)EncpkxΩi,a′⟵SMEncpkxΩi,a,Encpkxb2
(b)EncpkxΩi,b′⟵SMEncpkxΩi,b,Encpkxa2
Alice:
(a) ComputeEncpkxΩi,b′=EncpkxΩi,b′N−1
(b) ComputeEncpkxΔa,b=EncpkxΩi,a′⋅EncpkxΩi,b″
(c) Pick a random numberr∈ℤN
Alice interacts with Bob to compute:
(a)EncpkxrΔa,b⟵SMEncpkxr,EncpkxΔa,b
Alice:
(a) SendEncpkxrΔa,b to Bob
Bob:
(a) DecryptrΔa,b⟵DecEncpkxrΔa,b
(b) IfrΔa,b>η, sn⟵Encpky1; otherwise, randomly choose r′∈ℤN satisfying r≠1, sn⟵Encpkyr′
(c) Sendsn to Alice
Alice:
(a) IfDecskysn=1, let EncpkxΩi,min=EncpkxΩi,a, cmin=ca; Otherwise, we have Decskysn≠1, let EncpkxΩi,min=EncpkxΩi,b,ci,min=cb
Output:EncpkxΩi,min,ci,minIn the process, Bob cannot obtainΩi,a,Ωi,b.


## 4.1.5. Secure Minimum Distance Measurement Protocol

Finally, we define the secure minimum distance measurement (SMDM) protocol as Algorithm6 to choose the shortest one among given distances.Algorithm 6:SMDM protocol.
Input:Encpkxd⟶i,Encpkxμ⟶1,Encpkxμ⟶2,…,Encpkxμ⟶k
Begin:for α=1 to k
(a) RunSDMEncpkxd⟶i,Encpkxμ⟶α and obtain the output EncpkxΩi,α,cα
end for
LetEncpkxΩi,min,ci,min=EncpkxΩi,1,c1
for α=2 to k
(a) RunSDCEncpkxΩi,min,ci,min,EncpkxΩi,2,c2 and obtain the output EncpkxΩi,min,ci,min
(b) SetEncpkxΩi,min,ci,min≔EncpkxΩi,min,ci,min
end for
Output:EncpkxΩi,min,ci,min


## 4.2. Our Scheme

At the beginning, the four entities in the system, i.e., data owners DOs, query client QC, cloud computing service CCS, and key management server KMS, setup the system by running the algorithms,Setup, KeyGen, and AKeyGen. DOs then run Enc and AEnc on their data records and upload to CCS separately. CCS decrypts the received ciphertexts using ADec. After receiving the clustering request from QC, CCS interacts with KMS to transform the ciphertexts encrypted under different public keys to ciphertexts encrypted under the same public key. Subsequently, CCS performs the clustering computation. Finally, CCS interacts with KMS to transfer the clustering result to QC. It is worth noting that the defined protocols are invoked through the process.


### 4.2.1. System Setup

As the setting in the system model (see Section 4.1), we haven data owners DOi1≤i≤n, cloud computing servers (CCS), key management server (KMS), and query client (QC). Before running the protocols, related entities in the system model generate their keys as follows:(1)
Taking as the input a security parameter λ, KMS runs the setup algorithmSetupλ of the BCP homomorphic cryptosystem and generate the public parameter pp and master secret key msk, where msk is kept secret(2)
Each data ownerDOi runs KeyGenpp to generate its own public/secret key pair pki,ski, 1≤i≤n(3)
EachDOi consults with CCS a symmetric key aski through Diffie–Hellman key exchange protocol or other methods for 1≤i≤n(4)
CCS runs the key generation algorithmKeyGenpp to generate its public/secret key pair as pkc,skc(5)
QC runsKeyGenpp to generate its own public/secret key pair pkq,skq


### 4.2.2. Data Uploading

Following the setting in Section 4.1, assume that each data ownerDOi has a dataset Di which contains ni data records, and each record has m attributes, and DOi encrypts Di with BCP cryptosystem first and then AES encryption, 1≤i≤n. Finally, DOi sends the output to CCS.(1)
DOi then runs the encryption algorithm on each record dji⟶=dj,1i,dj,2i,…,dj,mi,j∈1,ni and obtains the encrypted result as(15)Encpkid⟶ji1≤j≤ni.(2)
To prevent the privacy disclosure from KMS, data owners double-encrypt the output ciphertext with AES encryption. EachDOi computes(16)aEncaskiEncpkid⟶ji1≤j≤ni,and sends the output results to CCS.(3)
After receivingaEncaskiEncpkid⟶ji1≤j≤ni from DOi, CCS runs the decryption algorithm aDEC with the consulted symmetric key aski on each ciphertext to obtain(17)aDECaskaEncaskEncpkid⟶ji1≤i≤ni=Encpkid⟶ji1≤i≤ni.In our setting for data uploading, each data ownerDOi sends their double-encrypted ciphertext to CCS such that the KMS cannot obtain the original message of the data owner although the KMS has the master secret key msk which can be used to decrypt the ciphertext encrypted under the BCP homomorphic cryptosystem.


### 4.2.3. Ciphertext Transformation

This phase is to transfer “multiuser” to “single-user” by re-encrypting the ciphertext encrypted under the public key ofpki to the ciphertext encrypted under pkc, 1≤i≤n.(1)
QC sends a clustering request to CCS.(2)
For a ciphertextEncpkid⟶ji from DOi, CCS interacts with KMS to run the SCT protocol by setting pkx=pki,pky=pkc,EncpkxM=Encpkid⟶ji,msk=msk. Finally, CCS obtains Encpkcd⟶ji.(3)
By performing the SCT protocol on all the ciphertexts received fromDOi1≤i≤n, CCS finally obtains(18)Encpkcd⟶ji1≤i≤n,1≤j≤ni.Letn=n1+n2+⋯+nl, and denote these n ciphertexts as(19)Encpkcd⟶i1≤i≤n.For simplicity, we denoteEncpkcd⟶i as Encd⟶i in the following.It is worth noting that the final ciphertexts are unknown to the KMS since they are blinded in the SCT protocol.


### 4.2.4. Clustering Computation

In this phase, CCS computes the clustering results withk randomly chosen cluster centers Encμ⟶1,Encμ⟶2,…,Encμ⟶k from Encpkcd⟶i1≤i≤n. Let Encμ⟶i=Encs⟶j=Encsj,1,Encsj,2,…,Encsj,m and ci=1. CCS also outputs a matrix Vn×k which refers to the location in k clusters of n records, where Vi,j=1 means d⟶i is allocated to j-th cluster. In addition, there is a maximum iteration time ϕmax. Let ϕ=0.(1)
For a data recordEncd⟶i, CCS runs the SMDM protocol on it and k-cluster centers with the setting pkx=pkc. Finally, CCS obtains the output(20)EncΩi,min,ci,min,whereci,min=cα. Let Vi,j=0 for j≠α.(2)
For each data recordEncd⟶i where d⟶i≠μ⟶j,1≤i≤n,1≤j≤k, CCS runs step 1 and obtains(21)EncΩi,min,ci,min,1≤i≤n,and the matrixVn×k.(3)
With the matrixVn×k and data records Encd⟶i=Encdi,1,di,2,…,di,m, if Vi,j=1, CCS updates cj=cj+1 and Encsj,α as(22)Encdi,α⋅Encsj,α=Encdi,α+sj,α,for1≤α≤m. Finally, CCS obtains new cj and Encs⟶j=Encsj,1,Encsj,2,…,Encsj,m for 1≤j≤k. Let ϕ=ϕ+1.(4)
Ifϕ<ϕmax and the output matrix Vn×k is different from that in the last iteration, CCS starts a new iteration by running steps (1), (2), and (3). Otherwise, CCS outputs the final(23)Encs⟶j,cj1≤j≤k.


### 4.2.5. Result Retrieval

(1)
CCS interacts with KMS to run the SCT protocol onEncpkcs⟶j1≤j≤k with the setting pkx=pkc,pky=pkq,EncpkxM=Encpkcs⟶j. CCS obtains
(24)
Enc
pk
q
s
⟶
j
1
≤
j
≤
k
and sends it andVn×k to QC.
(2)
QC decrypts the receivedEncpkqs⟶j with its secret key skq by computing
(25)
Dec
sk
q
Enc
pk
q
s
⟶
j
=
s
⟶
j
1
≤
j
≤
k
.
QC then computes the cluster centers as
(26)
s
⟶
j
c
j
1
≤
j
≤
k
,
wherecj=∑i=1nVi,j.


## 4.2.1. System Setup

As the setting in the system model (see Section 4.1), we haven data owners DOi1≤i≤n, cloud computing servers (CCS), key management server (KMS), and query client (QC). Before running the protocols, related entities in the system model generate their keys as follows:(1)
Taking as the input a security parameter λ, KMS runs the setup algorithmSetupλ of the BCP homomorphic cryptosystem and generate the public parameter pp and master secret key msk, where msk is kept secret(2)
Each data ownerDOi runs KeyGenpp to generate its own public/secret key pair pki,ski, 1≤i≤n(3)
EachDOi consults with CCS a symmetric key aski through Diffie–Hellman key exchange protocol or other methods for 1≤i≤n(4)
CCS runs the key generation algorithmKeyGenpp to generate its public/secret key pair as pkc,skc(5)
QC runsKeyGenpp to generate its own public/secret key pair pkq,skq


## 4.2.2. Data Uploading

Following the setting in Section 4.1, assume that each data ownerDOi has a dataset Di which contains ni data records, and each record has m attributes, and DOi encrypts Di with BCP cryptosystem first and then AES encryption, 1≤i≤n. Finally, DOi sends the output to CCS.(1)
DOi then runs the encryption algorithm on each record dji⟶=dj,1i,dj,2i,…,dj,mi,j∈1,ni and obtains the encrypted result as(15)Encpkid⟶ji1≤j≤ni.(2)
To prevent the privacy disclosure from KMS, data owners double-encrypt the output ciphertext with AES encryption. EachDOi computes(16)aEncaskiEncpkid⟶ji1≤j≤ni,and sends the output results to CCS.(3)
After receivingaEncaskiEncpkid⟶ji1≤j≤ni from DOi, CCS runs the decryption algorithm aDEC with the consulted symmetric key aski on each ciphertext to obtain(17)aDECaskaEncaskEncpkid⟶ji1≤i≤ni=Encpkid⟶ji1≤i≤ni.In our setting for data uploading, each data ownerDOi sends their double-encrypted ciphertext to CCS such that the KMS cannot obtain the original message of the data owner although the KMS has the master secret key msk which can be used to decrypt the ciphertext encrypted under the BCP homomorphic cryptosystem.


## 4.2.3. Ciphertext Transformation

This phase is to transfer “multiuser” to “single-user” by re-encrypting the ciphertext encrypted under the public key ofpki to the ciphertext encrypted under pkc, 1≤i≤n.(1)
QC sends a clustering request to CCS.(2)
For a ciphertextEncpkid⟶ji from DOi, CCS interacts with KMS to run the SCT protocol by setting pkx=pki,pky=pkc,EncpkxM=Encpkid⟶ji,msk=msk. Finally, CCS obtains Encpkcd⟶ji.(3)
By performing the SCT protocol on all the ciphertexts received fromDOi1≤i≤n, CCS finally obtains(18)Encpkcd⟶ji1≤i≤n,1≤j≤ni.Letn=n1+n2+⋯+nl, and denote these n ciphertexts as(19)Encpkcd⟶i1≤i≤n.For simplicity, we denoteEncpkcd⟶i as Encd⟶i in the following.It is worth noting that the final ciphertexts are unknown to the KMS since they are blinded in the SCT protocol.


## 4.2.4. Clustering Computation

In this phase, CCS computes the clustering results withk randomly chosen cluster centers Encμ⟶1,Encμ⟶2,…,Encμ⟶k from Encpkcd⟶i1≤i≤n. Let Encμ⟶i=Encs⟶j=Encsj,1,Encsj,2,…,Encsj,m and ci=1. CCS also outputs a matrix Vn×k which refers to the location in k clusters of n records, where Vi,j=1 means d⟶i is allocated to j-th cluster. In addition, there is a maximum iteration time ϕmax. Let ϕ=0.(1)
For a data recordEncd⟶i, CCS runs the SMDM protocol on it and k-cluster centers with the setting pkx=pkc. Finally, CCS obtains the output(20)EncΩi,min,ci,min,whereci,min=cα. Let Vi,j=0 for j≠α.(2)
For each data recordEncd⟶i where d⟶i≠μ⟶j,1≤i≤n,1≤j≤k, CCS runs step 1 and obtains(21)EncΩi,min,ci,min,1≤i≤n,and the matrixVn×k.(3)
With the matrixVn×k and data records Encd⟶i=Encdi,1,di,2,…,di,m, if Vi,j=1, CCS updates cj=cj+1 and Encsj,α as(22)Encdi,α⋅Encsj,α=Encdi,α+sj,α,for1≤α≤m. Finally, CCS obtains new cj and Encs⟶j=Encsj,1,Encsj,2,…,Encsj,m for 1≤j≤k. Let ϕ=ϕ+1.(4)
Ifϕ<ϕmax and the output matrix Vn×k is different from that in the last iteration, CCS starts a new iteration by running steps (1), (2), and (3). Otherwise, CCS outputs the final(23)Encs⟶j,cj1≤j≤k.


## 4.2.5. Result Retrieval

(1)
CCS interacts with KMS to run the SCT protocol onEncpkcs⟶j1≤j≤k with the setting pkx=pkc,pky=pkq,EncpkxM=Encpkcs⟶j. CCS obtains
(24)
Enc
pk
q
s
⟶
j
1
≤
j
≤
k
and sends it andVn×k to QC.
(2)
QC decrypts the receivedEncpkqs⟶j with its secret key skq by computing
(25)
Dec
sk
q
Enc
pk
q
s
⟶
j
=
s
⟶
j
1
≤
j
≤
k
.
QC then computes the cluster centers as
(26)
s
⟶
j
c
j
1
≤
j
≤
k
,
wherecj=∑i=1nVi,j.


## 5. Security and Performance Analysis

### 5.1. Security Analysis

As shown in the proposed scheme (see Section 4.2), our protocol is realized by invoking the BCP homomorphic cryptosystem, AES encryption, and the defined protocols. Upon that, the former two cryptosystems are semantic secure, and we give the security proof of the defined protocols as follows. We take the SM protocol’s security proof under “Real-vs.-Ideal” framework as an example. Other protocols’ security proofs are in a similar manner and we omit here.Theorem 1.
SM protocol is secure.Proof.
SM protocol relates to two semihonest parties, namely, Alice and Bob. Therefore, we consider both securities of SM protocol against semihonest attacker AliceAA and semihonest attacker Bob AB. In the protocol, Alice takes as the input pkx,EncpkxM1,EncpkxM2 and Bob takes as the input the corresponding secret key skx of public key pkx.(i)
Security againstAA: In the SM protocol, the real-world view of the attacker ℤA includes the input pkx,EncpkxM1,EncpkxM2, random numbers r1,r2, EncpkxΛ, and the output EncpkxM1⋅M2, where Λ=M1+r1M2+r2. AA tries to obtain useful information about the underlying messages, i.e., M1,M2,M1+r1M2+r2,M1⋅M2 that are encrypted under pkx. Because of the semantic security of the used BCP homomorphic cryptosystem, we have that AA cannot extract any information of underlying messages except the bit length without skx. Therefore, we can construct a simulator SA in the ideal world by using ciphertexts of random chosen messages. It will be computationally hard for AA to distinguish the ideal world with real world because of the semantic security of the BCP homomorphic cryptosystem. We have(27)IdealSA,AA≈cRealSM,AA,where≈c means computationally indistinguishable.(ii)
Security againstAB: In the protocol, AB takes as the input the secret key skx of pkx and EncpkxM1+r1,EncpkxM2+r2. With skx, AB can decrypt the ciphertexts and obtain the underlying messages M1+r1,M2+r2. However, since r1,r2 are randomly chosen by Alice, they are random numbers in the point of view of AB. We can then construct a simulator SB in the ideal world by using ciphertexts of random chosen messages, and it will be computationally hard for AB to distinguish the ideal world with the real world. We have(28)IdealSB,AB≈cRealSM,AB.
This completes the proof of Theorem1.
Next, we prove that our protocol is secure by taking the process of data uploading as an example.Theorem 2.
The data uploading process is secure.Proof.
In the data uploading process, data owners (DOs) double-encrypt their data records withpk and ask using the BCP homomorphic cryptosystem and AES encryption separately. They then send the encrypted result to CCS who has ask but does not have the corresponding secret key sk of pk. Because of the semantic security of the BCP homomorphic cryptosystem, it is secure against semihonest CCS. Although KMS can extract the underlying messages of ciphertexts encrypted using the BCP homomorphic cryptosystem, it is also computationally hard for a semihonest KMS to obtain any information of data records with the semantic security of AES encryption. Furthermore, CCS and KMS are supposed not to collude in our scheme such that the data uploading process is secure against semihonest CCS and KMS separately. This completes the proof of Theorem 2.
It is worth noting that the security of our construction is protected by the semantic security of the BCP homomorphic cryptosystem, AES encryption, and blinding with random numbers, which prevents the adversaries from obtaining any useful information from the received ciphertexts.


### 5.2. Performance Analysis

In our construction, we use the BCP homomorphic cryptosystem and AES encryption to encrypt data owners’ data records to prevent the information disclosure to KMS. Compared with the underlying scheme [19] which utilizes Youn’s homomorphic encryption scheme [33], our scheme therefore increases the computation cost between DOs and CCS along with the increased security.In particular, each data owner additionally needs to interact with CCS to consult a symmetric key of AES encryption in the system setup phase. Except this, since BCP encryption has additive homomorphic property instead multiplication in Youn’s encryption scheme [33], we give a secure multiplication protocol SM instead of secure addition SA in [19]. This leads to different invocations in other defined protocols, which result in more computation cost.With the sacrifice on the computation cost, our scheme achieves semantic security that adversaries cannot obtain any useful information about underlying data records, while AS can extractM1/M2 in SA protocol of [19]. Furthermore, in our scheme, KMS cannot extract the underlying data records of data owners, while KMS can realize this with its master secret key in [19].Finally, we compare our scheme with the existing outsourcedk-means clustering schemes [19, 22, 23, 26, 30, 34] in Table 2 on six aspects, i.e., whether the scheme is based on symmetric or asymmetric cryptosystem, whether it supports or achieves multiple data owners and multiple keys, ciphertext comparison, security, and multidimensional data. As shown in Table 2, our scheme achieves all the listed functionalities under the asymmetric cryptosystem.Table 2
The summary of schemes.
Scheme
S/AS
Multiple data owners
Multiple keys
Cipher comparison
Security
Multidimensional data
[22]
AS
×
×
×
×
√
[23]
S
×
×
√
√
√
[26]
AS
√
×
√
√
√
[30]
AS
√
√
√
×
√
[34]
AS
√
√
√
×
√
[19]
AS
√
√
√
×
√
Ours
AS
√
√
√
√
√
S/AS: symmetric/asymmetric.


## 5.1. Security Analysis

As shown in the proposed scheme (see Section 4.2), our protocol is realized by invoking the BCP homomorphic cryptosystem, AES encryption, and the defined protocols. Upon that, the former two cryptosystems are semantic secure, and we give the security proof of the defined protocols as follows. We take the SM protocol’s security proof under “Real-vs.-Ideal” framework as an example. Other protocols’ security proofs are in a similar manner and we omit here.Theorem 1.
SM protocol is secure.Proof.
SM protocol relates to two semihonest parties, namely, Alice and Bob. Therefore, we consider both securities of SM protocol against semihonest attacker AliceAA and semihonest attacker Bob AB. In the protocol, Alice takes as the input pkx,EncpkxM1,EncpkxM2 and Bob takes as the input the corresponding secret key skx of public key pkx.(i)
Security againstAA: In the SM protocol, the real-world view of the attacker ℤA includes the input pkx,EncpkxM1,EncpkxM2, random numbers r1,r2, EncpkxΛ, and the output EncpkxM1⋅M2, where Λ=M1+r1M2+r2. AA tries to obtain useful information about the underlying messages, i.e., M1,M2,M1+r1M2+r2,M1⋅M2 that are encrypted under pkx. Because of the semantic security of the used BCP homomorphic cryptosystem, we have that AA cannot extract any information of underlying messages except the bit length without skx. Therefore, we can construct a simulator SA in the ideal world by using ciphertexts of random chosen messages. It will be computationally hard for AA to distinguish the ideal world with real world because of the semantic security of the BCP homomorphic cryptosystem. We have(27)IdealSA,AA≈cRealSM,AA,where≈c means computationally indistinguishable.(ii)
Security againstAB: In the protocol, AB takes as the input the secret key skx of pkx and EncpkxM1+r1,EncpkxM2+r2. With skx, AB can decrypt the ciphertexts and obtain the underlying messages M1+r1,M2+r2. However, since r1,r2 are randomly chosen by Alice, they are random numbers in the point of view of AB. We can then construct a simulator SB in the ideal world by using ciphertexts of random chosen messages, and it will be computationally hard for AB to distinguish the ideal world with the real world. We have(28)IdealSB,AB≈cRealSM,AB.
This completes the proof of Theorem1.
Next, we prove that our protocol is secure by taking the process of data uploading as an example.Theorem 2.
The data uploading process is secure.Proof.
In the data uploading process, data owners (DOs) double-encrypt their data records withpk and ask using the BCP homomorphic cryptosystem and AES encryption separately. They then send the encrypted result to CCS who has ask but does not have the corresponding secret key sk of pk. Because of the semantic security of the BCP homomorphic cryptosystem, it is secure against semihonest CCS. Although KMS can extract the underlying messages of ciphertexts encrypted using the BCP homomorphic cryptosystem, it is also computationally hard for a semihonest KMS to obtain any information of data records with the semantic security of AES encryption. Furthermore, CCS and KMS are supposed not to collude in our scheme such that the data uploading process is secure against semihonest CCS and KMS separately. This completes the proof of Theorem 2.
It is worth noting that the security of our construction is protected by the semantic security of the BCP homomorphic cryptosystem, AES encryption, and blinding with random numbers, which prevents the adversaries from obtaining any useful information from the received ciphertexts.


## 5.2. Performance Analysis

In our construction, we use the BCP homomorphic cryptosystem and AES encryption to encrypt data owners’ data records to prevent the information disclosure to KMS. Compared with the underlying scheme [19] which utilizes Youn’s homomorphic encryption scheme [33], our scheme therefore increases the computation cost between DOs and CCS along with the increased security.In particular, each data owner additionally needs to interact with CCS to consult a symmetric key of AES encryption in the system setup phase. Except this, since BCP encryption has additive homomorphic property instead multiplication in Youn’s encryption scheme [33], we give a secure multiplication protocol SM instead of secure addition SA in [19]. This leads to different invocations in other defined protocols, which result in more computation cost.With the sacrifice on the computation cost, our scheme achieves semantic security that adversaries cannot obtain any useful information about underlying data records, while AS can extractM1/M2 in SA protocol of [19]. Furthermore, in our scheme, KMS cannot extract the underlying data records of data owners, while KMS can realize this with its master secret key in [19].Finally, we compare our scheme with the existing outsourcedk-means clustering schemes [19, 22, 23, 26, 30, 34] in Table 2 on six aspects, i.e., whether the scheme is based on symmetric or asymmetric cryptosystem, whether it supports or achieves multiple data owners and multiple keys, ciphertext comparison, security, and multidimensional data. As shown in Table 2, our scheme achieves all the listed functionalities under the asymmetric cryptosystem.Table 2
The summary of schemes.
Scheme
S/AS
Multiple data owners
Multiple keys
Cipher comparison
Security
Multidimensional data
[22]
AS
×
×
×
×
√
[23]
S
×
×
√
√
√
[26]
AS
√
×
√
√
√
[30]
AS
√
√
√
×
√
[34]
AS
√
√
√
×
√
[19]
AS
√
√
√
×
√
Ours
AS
√
√
√
√
√
S/AS: symmetric/asymmetric.


## 6. Conclusions

This paper proposed a highly secure privacy-preserving outsourcedk-means clustering scheme on the encrypted datasets under multiple keys. We utilized BCP homomorphic encryption and AES encryption to double-encrypt the data records in the database to protect the security against semihonest cloud computing server and key management server. Furthermore, we constructed five protocols, i.e., secure ciphertext transformation (SCT), secure multiplication (SM), secure distance measurement (SDM), secure distance comparison (SDC), and secure minimum distance measurement (SMDM), as the base of our scheme. In particular, SM protocol is built to achieve the homomorphic multiplicative property using BCP encryption. Finally, we proposed our scheme by invoking the defined protocols thoroughly. The given security and performance analysis shows that our scheme is comparable with the existing outsourced k-means clustering scheme on security and functionality.



---

*Source: 1238505-2020-03-09.xml*