Protecting K-Nearest Neighbor Queries from Location Inference Attacks

Computer Science > Cryptography and Security [Submitted on 4 Jun 2026] Protecting K-Nearest Neighbor Queries from Location Inference Attacks Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, Zhili Chen 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 this https URL. Comments: This paper has been accepted by ECML-PKDD 2026 Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2606.05648 [cs.CR]   (or arXiv:2606.05648v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2606.05648 Focus to learn more Submission history From: Zhiyu Sun [view email] [v1] Thu, 4 Jun 2026 03:25:58 UTC (366 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-06 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)