Fine-Grained Query Authorization With Integrity Verification Over Encrypted Spatial Data in Cloud Storage

In this article, a fine-grained query authorization scheme with integrity verification is proposed over encrypted spatial data for location-based services (LBS). The fine-grained query authorization is enabled based on a distribution of the spatial data by employing a non-uniform partition in the spatial domain to generate a density-based space filling curve (DSC), which can be used to generate index values for querying and transformation keys. The transformation keys can be used to generate query tokens for a secure spatial query as well as construct a transformation key tree whose subtree can be distributed by the LBS provider to an authorized user as transformation key for query tokens generation. Furthermore, the proposed scheme constructs a Merkle quad tree (MQ-tree) to support integrity verification by aggregating a digest of the spatial data based on the DSC and employing the MQ-tree as a verification structure. The LBS provider can share a subtree of the MQ-tree to authorized user as his verification structure, which corresponds to the transformation key of the authorized user. In this way, the authorized user can only generate the valid query tokens and verify the query results in his authorized region. The security properties of the proposed scheme is discussed, and extensive experimental results demonstrate the high efficiency of verification structure generation and verification operations.