# Privacy-Preserving KNN Classification Algorithm for Smart Grid

Authors: Zhuhuan Song; Yanli Ren; Gang He
Journal: Security and Communication Networks
 (2022)

---

## Abstract

With the development of Internet of Things (IOT), outsourcing data and tasks to a cloud server has become a popular and economical way for small devices with restricted ability. Thek-nearest neighbors (KNNs) classification algorithm have been commonly applied to medical image classification, abnormal detection, defective product identification, and so on. The previous privacy-preserving KNN algorithms are based on two cloud servers, which have high computational and communication costs. In this paper, we design a privacy-preserving KNN classification (PPKC) algorithm with single cloud server for smart grid. Specifically, each smart meter and control center encrypted their data with Paillier cryptosystem and the cloud server does some calculation on the encrypted data. We prove that PPKC can protect the privacy of both smart meters and control centers, and the classification results are also private for the server. Besides, both smart meters and control centers can stay offline after uploading their data. The experiment results demonstrate that the proposed PPKC algorithm is more efficient than the previous algorithms and it can obtain almost the same accuracy as the original KNN, which means the PPKC algorithm is more applicable for small devices in IOT.


---

## Body

## 1. Introduction

In recent years, Internet of Things (IOT) has been widely used in medical devices, industrial detection, intelligent transportation, and so on. At the same time, more and more applications of machine learning have been applied to IOT, which can greatly facilitate our work and life [1].As we know, a large amount of data can be generated in IOT. If massive data is given to small terminals for storage or calculation, it may undoubtedly increase the burden of these devices and reduce their efficiency [2]. In the worst case, this may even lead to calculation errors and the loss of stored data. Fortunately, the cloud server can be used to store and calculate data. Generally speaking, the cloud server has huge computing resources and storage capacity [3]. For these devices or users with insufficient computing power, they only need to spend a small amount of money and then enjoy the benefits of cloud platform including powerful computing ability and massive storage resources. For example, in the medical industry, using cloud platform can help doctors judge the specific situation of the disease quickly and then save the lives of patients [4].Notice that training models of machine learning or deep learning on cloud platform can also bring great convenience to those users with limited computing power [5]. However, the users cannot directly outsource private data to the cloud server since it is always untrusted. Usually, the devices or users encrypt sensitive information before sending them to the cloud server. Unfortunately, calculating on the encrypted data may not get the correct answer. In addition, for small devices, many encryption algorithms may also consume a lot of computing resources and spend a lot of time. Therefore, it is urgent to propose an efficient privacy-preserving algorithm for the outsourced data.At present, there are many machine learning algorithms, such as decision tree [6], k-means [7], support vector machine (SVM) [8], and so on. By using these algorithms, we can efficiently carry out the classification task and get the results. Note that k-nearest neighbor (KNN) [9] classification algorithm is one of the most commonly used machine learning algorithms, which has been widely applied to IOT, including smart grid and smart home. Typically, KNN classification algorithm can obtain high accuracy in medical image classification, abnormal detection, defective product identification, and so on. For example, a lot of electrical consumption data will be generated in smart grid where the control centers collect the electricity consumption in a specific area and adjust the power generation to maintain the balance of supply and power demand. However, KNN classification may have a high computational complexity for big data, and the resource-constrained terminals may spend much time to complete the algorithm. Outsourcing these tasks to the cloud server is a solution to this problem. In the past few years, many privacy-preserving KNN classification algorithms have been presented. However, they either have security risks or are based on several noncolluding cloud servers [10, 11], which may be very difficult to be realized. Therefore, we aim to propose an efficient and secure privacy-preserving KNN classification algorithm for the outsourced data with only one cloud server.


### 1.1. Related Work

With the rapid development of machine learning, people pay more attention to the security risks. Rahulamathavan et al. [12] designed a secure SVM classification algorithm, which uses Paillier homomorphic encryption to protect the data. However, this scheme cannot protect the output result from the cloud server. Yuan and Tian [13] put forward a secure K-means clustering algorithm by using MapReduce, which encrypts the data based on the learning with error (LWE) problem, and the cloud server iterates on the encrypted data. However, the client should interact with cloud server several times, which appends the communication costs of the client. Liu et al. [14] proposed a secure decision tree training and evaluation algorithm, which realized data privacy protection by using public key encryption with distributed trapdoors and additive secret sharing. This protocol protects the secret of users well, but it can only be used in ID3 algorithm and is not applicable to other decision tree algorithms.Many privacy-preserving KNN classification protocols have been extensively studied in the past years. Samanthula et al. [10] presented the first privacy-preserving KNN classification protocol, which used the Paillier cryptosystem and two cloud servers to build some secure blocks, including secure Euclidean distance, secure multiplication, secure minimum value, and secure frequency to hide the private data. However, the computation complexity is very high, and it is infeasible for limited users on large datasets. Rong et al. [15] presented a cooperative KNN protocol with ElGamal cryptosystem [16]. However, the protocol has high computational complexity and uses two cloud servers. For multiple data owners, Li et al. [17] proposed a secure KNN classification protocol. However, this protocol cannot protect the outputs from the servers. Cheng et al. [18] put forward a secure KNN query protocol with multiple keys. Unfortunately, the protocol is based on multiple servers and cannot realize the privacy of data. Yang et al. [19] designed an efficient KNN scheme by using vector homomorphic encryption (VHE) [20], which achieved high efficiency. However, it is proved that VHE has some secure risks in [21]. After that, Yang et al. [22] designed a secure VHE and applied it to KNN classification, but the query data cannot be protected from the server. Liu et al. [11] presented an efficient KNN classification protocol, which greatly improves the computational efficiency by using additive secret sharing. However, this protocol uses two noncolluding servers and needs multiple interactions between servers.In summary, there is no privacy-preserving KNN algorithm that can simultaneously realize the privacy of data, query, and classification results based on only one cloud server.


### 1.2. Our Contributions

In this paper, we propose a privacy-preserving KNN classification (PPKC) algorithm with only one cloud server for smart grid, which is much more secure and efficient compared with the previous algorithms [10, 11]. Specifically, the contributions of this paper are summarized as follows.(1)
Based on the Paillier cryptosystem, we design a privacy-preserving KNN classification (PPKC) algorithm, which only uses one cloud server. In [10, 11], the outsourcing algorithms of KNN are all based on two noncolluding servers, which needs multiple interactions between servers and is almost impossible in practical applications.(2)
The proposed PPKC can not only realize the privacy of both control centers and smart meters but also protect the final outputs from the servers. After the smart meters upload encrypted data to the cloud server, they only need to keep offline. Similarly, the control centers upload encrypted query data and then keep offline until the cloud server return the encrypted results. Therefore, the proposed algorithm can not only protect the sensitive information but also reduce the computational and communication costs of smart meters and control centers as much as possible.(3)
Some experiments are evaluated to analyze the performance of PPKC on four relevant datasets. The PPKC algorithm is the most efficient for the smart meters compare with the previous work. Besides, the accuracy of proposed PPKC is nearly same as the original KNN, which means PPKC can help control centers find the abnormal power consumption of smart meters without leaking privacy.The rest of our paper is organized as follows. We briefly introduce some preliminaries in Section2. Section 3 formalizes the concrete construction of PPKC algorithm. We give the security proofs, computational complexity, and efficiency comparisons in Section 4. Section 5 gives the performance evaluations of efficiency and accuracy. Finally, we conclude the paper in Section 6.


## 1.1. Related Work

With the rapid development of machine learning, people pay more attention to the security risks. Rahulamathavan et al. [12] designed a secure SVM classification algorithm, which uses Paillier homomorphic encryption to protect the data. However, this scheme cannot protect the output result from the cloud server. Yuan and Tian [13] put forward a secure K-means clustering algorithm by using MapReduce, which encrypts the data based on the learning with error (LWE) problem, and the cloud server iterates on the encrypted data. However, the client should interact with cloud server several times, which appends the communication costs of the client. Liu et al. [14] proposed a secure decision tree training and evaluation algorithm, which realized data privacy protection by using public key encryption with distributed trapdoors and additive secret sharing. This protocol protects the secret of users well, but it can only be used in ID3 algorithm and is not applicable to other decision tree algorithms.Many privacy-preserving KNN classification protocols have been extensively studied in the past years. Samanthula et al. [10] presented the first privacy-preserving KNN classification protocol, which used the Paillier cryptosystem and two cloud servers to build some secure blocks, including secure Euclidean distance, secure multiplication, secure minimum value, and secure frequency to hide the private data. However, the computation complexity is very high, and it is infeasible for limited users on large datasets. Rong et al. [15] presented a cooperative KNN protocol with ElGamal cryptosystem [16]. However, the protocol has high computational complexity and uses two cloud servers. For multiple data owners, Li et al. [17] proposed a secure KNN classification protocol. However, this protocol cannot protect the outputs from the servers. Cheng et al. [18] put forward a secure KNN query protocol with multiple keys. Unfortunately, the protocol is based on multiple servers and cannot realize the privacy of data. Yang et al. [19] designed an efficient KNN scheme by using vector homomorphic encryption (VHE) [20], which achieved high efficiency. However, it is proved that VHE has some secure risks in [21]. After that, Yang et al. [22] designed a secure VHE and applied it to KNN classification, but the query data cannot be protected from the server. Liu et al. [11] presented an efficient KNN classification protocol, which greatly improves the computational efficiency by using additive secret sharing. However, this protocol uses two noncolluding servers and needs multiple interactions between servers.In summary, there is no privacy-preserving KNN algorithm that can simultaneously realize the privacy of data, query, and classification results based on only one cloud server.


## 1.2. Our Contributions

