Efficient and Privacy-Preserving Polygons Spatial Query Framework for Location-Based Services

TLDR

Mobile devices and wireless communication have made location‑based services ubiquitous, and polygon‑based spatial queries offer greater flexibility but raise significant privacy concerns. This paper introduces Polaris, an efficient, privacy‑preserving framework for polygon spatial queries in LBS. Polaris outsources encrypted LBS data to a cloud server and lets users issue encrypted polygon queries that are processed by a special polygons spatial query algorithm built on improved homomorphic encryption over a composite‑order group, returning accurate results without revealing query information to the provider or server. Security analysis confirms Polaris resists known threats, and empirical tests on smartphones and workstations with real LBS data demonstrate its practical effectiveness.

Abstract

With the pervasiveness of mobile devices and the development of wireless communication technique, location-based services (LBSs) have made our life more convenient, and the polygons spatial query, which can provide more flexible LBS, has attracted considerable interest recently. However, the flourish of polygons spatial query still faces many challenges including the query information privacy. In this paper, we present an efficient and privacy-preserving polygons spatial query framework for location-based services, called Polaris. With Polaris, the LBS provider (LP) outsources the encrypted LBS data to cloud server (CS), and the registered user can query any polygon range to get accurate LBS results without divulging his/her query information to the LP and CS. Specifically, an efficient special polygons spatial query (SPSQ) algorithm over ciphertext is constructed, based on an improved homomorphic encryption technology over composite order group. With SPSQ, Polaris can search outsourced encrypted LBS data in CS by the encrypted request, and respond the encrypted polygons spatial query results accurately. Detailed security analysis shows that the proposed Polaris can resist various known security threats. In addition, performance evaluations via implementing Polaris on smartphone and workstation with real LBS dataset demonstrate Polaris' effectiveness in term of real environment.