Privacy-Preserving Linear Region Search Service

Due to a variety of advantages of data outsourcing, some Location Based Services (LBS) providers are motivated to outsource the geographic data and query service to commercial cloud. However, for protecting data confidentiality, the valuable data should be encrypted before outsourcing, which obstructs the utilization like geographic information query. To address this problem, some previous works regarding to secure search on encrypted database could be applied in outsourced LBS scenario directly, but none of them is tailor-made for linear region search (LRS). The LRS is a kind of LBS that widely used in navigation system, it finds the nearby points of interest (POI) for a query segment. In this paper, for the first time, we explore and solve the challenging problem of privacy-preserving linear region search. Specifically, we choose the quadtree structure to build index for POI database, then the results of LRS can be efficiently obtained by finding out the rectangular regions that query segment passes through. In order to preserve the privacy of both LBS providers and users, according to computational geometry and Asymmetric Scalar-product Preserving Encryption (ASPE) approach, we design a novel algorithm for accurately determining whether a segment intersects with a rectangle on ciphertext. Moreover, this algorithm also provides a new idea to solve other computational problems in encrypted 2-dimensional geometry space. Based on different privacy requirements of two threat models, we propose two privacy-preserving LRS schemes and corresponding dynamic update operations. Security analysis and experiments on real-world dataset show that our schemes are secure and efficient.