In this paper, we propose a privacy-preserving KNN classification (PPKC) algorithm with only one cloud server for smart grid, which is much more secure and efficient compared with the previous algorithms [10, 11]. Specifically, the contributions of this paper are summarized as follows.(1)
Based on the Paillier cryptosystem, we design a privacy-preserving KNN classification (PPKC) algorithm, which only uses one cloud server. In [10, 11], the outsourcing algorithms of KNN are all based on two noncolluding servers, which needs multiple interactions between servers and is almost impossible in practical applications.(2)
The proposed PPKC can not only realize the privacy of both control centers and smart meters but also protect the final outputs from the servers. After the smart meters upload encrypted data to the cloud server, they only need to keep offline. Similarly, the control centers upload encrypted query data and then keep offline until the cloud server return the encrypted results. Therefore, the proposed algorithm can not only protect the sensitive information but also reduce the computational and communication costs of smart meters and control centers as much as possible.(3)
Some experiments are evaluated to analyze the performance of PPKC on four relevant datasets. The PPKC algorithm is the most efficient for the smart meters compare with the previous work. Besides, the accuracy of proposed PPKC is nearly same as the original KNN, which means PPKC can help control centers find the abnormal power consumption of smart meters without leaking privacy.The rest of our paper is organized as follows. We briefly introduce some preliminaries in Section2. Section 3 formalizes the concrete construction of PPKC algorithm. We give the security proofs, computational complexity, and efficiency comparisons in Section 4. Section 5 gives the performance evaluations of efficiency and accuracy. Finally, we conclude the paper in Section 6.


## 2. Preliminaries

In this section, we mainly introduce the original KNN algorithm, Paillier cryptosystem, and the system model, which are the basis of the PPKC algorithm.


### 2.1.K-Nearest Neighbors (KNNs) Classification Algorithm

KNN algorithm is a nonparametric classification or regression algorithm in the field of pattern recognition. In this subsection, we briefly introduce the KNN classification algorithm. Assume that there are a few training data which have several attributes and a label. Next, there is a group of testing data which only has some attributes without labels. The aim of KNN classification algorithm is to get the label of the testing data. The specific process is as follows.(1)
Prepare training data and testing data. There arem groups of training data and each group has n attributes σi1,σi2,…,σin and a label ti, where i∈1,m. Suppose there is a group of testing data q1,q2,…,qn.(2)
Compute the Euclidean distancedi between each training data and the testing data.(1)di=q1−σi12+⋯+qn−σin2,i∈1,m.(3)
All the distancedi and its corresponding label ti are used to generate an ordered collection C=d1,t1,d2,t2,…,dm,tm.(4)
Sort the ordered collectionC of distance di and labels ti according to the distance di.(5)
Select the firstK labels from the sorted collection C.(6)
Count the frequency of theK labels and set the label with the highest frequency as the final result of the testing data.


### 2.2. Paillier Cryptosystem

Paillier cryptosystem [23] is a public key cryptosystem, which realizes additive homomorphism and is mainly used in signal processing and data processing. Its security relies on the problem of determining n-order residue classes. We briefly give the introduction of Paillier cryptosystem as follows.(1)
Key generation: input a security parameterκ and two big primes p and q with bit length κ. Calculate N=p⋅q and λ=lcmp−1,q−1, where lcm⋅ means the least common multiple. Define Lx=x−1/N. Next, choose a random generator g∈ℤN2∗ and calculate μ=LgλmodN2−1modN. Finally, the public key pk is N,g and the private key is μ,λ.(2)
Encryption: input a plaintextm∈ℤN, the ciphertext c can be computed with public key pk as follows:(2)c=Epkm=gm⋅rNmodN2,wherer is the random number in ℤN∗.(3)
Decryption: for a ciphertextc∈ℤN2∗, the plaintext m can be computed with the private key sk as follows:(3)m=Dskc=LcλmodN2⋅μmodN.In addition, the Paillier cryptosystem has the following properties:(1)
Homomorphic addition:(4)Epkm1+m2=Epkm1∗Epkm2,wherem1 and m2 are any two plaintexts and pk is the public key.(2)
Scalar multiplicative homomorphism:(5)Epka∗m=Epkma,wherea is a scalar and m is a plaintext.(3)
Semantic security: Paillier cryptosystem has been certified to be semantically secure against chosen plaintext attack [23]. The attacker has no access to obtain any sensitive data about plaintext from the ciphertext.In the proposed PPKC algorithm, smart meters and control centers first use Paillier cryptosystem to encrypt sensitive data and then transmit the ciphertext to the cloud server. Notice that all data in the Paillier cryptosystem belong toℤN. We omit mod n in the following content for simplicity.


### 2.3. System Model

The proposed PPKC can be used in the smart grid and the participants include smart meters, control centers, and the cloud server. Figure1 demonstrates the system model of PPKC algorithm.Figure 1
The system model of PPKC.Assume that there are some smart meters in a city, which can separately collect the power consumption in a region of the city and send these collected data to the cloud server. At the same time, some control centers can collect and detect abnormal data in this city. After collecting some abnormal data, the control center encrypts and sends them to the cloud server. The cloud server uses KNN classification algorithm to calculate and obtain the label of abnormal data and send it back. The control center can then timely find out which region has abnormal power consumption according to the label and solve the problem in time. The detailed introduction of each participant is listed as follows.


#### 2.3.1. Smart Meters

The smart meters are composed of various sensors which can collect the energy consumption information of electrical equipment. However, these sensors have limited storage and cannot store massive data. In the PPKC model, the smart meters send the collected data to the cloud server. Suppose there arem smart meters xi, where i∈1,m. Each smart meter xi has a dataset Di=xi1,xi2,…,xin,ti, where xi1,xi2,…,xin and ti are separately the attributes and the label of the dataset. At the same time, each smart meter xi needs to generate a tuple of random numbers ai1,ai2,…,ain,ain+1, which is used to encrypt their data. For saving storage, the smart meter uploads the ciphertext Di′ to the cloud server.


#### 2.3.2. Control Centers

The control centers in the smart grid collect abnormal data to realize power adjustment, abnormal remind, or process optimization. In the PPKC model, the control centers submit some query data to obtain the labels of abnormal data. Suppose that there arel control centers Qj, where j∈1,l. Each control center Qj has a query dataset qj=Qj1,Qj2,…,Qjn and sends encrypted query data qj′ to the cloud server. Each control center Qj broadcasts the public key to smart meters.


#### 2.3.3. Cloud Server

The cloud server has powerful computational resources and storage capacity to implement KNN classification algorithm. In the proposed PPKC algorithm, it will do some calculation on the encrypted data from smart meters and control centers and return the encrypted results to the control centers. The cloud server broadcasts the public key to smart meters and control centers. We suppose that the cloud server is honest but curious, which denotes that the cloud server correctly carries out every step in the algorithm, but may try to obtain the private data of the smart meters and control center.


### 2.4. Security Model

IND-CPA Security. In a public key cryptosystem, the indistinguishability of ciphertext against chosen plaintext attack (IND-CPA) [24] is executed by the following game between an adversary A and a challenger C.(1)
Setup. The challengerC generates public key PK and private key SK based on security parameter and publishes PK to the adversary A and keeps SK secret.(2)
Queries. The adversaryA can execute encryption queries to the challenger. The adversary A sends a plaintext m to the challenger. The challenger C executes Encrypt algorithm and generates the corresponding ciphertext c and sends it to A.(3)
Challenge. The adversaryA randomly selects two plaintexts m0, m1 with the same length and returns them to C. These two plaintexts m0, m1 are not queried in the Queries phase. The challenger randomly selects b∈0,1 and transmits the ciphertext cb=EncryptPK,mb to A.(4)
Guess.A sends a bit b′∈0,1 as its guess. If b′=b with a probability which is larger than 1/2, the adversary wins the game and the advantage is defined as Prb′=b−1/2.An encryption system ist,ε-IND-CPA secure if all t-time IND-CPA adversaries have advantage of at most ϵ in winning the game.


## 2.1.K-Nearest Neighbors (KNNs) Classification Algorithm

KNN algorithm is a nonparametric classification or regression algorithm in the field of pattern recognition. In this subsection, we briefly introduce the KNN classification algorithm. Assume that there are a few training data which have several attributes and a label. Next, there is a group of testing data which only has some attributes without labels. The aim of KNN classification algorithm is to get the label of the testing data. The specific process is as follows.(1)
Prepare training data and testing data. There arem groups of training data and each group has n attributes σi1,σi2,…,σin and a label ti, where i∈1,m. Suppose there is a group of testing data q1,q2,…,qn.(2)
Compute the Euclidean distancedi between each training data and the testing data.(1)di=q1−σi12+⋯+qn−σin2,i∈1,m.(3)
All the distancedi and its corresponding label ti are used to generate an ordered collection C=d1,t1,d2,t2,…,dm,tm.(4)
Sort the ordered collectionC of distance di and labels ti according to the distance di.(5)
Select the firstK labels from the sorted collection C.(6)
Count the frequency of theK labels and set the label with the highest frequency as the final result of the testing data.


## 2.2. Paillier Cryptosystem

