Protecting K-Nearest Neighbor Queries from Location Inference Attacks

• URL: http://arxiv.org/abs/2606.05648v1
• Date: Thu, 04 Jun 2026 03:25:58 GMT
• Title: Protecting K-Nearest Neighbor Queries from Location Inference Attacks
• Abstract summary: k-nearest neighbor query (kNNQ) is a core component of modern location-based services (LBS)<n>In this work, we present the first two attacks against kNNQ, revealing the inherent location privacy risks posed by kNNQ.<n>To mitigate these privacy risks, we propose DPRS, a differential privacy framework for kNNQ protection.
• Score: 10.316884038674038
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Privacy Without Losing Place: A Paradigm for Private Retrieval in Spatial RAGs [5.928512439824825]
  PAS represents location with relative anchor encoding consisting of an anchor, direction bin, and distance bin.<n>We evaluate PAS on a synthetic urban dataset and show that it achieves impressive coarse privacy guarantees, with approximately 370-400m adversarial location error.
  arXiv  Detail & Related papers  (2026-05-06T21:33:43Z)
• Road Network-Aware Personalized Trajectory Protection with Differential Privacy under Spatiotemporal Correlations [33.41548062041307]
  This paper proposes a Personalized Trajectory Privacy Protection Mechanism (PTPPM) to address these challenges.<n>Our approach begins by modeling an attacker's knowledge of a user's trajectory sensitivity, which enables the attacker to identify possible location sets.<n>To combat this, we integrate geo-inability correlations with distortion, allowing users to customize their privacy preferences.
  arXiv  Detail & Related papers  (2025-11-26T03:33:24Z)
• Convergent Differential Privacy Analysis for General Federated Learning: the $f$-DP Perspective [57.35402286842029]
  Federated learning (FL) is an efficient collaborative training paradigm with a focus on local privacy. differential privacy (DP) is a classical approach to capture and ensure the reliability of private protections.
  arXiv  Detail & Related papers  (2024-08-28T08:22:21Z)
• Enhanced Privacy Bound for Shuffle Model with Personalized Privacy [32.08637708405314]
  Differential Privacy (DP) is an enhanced privacy protocol which introduces an intermediate trusted server between local users and a central data curator. It significantly amplifies the central DP guarantee by anonymizing and shuffling the local randomized data. This work focuses on deriving the central privacy bound for a more practical setting where personalized local privacy is required by each user.
  arXiv  Detail & Related papers  (2024-07-25T16:11:56Z)
• Secure Aggregation is Not Private Against Membership Inference Attacks [66.59892736942953]
  We investigate the privacy implications of SecAgg in federated learning. We show that SecAgg offers weak privacy against membership inference attacks even in a single training round. Our findings underscore the imperative for additional privacy-enhancing mechanisms, such as noise injection.
  arXiv  Detail & Related papers  (2024-03-26T15:07:58Z)
• From Mean to Extreme: Formal Differential Privacy Bounds on the Success of Real-World Data Reconstruction Attacks [54.25638567385662]
  Differential Privacy in machine learning is often interpreted as guarantees against membership inference.<n> translating DP budgets into quantitative protection against the more damaging threat of data reconstruction remains a challenging open problem.<n>This paper bridges the critical gap by deriving the first formal privacy bounds tailored to the mechanics of demonstrated "from-scratch" attacks.
  arXiv  Detail & Related papers  (2024-02-20T09:52:30Z)
• Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks [72.51255282371805]
  We prove a privacy bound for the KL divergence between model distributions on worst-case neighboring datasets. We find that this KL privacy bound is largely determined by the expected squared gradient norm relative to model parameters during training.
  arXiv  Detail & Related papers  (2023-10-31T16:13:22Z)
• Privacy-Preserving Community Detection for Locally Distributed Multiple Networks [11.693304974549893]
  We propose a new method for consensus community detection and estimation in a multi-layer block model. A novel algorithm named Distributed Spectral Clustering (ppDSC) is developed.
  arXiv  Detail & Related papers  (2023-06-27T08:36:13Z)
• On Differentially Private Federated Linear Contextual Bandits [9.51828574518325]
  We consider cross-silo federated linear contextual bandit (LCB) problem under differential privacy. We identify three issues in the state-of-the-art: (i) failure of claimed privacy protection and (ii) incorrect regret bound due to noise miscalculation. We show that our algorithm can achieve nearly optimal'' regret without a trusted server.
  arXiv  Detail & Related papers  (2023-02-27T16:47:49Z)
• Over-the-Air Federated Learning with Privacy Protection via Correlated Additive Perturbations [57.20885629270732]
  We consider privacy aspects of wireless federated learning with Over-the-Air (OtA) transmission of gradient updates from multiple users/agents to an edge server. Traditional perturbation-based methods provide privacy protection while sacrificing the training accuracy. In this work, we aim at minimizing privacy leakage to the adversary and the degradation of model accuracy at the edge server.
  arXiv  Detail & Related papers  (2022-10-05T13:13:35Z)
• Privacy Amplification via Shuffling for Linear Contextual Bandits [51.94904361874446]
  We study the contextual linear bandit problem with differential privacy (DP) We show that it is possible to achieve a privacy/utility trade-off between JDP and LDP by leveraging the shuffle model of privacy. Our result shows that it is possible to obtain a tradeoff between JDP and LDP by leveraging the shuffle model while preserving local privacy.
  arXiv  Detail & Related papers  (2021-12-11T15:23:28Z)
• Smoothed Differential Privacy [55.415581832037084]
  Differential privacy (DP) is a widely-accepted and widely-applied notion of privacy based on worst-case analysis. In this paper, we propose a natural extension of DP following the worst average-case idea behind the celebrated smoothed analysis. We prove that any discrete mechanism with sampling procedures is more private than what DP predicts, while many continuous mechanisms with sampling procedures are still non-private under smoothed DP.
  arXiv  Detail & Related papers  (2021-07-04T06:55:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.