Secure k-NN Query With Multiple Keys Based on Random Projection Forests

As a basic primitive in spatial and multimedia databases, the k-nearest neighbors (k-NN) query has been widely used in electronic medicine, location-based services, and so on. With the boom in cloud computing, it is currently a trend to upload massive data to the cloud server to enjoy its powerful storage and computing resources. Recently, research communities and commercial applications have proposed many schemes to support k-NN query on cloud data. However, most of the existing k-NN query schemes were designed under the assumption that the query users (QUs) are fully trusted and hold the key of the data owner. In this case, even if the queries were encrypted, the QUs can capture the query content from each other, leading to the query privacy leakage. Unfortunately, to the best of our knowledge, few k-NN query schemes can ensure data privacy under the key-confidentiality condition. In this article, we propose a secure k-NN query with multiple keys based on random projection forests (SMkNN), in which each QU's partial strong private key can only decrypt the encrypted query results belonging to its own, but not the encrypted database, the encrypted query data and query results of other QUs. Moreover, our proposal not only answers the query efficiently but also ensures the privacy of data, query, results, and access pattern, and the verification of the correctness of the results. Finally, the complexity and security are theoretically analyzed, and the practicality and efficiency of our proposed scheme are compared by simulation experiments. Index Terms-Access pattern