Privacy Preserving Spatial Range Query Over Outsourced Encrypted Data

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.