Enhancing privacy through uniform grid and caching in location-based services

With the increasing popularity of location-based services (LBSs), there is a corresponding increase in the potential for location privacy leakage. Existing solutions generally introduce a fully-trusted third party between the users and the location service provider (LSP). However, such an approach offers limited privacy guarantees and incurs high communication overhead. Specifically, once a fully-trusted third party is compromised, user information would likely be exposed. In this paper, we propose a solution designed to enhance location privacy in LBSs. Our scheme is based on the uniform grid, and adopts both order-preserving symmetric encryption (OPSE) and k-anonymity technique. Thus, the anonymizer knows nothing about a user's real location, and it can only implement simple matching and comparison operations. In our approach, we also employ an entity (hereafter referred to as the converter) to transform the user-defined grid structure into the uniform grid structure. This combined with the caching mechanism, allow us to avoid repeated queries from different users on the same query spatial region and consequently, reduce the overhead of the LBS server. The analysis and simulation results demonstrate that our proposal can effectively preserve a user's location privacy, with reduced overheads at the anonymizer and the LBS server.