Efficient k-Nearest Neighbor Classification Over Semantically Secure Hybrid Encrypted Cloud Database

Nowadays, individuals and companies increasingly tend to outsource their databases and further data operations to cloud service provides. However, utilizing the cost-saving advantages of cloud computing brings about the risk of violating database security and user's privacy. In this paper, we focus on the problem of privacy-preserving k-nearest neighbor (kNN) classification, in which a query user (QU) submits an encrypted query point to a cloud server (CS) and asks for the kNN classification labels based on the encrypted cloud database outsourced by a data owner (DO), without disclosing any privacy of DO or QU to CS. Previous secure kNN query schemes either cannot fully achieve required security properties or introduce heavy computation costs, making them not practical in real-world applications. To better solve this problem, we propose a novel efficient privacy-preserving kNN classification protocol over semantically secure hybrid encrypted cloud database using Paillier and ElGamal cryptosystems. The proposed protocol protects both database security and query privacy and also hides data access patterns from CS. We formally analyze the security of our protocol and evaluate the performance through extensive experiments. The experiment results show that the computation cost of our protocol is about two orders of magnitude lower than that of the state-of-the-art protocol while achieving the same security and privacy properties.