Privacy-preserving Boolean range query with verifiability and forward security over spatio-textual data

Boolean range query, as one typical spatial keyword query, has received more and more attention and been widely deployed in many applications. To release the storage and computation burden of client, the spatio-textual data is usually outsourced to the cloud. Some existing schemes have been proposed to realize privacy -preserving boolean range query over spatio-textual data. Nevertheless, these schemes do not support the verifiability and the forward security of spatiotextual data simultaneously. In this paper, we aim at exploring this issue and design a privacypreserving boolean range query scheme with verifiability and forward security over spatio-textual data. In order to realize forward security, we build a secure binary tree index and a secure keyword index for the spatio-textual data. In each update, we generate new tokens for all leaf nodes using different keys, and assign new states for updated keywords. The cloud cannot learn the keyword of previous query token because the update token is not matched with the previous query token. As a result, the proposed scheme realizes forward security. To realize result verification, we design a novel forward secure verification tag. Benefiting from the accumulation of this tag and the newly state assigned for keyword, we can conveniently perform update operation and prevent the cloud from returning the object not updated. According to the newly state stored locally and the returned objects by the cloud, we can generate the tag and check whether it is the same as the returned tag for verifying the result validity. We leverage the additive symmetric homomorphic encryption algorithm to securely realize the accumulation of ciphertexts. Formal security analysis presents that our proposed scheme satisfies forward security and verifiability. Extend experiment is conducted to show its efficiency.