VeriRange: A Verifiable Range Query Model on Encrypted Geographic Data for IoT Environment

Abstract

In the era of the Internet of Things (IoT), the rapid development of cloud computing has been advancing location-based services (LBS). To enjoy the considerable advantages of lower cost and higher performance of cloud computing, it has become the first choice for most IoT enterprises to outsource data and services to public clouds. However, the privacy protection of data and the integrity of query results cannot be effectively guaranteed since public clouds cannot be fully trusted. In this paper, we propose a lightweight verifiable range query scheme (namely VeriRange). First, a pair of mutually perpendicular locality-sensitive hashing (LSH) is adopted to divide the original geographic data into subsets. Then a pivoted k dimensional (PKD) tree and a height-balanced binomial search tree (i.e., AVL tree) are established on the client and the cloud respectively to accelerate the processes of queries. To ensure the verification of query results, a keyed hash function is utilized to generate a verification tag for each subset. Verification tags in the public cloud are encrypted and independent of queries. It ensures fast verification of query results because the verification tags are not repeatedly calculated on each query. Formal security analysis shows VeriRange ensures the privacy of data, queries, and results. Experimental studies were conducted on real and synthetic datasets and demonstrated that the query and verification time in VeriRange is almost 2-3 orders of magnitude faster than that in state-of-art schemes.