Paillier cryptosystem [23] is a public key cryptosystem, which realizes additive homomorphism and is mainly used in signal processing and data processing. Its security relies on the problem of determining n-order residue classes. We briefly give the introduction of Paillier cryptosystem as follows.(1)
Key generation: input a security parameterκ and two big primes p and q with bit length κ. Calculate N=p⋅q and λ=lcmp−1,q−1, where lcm⋅ means the least common multiple. Define Lx=x−1/N. Next, choose a random generator g∈ℤN2∗ and calculate μ=LgλmodN2−1modN. Finally, the public key pk is N,g and the private key is μ,λ.(2)
Encryption: input a plaintextm∈ℤN, the ciphertext c can be computed with public key pk as follows:(2)c=Epkm=gm⋅rNmodN2,wherer is the random number in ℤN∗.(3)
Decryption: for a ciphertextc∈ℤN2∗, the plaintext m can be computed with the private key sk as follows:(3)m=Dskc=LcλmodN2⋅μmodN.In addition, the Paillier cryptosystem has the following properties:(1)
Homomorphic addition:(4)Epkm1+m2=Epkm1∗Epkm2,wherem1 and m2 are any two plaintexts and pk is the public key.(2)
Scalar multiplicative homomorphism:(5)Epka∗m=Epkma,wherea is a scalar and m is a plaintext.(3)
Semantic security: Paillier cryptosystem has been certified to be semantically secure against chosen plaintext attack [23]. The attacker has no access to obtain any sensitive data about plaintext from the ciphertext.In the proposed PPKC algorithm, smart meters and control centers first use Paillier cryptosystem to encrypt sensitive data and then transmit the ciphertext to the cloud server. Notice that all data in the Paillier cryptosystem belong toℤN. We omit mod n in the following content for simplicity.


## 2.3. System Model

The proposed PPKC can be used in the smart grid and the participants include smart meters, control centers, and the cloud server. Figure1 demonstrates the system model of PPKC algorithm.Figure 1
The system model of PPKC.Assume that there are some smart meters in a city, which can separately collect the power consumption in a region of the city and send these collected data to the cloud server. At the same time, some control centers can collect and detect abnormal data in this city. After collecting some abnormal data, the control center encrypts and sends them to the cloud server. The cloud server uses KNN classification algorithm to calculate and obtain the label of abnormal data and send it back. The control center can then timely find out which region has abnormal power consumption according to the label and solve the problem in time. The detailed introduction of each participant is listed as follows.


### 2.3.1. Smart Meters

The smart meters are composed of various sensors which can collect the energy consumption information of electrical equipment. However, these sensors have limited storage and cannot store massive data. In the PPKC model, the smart meters send the collected data to the cloud server. Suppose there arem smart meters xi, where i∈1,m. Each smart meter xi has a dataset Di=xi1,xi2,…,xin,ti, where xi1,xi2,…,xin and ti are separately the attributes and the label of the dataset. At the same time, each smart meter xi needs to generate a tuple of random numbers ai1,ai2,…,ain,ain+1, which is used to encrypt their data. For saving storage, the smart meter uploads the ciphertext Di′ to the cloud server.


### 2.3.2. Control Centers

The control centers in the smart grid collect abnormal data to realize power adjustment, abnormal remind, or process optimization. In the PPKC model, the control centers submit some query data to obtain the labels of abnormal data. Suppose that there arel control centers Qj, where j∈1,l. Each control center Qj has a query dataset qj=Qj1,Qj2,…,Qjn and sends encrypted query data qj′ to the cloud server. Each control center Qj broadcasts the public key to smart meters.


### 2.3.3. Cloud Server

The cloud server has powerful computational resources and storage capacity to implement KNN classification algorithm. In the proposed PPKC algorithm, it will do some calculation on the encrypted data from smart meters and control centers and return the encrypted results to the control centers. The cloud server broadcasts the public key to smart meters and control centers. We suppose that the cloud server is honest but curious, which denotes that the cloud server correctly carries out every step in the algorithm, but may try to obtain the private data of the smart meters and control center.


## 2.3.1. Smart Meters

The smart meters are composed of various sensors which can collect the energy consumption information of electrical equipment. However, these sensors have limited storage and cannot store massive data. In the PPKC model, the smart meters send the collected data to the cloud server. Suppose there arem smart meters xi, where i∈1,m. Each smart meter xi has a dataset Di=xi1,xi2,…,xin,ti, where xi1,xi2,…,xin and ti are separately the attributes and the label of the dataset. At the same time, each smart meter xi needs to generate a tuple of random numbers ai1,ai2,…,ain,ain+1, which is used to encrypt their data. For saving storage, the smart meter uploads the ciphertext Di′ to the cloud server.


## 2.3.2. Control Centers

The control centers in the smart grid collect abnormal data to realize power adjustment, abnormal remind, or process optimization. In the PPKC model, the control centers submit some query data to obtain the labels of abnormal data. Suppose that there arel control centers Qj, where j∈1,l. Each control center Qj has a query dataset qj=Qj1,Qj2,…,Qjn and sends encrypted query data qj′ to the cloud server. Each control center Qj broadcasts the public key to smart meters.


## 2.3.3. Cloud Server

The cloud server has powerful computational resources and storage capacity to implement KNN classification algorithm. In the proposed PPKC algorithm, it will do some calculation on the encrypted data from smart meters and control centers and return the encrypted results to the control centers. The cloud server broadcasts the public key to smart meters and control centers. We suppose that the cloud server is honest but curious, which denotes that the cloud server correctly carries out every step in the algorithm, but may try to obtain the private data of the smart meters and control center.


## 2.4. Security Model

IND-CPA Security. In a public key cryptosystem, the indistinguishability of ciphertext against chosen plaintext attack (IND-CPA) [24] is executed by the following game between an adversary A and a challenger C.(1)
Setup. The challengerC generates public key PK and private key SK based on security parameter and publishes PK to the adversary A and keeps SK secret.(2)
Queries. The adversaryA can execute encryption queries to the challenger. The adversary A sends a plaintext m to the challenger. The challenger C executes Encrypt algorithm and generates the corresponding ciphertext c and sends it to A.(3)
Challenge. The adversaryA randomly selects two plaintexts m0, m1 with the same length and returns them to C. These two plaintexts m0, m1 are not queried in the Queries phase. The challenger randomly selects b∈0,1 and transmits the ciphertext cb=EncryptPK,mb to A.(4)
Guess.A sends a bit b′∈0,1 as its guess. If b′=b with a probability which is larger than 1/2, the adversary wins the game and the advantage is defined as Prb′=b−1/2.An encryption system ist,ε-IND-CPA secure if all t-time IND-CPA adversaries have advantage of at most ϵ in winning the game.


## 3. The Proposed PPKC Algorithm

We introduce the privacy-preserving KNN classification algorithm in this section. Compared with [10, 11], the proposed PPKC algorithm is constructed based on single cloud server and realizes input privacy, query privacy, and output privacy simultaneously.As shown in Section2, there are three types of participants in the proposed PPKC algorithm, including smart meters (SM), control centers (CC), and cloud server (CS). All the data of smart meters and control centers belong to ℤN. The public keys and private keys of cloud server and control centers are denoted as PK, PKqj and SK, SKqj. In the proposed PPKC, the cloud server and control centers encrypt their data by using Paillier cryptosystem.


### 3.1. The Concrete Construction

The proposed PPKC algorithm includes uploading encrypted data, uploading query data, executing KNN on the ciphertext, and decrypting the ciphertext.


#### 3.1.1. Uploading Encrypted Data

Assume that there arem smart meters. For a smart meter xi, it firstly chooses a tuple of random numbers ai1,ai2,…,ain,ain+1 and calculates xi1−ai1,xi2−ai2,…,xin−ain,ti−ain+1. Next, it uses PK to encrypt the first n data and uses PKqj to encrypt the last data and all the random numbers. Finally, it transmits these secure data to the cloud server. After this step, smart meters can stay offline.


#### 3.1.2. Uploading Query Data

Assume the query data isQj1,Qj2,…,Qjn. The control center Qj downloads EPKqjai1,EPKqjai2,…EPKqjain, i∈1,m, from the cloud server. It then decrypts and obtains random numbers ai1,ai2,…,ain, i∈1,m. Next, the control center Qj calculates each random number minus all the query data and encrypts them with PK. Finally, the control center Qj sends the ciphertext of ai1−Qj1,ai2−Qj2,…,ain−Qjn, i∈1,m, to the cloud server. After that, the control center can stay offline.


#### 3.1.3. Executing KNN on the Ciphertext

After receiving the encrypted data from the control centerQj and smart meters, the cloud server computes the dots products based on EPKxi1−ai1,…,EPKxin−ain and EPKai1−Qj1,…,EPKain−Qjn and obtains EPKxi1−Qj1,…,EPKxin−Qjn. Then, the cloud server decrypts and gets xi1−Qj1,xi2−Qj2,…,xin−Qjn, i∈1,m. Next, the cloud server computes di, which is the Euclidean distance between the data of smart meters and the query data, and each di has a corresponding encrypted label EPKqjti. At this time, the cloud server has m groups of di,EPKqjti. After that, the cloud server sorts and selects the smallest K numbers in d1,d2,…,dm and their corresponding encrypted labels. Finally, these K encrypted labels are transmitted to the control center Qj.


#### 3.1.4. Decrypting the Ciphertext

