Full Program »
Privacy Preserving kNN Spatial Query with Voronoi Neighbors
With the increased demand for outsourcing databases, there is a demand to enable secure and efficient communications. The concern regarding outsourcing da-ta is mainly providing confidentiality and integrity to the data. This paper pro-poses a novel solution to answering kNN queries at the cloud server over encrypted data. Data owners transform their data from a native domain to a new domain to assist in nearest neighbors’ classification. The transformation is achieved by Voronoi diagram, which transforms the data space into numerous small regions, simplifying the nearest neighbor search. However, because the regions that make up a Voronoi diagram are irregularly shaped, the search through the network becomes hard to accomplish. Thus, the solution includes a Grid-based indexing approach for the Voronoi diagram to expedite the kNN search. Additionally, a strong encryption algorithm, like AES, is used to encrypt the data objects being sent from the data owner to the cloud. An authorized user sends encrypted kNN queries to the cloud where the query is processed over encrypted data. The cloud service provider utilizes the proposed indexing scheme to identify a superset of the nearest neighboring objects to be sent back to the user. The user possessing a copy of the encryption key decrypts the superset of k nearest neighbors and filters the exact k objects.