💻 computer science

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

This paper identifies inherent location privacy risks in k-nearest neighbor queries through two novel inference attacks and proposes DPRS, a differential privacy framework utilizing rejection sampling and private interval construction to effectively balance privacy protection with query utility.

Original authors: Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, Zhili Chen

Published 2026-06-05

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, Zhili Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are using a popular app to find friends or people nearby. You don't want to show your exact address, so the app gives you a list of the "Top 5 closest people" instead of a map with pins. You think, "Great, my exact location is hidden!"

This paper says: Not so fast. Even without seeing your exact coordinates, a clever attacker can still figure out where you are just by looking at that ranked list.

Here is a breakdown of what the researchers found and how they fixed it, using simple analogies.

The Problem: The "Ranking" Trap

The researchers discovered that the simple list of "Who is closest?" leaks more information than you think. They invented two ways to hack this system:

1. The "Flashlight" Attack (GI-LIA)
Imagine you are standing in a dark field (your true location). An attacker has a flashlight (a known location).

The attacker moves the flashlight around until they see you appear on the list as the "5th closest person."
This tells the attacker: "You are exactly 100 meters away from this flashlight."
The attacker moves to a second spot, finds you are also the 5th closest person there. Now they know you are 100 meters from that spot too.
Where do those two circles of 100 meters overlap? Right on top of you!
The Catch: This works perfectly, but it's slow. The attacker has to walk around a lot and ask the app thousands of times to draw those circles.

2. The "Homing Pigeon" Attack (ZO-LIA)
This is the smarter, faster version.

The attacker starts with one circle (like the first step above).
Instead of drawing a second circle, they send out "probes" in different directions around that circle.
They check the list: "If I move North, does the target move up the list? If I move South, do they move down?"
By watching how the target's rank changes, the attacker can guess the direction to move to get closer to the target, like a homing pigeon finding its way home.
The Result: They can pinpoint your location with over 95% accuracy, and they do it much faster than the first method.

The Solution: The "Fuzzy Bubble" (DPRS)

The researchers realized that simply adding random "noise" (fake locations) to your data often breaks the app. If the fake location is too far away, the "Top 5" list becomes useless because the people on the list aren't actually the closest anymore.

They created a new defense called DPRS. Think of it like this:

The Old Way: Imagine trying to hide a secret by throwing a dart blindfolded anywhere on a giant wall. You might hide the secret, but you might also throw the dart so far off that it hits a completely different room. The data becomes useless.
The DPRS Way: Instead of throwing the dart anywhere, they build a small, private bubble around your real location.
1. Private Bubble Construction: First, they group people into neighborhoods and create a "safe zone" (a bubble) for each group.
2. The Rejection Sampling: When they need to hide your location, they pick a random spot inside that bubble.
3. The "Nope" Filter: If the random spot they picked is too far from your real location (which would ruin the "closest people" list), they say "Nope!" and pick a new spot inside the bubble. They keep doing this until they find a spot that is close enough to be useful but far enough to be safe.

Why This Matters

The researchers tested their new "Fuzzy Bubble" method against the old ways of hiding location data.

Better Privacy: It stops the "Homing Pigeon" attack almost completely. The attackers' success rate dropped from 95% down to less than 3%.
Better Utility: Because the fake location is kept inside a carefully calculated bubble, the "Top 5 closest people" list remains accurate. The app still works well for real users.

The Bottom Line

The paper proves that "nearby" lists are a privacy leak waiting to happen. But, by using a smart "Fuzzy Bubble" technique that carefully controls how much we distort your location, we can keep the app useful for everyone while making it impossible for attackers to find you.

Technical Summary: Protecting K-Nearest Neighbor Queries from Location Inference Attacks

1. Problem Statement

The paper addresses a critical, previously overlooked privacy vulnerability in Location-Based Services (LBS) that utilize k-Nearest Neighbor Queries (kNNQ). While LBS features like "people nearby" (e.g., in social apps such as Tinder) typically return a ranked list of users rather than exact coordinates, the authors argue that this ranking itself acts as a potent side-channel.

Existing location inference attacks (LIAs) generally rely on access to obfuscated coordinates or trajectory data. However, this work investigates a stricter threat model where an adversary, acting as a legitimate user, can only access the anonymous, ranked list of the $k$ nearest neighbors returned by the API. The core problem is that by adaptively querying from different locations (potentially with colluding users), an attacker can infer the precise geographic coordinates of a target user, despite the server claiming to hide exact distances and locations.

2. Methodology

The paper proposes a two-pronged methodology: first, demonstrating the severity of the threat through novel attacks, and second, introducing a defense mechanism based on Differential Privacy (DP).

A. Attack Methods

The authors design and evaluate two location inference attacks against kNNQ services:

