Protecting query privacy with differentially private k-anonymity in location-based services

Nowadays, location-based services (LBS) are facilitating people in daily life through answering LBS queries. However, privacy issues including locationprivacy and queryprivacy arise at the same time. Existing works for protecting queryprivacy either work on trusted servers or fail to provide sufficient privacy guarantee. This paper combines the concepts of differential privacy and k-anonymity to propose the notion of differentially private k-anonymity (DPkA) for queryprivacy in LBS. We recognize the sufficient and necessary condition for the availability of 0-DPkA and present how to achieve it. For cases where 0-DPkA is not achievable, we propose an algorithm to achieve 𝜖-DPkA with minimized 𝜖. Extensive simulations are conducted to validate the proposed mechanisms based on real-life datasets and synthetic data distributions.