Protecting K-Nearest Neighbor Queries from Location Inference Attacks
This work addresses location inference attacks against kNNQ, a widely used LBS feature, and provides a practical defense mechanism for users and service providers.
The paper identifies location privacy risks in k-nearest neighbor queries (kNNQ) and proposes a differential privacy framework (DPRS) that uses rejection sampling within a constrained perturbation interval to improve the privacy-utility trade-off, outperforming existing methods on real-world datasets.
The k-nearest neighbor query (kNNQ) is a core component of modern location-based services (LBS) and has been widely adopted in popular features such as ``people nearby''. However, its potential privacy risks have long been overlooked. In this work, we present the first two attacks against kNNQ, namely the geometric intersection location inference attack (GI-LIA) and the zero-order optimization location inference attack (ZO-LIA), revealing the inherent location privacy risks posed by kNNQ. To mitigate these privacy risks, we further propose DPRS, a differential privacy framework for kNNQ protection. The core idea of DPRS is to incorporate a rejection sampling mechanism within a constrained perturbation interval, thereby mitigating the distance distortion caused by excessive noise injection. In addition, we design a private interval construction algorithm to construct the perturbation interval, enabling the rejection sampling mechanism to achieve a more favorable trade-off between privacy protection and query utility in kNNQ. Extensive experiments on real-world spatial datasets demonstrate that DPRS outperforms existing methods in both privacy protection and query utility. Our code is available at https://github.com/reanatom/DPRS.