A Privacy Preserving Spatial Range Query Over Encrypted Data Without Disclosing User Locations To The Cloud

Abstract

The Location based services (LBS) have received considerable attention and become more popular and vital recently. However, the use of LBS also poses a potential threat to user’s location privacy. In this paper, aiming at spatial range query, a popular LBS providing information about POIs (Points of Interest) within a given distance, we present an efficient and privacy-preserving location based query solution, called EPLQ. Specifically, to achieve privacy preserving spatial range query, we propose the first predicate only encryption scheme for inner product range, which can be used to detect whether a position is within a given circular area in a privacy-preserving way.

Significant challenges still remain in the design of privacy preserving LBS, and new challenges arise particularly due to data outsourcing. In recent years, there is a growing trend of outsourcing data including LBS data because of its financial and operational benefits. Lying at the intersection of mobile computing and cloud computing, designing privacy-preserving outsourced spatial range query faces the challenges. The techniques used to realize privacy-preserving query usually increase the search latency.

A novel predicate-only encryption scheme for inner product range named IPRE, which allows testing whether the inner product of two vectors is within a given range without disclosing the vectors and an efficient solution for privacy-preserving spatial range query. In particular, we show that whether a POI matches aspatial range query or not can be tested by examining whether the inner product of two vectors is in a given range. This can be used for more kinds of privacy-preserving queries over outsourced data. In the spatial range query discussed in this work, we consider Euclidean distance, which is widely used in spatial databases.

EPLQ, we have designed a novel predicate-only encryption scheme for inner product range named IPRE and a novel privacy-preserving index tree named ss-tree. EPLQ’s efficacy has been evaluated with theoretical analysis and experiments, and detailed analysis shows its security against known-sample attacks and cipher text-only attacks. Techniques have potential usages in other kinds of privacy-preserving queries. If the query can be performed through comparing inner products to a given range and two potential usages are privacy preserving similarity query and long spatial range query.