Achieving Efficient and Privacy-Preserving Arbitrary Geographic Range Query for Cloud

Geographic range query, as a basic query function, has been widely leveraged in location-based services. To adapt to the explosive growth of location data, more and more businesses and individuals choose to store their massive amounts of data on the powerful cloud, which however may raise severe threats to users' privacy. To resolve this problem, the location data is often encrypted before outsourcing, but this may sacrifice the availability and utility of the location data. In this paper, we design a geographic range query scheme to support efficient and privacy-preserving arbitrary geographic range queries over encrypted location data. Specifically, we first utilize the polynomial fitting technique to generate trapdoors for arbitrary geographic query ranges. Then, we design a randomizable matrix multiplication method based on matrix decomposition to achieve geographic range queries between data owners and data requesters. Through rigorous security analysis, we demonstrate the privacy of location data and queries is well protected in our scheme. Extensive experiments and performance evaluations show that our proposed scheme is highly efficient in terms of computational cost and communication overhead.