P³GQ: A practical privacy-preserving generic location-based services query scheme

The Location-Based Services (LBS) enables people to find location places according to their interests. As the size of LBS dataset surprisingly increases, the LBS providers inevitably outsource their LBS dataset to a cloud server, but needs to encrypt it at first for preventing sensitive information leakage. However, designing a scheme that supports generic LBS query over encrypted data is still a challenging problem. Motivated by this, we present a practical privacy-preserving generic LBS query scheme (P³GQ), which achieves both data privacy and query privacy. In the scheme, a LBS provider outsources its dataset to a cloud server and relies on it to process LBS queries, but leaks no confidential information about both the dataset and queries to the cloud server. More specifically, we introduce a new tool called CircleTest: to test whether a point is inside of a given circular area or not, while keeps them secret. Hence, we obtain the P³GQ scheme to support for generic LBS query while achieving privacy-preserving based on the CircleTest building block and an encrypted inverted index technique. We analyze the privacy requirements of our scheme, and additionally conduct an experiment on both the building block CircleTest and the P³GQ scheme to show their practical performance.