The control centerQj decrypts these K encrypted labels and calculates the frequency of each label. Finally, Qj sets the label with the highest frequency as the result.Please see Algorithm 1 for the details of the proposed PPKC algorithm.Algorithm 1: PPKC.
Suppose that there arem smart meters and l control centers. Each smart meter xi has xi1,xi2,…,xin,ti, i∈1,m, where ti is the label and the attributes are xi1,xi2,…,xin. Each control center Qj has a query data Qj1,Qj2,…,Qjn, j∈1,l. PK,SK are public key and private key of the cloud server while PKqj,SKqj are public key and private key of the control center Qj.Smart MeterxiUploading Encrypted Data:(1)
Generate a series of random numbersai1,ai2,…,ain,ain+1 and calculate xi1−ai1,xi2−ai2,…,xin−ain,ti−ain+1.(2)
Use public keyPK and PKqj to encrypt xi1−ai1,xi2−ai2,…,xin−ain and ti−ain+1,ai1,ai2,…,ain,ain+1, respectively.(3)
Send these encrypted numbers,EPKxi1−ai1,EPKxi2−ai2,…,EPKxin−ain and EPKqjti−ain+1,EPKqjai1,EPKqjai2,…,EPKqjain+1, j∈1,l, to the cloud server.Control CenterQjUploading Query Data:(1)
DownloadEPKqjai1,EPKqjai2,…,EPKqjain, i∈1,m, from the cloud server.(2)
Decrypt by using the private keySKqj and obtain these random numbers ai1,ai2,…,ain, i∈1,m.(3)
Calculatea11−Qj1,a12−Qj2,…,a1n−Qjn⋮⋮⋮⋮am1−Qj1,am2−Qj2,…,amn−Qjn.(4)
Encrypt the above random numbers by using public keyPK and get EPKa11−Qj1,EPKa12−Qj2,…,EPKa1n−Qjn…EPKam1−Qj1,EPKam2−Qj2,…,EPKamn−Qjn.(5)
Send these encrypted random numbers to the cloud server.The Cloud Server Executing KNN on the Ciphertext:(1)
ComputeEPKxi1−ai1⋅EPKai1−Qj1=EPKxi1−Qj1…EPKxin−ain⋅EPKain−Qjn=EPKxin−Qjn, i∈1,m, and then use SK to decrypt these encrypted numbers.(2)
Calculatedi=xi1−Qj12+xi2−Qj22+⋅⋅⋅+xin−Qjn2, i∈1,m, which is the Euclidean distance between the data of smart meters and the query data.(3)
Calculate the encrypted label of each Euclidean distancedi. In detail, EPKqjti−ain+1.EPKqjain+1=EPKqjti. Thus, there are m groups Euclidean distance di and its corresponding encrypted label d1,EPKqjt1,d2,EPKqjt2,…,dm,EPKqjtm.(4)
Sort and select the smallestK numbers in d1,d2,…,dm and their corresponding encrypted labels.(5)
Send theseK encrypted labels EPKqjt1,EPKqjt2,…,EPKqjta, a∈1,K, to the control center Qj.Control CenterQjDecrypting the Ciphertext:(1)
Decrypt theseK encrypted labels with SKqj and get t1,t2,…,tK.(2)
Calculate the frequency of each label.(3)
Set the label with the highest frequency as the final result.


### 3.2. Correctness

The correctness of PPKC relies on the properties of Paillier cryptosystem, including homomorphic addition and scalar multiplicative homomorphism.After the smart meters upload encrypted data and the control center uploads query data, the cloud server executes KNN on the ciphertext. The cloud server calculates the dots products based onEPKxi1−ai1,…,EPKxin−ain and EPKai1−Qj1,…,EPKain−Qjn. According to the homomorphic addition of Paillier cryptosystem, we can easily get the following equation:(6)EPKxi1−ai∗EPKai−Q1=EPKxi1−ai+ai−Q1,=EPKxi1−Q1.Besides, the cloud server needs to calculate the encryption labels. According to the homomorphic addition of Paillier cryptosystem, we can get the following equation:(7)EPKqjti−ain+1∗EPKqjain+1=EPKqjti−ain+1+ain+1,=EPKqjti.Finally, the cloud server returnsK encrypted labels to the control center Qj. If the cloud server follows every step of the proposed PPKC, the control center finally gets the correct label.Therefore, we can prove that the result obtained by the control center is correct through the above analysis.


## 3.1. The Concrete Construction

The proposed PPKC algorithm includes uploading encrypted data, uploading query data, executing KNN on the ciphertext, and decrypting the ciphertext.


### 3.1.1. Uploading Encrypted Data

Assume that there arem smart meters. For a smart meter xi, it firstly chooses a tuple of random numbers ai1,ai2,…,ain,ain+1 and calculates xi1−ai1,xi2−ai2,…,xin−ain,ti−ain+1. Next, it uses PK to encrypt the first n data and uses PKqj to encrypt the last data and all the random numbers. Finally, it transmits these secure data to the cloud server. After this step, smart meters can stay offline.


### 3.1.2. Uploading Query Data

Assume the query data isQj1,Qj2,…,Qjn. The control center Qj downloads EPKqjai1,EPKqjai2,…EPKqjain, i∈1,m, from the cloud server. It then decrypts and obtains random numbers ai1,ai2,…,ain, i∈1,m. Next, the control center Qj calculates each random number minus all the query data and encrypts them with PK. Finally, the control center Qj sends the ciphertext of ai1−Qj1,ai2−Qj2,…,ain−Qjn, i∈1,m, to the cloud server. After that, the control center can stay offline.


### 3.1.3. Executing KNN on the Ciphertext

After receiving the encrypted data from the control centerQj and smart meters, the cloud server computes the dots products based on EPKxi1−ai1,…,EPKxin−ain and EPKai1−Qj1,…,EPKain−Qjn and obtains EPKxi1−Qj1,…,EPKxin−Qjn. Then, the cloud server decrypts and gets xi1−Qj1,xi2−Qj2,…,xin−Qjn, i∈1,m. Next, the cloud server computes di, which is the Euclidean distance between the data of smart meters and the query data, and each di has a corresponding encrypted label EPKqjti. At this time, the cloud server has m groups of di,EPKqjti. After that, the cloud server sorts and selects the smallest K numbers in d1,d2,…,dm and their corresponding encrypted labels. Finally, these K encrypted labels are transmitted to the control center Qj.


### 3.1.4. Decrypting the Ciphertext

The control centerQj decrypts these K encrypted labels and calculates the frequency of each label. Finally, Qj sets the label with the highest frequency as the result.Please see Algorithm 1 for the details of the proposed PPKC algorithm.Algorithm 1: PPKC.
Suppose that there arem smart meters and l control centers. Each smart meter xi has xi1,xi2,…,xin,ti, i∈1,m, where ti is the label and the attributes are xi1,xi2,…,xin. Each control center Qj has a query data Qj1,Qj2,…,Qjn, j∈1,l. PK,SK are public key and private key of the cloud server while PKqj,SKqj are public key and private key of the control center Qj.Smart MeterxiUploading Encrypted Data:(1)
Generate a series of random numbersai1,ai2,…,ain,ain+1 and calculate xi1−ai1,xi2−ai2,…,xin−ain,ti−ain+1.(2)
Use public keyPK and PKqj to encrypt xi1−ai1,xi2−ai2,…,xin−ain and ti−ain+1,ai1,ai2,…,ain,ain+1, respectively.(3)
Send these encrypted numbers,EPKxi1−ai1,EPKxi2−ai2,…,EPKxin−ain and EPKqjti−ain+1,EPKqjai1,EPKqjai2,…,EPKqjain+1, j∈1,l, to the cloud server.Control CenterQjUploading Query Data:(1)
DownloadEPKqjai1,EPKqjai2,…,EPKqjain, i∈1,m, from the cloud server.(2)
Decrypt by using the private keySKqj and obtain these random numbers ai1,ai2,…,ain, i∈1,m.(3)
Calculatea11−Qj1,a12−Qj2,…,a1n−Qjn⋮⋮⋮⋮am1−Qj1,am2−Qj2,…,amn−Qjn.(4)
Encrypt the above random numbers by using public keyPK and get EPKa11−Qj1,EPKa12−Qj2,…,EPKa1n−Qjn…EPKam1−Qj1,EPKam2−Qj2,…,EPKamn−Qjn.(5)
Send these encrypted random numbers to the cloud server.The Cloud Server Executing KNN on the Ciphertext:(1)
ComputeEPKxi1−ai1⋅EPKai1−Qj1=EPKxi1−Qj1…EPKxin−ain⋅EPKain−Qjn=EPKxin−Qjn, i∈1,m, and then use SK to decrypt these encrypted numbers.(2)
Calculatedi=xi1−Qj12+xi2−Qj22+⋅⋅⋅+xin−Qjn2, i∈1,m, which is the Euclidean distance between the data of smart meters and the query data.(3)
Calculate the encrypted label of each Euclidean distancedi. In detail, EPKqjti−ain+1.EPKqjain+1=EPKqjti. Thus, there are m groups Euclidean distance di and its corresponding encrypted label d1,EPKqjt1,d2,EPKqjt2,…,dm,EPKqjtm.(4)
Sort and select the smallestK numbers in d1,d2,…,dm and their corresponding encrypted labels.(5)
Send theseK encrypted labels EPKqjt1,EPKqjt2,…,EPKqjta, a∈1,K, to the control center Qj.Control CenterQjDecrypting the Ciphertext:(1)
Decrypt theseK encrypted labels with SKqj and get t1,t2,…,tK.(2)
Calculate the frequency of each label.(3)
Set the label with the highest frequency as the final result.


## 3.1.1. Uploading Encrypted Data

Assume that there arem smart meters. For a smart meter xi, it firstly chooses a tuple of random numbers ai1,ai2,…,ain,ain+1 and calculates xi1−ai1,xi2−ai2,…,xin−ain,ti−ain+1. Next, it uses PK to encrypt the first n data and uses PKqj to encrypt the last data and all the random numbers. Finally, it transmits these secure data to the cloud server. After this step, smart meters can stay offline.


## 3.1.2. Uploading Query Data

Assume the query data isQj1,Qj2,…,Qjn. The control center Qj downloads EPKqjai1,EPKqjai2,…EPKqjain, i∈1,m, from the cloud server. It then decrypts and obtains random numbers ai1,ai2,…,ain, i∈1,m. Next, the control center Qj calculates each random number minus all the query data and encrypts them with PK. Finally, the control center Qj sends the ciphertext of ai1−Qj1,ai2−Qj2,…,ain−Qjn, i∈1,m, to the cloud server. After that, the control center can stay offline.


