Achieving k-anonymity in privacy-aware location-based services

TLDR

Location‑based services are ubiquitous but expose users to privacy risks from untrusted servers that can track or share personal data. We propose a Dummy‑Location Selection algorithm to achieve k‑anonymity for users in LBS. The algorithm selects dummy locations using an entropy metric and then spreads them far apart to maximize anonymity, with an enhanced version that further enlarges the cloaking region. Evaluation shows the DLS algorithm significantly improves entropy‑based privacy, and the enhanced version enlarges the cloaking region while maintaining similar privacy.

Abstract

Location-Based Service (LBS) has become a vital part of our daily life. While enjoying the convenience provided by LBS, users may lose privacy since the untrusted LBS server has all the information about users in LBS and it may track them in various ways or release their personal data to third parties. To address the privacy issue, we propose a Dummy-Location Selection (DLS) algorithm to achieve k-anonymity for users in LBS. Different from existing approaches, the DLS algorithm carefully selects dummy locations considering that side information may be exploited by adversaries. We first choose these dummy locations based on the entropy metric, and then propose an enhanced-DLS algorithm, to make sure that the selected dummy locations are spread as far as possible. Evaluation results show that the proposed DLS algorithm can significantly improve the privacy level in terms of entropy. The enhanced-DLS algorithm can enlarge the cloaking region while keeping similar privacy level as the DLS algorithm.