A query integrity assurance scheme for accessing outsourced spatial databases

With the trend of cloud computing, outsourcing databases to third party service providers is becoming a common practice for data owners to decrease the cost of managing and maintaining databases in-house. In conjunction, due to the popularity of location-based-services (LBS), the need for spatial data (e.g., gazetteers, vector data) is increasing dramatically. Consequently, there is a noticeably new tendency of outsourcing spatial datasets by data collectors. Two main challenges with outsourcing datasets are to keep the data private (from the data provider) and to ensure the integrity of the query result (for the clients). Unfortunately, most of the techniques proposed for privacy and integrity do not extend to spatial data in a straightforward manner. Hence, recent studies proposed various techniques to support either privacy or integrity (but not both) on spatial datasets. In this paper, for the first time, we propose a technique that can ensure both privacy and integrity for outsourced spatial data. In particular, we first use a one-way spatial transformation method based on Hilbert curves, which encrypts the spatial data before outsourcing and, hence, ensures its privacy. Next, by probabilistically replicating a portion of the data and encrypting it with a different encryption key, we devise a technique for the client to audit the trustworthiness of the query results. We show the applicability of our approach for both k-nearest-neighbor queries and spatial range queries, which are the building blocks of any LBS application. We also design solutions to guarantee the freshness of outsourced spatial databases. Finally, we evaluate the validity and performance of our algorithms with security analyses and extensive simulations.