## 3.1.3. Executing KNN on the Ciphertext

After receiving the encrypted data from the control centerQj and smart meters, the cloud server computes the dots products based on EPKxi1−ai1,…,EPKxin−ain and EPKai1−Qj1,…,EPKain−Qjn and obtains EPKxi1−Qj1,…,EPKxin−Qjn. Then, the cloud server decrypts and gets xi1−Qj1,xi2−Qj2,…,xin−Qjn, i∈1,m. Next, the cloud server computes di, which is the Euclidean distance between the data of smart meters and the query data, and each di has a corresponding encrypted label EPKqjti. At this time, the cloud server has m groups of di,EPKqjti. After that, the cloud server sorts and selects the smallest K numbers in d1,d2,…,dm and their corresponding encrypted labels. Finally, these K encrypted labels are transmitted to the control center Qj.


## 3.1.4. Decrypting the Ciphertext

The control centerQj decrypts these K encrypted labels and calculates the frequency of each label. Finally, Qj sets the label with the highest frequency as the result.Please see Algorithm 1 for the details of the proposed PPKC algorithm.Algorithm 1: PPKC.
Suppose that there arem smart meters and l control centers. Each smart meter xi has xi1,xi2,…,xin,ti, i∈1,m, where ti is the label and the attributes are xi1,xi2,…,xin. Each control center Qj has a query data Qj1,Qj2,…,Qjn, j∈1,l. PK,SK are public key and private key of the cloud server while PKqj,SKqj are public key and private key of the control center Qj.Smart MeterxiUploading Encrypted Data:(1)
Generate a series of random numbersai1,ai2,…,ain,ain+1 and calculate xi1−ai1,xi2−ai2,…,xin−ain,ti−ain+1.(2)
Use public keyPK and PKqj to encrypt xi1−ai1,xi2−ai2,…,xin−ain and ti−ain+1,ai1,ai2,…,ain,ain+1, respectively.(3)
Send these encrypted numbers,EPKxi1−ai1,EPKxi2−ai2,…,EPKxin−ain and EPKqjti−ain+1,EPKqjai1,EPKqjai2,…,EPKqjain+1, j∈1,l, to the cloud server.Control CenterQjUploading Query Data:(1)
DownloadEPKqjai1,EPKqjai2,…,EPKqjain, i∈1,m, from the cloud server.(2)
Decrypt by using the private keySKqj and obtain these random numbers ai1,ai2,…,ain, i∈1,m.(3)
Calculatea11−Qj1,a12−Qj2,…,a1n−Qjn⋮⋮⋮⋮am1−Qj1,am2−Qj2,…,amn−Qjn.(4)
Encrypt the above random numbers by using public keyPK and get EPKa11−Qj1,EPKa12−Qj2,…,EPKa1n−Qjn…EPKam1−Qj1,EPKam2−Qj2,…,EPKamn−Qjn.(5)
Send these encrypted random numbers to the cloud server.The Cloud Server Executing KNN on the Ciphertext:(1)
ComputeEPKxi1−ai1⋅EPKai1−Qj1=EPKxi1−Qj1…EPKxin−ain⋅EPKain−Qjn=EPKxin−Qjn, i∈1,m, and then use SK to decrypt these encrypted numbers.(2)
Calculatedi=xi1−Qj12+xi2−Qj22+⋅⋅⋅+xin−Qjn2, i∈1,m, which is the Euclidean distance between the data of smart meters and the query data.(3)
Calculate the encrypted label of each Euclidean distancedi. In detail, EPKqjti−ain+1.EPKqjain+1=EPKqjti. Thus, there are m groups Euclidean distance di and its corresponding encrypted label d1,EPKqjt1,d2,EPKqjt2,…,dm,EPKqjtm.(4)
Sort and select the smallestK numbers in d1,d2,…,dm and their corresponding encrypted labels.(5)
Send theseK encrypted labels EPKqjt1,EPKqjt2,…,EPKqjta, a∈1,K, to the control center Qj.Control CenterQjDecrypting the Ciphertext:(1)
Decrypt theseK encrypted labels with SKqj and get t1,t2,…,tK.(2)
Calculate the frequency of each label.(3)
Set the label with the highest frequency as the final result.


## 3.2. Correctness

The correctness of PPKC relies on the properties of Paillier cryptosystem, including homomorphic addition and scalar multiplicative homomorphism.After the smart meters upload encrypted data and the control center uploads query data, the cloud server executes KNN on the ciphertext. The cloud server calculates the dots products based onEPKxi1−ai1,…,EPKxin−ain and EPKai1−Qj1,…,EPKain−Qjn. According to the homomorphic addition of Paillier cryptosystem, we can easily get the following equation:(6)EPKxi1−ai∗EPKai−Q1=EPKxi1−ai+ai−Q1,=EPKxi1−Q1.Besides, the cloud server needs to calculate the encryption labels. According to the homomorphic addition of Paillier cryptosystem, we can get the following equation:(7)EPKqjti−ain+1∗EPKqjain+1=EPKqjti−ain+1+ain+1,=EPKqjti.Finally, the cloud server returnsK encrypted labels to the control center Qj. If the cloud server follows every step of the proposed PPKC, the control center finally gets the correct label.Therefore, we can prove that the result obtained by the control center is correct through the above analysis.


## 4. Analysis of the PPKC Algorithm

In this section, we analyze the data privacy of smart meters and control centers and prove that the data given back by the cloud server is secure. We assume that the cloud server is semi-honest.Therefore, we should prove that the private information of both smart meters and control centers is all private for the cloud server. Moreover, the outputs should also be well protected from the server.


### 4.1. Security Analysis

Theorem 1.
In the PPKC algorithm, the privacy of the smart meter is ensured for the server based on the Paillier cryptosystem.Proof. The security proof is executed between an adversaryA and a challenger C. At the beginning of the game, the challenger is given a ciphertext of Paillier cryptosystem EPKxb to decide the corresponding plaintext is x0 or x1. Suppose the adversary distinguish the ciphertext of smart meter with an overwhelming probability; the challenger can distinguish the ciphertext of Paillier cryptosystem with an overwhelming probability.(1)
Setup. The public keys of smart meter, cloud server, and control centers are published to the adversaryA and the challenger C.(2)
Queries. AdversaryA first executes encryption queries to the challenger. The adversary A sends xi1,xi2,…,xin,ti to the challenger. The challenger C executes the PPKC algorithm, selects some random numbers ai1,ai2,…,ain,ain+1 and returns the corresponding ciphertexts:(8)EPKxi1−ai1,EPKxi2−ai2,…,EPKxin−ain,EPKqjti−ain+1,EPKqjai1,…,EPKqjain+1,wherePK,PKqj are the public keys of cloud server and control center Qj, respectively.(3)
Challenge. The adversaryA randomly picks two messages x01,x02,…,x0n,t0, x11,x12,…,x1n,t1 and transmits them to C. Notice that these two plaintexts are not queried in the Queries phase. The challenger randomly selects b∈0,1 and returns the ciphertext to adversary A:(9)EPKqjxb,EPKxb1−ab1,…,EPKxbn−abn,EPKqjtb−abn+1,EPKqjxb1−xb,EPKqjab2,EPKqjab3…,EPKqjabn+1,whereEPKqjxb1−xb=EPKqjxb1EPKqjxb−1, and ab2,…,abn+1 are random numbers chosen by the challenger.(4)
Guess.A sends a bit b′∈0,1 as its guess, and then the challenger returns b′∈0,1. If the adversary wins the game with an advantage of ϵ, then the challenger can distinguish the ciphertext of Paillier cryptosystem with an advantage of ϵ.Therefore, the privacy of the smart meter is assured for the server based on the Paillier cryptosystem.Theorem 2.
In the PPKC algorithm, the privacy of the control center is also ensured for the server based on the Paillier cryptosystem.Proof. The same as Theorem1, the challenger is firstly given a ciphertext of Paillier cryptosystem EPKxb to decide the corresponding plaintext is x0 or x1. Suppose the adversary distinguish the ciphertext of control center with an overwhelming probability; the challenger can distinguish the ciphertext of Paillier cryptosystem with an overwhelming probability.(1)
Setup. The same as Theorem1.(2)
Queries. The adversaryA can execute encryption queries to the challenger. The adversary A sends Qj1,Qj2,…,Qjn to the challenger. The challenger C executes the PPKC algorithm, selects some numbers a11,a12,…,a1n;…;am1,am2,…,amn, and returns the corresponding ciphertexts:(10)EPKa11−Qj1,…,EPKa1n−Qjn…EPKam1−Qj1,…,EPKamn−Qjn,wherePK is the public key of cloud server.(3)
Challenge. The adversaryA randomly chooses two queries Q01,Q02,…,Q0n, Q11,Q12,…,Q1n and sends them to C. Note that these two queries are not queried in the Queries phase. The challenger selects b∈0,1 and returns the ciphertext to A:(11)EPKxb,EPKa12−Qb2,…,EPKa1n−Qbn…EPKam1−Qb1,…,EPKamn−Qbn,wherea12,…,a1n,…,am1,am2,…,amn are random numbers chosen by the challenger.(4)
Guess. The same as Theorem1.Therefore, the privacy of the control center is ensured for the server based on the Paillier cryptosystem.Theorem 3.
In the PPKC algorithm, the result of query is protected from the server based on the Paillier cryptosystem.Proof. As same as Theorem1, the challenger is firstly given a ciphertext of Paillier cryptosystem EPKqjtb to decide the corresponding plaintext is t0 or t1. Suppose the adversary distinguish the ciphertext of the query result with an overwhelming probability; the challenger can distinguish the ciphertext of Paillier cryptosystem with an overwhelming probability.(1)
Setup. The same as Theorem1.(2)
Queries. AdversaryA can execute encryption queries to the challenger. The adversary A sends the labels t1,t2,…,tK to the challenger. The challenger C executes the PPKC algorithm and returns the encrypted labels:(12)EPKqjt1−a1,…,EPKqjtK−aK,EPKqja1,EPKqja2,…,EPKqjaK,wherePKqj is the public key of the control center and a1,…,aK are random numbers chosen by the challenger.(3)
Challenge. The adversaryA chooses two tuples of labels t01,t02,…,t0K, t11,t12,…,t1K and sends them to C. Notice that these two tuples of labels are not queried in the Queries phase. The challenger randomly selects b∈0,1 and returns the ciphertext to A:(13)EPKqjtb,EPKqjtb2−ab2,…,EPKqjtbK−abK,EPKqjtb1−tb,EPKqjab2,…,EPKqjabK,whereEPKqjtb1−tb=EPKqjtb1EPKqjtb−1 and ab2,…,abK are random numbers chosen by the challenger.(4)
Guess. The same as Theorem1.Therefore, the result of the query is protected from the server based on the Paillier cryptosystem.


