Research On K Nearest Neighbor Query Over Encrypted Data

Recent years, with the rise of the cloud service, the company that has extra computing resources and storage resources provide the cloud service for the vast number of users, such as Ali cloud, Amazon Relational Database Service(Amzaon RDS). Some companies or person that cannot manage their data will send the data to service provider that help them tackle users'request,because they have limit computing resources and want to maximize the benefit of the company. In order to ensure the benefits of these people that have data, the data will be encrypted before uploading to the service provider; this can prevent the service providers to harm these people's interests. However, tackling query request over encrypted data will become difficult,so it is very necessary to provide an efficient and safe method to solve this problem. In this paper, we will study how to help the service provider to tackle the k nearest neighbor query request over encrypted data and prevent the data from being stolen by service provider.At present, many researchers have done research on this problem. The methods to solve this problem can be divided into two categories. The first category is to construct a particular data structure and then to choose a specific search strategy to get the knn results. The second category is to preserve the relation between ciphertext distance and plaintext distance through proposing new encryption algorithm, thus we can get the results by computing the ciphertext distance. There are two main problems in these methods. The first issue is the security of the data cannot be ensured, some attackers can get the plaintext by choosing specific attack method. The second issue is the query efficiency is low. Some work only focused on how to safely compute the distance between two encrypted data and ignored the query efficiency.In this paper,we solve this question from two aspects. Firstly,we focus on the query efficiency. It is necessary to improve the user experience and save computing resources through reducing query time. So we propose a k nearest neighbor query algorithm based on hierarchical clustering. The algorithm uses the pruning rules to exclude most of the non-nearest neighbor data and improve query efficiency. Secondly,we focus on data's security.The main problem over encrypted data is how to compute the distance between two ciphertext data. In this paper, we use the properties of homomorphic encryption algorithm to compute the distance between two encrypted data, this method can ensure the security of data. The combination of these two algorithms constitutes a k nearest neighbor query algorithm over encrypted data based on hierarchical clustering. The experiments show that the algorithm proposed in this paper has high query efficiency.