A k-Nearest Neighbor Algorithm Based on Homomorphic Encryption

Protection of privacy has become an essential problem in cloud platform security. In many cases, data is shared with the third party for the analysis purpose. However, the sharing of data for analysis is not safe. Fully homomorphic encryption (FHE) is very promising to deal with ciphertext without decryption, FHE has become one of the key technologies to improve the security of user sensitive information. In this paper, we solve the problem of privacy preserving k-Nearest neighbor classification (K-NN), which forms the basis of many data analysis applications. We propose a scheme FK-NN, which is based on homomorphic encryption and numerical comparator. In our scheme, the homomorphic subtraction operation is designed and implemented firstly. Then, the cloud calculates the nearest neighbors of a given data point while the data point as well as the data points in the training set are in encrypted form. We can obtain classification results which are in encrypted form. The correctness of the scheme has been shown over cardiac disease dataset. The results show the efficiency of the proposed scheme satisfy the requirements of the system and accurately classify data which is in encrypted form.