### 4.2. Computational Complexity

In Table1, we give the final computation overheads of each participant, where n, m, l separately mean the quantity of data records, smart meters, and control centers. As mentioned in Section 3, there are totally m smart meters and each smart meter has n+1 data records including n data attributes and one label. At the same time, there exist l control centers and each control center has n data records. We ignore the additions and multiplications in the following analysis since these operations have low computational costs and modular exponentiation (ME) and modular multiplication (MM) cost far more than them. For the Paillier cryptosystem, one encryption needs 2 ME and 1 MM, while one decryption needs 2 ME and 3 MM.Table 1
Computational complexity of PPKC.
OperationSmart metersControl centerCloud serverModular exponentiation2mn+ln+24mn2mnModular multiplicationmn+ln+24mn4mnIn the proposed PPKC, each smart meter needs to usePKqj to encrypt ti−ain+1,ai1,ai2,…,ain,ain+1 and use PK to encrypt xi1−ai1,xi2−ai2,…,xin−ain. Thus, each smart meter performs n+ln+2 encryptions and the total number of all smart meters is mn+n+2 for encryption. After downloading the encrypted random numbers, the control center Qj decrypts and then encrypts the query data by using random numbers. Thus, each control center Qj performs mn decryptions and mn encryptions. In the proposed PPKC, the cloud server needs to compute the Euclidean distance. For an Euclidean distance, the cloud server needs to perform n MM and n decryptions. Thus, computing m Euclidean distances needs to perform mn MM and mn decryptions. In the Decryption operation, the control center needs to decrypt K encrypted labels and calculates the label with the highest frequency. We ignore the operations in this paper because K is a small number.Therefore, all the smart meters need to perform2mn+ln+2 ME and mn+ln+2 MM. Each control center needs to perform mn encryptions and mn decryptions. Thus, the control center needs to execute 4mn ME and 4mn MM. The cloud server needs to perform 2mn ME and 4mn MM.


### 4.3. Comparisons

Table2 shows the comparison of the proposed PPKC and other privacy-preserving KNN algorithms, where m, k, v separately mean the quantity of data owners, the parameter of KNN, and the length of a value. Samanthula et al. [10] put forward a privacy-preserving KNN classification protocol, which is the first one to achieve query privacy, data privacy, and output privacy. Unfortunately, this protocol has high computational cost. Liu et al. [11] designed a secure KNN classification protocol with additive secret sharing, which protects all the data of each participant. Moreover, this protocol is much more efficient than [10]. However, these two protocols are constructed based on two noncolluding servers, which is difficult to be realized in reality. For multiple data owners, Li et al. [17] proposed a secure KNN classification protocol. Unfortunately, this protocol cannot totally protect the data from the servers. Cheng et al. [18] designed a secure KNN query protocol by utilizing the distributed two trapdoors public-key cryptosystem [25]. However, this protocol uses two cloud servers and cannot achieve the privacy of data. Yang et al. [19] presented another secure KNN classification algorithm with vector homomorphic encryption which is proved insecure in [21]. Thus, this protocol cannot protect any private information of data owners and query users. Yang et al. [22] used a secure VHE designed a privacy-preserving KNN classification algorithm, but the query data cannot be well protected.Table 2
Comparison of privacy-preserving KNN algorithms.
AlgorithmData privacyQuery privacyOutput privacySingle cloud serverComputation costSamanthula et al. [10]✓✓✓✕OmkvLiu et al. [11]✓✓✓✕OmkLi et al. [17]✕✓✓✓OmkCheng et al. [18]✕✓✓✕OmkYang et al. [19]✕✕✕✓OmYang et al. [22]✓✕✓✓OmThe PPKC algorithm✓✓✓✓OmTherefore, the proposed PPKC is the first algorithm which can protect the private information of smart meters, control centers, and the query results based on single cloud server.


## 4.1. Security Analysis

Theorem 1.
In the PPKC algorithm, the privacy of the smart meter is ensured for the server based on the Paillier cryptosystem.Proof. The security proof is executed between an adversaryA and a challenger C. At the beginning of the game, the challenger is given a ciphertext of Paillier cryptosystem EPKxb to decide the corresponding plaintext is x0 or x1. Suppose the adversary distinguish the ciphertext of smart meter with an overwhelming probability; the challenger can distinguish the ciphertext of Paillier cryptosystem with an overwhelming probability.(1)
Setup. The public keys of smart meter, cloud server, and control centers are published to the adversaryA and the challenger C.(2)
Queries. AdversaryA first executes encryption queries to the challenger. The adversary A sends xi1,xi2,…,xin,ti to the challenger. The challenger C executes the PPKC algorithm, selects some random numbers ai1,ai2,…,ain,ain+1 and returns the corresponding ciphertexts:(8)EPKxi1−ai1,EPKxi2−ai2,…,EPKxin−ain,EPKqjti−ain+1,EPKqjai1,…,EPKqjain+1,wherePK,PKqj are the public keys of cloud server and control center Qj, respectively.(3)
Challenge. The adversaryA randomly picks two messages x01,x02,…,x0n,t0, x11,x12,…,x1n,t1 and transmits them to C. Notice that these two plaintexts are not queried in the Queries phase. The challenger randomly selects b∈0,1 and returns the ciphertext to adversary A:(9)EPKqjxb,EPKxb1−ab1,…,EPKxbn−abn,EPKqjtb−abn+1,EPKqjxb1−xb,EPKqjab2,EPKqjab3…,EPKqjabn+1,whereEPKqjxb1−xb=EPKqjxb1EPKqjxb−1, and ab2,…,abn+1 are random numbers chosen by the challenger.(4)
Guess.A sends a bit b′∈0,1 as its guess, and then the challenger returns b′∈0,1. If the adversary wins the game with an advantage of ϵ, then the challenger can distinguish the ciphertext of Paillier cryptosystem with an advantage of ϵ.Therefore, the privacy of the smart meter is assured for the server based on the Paillier cryptosystem.Theorem 2.
In the PPKC algorithm, the privacy of the control center is also ensured for the server based on the Paillier cryptosystem.Proof. The same as Theorem1, the challenger is firstly given a ciphertext of Paillier cryptosystem EPKxb to decide the corresponding plaintext is x0 or x1. Suppose the adversary distinguish the ciphertext of control center with an overwhelming probability; the challenger can distinguish the ciphertext of Paillier cryptosystem with an overwhelming probability.(1)
Setup. The same as Theorem1.(2)
Queries. The adversaryA can execute encryption queries to the challenger. The adversary A sends Qj1,Qj2,…,Qjn to the challenger. The challenger C executes the PPKC algorithm, selects some numbers a11,a12,…,a1n;…;am1,am2,…,amn, and returns the corresponding ciphertexts:(10)EPKa11−Qj1,…,EPKa1n−Qjn…EPKam1−Qj1,…,EPKamn−Qjn,wherePK is the public key of cloud server.(3)
Challenge. The adversaryA randomly chooses two queries Q01,Q02,…,Q0n, Q11,Q12,…,Q1n and sends them to C. Note that these two queries are not queried in the Queries phase. The challenger selects b∈0,1 and returns the ciphertext to A:(11)EPKxb,EPKa12−Qb2,…,EPKa1n−Qbn…EPKam1−Qb1,…,EPKamn−Qbn,wherea12,…,a1n,…,am1,am2,…,amn are random numbers chosen by the challenger.(4)
Guess. The same as Theorem1.Therefore, the privacy of the control center is ensured for the server based on the Paillier cryptosystem.Theorem 3.
In the PPKC algorithm, the result of query is protected from the server based on the Paillier cryptosystem.Proof. As same as Theorem1, the challenger is firstly given a ciphertext of Paillier cryptosystem EPKqjtb to decide the corresponding plaintext is t0 or t1. Suppose the adversary distinguish the ciphertext of the query result with an overwhelming probability; the challenger can distinguish the ciphertext of Paillier cryptosystem with an overwhelming probability.(1)
Setup. The same as Theorem1.(2)
Queries. AdversaryA can execute encryption queries to the challenger. The adversary A sends the labels t1,t2,…,tK to the challenger. The challenger C executes the PPKC algorithm and returns the encrypted labels:(12)EPKqjt1−a1,…,EPKqjtK−aK,EPKqja1,EPKqja2,…,EPKqjaK,wherePKqj is the public key of the control center and a1,…,aK are random numbers chosen by the challenger.(3)
Challenge. The adversaryA chooses two tuples of labels t01,t02,…,t0K, t11,t12,…,t1K and sends them to C. Notice that these two tuples of labels are not queried in the Queries phase. The challenger randomly selects b∈0,1 and returns the ciphertext to A:(13)EPKqjtb,EPKqjtb2−ab2,…,EPKqjtbK−abK,EPKqjtb1−tb,EPKqjab2,…,EPKqjabK,whereEPKqjtb1−tb=EPKqjtb1EPKqjtb−1 and ab2,…,abK are random numbers chosen by the challenger.(4)
Guess. The same as Theorem1.Therefore, the result of the query is protected from the server based on the Paillier cryptosystem.


