Privacy-Area Aware Dummy Generation Algorithms for Location-Based Services

Location-Based Services (LBSs) have been one of the most popular activities in our daily life. Users can send queries to the LBS server easily to learn their surroundings. However, these location-related queries may result in serious privacy concerns since the un-trusted LBS server has all the information about users and may track them in various ways. In this paper, we propose two dummy-based solutions to achieve k-anonymity for privacy-area aware users in LBSs with considering that side information may be exploited by adversaries. We first choose some candidates based on a virtual circle or grid method, then blur these candidates into the final positions of dummy locations based on the entropy-based privacy metric. Security analysis and evaluation results indicate that the V-circle solution can significantly improve the privacy anonymity level. The V-grid solution can further enlarge the cloaking region while keeping similar privacy level.