Secure and Efficient Nearest Neighbor Query for an Outsourced Database

Cloud computing enables resource-constrained clients to outsource their computation-intensive data storage and computation tasks to a cloud server. Although it creates many benefits, data outsourcing causes some security challenges for clients. In this paper, we propose the secure and efficient query (SecNN) scheme to address the secure nearest neighbor query problem, which is popular in academia and industry. Compared with the state-of-the-art scheme, the proposed scheme can significantly decrease the number of communications between the clients and the cloud server. Furthermore, it achieves the desired security in the random oracle model. Moreover, the extending scheme described can verify the correctness and completeness of query results and database updates by using the Merkle hash tree technique. Finally, an experimental evaluation demonstrates the high efficiency of our scheme.