## 4.2. Computational Complexity

In Table1, we give the final computation overheads of each participant, where n, m, l separately mean the quantity of data records, smart meters, and control centers. As mentioned in Section 3, there are totally m smart meters and each smart meter has n+1 data records including n data attributes and one label. At the same time, there exist l control centers and each control center has n data records. We ignore the additions and multiplications in the following analysis since these operations have low computational costs and modular exponentiation (ME) and modular multiplication (MM) cost far more than them. For the Paillier cryptosystem, one encryption needs 2 ME and 1 MM, while one decryption needs 2 ME and 3 MM.Table 1
Computational complexity of PPKC.
OperationSmart metersControl centerCloud serverModular exponentiation2mn+ln+24mn2mnModular multiplicationmn+ln+24mn4mnIn the proposed PPKC, each smart meter needs to usePKqj to encrypt ti−ain+1,ai1,ai2,…,ain,ain+1 and use PK to encrypt xi1−ai1,xi2−ai2,…,xin−ain. Thus, each smart meter performs n+ln+2 encryptions and the total number of all smart meters is mn+n+2 for encryption. After downloading the encrypted random numbers, the control center Qj decrypts and then encrypts the query data by using random numbers. Thus, each control center Qj performs mn decryptions and mn encryptions. In the proposed PPKC, the cloud server needs to compute the Euclidean distance. For an Euclidean distance, the cloud server needs to perform n MM and n decryptions. Thus, computing m Euclidean distances needs to perform mn MM and mn decryptions. In the Decryption operation, the control center needs to decrypt K encrypted labels and calculates the label with the highest frequency. We ignore the operations in this paper because K is a small number.Therefore, all the smart meters need to perform2mn+ln+2 ME and mn+ln+2 MM. Each control center needs to perform mn encryptions and mn decryptions. Thus, the control center needs to execute 4mn ME and 4mn MM. The cloud server needs to perform 2mn ME and 4mn MM.


## 4.3. Comparisons

Table2 shows the comparison of the proposed PPKC and other privacy-preserving KNN algorithms, where m, k, v separately mean the quantity of data owners, the parameter of KNN, and the length of a value. Samanthula et al. [10] put forward a privacy-preserving KNN classification protocol, which is the first one to achieve query privacy, data privacy, and output privacy. Unfortunately, this protocol has high computational cost. Liu et al. [11] designed a secure KNN classification protocol with additive secret sharing, which protects all the data of each participant. Moreover, this protocol is much more efficient than [10]. However, these two protocols are constructed based on two noncolluding servers, which is difficult to be realized in reality. For multiple data owners, Li et al. [17] proposed a secure KNN classification protocol. Unfortunately, this protocol cannot totally protect the data from the servers. Cheng et al. [18] designed a secure KNN query protocol by utilizing the distributed two trapdoors public-key cryptosystem [25]. However, this protocol uses two cloud servers and cannot achieve the privacy of data. Yang et al. [19] presented another secure KNN classification algorithm with vector homomorphic encryption which is proved insecure in [21]. Thus, this protocol cannot protect any private information of data owners and query users. Yang et al. [22] used a secure VHE designed a privacy-preserving KNN classification algorithm, but the query data cannot be well protected.Table 2
Comparison of privacy-preserving KNN algorithms.
AlgorithmData privacyQuery privacyOutput privacySingle cloud serverComputation costSamanthula et al. [10]✓✓✓✕OmkvLiu et al. [11]✓✓✓✕OmkLi et al. [17]✕✓✓✓OmkCheng et al. [18]✕✓✓✕OmkYang et al. [19]✕✕✕✓OmYang et al. [22]✓✕✓✓OmThe PPKC algorithm✓✓✓✓OmTherefore, the proposed PPKC is the first algorithm which can protect the private information of smart meters, control centers, and the query results based on single cloud server.


## 5. Performance Evaluation

To observe the efficiency and accuracy of the PPKC algorithm, we execute the following two experiments. In the first experiment, we compare the PPKC with the previous protocols to demonstrate the efficiency of PPKC. Next, we test the accuracy of original KNN with that of PPKC to show that the accuracy does not decrease in the privacy-preserving setting.All the experiments are designed on a MacBook Pro laptop equipped with 4 cores rated at 1.4 GHz and 16 GB of RAM by Java language.


### 5.1. Computational Overheads

In this subsection, we do some experiments to show the effectiveness of the PPKC. As shown in Table2, the proposed PPKC and [10, 11] achieve data privacy, query privacy, and result privacy, but [17–19, 22] cannot realize the properties simultaneously; we thus only compare the PPKC with these two protocols. Our experiments are performed on the Car Evaluation dataset from University of California Irvine (UCI) dataset [26], which is also used in [10, 11]. Specifically, there are total 1728 records and each record has 6 data attributes in this dataset, which means m=1728, n=6. Besides, these records are categorized into 4 classes, which means there are 4 different kinds of labels in this dataset. For a fair comparison, we compare the performance of our PPKC with different k, which is chosen from 5 to 25. Moreover, we test the time of control centers, smart meters, and cloud server during executing the PPKC.Since the length ofN has an effect on the efficiency of PPKC, we separately select N=512 and N=1024 in the following experiments, which is the same as [10, 11]. Tables 3 and 4 mainly present the computation cost of SM, CC, and CS in the PPKC algorithm for different N. We define tPPKC as the total time of executing PPKC. tSM, tCC, and tCS separately denote the time of smart meters, control center, and cloud server during executing PPKC.Table 3
Computation cost of PPKC whenN=512.
ktSM (sec)tCC (sec)tCS (sec)tPPKC (sec)57.444.5086.77818.726107.4994.7426.80219.043157.5494.7776.9219.246207.5324.8196.90219.253257.4534.986.91519.348Table 4
Computation cost of PPKC whenN=1024.
ktSM (sec)tCC (sec)tCS (sec)tPPKC (sec)540.91826.76343.949111.631041.61127.37443.459112.4941541.54927.59443.425112.5682041.41227.8943.762113.0642541.7228.01143.621113.352We specifically discuss the running time of smart meters, control center, and cloud server, respectively. As shown in Tables3 and 4, we make a comparison of tSM, tCC, and tCS. When N=512 and k=5, tSM, tCC, and tCS is 7.44 s, 4.508 s, and 6.778 s, respectively. When N=512 and k=25, tSM is changed from 7.44 s to 7.453 s, tCC is changed from 4.508 s to 4.98 s, and tCS is changed from 6.778 s to 6.915 s. With the increase of k, tSM, tCC and tCS are almost unchanged. Similarly, when N=1024 and k=5, tSM, tCC, and tCS are 40.918 s, 26.763 s, and 43.949 s, respectively. When N=1024 and k=25, tSM, tCC, and tCS are 41.72 s, 28.011 s, and 43.621 s, respectively. With the increase of k, tSM, tCC and tCS do not obviously change. Thus, we can conclude that the increase of k does not have a great impact on tSM, tCC, and tCS.Considering there are 1728 data records in this dataset, which means there are 1728 smart meters. Since the total time of smart meters executing PPKC is 7.453 s and 41.72 s, respectively, each smart meter only needs 4.31 ms and 24.14 ms to encrypted their data records whenN is varied from 512 to 1024, which is quite time-saving. As shown in Tables 3 and 4, each control center may spend more time than each smart meter since it needs to encrypt all the query data. It is acceptable for the control center because there is only one cloud server in PPKC algorithm and the control center need to do more computation to protect the query.Next, we compare the efficiency of PPKC with those of Samanthula et al. [10] and Liu et al. [11] during executing the whole algorithm as shown in Figures 2 and 3. When k is varied from 5 to 25 and N=512, the total running time of PPKC is varied from 18.726 s to 19.348 s. Similarly, when N=1024, the total running time of PPKC is varied from 111.63s to 113.352s. In [10, 11], when N=512 and k=5, their running time is 10.01 min and 0.59 min, respectively. Simultaneously, when N=1024 and k=5, their running time is 67.97 min and 3.091 min, respectively. Therefore, the proposed PPKC is much more efficient than the previous privacy-preserving KNN protocols.Figure 2
Efficiency comparison with [11].Figure 3
Efficiency comparison with [10].


### 5.2. Classification Accuracy

