Enabling Efficient and Geometric Range Query With Access Control Over Encrypted Spatial Data

TLDR

Range queries are widely used in SQL, location‑based services, and computational geometry, yet as data volumes grow and users outsource to the cloud, encrypted storage is required to prevent full data disclosure. The authors propose an efficient and geometric range query scheme (EGRQ) that supports searching and data access control over encrypted spatial data. EGRQ employs secure KNN, polynomial fitting, and order‑preserving encryption, together with a novel access‑control strategy and R‑tree indexing, to enable secure, efficient, and accurate geometric range queries on cloud data. The scheme is proven secure in confidentiality, privacy, and unlinkability, and experiments demonstrate its high efficiency compared with existing methods.

Abstract

As a basic query function, range query has been exploited in many scenarios such as SQL retrieves, location-based services, and computational geometry. Meanwhile, with explosive growth of data volume, users are increasingly inclining to store data on the cloud for saving local storage and computational cost. However, a long-standing problem is that the user's data may be completely revealed to the cloud server because it has full data access right. To cope with this problem, a frequently-used method is to encrypt raw data before outsourcing them, but the availability and operability of data will be reduced significantly. In this paper, we propose an efficient and geometric range query scheme (EGRQ) supporting searching and data access control over encrypted spatial data. We employ secure KNN computation, polynomial fitting technique, and order-preserving encryption to achieve secure, efficient, and accurate geometric range query over cloud data. Then, we propose a novel spatial data access control strategy to refine user's rights in our EGRQ. To improve the efficiency, R-tree is adopted to reduce the searching space and matching times in whole search process. Finally, we theoretically prove the security of our proposed scheme in terms of confidentiality of spatial data, privacy protection of index and trapdoor, and the unlinkability of trapdoors. In addition, extensive experiments demonstrate the high efficiency of our proposed model compared with existing schemes.