Circular Range Search On Encrypted Spatial Data

With the rapid development of location-based services(LBS),the volume of spatial data will inevitably explode.In order to reduce local storage and computing overhead,users tend to outsource data and initiate queries to the cloud.However,since cloud service providers are not completely credible,if they have the right to directly access original data and plaintext queries,they may bring security risks to sensitive data or user-inquired interest content.In order to solve this problem,it is necessary to encrypt the data before uploading it to the cloud server.However,the encrypted data greatly increases the difficulty of searching,and the efficiency of traditional search algorithms is low.Using searchable encryption methods,the search for encrypted data can be completed efficiently without revealing privacy.This paper proposes two schemes to solve the problem of circular range search on encrypted spatial data.The circular range search problem means that a user gives a circular query range,and the cloud server returns all data points fall in this range.Aiming at this basic problem,this paper converts the matching calculation of ciphertext into the calculation of inner product,and proposes a polynomial segmentation algorithm,which can greatly separate the data information and query information in a polynomial,and will complete accurate and effective search on encrypted data without reveal index privacy and query privacy.Through security analysis and simulation experiments,it can be known that the algorithm has high security and feasibility.In order to further improve the search efficiency,this paper uses the R-tree data structure to build an index,which can narrow the search range to achieve sub-linear search complexity.Considering the problem of access control in practical systems,this paper proposes an access control strategy that can efficiently verify the legitimacy of user access.Then,we formally defined the security of the scheme and theoretically proved its indistinguishable security(IND-SCPA)under selective chosen plaintext attacks.In addition,we compare the scheme proposed in this paper with the existing schemes,and through comparative experiments we prove that the scheme can effectively reduce the user's query time,which is of great significance to the application of real world scenarios.