k-Nearest Neighbor Classification over Semantically Secure Encrypted Relational Data

Abstract

Data Mining has wide applications in many areas such as banking, medicine, scientific research and among
government agencies. Classification is one of the commonly used tasks in data mining applications. For the past decade, due
to the rise of various privacy issues, many theoretical and practical solutions to the classification problem have been
proposed under different security models. However, with the recent popularity of cloud computing, users now have the
opportunity to outsource their data, in encrypted form, as well as the data mining tasks to the cloud. Since the data on the
cloud is in encrypted form, existing privacy-preserving classification techniques are not applicable. In this paper, we focus
on solving the classification problem over encrypted data. In particular, we propose a secure k -NN classifier over encrypted
data in the cloud. The proposed protocol protects the confidentiality of data, privacy of user’s input query, and hides the data
access patterns. To the best of our knowledge, our work is the first to develop a secure k -NN classifier over encrypted data
under the semi-honest model. Also, we empirically analyze the efficiency of our proposed protocol using a real-world dataset
under different parameter settings.