Location privacy-preserving k nearest neighbor query under user’s preference

摘要

Location-based services can provide users’ surroundings anywhere and anytime. While this service brings convenience for users, the disclosure of user’s location becomes the main concerns. Most current practices fall into K-anonymity model, in parallel with location cloaking. This schema commonly suffers from the following constraints. (1) K-anonymity cannot support users’ preferential query requirements effectively. (2) location cloaking commonly assumes that there exists a trusted third party to serve as anonymizer, which is inclined to be the bottleneck of the query. Concerning these problems, a novel location privacy model (s, ε)-anonymity is devised from perspective of minimum inferred region and candidate answer region, which present location protection strength and scale of intermediate results, respectively. Particularly, user’s preferential query requirements on privacy protection strength and query efficiency can be presented in a more convenient and effective way by setting parameters s and ε rather than K-anonymity model does. A thin server solution is developed to realize the model, which pushes most workload originated from user’s preferential requirement down to client side leveraging false query technology without any trusted third parties’ intervention. Furthermore, an entropy based strategy is devised to construct candidate answer region, which boosts privacy protection strength and query efficiency simultaneously. Theoretical analysis and empirical studies demonstrate our implementation delivers well trade-off among location protection, query performance and query user’s privacy preference.