{"ID":3084811,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T03:05:32.813677833Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.05648","arxiv_id":"2606.05648","title":"Protecting K-Nearest Neighbor Queries from Location Inference Attacks","abstract":"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.","short_abstract":"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 int...","url_abs":"https://arxiv.org/abs/2606.05648","url_pdf":"https://arxiv.org/pdf/2606.05648v1","authors":"[\"Zhiyu Sun\",\"Jie Fu\",\"Xinpeng Ling\",\"Huifa Li\",\"Zhili Chen\"]","published":"2026-06-04T03:25:58Z","proceeding":"cs.CR","tasks":"[\"cs.CR\"]","methods":"[]","has_code":false,"code_links":[{"ID":612859,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-05T06:46:15.197025399Z","DeletedAt":null,"paper_id":3084811,"paper_url":"https://arxiv.org/abs/2606.05648","paper_title":"Protecting K-Nearest Neighbor Queries from Location Inference Attacks","repo_url":"https://github.com/reanatom/DPRS","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}