Geometric Intersection Location Inference Attack (GI-LIA):
- Mechanism: This baseline attack uses geometric triangulation. An attacker identifies a circle centered at a probe location where a colluder appears at rank $k$ in the query results. Since the target also appears at rank $k$ , the target must lie on the circumference of this circle. By repeating this process with a second probe location, the attacker generates a second circle. The intersection of these two circles yields two candidate locations, which are verified to pinpoint the target.
- Limitation: While highly accurate, GI-LIA incurs significant communication overhead due to the binary searches required to find circle radii and locate the second probe point.
Zero-order Optimization Location Inference Attack (ZO-LIA):
- Mechanism: To improve efficiency, ZO-LIA avoids constructing a second geometric constraint. Instead, it performs a rank-guided local search within the feasible region defined by the first constraint circle.
- Process:
  1. Radius Search: Establishes the initial constraint circle $C(A_1, R_1)$ as in GI-LIA.
  2. Probe Generation: Samples probe points around the circle center and records the target's rank at each.
  3. Rank Optimization: Uses zeroth-order optimization to estimate a pseudo-gradient based on rank feedback, iteratively moving the probe toward a point that minimizes the target's rank.
  4. Constrained Projection: Projects the optimized internal point orthogonally onto the circle boundary to estimate the final location.
- Advantage: ZO-LIA achieves high success rates with roughly half the communication overhead (query count and time) of GI-LIA.

B. Defense Mechanism: DPRS

To mitigate these risks, the authors propose DPRS (Differential Privacy framework for kNNQ protection). DPRS aims to perturb user locations while preserving the utility of the kNNQ ranking.

Core Components:
1. Private Interval Construction (PIC): Instead of perturbing individual points directly (which causes excessive distance distortion), DPRS first clusters the dataset using a differentially private k-means algorithm. It constructs a "private interval" (a Euclidean ball) for each cluster, defined by a private centroid and a private radius. The radius is determined by the distance to the nearest neighboring centroid, avoiding the need for additional privacy budget.
2. Rejection Sampling Mechanism (RSM): This module perturbs original data points into the constructed private intervals. It employs a rejection sampling strategy where candidate locations are drawn from a noise distribution (e.g., Laplace) and accepted only if they fall within the specific interval and satisfy a probability threshold. This ensures the perturbed data follows the target distribution while strictly adhering to the interval constraints, thereby limiting distance distortion.
Privacy Guarantee: The framework utilizes Rényi Differential Privacy (RDP) to analyze the privacy loss of both the PIC and RSM modules, providing a rigorous $(\epsilon, \delta)$ -DP guarantee for the overall system.

3. Key Contributions

The paper claims the following primary contributions:

First Attacks on kNNQ: It presents the first systematic study of location inference attacks specifically targeting kNNQ services, introducing GI-LIA and ZO-LIA.
Defense Framework (DPRS): It proposes DPRS, a privacy-preserving framework that achieves a superior privacy-utility trade-off by combining constrained perturbation intervals with rejection sampling.
Theoretical Analysis: It establishes an RDP-based privacy guarantee for the rejection sampling mechanism and derives utility bounds for the default interval.
Empirical Validation: Extensive experiments on real-world (Brightkite, Gowalla) and synthetic datasets demonstrate the effectiveness of the proposed methods.

4. Experimental Results

The authors evaluated DPRS against three state-of-the-art baselines (L-SRR, Square, and Laplace mechanisms) across four datasets.

Attack Effectiveness: Both GI-LIA and ZO-LIA proved highly effective. ZO-LIA achieved attack success rates (Acc) above 90% (e.g., 0.948 on Brightkite with $k=10$ ) with average distance errors under 40 meters, while GI-LIA reached success rates up to 99.6%.
Defense Performance:
- Privacy Protection: Under a low privacy budget ( $\epsilon = 0.5$ ), DPRS reduced the success rates of both attacks to below 3% (e.g., Acc = 0.012 on Brightkite), significantly outperforming baselines.
- Query Utility: DPRS consistently outperformed existing methods in query utility metrics (Recall and Ratio). For instance, on the Brightkite dataset with $\epsilon=1$ , DPRS improved Recall from 0.423 (SRR) to 0.464 and Ratio from 0.832 to 0.881.
- Trade-off: The results indicate that DPRS successfully mitigates privacy leakage without the severe utility degradation seen in other DP-kNNQ methods.

5. Significance and Claims

The paper positions its work as a necessary response to a "severe privacy risk" inherent in widely used LBS features. The authors claim that current kNNQ services are vulnerable even when exact coordinates are hidden, as the ranking information alone is sufficient for precise location inference.

The significance of DPRS lies in its ability to decouple privacy protection from utility loss. By constraining perturbations within a carefully constructed interval and using rejection sampling, the framework prevents the "excessive noise injection" that typically renders kNNQ data useless for aggregation or ranking. The authors conclude that DPRS offers a robust, scalable defense that is practical for real-world deployment, as evidenced by its low online overhead (under 40ms) and superior performance across diverse datasets.