We test the classification accuracy of KNN and PPKC on some datasets from UCI dataset [26] in this subsection.Assume thatm, n, t, q are separately the number of data records, the attributes, the training data records, and query data. The query data are randomly selected from the dataset. Thus, each query data has its own label, which can be judged whether the classification results of PPKC are true or false. Table 5 demonstrates some information of the datasets.Table 5
Information of some datasets.
DatasetmntqCar evaluation172861400328Mammographic mass8305600230Electrical grid100001180002000Letter recognition2000016160004000We totally use 4 different datasets. The first dataset is Car Evaluation dataset. As demonstrated in previous part, there are 1728 data records and 4 different labels, including unaccuracy, accuracy, good, and very good, while each data record has 6 attributes. Here, we set the first 1400 records as training data and the other 328 records as testing data.The second dataset is Mammographic Mass dataset. There are a total of 830 data records with 5 attributes and 2 different labels including benign and malignant. In this dataset, the first 600 data records are training data and the other 230 data records are testing data.The third dataset is Electrical Grid Stability dataset, which is widely used in smart grid. In this dataset, there are some attributes including power consumed, value for electricity producer, and so on. There are a total of 10000 data records with 11 attributes and 2 different labels including stable and unstable. In this dataset, the first 8000 data records are training data and the other 2000 data records are testing data.The fourth dataset is Letter Recognition dataset. In this dataset, there are a total of 20000 data records which have 16 attributes. The labels are 26 capital letters in the English alphabet. The first 16000 records are training data and the other 4000 records are testing data.For different datasets, we totally carry out 5 groups of experiments with differentk. For each dataset, we set the value of k 1, 2, 3, 5, and 10.As shown in Table6, we give the accuracy of original KNN and PPKC with different k. In the first dataset, the accuracy of original KNN is varied from 89.975% to 65.853%, while the accuracy of PPKC is varied from 89.975% to 65.548%. In the other three datasets, it is also not much difference between the accuracy of original KNN and PPKC. No matter what k is, the accuracy of KNN is almost the same as that of PPKC. Besides, the proposed PPKC can protect the data of smart meters and control centers, which can prevent cloud server from obtaining their private information. Moreover, the results of Electrical Grid Stability dataset shows that the proposed PPKC can be well applied to the smart grid. Thus, PPKC is secure and practical for smart grid.Table 6
Accuracy of KNN and PPKC.
Car evaluationMammographic massElectrical grid stabilityLetter recognitionNokAccuracyNokAccuracyNokAccuracyNokAccuracyKNN (%)PPKC (%)KNN (%)PPKC (%)KNN (%)PPKC (%)KNN (%)PPKC (%)1189.97589.9751170.869701174.974.951195.67495.6742289.32989.0242273.04373.9132276.0575.92294.02594.1253388.71988.6483376.95676.5213376.9576.853394.67494.5754578.96378.9634574.34774.3474577.377.14594.17494.02551065.85365.54851074.78274.34751078.5578.451092.02591.825


## 5.1. Computational Overheads

In this subsection, we do some experiments to show the effectiveness of the PPKC. As shown in Table2, the proposed PPKC and [10, 11] achieve data privacy, query privacy, and result privacy, but [17–19, 22] cannot realize the properties simultaneously; we thus only compare the PPKC with these two protocols. Our experiments are performed on the Car Evaluation dataset from University of California Irvine (UCI) dataset [26], which is also used in [10, 11]. Specifically, there are total 1728 records and each record has 6 data attributes in this dataset, which means m=1728, n=6. Besides, these records are categorized into 4 classes, which means there are 4 different kinds of labels in this dataset. For a fair comparison, we compare the performance of our PPKC with different k, which is chosen from 5 to 25. Moreover, we test the time of control centers, smart meters, and cloud server during executing the PPKC.Since the length ofN has an effect on the efficiency of PPKC, we separately select N=512 and N=1024 in the following experiments, which is the same as [10, 11]. Tables 3 and 4 mainly present the computation cost of SM, CC, and CS in the PPKC algorithm for different N. We define tPPKC as the total time of executing PPKC. tSM, tCC, and tCS separately denote the time of smart meters, control center, and cloud server during executing PPKC.Table 3
Computation cost of PPKC whenN=512.
ktSM (sec)tCC (sec)tCS (sec)tPPKC (sec)57.444.5086.77818.726107.4994.7426.80219.043157.5494.7776.9219.246207.5324.8196.90219.253257.4534.986.91519.348Table 4
Computation cost of PPKC whenN=1024.
ktSM (sec)tCC (sec)tCS (sec)tPPKC (sec)540.91826.76343.949111.631041.61127.37443.459112.4941541.54927.59443.425112.5682041.41227.8943.762113.0642541.7228.01143.621113.352We specifically discuss the running time of smart meters, control center, and cloud server, respectively. As shown in Tables3 and 4, we make a comparison of tSM, tCC, and tCS. When N=512 and k=5, tSM, tCC, and tCS is 7.44 s, 4.508 s, and 6.778 s, respectively. When N=512 and k=25, tSM is changed from 7.44 s to 7.453 s, tCC is changed from 4.508 s to 4.98 s, and tCS is changed from 6.778 s to 6.915 s. With the increase of k, tSM, tCC and tCS are almost unchanged. Similarly, when N=1024 and k=5, tSM, tCC, and tCS are 40.918 s, 26.763 s, and 43.949 s, respectively. When N=1024 and k=25, tSM, tCC, and tCS are 41.72 s, 28.011 s, and 43.621 s, respectively. With the increase of k, tSM, tCC and tCS do not obviously change. Thus, we can conclude that the increase of k does not have a great impact on tSM, tCC, and tCS.Considering there are 1728 data records in this dataset, which means there are 1728 smart meters. Since the total time of smart meters executing PPKC is 7.453 s and 41.72 s, respectively, each smart meter only needs 4.31 ms and 24.14 ms to encrypted their data records whenN is varied from 512 to 1024, which is quite time-saving. As shown in Tables 3 and 4, each control center may spend more time than each smart meter since it needs to encrypt all the query data. It is acceptable for the control center because there is only one cloud server in PPKC algorithm and the control center need to do more computation to protect the query.Next, we compare the efficiency of PPKC with those of Samanthula et al. [10] and Liu et al. [11] during executing the whole algorithm as shown in Figures 2 and 3. When k is varied from 5 to 25 and N=512, the total running time of PPKC is varied from 18.726 s to 19.348 s. Similarly, when N=1024, the total running time of PPKC is varied from 111.63s to 113.352s. In [10, 11], when N=512 and k=5, their running time is 10.01 min and 0.59 min, respectively. Simultaneously, when N=1024 and k=5, their running time is 67.97 min and 3.091 min, respectively. Therefore, the proposed PPKC is much more efficient than the previous privacy-preserving KNN protocols.Figure 2
Efficiency comparison with [11].Figure 3
Efficiency comparison with [10].


## 5.2. Classification Accuracy

We test the classification accuracy of KNN and PPKC on some datasets from UCI dataset [26] in this subsection.Assume thatm, n, t, q are separately the number of data records, the attributes, the training data records, and query data. The query data are randomly selected from the dataset. Thus, each query data has its own label, which can be judged whether the classification results of PPKC are true or false. Table 5 demonstrates some information of the datasets.Table 5
Information of some datasets.
DatasetmntqCar evaluation172861400328Mammographic mass8305600230Electrical grid100001180002000Letter recognition2000016160004000We totally use 4 different datasets. The first dataset is Car Evaluation dataset. As demonstrated in previous part, there are 1728 data records and 4 different labels, including unaccuracy, accuracy, good, and very good, while each data record has 6 attributes. Here, we set the first 1400 records as training data and the other 328 records as testing data.The second dataset is Mammographic Mass dataset. There are a total of 830 data records with 5 attributes and 2 different labels including benign and malignant. In this dataset, the first 600 data records are training data and the other 230 data records are testing data.The third dataset is Electrical Grid Stability dataset, which is widely used in smart grid. In this dataset, there are some attributes including power consumed, value for electricity producer, and so on. There are a total of 10000 data records with 11 attributes and 2 different labels including stable and unstable. In this dataset, the first 8000 data records are training data and the other 2000 data records are testing data.The fourth dataset is Letter Recognition dataset. In this dataset, there are a total of 20000 data records which have 16 attributes. The labels are 26 capital letters in the English alphabet. The first 16000 records are training data and the other 4000 records are testing data.For different datasets, we totally carry out 5 groups of experiments with differentk. For each dataset, we set the value of k 1, 2, 3, 5, and 10.As shown in Table6, we give the accuracy of original KNN and PPKC with different k. In the first dataset, the accuracy of original KNN is varied from 89.975% to 65.853%, while the accuracy of PPKC is varied from 89.975% to 65.548%. In the other three datasets, it is also not much difference between the accuracy of original KNN and PPKC. No matter what k is, the accuracy of KNN is almost the same as that of PPKC. Besides, the proposed PPKC can protect the data of smart meters and control centers, which can prevent cloud server from obtaining their private information. Moreover, the results of Electrical Grid Stability dataset shows that the proposed PPKC can be well applied to the smart grid. Thus, PPKC is secure and practical for smart grid.Table 6
Accuracy of KNN and PPKC.
Car evaluationMammographic massElectrical grid stabilityLetter recognitionNokAccuracyNokAccuracyNokAccuracyNokAccuracyKNN (%)PPKC (%)KNN (%)PPKC (%)KNN (%)PPKC (%)KNN (%)PPKC (%)1189.97589.9751170.869701174.974.951195.67495.6742289.32989.0242273.04373.9132276.0575.92294.02594.1253388.71988.6483376.95676.5213376.9576.853394.67494.5754578.96378.9634574.34774.3474577.377.14594.17494.02551065.85365.54851074.78274.34751078.5578.451092.02591.825


## 6. Conclusion

In this paper, we propose a privacy-preserving KNN classification algorithm based on single cloud server for smart grid. The proposed PPKC algorithm can protect private data of smart meters, control centers, and the classification results based on Paillier cryptosystem. Compared with the previous protocols, PPKC only uses one cloud server, which is more practical in reality. The experiments results demonstrate that PPKC is much more efficient than the previous protocols and the classification accuracy of PPKC is almost the same as that of the original KNN, which means PPKC is efficient and feasible for smart grid. However, the proposed PPKC algorithm is only applicable to the KNN algorithm, and we will pay more attention to other privacy-preserving machine learning algorithms in the future.



---

*Source: 7333175-2022-05-11.xml*