A novel location privacy-preserving scheme based on l-queries for continuous LBS

Location cloaking based on k-anonymity is one of the most prevalent privacy-preserving technologies for Location Based Services (LBS). However, it has been proved vulnerable to expose the user's identity. In this paper, we propose a location anonymity scheme based on the fake queries in continuous location-based services. To prevent attackers from tracing a mobile user by his/her continuous queries, some fake queries will be randomly injected by a Trusted Third Party. These fake queries can prevent the reverse mapping from user identity to query content. Also, we hide his/her actual query amongst a set of queries by merging the neighbors' request in a single query. Moreover, a partitioning algorithm and a clustering algorithm are introduced to reduce the computation and communication overhead further. Security analysis shows that our scheme can resist the continuous queries attack and the trajectory attack. Detailed theoretical analyses and experimental results show the effectiveness and practicality of the proposed scheme.