Protecting K-Nearest Neighbor Queries from Location Inference Attacks

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

Protecting K-Nearest Neighbor Queries from Location Inference Attacks Zhiyu Sun1∗ , Jie Fu2∗ , Xinpeng Ling3 , Huifa Li4 , and Zhili Chen1 (

)

East China Normal University, China [email protected] 2 Stevens Institute of Technology, USA 3 Tongji University, China 4 Mohamed bin Zayed University of Artificial Intelligence, UAE

arXiv:2606.05648v1 [cs.CR] 4 Jun 2026

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 tradeoff 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. Keywords: K-nearest neighbor query · Location inference attack · Differential privacy

Introduction

Location-Based Services (LBS) have become a fundamental component of modern mobile applications [14,15,16], but they also introduce significant privacy risks. Prior work has demonstrated that attackers can infer users’ true locations from obfuscated location information. Existing location inference attacks (LIAs) typically exploit distance information [6], spatial regions [23], or user trajectories [21,19] to recover sensitive location data. ∗

Both authors contributed equally to this work.

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

)

However, location privacy threats in k -nearest neighbor query (kNNQ) services (e.g., “nearby people” features) have been largely overlooked. To the best of our knowledge, location inference attacks specifically targeting kNNQ services have not been systematically studied. In such systems, attackers may exploit the ranked neighbor list returned by the API to infer the precise location of a target user. Given the widespread use of kNNQ in social and recommendation applications (such as Tinder [6]), this work systematically investigates location privacy risks in kNNQ services and proposes an effective defense mechanism to mitigate such threats. Attack design and evaluation. We propose two location inference attacks against kNNQ services: the Geometric Intersection-based LIA (GI-LIA) and the Zero-order Optimization-based LIA (ZO-LIA). GI-LIA leverages distance relationships between the attacker at multiple query locations and the target, and solves the target’s coordinates using geometric intersection. In contrast, ZOLIA estimates a pseudo-gradient from the target’s ranking information in query results and iteratively approximates the target’s true location. Experimental results demonstrate that both attacks are highly effective, achieving inference success rates above 95%. These findings indicate that current kNNQ services face severe privacy risks even when users’ exact coordinates are not explicitly disclosed. Design of defense method. To mitigate location privacy risks in kNNQ, we propose DPRS, a privacy-preserving perturbation framework. DPRS perturbs original location data within a carefully constructed privacy region, thereby reducing distance distortion among nearest neighbors. To achieve this goal, we design a rejection-sampling-based location perturbation mechanism that repeatedly proposes and tests candidate locations within a specified interval to ensure the resulting samples follow the target distribution. This mechanism also constrains perturbed samples within the interval, preventing excessive deviation. Applying rejection sampling to DP-kNNQ poses two key challenges: guaranteeing differential privacy under the altered noise distribution and selecting an appropriate perturbation interval to preserve query utility. To address them, we characterize the post-rejection noise using Rényi divergence and design a private interval construction algorithm that adaptively determines the perturbation interval. Evaluation. We conduct extensive experiments on two real-world datasets and two synthetic datasets to evaluate the performance of DPRS. The results show that DPRS effectively protects location privacy and significantly reduces privacy leakage. In particular, under a low privacy budget, DPRS reduces the success rates of both GI-LIA and ZO-LIA attacks to below 3%, demonstrating the robustness of the proposed defense. Moreover, under the same privacy budget, DPRS consistently outperforms three state-of-the-art location differential privacy methods [1,7,18] across multiple utility metrics. The main contributions of this paper are summarized as follows: – We present the first location inference attacks against kNNQ services, exposing serious privacy risks in existing kNN-based location services.

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

– We propose DPRS, a privacy-preserving framework for kNNQ that achieves a better privacy–utility trade-off through constrained perturbation. – We establish an RDP-based privacy guarantee for the rejection sampling mechanism and derive its utility bound under the default interval. – Experiments on two real-world and two synthetic datasets show that DPRS consistently outperforms existing methods in both privacy protection and query utility.

Background and Related Work

Existing location inference attacks (LIAs) deduce true locations from obfuscated data using probabilistic models and contextual information [1,21,19,3], but fundamentally rely on access to coordinate data or trajectory. This work explores a more stringent scenario: the LBS only returns an anonymous, ranked list of k-nearest neighbors (kNN) [13]. This operation, known as a k-nearest neighbor query (kNNQ), is a fundamental block in numerous modern applications and is defined as follows: Definition 1. (K-nearest neighbor query [13]) For a query object q ∈ O and a query parameter k, the k-nearest neighbor query returns the smallest set N Nq (k) ⊆ D that contains (at least) k objects from the database, satisfying: N Nq (k) = {o ∈ D | d(o, q) ≤ d(ok , q)},

(1)

where ok is the k-th closest object to q in the database D. Although kNNQ seemingly protects privacy by concealing coordinates, its ranked list forms a potent side-channel highly susceptible to location inference. Differential privacy (DP) [5] is currently the gold standard for geolocation protection. Definition 2. (Differential Privacy [5]). The algorithm A provides (ϵ, δ)Differential Privacy, if for any two neighboring datasets D and D′ that differ in only a single entry, ∀S ⊆ Range(A), the following holds: Pr(A(D) ∈ S) ≤ eϵ × Pr(A(D′ ) ∈ S) + δ.

(2)

DP, foundationalized by geo-indistinguishability [1], is widely applied in LBS [20,12]. However, existing DP-kNNQ methods suffer from severe flaws: L-SRR [18] can only perform kNNQ by perturbing users to a finite, predefined set of points of interest (POIs). This approach severely distorts the data’s underlying spatial distribution, rendering the dataset unusable for other aggregation analyses. Meanwhile, other methods, such as ReuseKNN [11], provide uneven protection; they only apply perturbation to a small subset of users deemed vulnerable, leaving the broader user population with weaker privacy guarantees. Schemes like FedKNN [22], on the other hand, only perturb each participant’s contribution weight, rendering their security entirely dependent on hardware isolation and

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen ( Coordinate

Locations

Other Users Colluder

Target User

)

Adversary

Attack k-NN Training LBS Platform

Fig. 1: Threat model

creating a catastrophic “all-or-nothing” privacy risk. To overcome these limitations, we propose the DPRS mechanism. In this paper, we use a more powerful privacy framework: Rényi Differential Privacy (RDP) [10] for privacy loss analysis. Definition 3. (Rényi Divergence [17]) Given two probability distributions P and Q, the Rényi divergence of order α > 1 is: α 1 P (x) Dα (P ∥Q) = ln Ex∼Q , (3) α−1 Q(x) where P (x), Q(x) denotes the probability density of P , Q.

Problem Setup

We consider a location-based service (LBS) platform that maintains a set of users U = {u1 , u2 , ..., uN }, where each user ui is associated with a 2D geographic coordinate Li = (xi , yi ). The LBS server supports the kNNQ interface that allows a user to submit a query location Lq and obtain a ranked list of the k nearest users based on their distances to Lq . Formally, given a query location Lq , the server returns an ordered list: kNNQ(Lq ) = [u(1) , u(2) , ..., u(k) ].

(4)

To protect user privacy, the server does not reveal the exact distance values or the precise locations of users. Instead, it only returns the ranked order of users. 3.1

Threat Model

We consider the adversary who is a legitimate registered user of the LBS platform and has normal access to the kNNQ API. The adversary cannot compromise the server or access its internal data structures, and can only interact with the system through API queries. The adversary possesses the following capabilities:

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

– API Access. The adversary can repeatedly issue kNN queries from arbitrary locations and observe the returned ranked list of anonymized user IDs. – Collusion. The adversary can collaborate with one or more colluding users whose precise locations are known to the adversary. These colluders act as mobile probes that can move to different locations and report their exact coordinates. – Adaptive Queries. The adversary can adaptively change the probe locations and repeatedly query the API to observe how the ranking of the target user changes with respect to other users. Figure 1 illustrates the threat model. Although the server does not reveal distance values, the ranking output implicitly encodes relative distance information. In particular, when a probe moves to a location where the rank of the target user changes relative to another user, this event indicates that the probe lies on a boundary where the distances to the two users become equal. Practicality of the Attack. This attack scenario naturally arises in many realworld location-based services. To protect user privacy, many LBS platforms avoid revealing exact locations or distances and instead return a ranked list of nearby users. For example, social applications such as Tinder [6] provide “nearby users” functionality that displays profiles ordered by proximity while hiding precise coordinates or distance values. Since such services are accessible through mobile interfaces or public APIs, an adversary can repeatedly issue queries from different locations—either by moving their own device or collaborating with colluding users, and observe how the target user’s rank changes. These observations enable the adversary to gradually infer the target user’s location. 3.2

Attack Formulation

Let the true location of the target user be Lt = (xt , yt ). The adversary interacts with the LBS server by issuing a sequence of kNN queries from different probe locations. Let Q = {q1 , q2 , ..., qn } denotes the set of query results obtained from the server, where each query result qi corresponds to the ranked list returned by the kNNQ interface at probe location Li . Meanwhile, the adversary also maintains a set of colluding probe locations C = {c1 , c2 , ..., cl }, where each cj represents the exact coordinate of a colluder used in the probing process. Through adaptive probing, the adversary observes the positions where the ranking of the target user changes relative to other users. Based on the collected query results and probe locations, the adversary aims to design a location inference algorithm.

A : (Q, C) → Linf , which outputs an estimated location of the target user: Linf = (xinf , yinf ).

(5)

3.3

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

)

Measurement of the Attack

To quantitatively evaluate the effectiveness and efficiency of the proposed attack, we adopt three metrics. Error Distance (Dist). We measure the average inference error between the estimated location and the true location of the target user. Given a set of N attack instances, the average error distance is defined as below: N

Dist =

1 X (i) (i) d Linf , Lt , N i=1 (i)

(6) (i)

where d(·) denotes the Euclidean distance, Linf is the inferred location, and Lt is the true location of the i-th target user. Attack Success Rate (Acc). We define a successful attack as one where the inferred location lies within a predefined distance threshold τ from the true location. The attack success rate is defined as follows: Acc =

N 1 X (i) (i) 1 d(Linf , Lt ) ≤ τ , N i=1

(7)

where 1[·] is the indicator function. In our experimental evaluation, we set τ = 100 meters by default, following the commonly adopted evaluation standard in location privacy research [1]. Attack Cost (Cost). To measure the efficiency of the attack, we compute the average time required to complete an attack instance: N

Cost =

1 X Ti , N i=1

(8)

where Ti denotes the time (seconds) to infer the location of the i-th target user. Among these metrics, Dist and Acc reflect the attack effectiveness, while Cost measures the attack efficiency.

Our Attack Methods

In this section, we present two attack methods against KNNQ. We first introduce a geometry-based attack and analyze its inherent limitations in terms of communication overhead. We then propose a more communication-efficient attack framework that leverages zeroth-order optimization to achieve a better trade-off between attack effectiveness and efficiency. 4.1

A Straw-man Approach: GI-LIA

The first approach to location inference is based on geometric triangulation. We refer to this baseline method as the Geometric Intersection Location Inference

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

Attack (GI-LIA). The key idea is to infer the target’s location by determining the intersection points of two circular trajectories on which the target must reside. First, the attacker establishes an initial circular trajectory centered at an attack point A1 . Specifically, the attacker determines the radius R1 of the circle C(A1 , R1 ) through a binary search procedure assisted by a collaborator. The collaborator moves radially with respect to A1 , while the attacker repeatedly issues kNNQ queries. By adjusting the collaborator’s distance from A1 , the attacker identifies a distance R1 at which the collaborator’s rank in the query result becomes exactly k. Since the target also appears at rank k, the target must lie on the circumference of C(A1 , R1 ). Next, the attacker selects a second attack point A2 to obtain another geometric constraint. The attacker performs a search over candidate locations for A2 , ensuring that (i) A2 is sufficiently distant from A1 to provide geometric stability and (ii) the target remains within the kNNQ result set. Once such a point is found, the attacker repeats the binary search procedure to determine the second circular trajectory C(A2 , R2 ). The intersection of the two circles C(A1 , R1 ) and C(A2 , R2 ) yields two candidate locations {P1 , P2 }. The attacker then issues verification queries at these candidate points and selects the location that yields the lower rank for the target as the inferred target position. The total communication overhead of GI-LIA can be expressed as: R2 1 CostGI−LIA = CostR binary + Costsearch (A2 ) + Costbinary + 2,

(9)

where Costbinary denotes the query cost of a single binary search used to determine a circle radius, and Costsearch (A2 ) represents the cost of locating the second attack point A2 . The final term accounts for the two verification queries at candidate locations P1 and P2 . Because both the binary search procedures and the search for A2 require numerous queries, GI-LIA incurs substantial communication overhead, making it inefficient and impractical for real-time or stealthy attacks. 4.2

Improvement: ZO-LIA

To reduce the excessive communication overhead of GI-LIA, we propose an efficient zeroth-order optimization location inference attack (ZO-LIA). Unlike the GI-LIA, 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 and then projects the result onto the circle boundary. The overall process is illustrated in Figure 2. Phase ①: Radius Search. ZO-LIA first determines the initial constraint circle C(A1 , R1 ) using the same radius search procedure described in GI-LIA. By performing a binary search with the help of a collaborator, the attacker finds a distance R1 such that the collaborator appears at rank k in the kNNQ results. Since the target also appears at rank k, the target must lie on the circumference of C(A1 , R1 ). Phase ②: Probe Generation and Evaluation. Instead of constructing a second circle, ZO-LIA generates a set of probe points around the circle center A1 .

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (  Radius Search

 Constrained Projection

r Rank( ) = K

Final Estimation

)

 Rank Optimization

𝑬𝒕 = 𝑬𝒕−𝟏 − 𝜼 ⋅ 𝒈𝒕

Rank( ) ≈ Rank( ) K-5

 Probe Generation and Evaluation K+1

K-5

K K-2

𝒔𝒊 = −𝑹𝒂𝒏𝒌𝒊 ( ) 𝒎

K-2 K+1

𝒈𝒕 = − ෍ 𝒔𝒐𝒇𝒕𝒎𝒂𝒙 𝒔𝒊 ⋅ 𝒗𝒊 𝒊

Fig. 2: The framework of ZO-LIA

These probes are sampled along multiple directions in the local neighborhood. For each probe point, the attacker issues a kNNQ query and records the target’s rank. The rank serves as a score indicating how promising the corresponding direction is for approaching the target. Phase ③: Rank Optimization. This phase constitutes the core of ZO-LIA. We employ a zeroth-order optimization strategy that relies solely on rank feedback. Using the rank scores obtained from the probe evaluations, the attacker estimates a pseudo-gradient that approximates the direction in which the target’s rank decreases most rapidly. The attacker’s position is then iteratively updated along this estimated direction, gradually moving toward an internal point Popt that minimizes the observed rank of the target. Phase ④: Constrained Projection. Once the search converges to the internal point Popt , a final constrained projection step is applied. Because the target must lie on the circumference of C(A1 , R1 ), the attacker orthogonally projects Popt onto the circle boundary. This projection is a simple local computation with constant complexity and produces the final estimate of the target’s location. The total communication overhead of ZO-LIA is given by CostZO−LIA = Costbinary + Niter · Cost0−iter ,

(10)

where Costbinary denotes the query cost of the initial radius search, Niter is the number of optimization iterations, and Cost0−iter represents the number of probe queries per iteration. 4.3

Attack performance in real-world scenarios

We evaluate our attacks on two real-world and two synthetic datasets. The evaluation metrics include Dist, Acc, and Cost (see §3.3). We consider k = 10, k = 30,

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

Table 1: The performance of ZO-LIA and GI-LIA methods across four datasets. Method Dataset

k=10

k=30

k=50

Dist Acc Cost Dist Acc Cost Dist Acc Cost brightkite 28.91 0.948 15.94 40.59 0.914 17.62 41.98 0.912 19.21 gowalla 39.20 0.960 16.05 56.03 0.906 17.86 56.83 0.926 18.92 ZO-LIA gaussian 24.35 0.956 22.14 42.17 0.910 23.21 43.56 0.893 24.08 beta 40.39 0.944 22.17 43.96 0.896 23.09 48.51 0.873 23.96 brightkite 26.93 0.972 31.86 32.67 0.984 33.07 25.74 0.996 35.12 gowalla 20.59 0.996 31.42 24.55 0.992 34.67 23.56 0.992 35.98 GI-LIA gaussian 26.31 0.940 44.42 18.34 0.968 45.97 29.98 0.964 48.13 beta 39.96 0.948 43.21 41.67 0.948 45.07 51.84 0.976 47.31

and k = 50. For each k, we perform 5 independent runs with 50 attack instances per run, and report the average results. The results are shown in Table 1. Other attack setups are provided in Appendix A.1. Attack effectiveness. The results demonstrate that both attacks achieve consistently high effectiveness across all datasets. In particular, both GI-LIA and ZO-LIA maintain success rates above 90% under most settings, indicating that kNNQ-based LBS systems are highly vulnerable to location inference attacks. Among the two methods, GI-LIA achieves the best attack performance. It consistently yields the lowest average distance error and the highest success rates across datasets and k-values. For example, on the Brightkite dataset with k = 10, GI-LIA achieves a success rate of 0.972 with an average distance error of only 26.93 meters. These results confirm that the geometric intersection strategy can accurately recover the target’s location. Attack efficiency. Although GI-LIA achieves the highest attack accuracy, it incurs significantly higher communication overhead. In contrast, ZO-LIA substantially reduces the attack cost while maintaining high success rates. As shown in Table 1, ZO-LIA consistently requires roughly half the execution time of GILIA across all datasets and k-values. For instance, on the Brightkite dataset with k = 30, the time overhead of ZO-LIA is 17.62 seconds, compared to 33.07 seconds for GI-LIA. This reduction implies fewer queries are needed, making ZO-LIA faster, stealthier, and more practical for real-world attacks.

Proposed Defense Method: DPRS

To protect location privacy under kNN queries, we propose the DPRS mechanism. DPRS perturbs the geographic locations in the dataset to produce a new location dataset that strictly satisfies differential privacy guarantees. As illustrated in Figure 3 and Algorithm 3, DPRS consists of two main components: (i) Private Interval Construction (PIC): Establishes a private, data-aware interval for the perturbation. (ii) Reject Sampling Mechanism (RSM): The

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

)

Algorithm 1: Private Interval Construction (PIC) Input: dataset D, sensitivity 2r + 1, number of clusters m, number of iterations Nc , noise parameter of Lap distribution λc , radius scaling γ. Output: m private centroids. 1 Initialize k centroids by initial centroid selection. 2 for iter ← − 1 to Nc do 3 Get m clusters through the standard k-means. 4 Recalculate the centroid of each cluster. 5 for j ← − 1 to m do 6 for i ← − 1 to d do 7 sum′ (Cj∗ )[i] = sum(Cj∗ )[i] + Lap(0, λc ). 8 num′ (Cj∗ ) = num(Cj∗ ) + Lap(0, λc ). 9

sum′ (C ∗ )

cj = num′ (Cj∗ ) . j

for j ← − 1 to m do 11 Find the nearest centroid cmin from all centroids excluding cj . 12 Rj = γ · distance(cj , cmin ). 13 Ij = (cj , Rj ). 14 return m private intervals {I1 , I2 , . . . , Im }. 10

core engine that efficiently perturbs data into the private interval constructed by the previous module. Private-Interval-Construction

Reject-Sampling-Mechanism

DP AVG

Original data

Private interval

Reject sampling

Private data

Fig. 3: Overall framework of DPRS

5.1

Private Interval Construction

The privacy interval is designed as a Euclidean ball, consisting of two components: a private center and a private radius. Ideally, to avoid introducing excessive noise offset, the private center should be as close as possible to the original sample. However, directly perturbing the original sample to serve as the interval center would introduce significant distance errors. To address this issue, the DPk-means algorithm is introduced to obtain more stable and differentially private centers by injecting noise during the aggregation stage. In addition, the private radius is determined by the distance between the two nearest private centers, thereby eliminating the need for additional privacy budget.

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

Algorithm 2: Rejection Sampling Mechanism (RSM) Input : data x, norm n, interval I (center xc , radius R), sensitivity 2r, Lap distribution p(·|x, λp ), target function f (·) ∝ p(·|x, λp ). Output: perturbed data x′ . 1 if ∥x − xc ∥k ≤ R then 2 M ← 1. 3 else 4 B ← GetBoundary(xc , R). 5 z∗ ← minz∈B ∥z − x∥n . 6 M ← f (z∗ ). 7 while true do 8 u, u1 , u2 ← RandomUniform(0, 1). √ 9 R ← R u1 , θ ← 2πu2 . ′ 10 x ← xc + (R cos(θ), R sin(θ)). ′

11 12

) if u < f (x then M return x′ .

As shown in Algorithm 1, PIC is implemented as follows. In each iteration, after samples are assigned to their clusters, the sensitive centroid recomputation step is protected. Specifically, the coordinate sums and the member counts of each cluster are concatenated, and calibrated Laplace noise is injected. The combined operation has a total L1 sensitivity of 2r + 1. The private radius of each centroid is then set to half of the distance to its nearest neighboring centroid, which naturally defines the corresponding privacy interval. 5.2

Reject Sampling Mechanism

The rejection sampling mechanism efficiently perturbs private data into the privacy interval constructed by the PIC module. We begin by specifying a base noise distribution, typically p(·) = Lap(· | x, λ). By normalizing the 2D location data to the range [−r, r], the L1 sensitivity is bounded by 2r, which enables calibrated noise injection. To perturb data within the specified Euclidean sphere, we define f (·) ∝ p(·), thereby avoiding the computation of the normalization constant. Rejection sampling is then used to generate valid perturbed samples. This procedure requires an upper bound M of f (·) within the sphere in order to compute the acceptance probability. As shown in Algorithm 2 (Lines 1–6), a tight bound M is obtained under either the L1 norm (Laplace mechanism) or the L2 norm (Gaussian mechanism) by evaluating a set of candidate points on the boundary of the sphere via GetBoundary(xc , R) (Line 4). Furthermore, we also extend RSM to the Gaussian distribution in Appendix B. Given these components, the mechanism iteratively performs rejection sampling until a valid sample is accepted. Specifically, a candidate point x′ is first drawn uniformly from the sphere. The acceptance ratio f (x′ )/M is then computed, followed by drawing a random variable u ∼ U (0, 1). The candidate is

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

)

Algorithm 3: Overall algorithm of DPRS Input : dataset D, cluster number m, iteration Nc , noise parameter λp , λc . Output: perturbed dataset D′ . 1 {I1 , I2 , . . . , Ik } ← PIC(D, m, Nc , λc ). 2 Partition D into m clusters {C1 , C2 , . . . , Cm }. ′ 3 D ← ∅. 4 for j ← 1 to m do 5 for x ∈ Cj do 6 x′ ← RSM(x, Ij , λp ). 7 D′ ← D′ ∪ {x′ }. ′ 8 return D .

accepted if u ≤ f (x′ )/M ; otherwise, the sample is rejected and the process repeats. Additionally, Theorem 7 and Theorem 8 in the Appendix C.2 guarantee the distributional correctness of the rejection sampling mechanism and provide an upper bound on utility.

Privacy Analysis

We first analyze the privacy of the PIC (Algorithm 1) and RSM modules (Algorithm 2), then present the total privacy budget of DPRS (Algorithm 3). 6.1

Privacy Analysis of DPRS Components

ϵc Theorem 1. Algorithm 1 satisfies (α, α−1 )-RDP, where

ϵc =3Nc log

α exp 2α − 1

α−1 λc

α−1 exp + 2α − 1

−α λc

(11)

Proof. Let D be a dataset partitioned into k disjoint clusters, C1 , . . . , Ck . A neighboring dataset D′ is formed by removing a single point, such that D′ = D \ {x} for some x ∈ D, and the partition on D′ is composed of clusters C1′ , . . . , Ck′ . There exists an index J such that CJ′ = CJ \ {x} and Cj′ = Cj elsewhere. Therefore, each iteration can be regarded as the parallel composition of mechanisms querying function f (·) over k disjoint clusters, and differential privacy achievement is determined by the mechanism over cluster CJ (since mechanisms ′ ′ over other clusters Cj achieve 0-differential privacy for Cj = Cj ). Let p(·) and p′ (·) denote the probability density functions of the mechanism over cluster CJ . For any point v ∈ D2×N , its RDP characterization is formed by the composition of three single-dimension Laplace mechanisms, each with a sensitivity of 1, iterated Nc times. The first two mechanisms correspond to the position dimensions, and the last one corresponds to the counting dimension. According to Lemma 1 (§6.2), its privacy characterization is as follows:

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

3Nc Dα (p(v)||p (v)) = log α−1 ′

α exp 2α − 1

α−1 λ

α α−1 . + exp − 2α − 1 λ (12)

Therefore, Theorem 1 is proved. ϵ

p Theorem 2. Algorithm 2 satisfies (α, α−1 )-RDP, where

ϵp =2 log

α exp 2α − 1

α−1 λp

α−1 exp 2α − 1

−α λp

(13)

Proof. let Dα (S) be RDP of Algrithm 2, according to Lemma 5 (Appendix C.2) we have: Dα (S) ≤ Dα (Lap(t|0, λ)||Lap(t|µ, λ)).

(14)

In fact, the Rényi divergence of the multidimensional Laplace distribution has no analytical expression. Therefore, we characterize the Rényi differential privacy of the multidimensional Laplace distribution as a combination of different dimensions. According to Lemma 1 (§6.2), we have: Dα (Lap(t|0, λ)||Lap(t|µ, λ)) = 2Dα (Λ(0, λ)||Λ(µ, λ)).

(15)

Therefore, we have: Dα (S) α 1−α Z ∞ 2 1 − |x−µ| 1 − |x| log e λ e λ dx α−1 2λ 2λ −∞ Z ∞ 1 α|x − µ| − (α − 1)|x| 2 log exp − dx = α−1 2λ −∞ λ !! Z 0 Z µ Z ∞ αµ−(2α−1)x x−αµ 2 1 − αµ−x − − λ = log e λ dx + e dx + e λ dx α−1 2λ −∞ 0 µ ! (a−1)µ 2 1 1 1 1 − aµ = log − e λ + + e λ α−1 2 2(2α − 1) 2 2(2α − 1) ! αµ 2 α (α − 1)µ α−1 = log exp + exp − . α−1 2α − 1 λ 2α − 1 λ ≤

(16) For single-dimension Laplace noise, it is normalized to the range of [−1, 1], so we set µ = 1. Therefore, Theorem 2 is proved.

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

)

Table 2: Statistics of the datasets

6.2

Type

Dataset

Locations Density Dispersion Index

Real-World

Brightkite [4] Gowalla [4]

18,409 17,738

11.76 11.33

0.26% 0.32%

Synthetic

Gaussian [8] Beta [9]

25,000 25,000

15.97 15.97

0.61% 0.70%

Overall Privacy Analysis of DPRS

To derive the total privacy loss, we compose the guarantees from Theorem 1 and 2. This relies on two standard lemmas from the RDP literature: Lemma 1. (Composition Theorem [10]). Let two queries f , g be (α, R1 ) and (α, R2 )-RDP respectively. Then their composition (f, g) is (α, R1 + R2 )-RDP. Lemma 2. (Conversion Theorem [2]). If f is an (α, R)-RDP query ,then it satisfies(R + ln((α − 1)/α) − (ln δ + ln α)/(α − 1), δ)-DP for any 0 < δ < 1. By applying Lemma 1 to the results of Theorem 1, 2, and then applying Lemma 2, we arrive at the final privacy guarantee for the DPRS framework: Theorem 3. Algorithm 3 satisfies (ϵT otal , δ)-DP, where ϵT otal =

ϵc + ϵ p α−1 log(δ) + log(α) + log( )− . α−1 α α−1

(17)

Evaluation

In this section, we mainly examine the trade-off between defense effectiveness and KNNQ utility achieved by DPRS and the baselines in the KNNQ task, and further analyze the impact of key parameters on DPRS. There are additional experiment results that can be found in Appendix D. 7.1

Setup

We evaluate DPRS and three baselines (SRR [18], Square [7] and Laplace [1]) on four datasets under various k-NN settings. There are two real-world datasets (Brighktite [4] and Gowalla [4]) and two synthetic datasets (Gaussian [8] and Beta [9]). We restrict the real-world datasets to the San Francisco region, with latitude in [37.5, 37.9] and longitude in [−122.6, −122.2]. The synthetic datasets are generated from Gaussian N (0, 1) and Beta B(2, 5) distributions. Dataset details are shown in Table 2. Detailed descriptions of evaluation metrics, baselines, and parameter settings are provided in Appendix A.2.

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

Table 3: Performance comparison of different defense mechanisms in the 10-NN task. Recall and Ratio measure query utility, where higher values indicate better query performance. Acc and Dist characterize the attack performance of ZO-LIA, where lower Acc and higher Dist indicate stronger defense effectiveness. Dataset

Metric

ϵ = 0.5

ϵ=1

ϵ=3

ϵ=5

DPRS SRR Square Laplace DPRS SRR Square Laplace DPRS SRR Square Laplace DPRS SRR Square Laplace Brightkite

Gowalla

Gaussian

Beta

7.2

Recall(↑) 0.434 0.382 Ratio (↑) 0.852 0.814

0.389 0.811

0.353 0.745

0.464 0.423 0.881 0.832

0.414 0.823

0.398 0.766

0.472 0.436 0.885 0.851

0.440 0.844

0.416 0.699

0.489 0.447 0.889 0.861

0.448 0.856

0.423 0.782

Acc (↓) Dist (↑)

0.012 0.016 0.591 0.573

0.018 0.565

0.012 0.594

0.014 0.020 0.583 0.562

0.018 0.553

0.016 0.553

0.020 0.024 0.018 0.525 0.516 0.533

0.022 0.519

0.022 0.028 0.524 0.473

0.024 0.511

0.026 0.515

Recall(↑) 0.443 0.357 Ratio (↑) 0.827 0.773

0.382 0.779

0.331 0.705

0.461 0.430 0.872 0.830

0.418 0.815

0.393 0.737

0.471 0.453 0.879 0.844

0.442 0.840

0.417 0.749

0.482 0.459 0.886 0.853

0.454 0.848

0.446 0.797

Acc (↓) Dist (↑)

0.022 0.012 0.553 0.587

0.024 0.544

0.018 0.572

0.016 0.022 0.530 0.481

0.022 0.499

0.018 0.517

0.020 0.022 0.517 0.486

0.022 0.476

0.020 0.497

0.020 0.024 0.016 0.412 0.409 0.476

0.018 0.446

Recall(↑) 0.644 0.612 Ratio (↑) 0.902 0.864

0.587 0.848

0.541 0.792

0.655 0.637 0.927 0.886

0.624 0.874

0.607 0.837

0.664 0.643 0.929 0.888

0.630 0.879

0.611 0.851

0.672 0.649 0.933 0.900

0.645 0.897

0.629 0.863

Acc (↓) Dist (↑)

0.008 0.014 0.605 0.587

0.018 0.579

0.012 0.591

0.020 0.016 0.547 0.566

0.022 0.527

0.020 0.533

0.014 0.016 0.543 0.512

0.018 0.504

0.018 0.499

0.018 0.022 0.459 0.423

0.020 0.441

0.016 0.494

Recall(↑) 0.563 0.531 Ratio (↑) 0.827 0.751

0.524 0.734

0.482 0.678

0.593 0.567 0.861 0.782

0.553 0.768

0.523 0.714

0.601 0.582 0.873 0.807

0.576 0.796

0.545 0.749

0.623 0.602 0.886 0.822

0.592 0.815

0.594 0.782

Acc (↓) Dist (↑)

0.014 0.608

0.018 0.597

0.020 0.564

0.022 0.576

0.014 0.599

0.022 0.024 0.020 0.512 0.494 0.529

0.024 0.481

0.016 0.020 0.574 0.517

0.024 0.483

0.016 0.564

0.012 0.022 0.616 0.586

0.020 0.553

Tradeoff between Query Utility and Defense Effect

Query utility. As shown in Table 3, DPRS consistently achieves the best query utility across all datasets and privacy budgets. It ranks first in both Recall and Ratio in all 16 settings. Averaged over all settings, DPRS attains a Recall of 0.546 and a Ratio of 0.882, outperforming SRR (0.513/0.835), Square (0.507/0.827), and Laplace (0.482/0.765). Compared with the strongest baseline in each setting, DPRS improves Recall and Ratio by 6.04% and 5.33% on average, respectively. For example, on Brightkite with ϵ = 1, DPRS improves Recall from 0.423 to 0.464 and Ratio from 0.832 to 0.881. On Beta with ϵ = 1, DPRS achieves a Ratio of 0.861, exceeding the best baseline by 0.08. Defense effect. DPRS also provides strong defense effectiveness against ZOLIA 1 . Averaged over all settings, it achieves the lowest attack success rate (Acc = 0.017) and the largest distance error (Dist = 0.541), compared with 0.020/0.520 for SRR, 0.020/0.525 for Square, and 0.018/0.536 for Laplace. In several cases, DPRS improves both utility and defense simultaneously. For instance, on Brightkite with ϵ = 1, DPRS reduces Acc from 0.02 to 0.014 and increases Dist from 0.562 to 0.583 compared with SRR. On Gaussian with ϵ = 3, DPRS achieves both the lowest Acc (0.014) and the highest Dist (0.543). Although DPRS is not always the best on every single attack metric, it remains highly competitive while preserving substantially better query utility. Summary. Overall, DPRS achieves the best trade-off between query utility and defense effect. It consistently dominates all baselines in Recall and Ratio, while also achieving the best average defense performance. These results verify that DPRS can effectively protect against location inference attacks without sacrificing kNNQ utility. 1

As shown in Section 4.3, ZO-LIA achieves the strongest attack performance and is therefore used as the attack baseline.

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

5HFDOO

DPRS

SRR

Square

(a) Brightkite

Laplace

(b) Gowalla

)

(d) Beta

5HFDOO

Fig. 4: Performance impact on the number of neighbors at ϵ = 3.

&HQWHUVQXPEHU

(a) Brightkite

&HQWHUVQXPEHU

(b) Gowalla

&HQWHUVQXPEHU

&HQWHUVQXPEHU (d) Beta

Fig. 5: Performance impact on the number of interval centers at k = 10.

7.3

Parameter Sensitivity Analysis

Impact of the Number of Neighbors. We simulated scenarios with k ranging from 10 to 50 on two real-world datasets. As shown in Figure 4, we observe that the query recall consistently increases as the number of neighbors (k) grows. Furthermore, our method consistently outperforms the 2D Laplace, SRR, and Square mechanisms. This further demonstrates that the DPRS framework can effectively preserve the relative distances between neighboring samples. Impact of the Number of Centers. Figure 5 illustrates the recall performance of our method as the number of interval centers increases from 600 to 1,000. We observe that the recall rate gradually rises with the number of perturbation centers. This is because more centers allow for a more detailed extraction of the dataset’s features, thus capturing neighbor information at a finer granularity. Impact of the Radius Scaling. The size of the private interval directly determines the utility of the perturbed data, necessitating a careful trade-off for the radius scaling coefficient: An overly large coefficient leads to more frequent overlaps between different clusters, whereas a too small one disrupts the rank differences among nearest neighbors. As shown in Figure 9 in Appendix D, setting the radius scaling coefficient to 0.5 is optimal. 7.4

Time Overhead Analysis

DPRS avoids online query bottlenecks by performing PIC offline and periodically updating private intervals on LBS platforms. Furthermore, as shown in Figure 8

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

in Appendix D, our RSM incurs only lightweight online overhead given a private interval, which remains below 40ms and is substantially faster than standard noise-and-resampling methods. This demonstrates the scalability of DPRS to large-scale datasets.

Conclusion

This work investigates the location privacy issues in kNNQ services. By proposing two attacks, GI-LIA and ZO-LIA, we reveal the privacy threats of kNNQ. To mitigate privacy risk, we propose DPRS, a differentially private framework tailored to high-sensitivity kNNQ. Both theoretical analysis and experimental results show that DPRS can effectively defend against LIA attacks while achieving better utility than state-of-the-art methods.

Acknowledgment This work is supported by National Natural Science Foundation of China Key Program (Grant No. 62132005), Fundamental Research Funds for the Central Universities (Grant No. 40500-20104-222609).

References 1. Andrés, M.E., Bordenabe, N.E., Chatzikokolakis, K., Palamidessi, C.: Geoindistinguishability: Differential privacy for location-based systems. In: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. pp. 901–914 (2013) 2. Balle, B., Barthe, G., Gaboardi, M., Hsu, J., Sato, T.: Hypothesis testing interpretations and renyi differential privacy. In: International Conference on Artificial Intelligence and Statistics. pp. 2496–2506. PMLR (2020) 3. Bitsikas, E., Schnitzler, T., Pöpper, C., Ranganathan, A.: Amplifying threats: The role of multi-sender coordination in sms-timing-based location inference attacks. In: Doupé, A., Milburn, A. (eds.) 18th USENIX WOOT Conference on Offensive Technologies, WOOT 2024, Philadelphia, PA, USA, August 12-13, 2024. pp. 59–73. USENIX Association (2024) 4. Cho, E., Myers, S.A., Leskovec, J.: Friendship and mobility: user movement in location-based social networks. In: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 1082–1090 (2011) 5. Dwork, C., Roth, A., et al.: The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science 9(3–4), 211–407 (2014) 6. Frizell, S.: Tinder security flaw exposed users’ locations. The TIME (February 2014) 7. Hong, D., Jung, W., Shim, K.: Collecting geospatial data under local differential privacy with improving frequency estimation. IEEE Transactions on Knowledge and Data Engineering 35(7), 6739–6751 (2022)

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

)

8. Huang, Z., Liang, Y., Yi, K.: Instance-optimal mean estimation under differential privacy. Advances in Neural Information Processing Systems 34, 25993–26004 (2021) 9. Li, Z., Wang, T., Lopuhaä-Zwakenberg, M., Li, N., Škoric, B.: Estimating numerical distributions under local differential privacy. In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. p. 621–635. SIGMOD ’20, Association for Computing Machinery, New York, NY, USA (2020) 10. Mironov, I.: Rényi differential privacy. IEEE Computer Security Foundations Symposium (2017) 11. Müllner, P., Lex, E., Schedl, M., Kowald, D.: Reuseknn: Neighborhood reuse for differentially private knn-based recommendations. ACM Transactions on Intelligent Systems and Technology 14(5), 1–29 (2023) 12. Niu, B., Chen, Y., Wang, Z., Li, F., Wang, B., Li, H.: Eclipse: Preserving differential location privacy against long-term observation attacks. IEEE Transactions on Mobile Computing 21(1), 125–138 (2020) 13. Seidl, T., Kriegel, H.P.: Optimal multi-step k-nearest neighbor search. In: Proceedings of the 1998 ACM SIGMOD international conference on Management of data. pp. 154–165 (1998) 14. Shi, Y., Tong, Y., Zeng, Y., Zhou, Z., Ding, B., Chen, L.: Efficient approximate range aggregation over large-scale spatial data federation. IEEE Transactions on Knowledge and Data Engineering 35(1), 418–430 (2021) 15. Tao, Q., Tong, Y., Zhou, Z., Shi, Y., Chen, L., Xu, K.: Differentially private online task assignment in spatial crowdsourcing: A tree-based approach. In: 2020 IEEE 36th International Conference on Data Engineering (ICDE). pp. 517–528. IEEE (2020) 16. Tong, Y., Zhou, Z., Zeng, Y., Chen, L., Shahabi, C.: Spatial crowdsourcing: a survey: Y. tong et al. The VLDB Journal 29(1), 217–250 (2020) 17. Van Erven, T., Harremos, P.: Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory 60(7), 3797–3820 (2014) 18. Wang, H., Hong, H., Xiong, L., Qin, Z., Hong, Y.: L-srr: Local differential privacy for location-based services with staircase randomized response. In: Proceedings of the 2022 ACM SIGSAC Conference on computer and communications security. pp. 2809–2823 (2022) 19. Wang, W., Zhou, X., Qiu, T., He, X., Ge, S.: Location-privacy-aware service migration against inference attacks in multiuser mec systems. IEEE Internet of Things Journal 11(1), 1413–1426 (2023) 20. Wang, Z., Guo, C., Liu, J., Zhang, J., Wang, Y., Luo, J., Yang, X.: Accurate and privacy-preserving task allocation for edge computing assisted mobile crowdsensing. IEEE Transactions on Computational Social Systems 9(1), 120–133 (2021) 21. Yadav, S., Yu, C., Xie, X., Huang, Y., Qiu, C.: Protecting vehicle location privacy with contextually-driven synthetic location generation. In: Proceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems. pp. 29–41 (2024) 22. Zhang, X., Wang, Q., Xu, C., Peng, Y., Xu, J.: Fedknn: secure federated k-nearest neighbor search. Proceedings of the ACM on Management of Data 2(1), 1–26 (2024) 23. Zhao, S., Luo, X., Ma, X., Bai, B., Zhao, Y., Zou, W., Yang, Z., Au, M.H., Qiu, X.: Exploiting proximity-based mobile apps for large-scale location privacy probing. Security and Communication Networks 2018(1), 3182402 (2018)

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

Experiment Setup

A.1

Experiment Setup of LIA

For the GI-LIA configuration, we set the maximum number of queries for the radius binary search to 100. The center of the second circle (A2 ) is determined by generating four surrounding probes. The initial step size for these probes is equal to the radius, with a maximum of 10 retry rounds. If a round fails, the probe generation step size for the subsequent round is reduced by a factor of 0.8. For the ZO-LIA configuration, which builds upon the GI-LIA settings, we set the number of rank optimization iterations to 10, with 4 probes generated per iteration. Furthermore, we filter out any probes that yield a rank worse than the best result from the previous iteration, thereby preventing them from contributing to the estimation of the current pseudo-gradient direction. The learning rate for this optimization process is set to 0.005. A.2

Experiment Setup of DPRS

Baseline There are three baselines in our paper: 1) 2D Laplace mechanism[1]: Perturbs true coordinates by adding noise from a two-dimensional Laplace distribution. 2) SRR mechanism [18]: Assigns a staircase of perturbation probabilities to location groups based on their distance from the true coordinates. 3) Square mechanism [7]: Employs two distinct probabilities to sample locations, one for a square region around the user and another for the rest of the domain. Utility Metric For the k-NN task, we use the recall and distance ratio as the utility metrics to evaluate the performance. Given a query point q, the ground truth set is denoted as G(q), and the set returned by the k-NN algorithm is denoted as P (q). The recall and distance ratio are calculated as follows: |P (q) ∩ G(q)| . k P g∈G(q) ||g − q||2 distance ratio(q) = P . p∈P (q) ||p − q||2 recall(q, k) =

(18) (19)

Parameter Settings In our privacy budget design, we set ϵp = ϵc and δ = 10−5 . The number of iterations for Algorithm 1 is set to 12. The radius scaling ranges from 0.2 to 0.8 times the initial radius, where the initial radius is defined as the distance from a given center to its nearest center. For location setting, we normalize the data to the range [−1, 1].

Gaussian Rejection Sampling Mechanism

Algorithm 4 describes the pipeline of applying DPRS to the Gaussian distribution. The main logic aligns with Algorithm √ 2. The sensitivity of DPRS-Gau is the L2 norm of the original range (i.e., 2r).

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

)

Theoretical Analysis and Proofs

C.1

Theorem for Gaussian Rejection Sampling Mechanism

Algorithm 4: Gaussian-RSM

√ Input : data x, interval I (center xc , radius R), sensitivity ||µ||2 = 2r, Gaussian distribution p(·|x, σ 2 Id ), target function f (·) ∝ p(·|x, σ 2 Id ). Output: perturbed data x′ . 1 if ∥x − xc ∥k ≤ R then 2 M ← 1. 3 else 4 B ← GetBoundary(xc , R). 5 z∗ ← minz∈B ∥z − x∥2 . 6 M ← f (z∗ ). 7 while true do 8 u, u1 , u2 ← RandomUniform(0, 1). √ 9 R ← R u1 , θ ← 2πu2 . 10 x′ ← xc + (R cos(θ), R sin(θ)). ′

11 12

) if u < f (x then M return x′ .

Theorem 4. Let p(t|x, σ 2 ) be a probability density function with support on a bounded domain D ⊂ R2 , defined as: ( p(t|x, σ 2 Id ) =

1 2 NC Gau(t|x, σ Id )

if t ∈ D otherwise,

(20)

RR where NC = D Gau(t|x, σ 2 Id ) dt. If a sample x′ is generated by Algorithm 4, then the probability distribution of x′ follows distribution p(t|x, σ 2 Id ). The detailed proof of Theorem 4 is provided in Theorem 7.

Theorem 5. Algorithm 4 satisfies (α, α||µ||22 /2σ 2 ) − RDP .

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

Proof. let Dα (S) be RDP of Algrithm 4 according to Lemma 5, we have: Dα (S) ≤ Dα (N (0, σ 2 Id )||N (µ, σ 2 Id )) Z 1 1 α∥x − µ∥22 + (1 − α)∥x∥22 dd x} ≤ log{ · exp − α−1 2σ 2 (2πσ 2 )d/2 Rd Z 1 1 α(xT x − 2µT x + µT µ) + (1 − α)xT x · dd x} ≤ log{ exp − α−1 2σ 2 (2πσ 2 )d/2 Rd T Z 1 1 x x − 2αµT x + α∥µ∥2 dd x} ≤ log{ · exp − α−1 2σ 2 (2πσ 2 )d/2 Rd Z 1 ||x − αµ||2 − α(α − 1)||µ||2 1 ≤ · exp − dd x} log{ α−1 2σ 2 (2πσ 2 )d/2 Rd Z 1 α(α − 1)||µ||2 1 ||x − αµ||2 ≤ log{exp( ) dd x} · exp − α−1 2α2 2σ 2 (2πσ 2 )d/2 Rd α||µ||22 . ≤ 2α2 (21) So, Theorem 5 is proved. Theorem 6. Let xc = (0, 0), R = 1. For any input point x ∈ [−1, 1] × [−1, 1], Algorithm 4 produces a perturbed output x′ = A(x). Then the expected distance between x and x′ is bounded as follows: r ′

EA [|x − x|] ≤ σ

2 1 − e− σ 2 · . π Φ σ2 − 12

(22)

Proof. In fact, no analytical solution exists for the rejection sampling mechanism on the unit disk. Therefore, we replace the perturbation interval with a square region S = [−1, 1]2 . In fact, we have: ∥y−x∥22 ∥y − x∥ exp − dy 2 1 2σ S N2D (x) . = RR 2 ∥y−x∥2 C2D (x) exp − dy 2 2σ S

RR EA [|x − x′ |1 ] ≤

(23)

Z 1Z 1

(y1 − x1 )2 (y2 − x2 )2 ) exp(− )dy1 dy2 2 2σ 2σ 2 −1 −1 Z 1 Z 1 (t − x1 )2 (t − x2 )2 = exp(− )dt · exp(− )dt 2σ 2 2σ 2 −1 −1

C2D (x) =

exp(−

= C1D (x1 ) · C1D (x2 ).

(24)

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

)

∥y − x∥22 )dy (|y1 − x1 | + |y2 − x2 |) exp(− 2σ 2 Z ZS ZZ = |y1 − x1 | exp(− . . .)dy + |y2 − x2 | exp(− . . .)dy S S Z 1 Z 1 (t−x )2 (t−x )2 − 2σ21 − 2σ22 |t − x1 |e e = dt · dt ZZ

N2D (x) =

−1

Z 1

(t−x )2 − 2σ22

|t − x2 |e

(25)

Z 1 (t−x1 )2 e− 2σ2 dt dt ·

−1

= N1D (x1 )C1D (x2 ) + N1D (x2 )C1D (x1 ). N1D (x1 )C1D (x2 ) + C1D (x1 )N1D (x2 ) C1D (x1 )C1D (x2 ) N1D (x1 ) N1D (x2 ) = + . C1D (x1 ) C1D (x2 )

EA [|x − x′ |1 ] ≤

(26)

1D (x) Let E1D (x) = N C1D (x) , in fact we have:

(y−1)2 |y − 1| exp − dy 2 2σ −1 E1D (x) ≤ E1D (1) = R1 2 dt exp − (t−1) 2σ 2 −1 R0 z2 dz |z| exp − 2σ 2 −2 = R0 z2 dz exp − 2σ 2 −2 2 σ 2 1 − e−2/σ = R0 σ −2/σ e−t2 /2 dt 2 σ 1 − e−2/σ . =√ 2π (Φ(2/σ) − 1/2) R1

Therefore, Theorem 6 is proved as follows: r EA [|x − x′ |1 ] ≤ 2E1D (x) ≤ σ

C.2

(27)

2 1 − e− σ 2 · . π Φ σ2 − 12

(28)

Lemma and Theorem for Laplace Rejection Sampling Mechanism

Lemma 3. For any interval S and α > 1, we have: (29) Iα (S) · ZQ (S)α−1 ≥ ZP (S)α , R R R where Iα (S) = S p(x)α q(x)1−α dx, ZP (S) = S p(x)dx, ZQ (S) = S q(x)dx.

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

α Proof. we define g(x) = Zq(x) , h(x) = p(x) q(x) and a convex function f (t) = t . Q (S)

Definition 4 (Jensen’s Inequality). If f (·) is a convex function, then for any g(x), h(x), we have: Z Z f ( h(x)g(x)dx) ≤ f (h(x))g(x)dx. (30) According to Definition 4 above, we have: Z Z f ( h(x)g(x)dx) ≤ f (h(x))g(x)dx S S Z α Z q(x) p(x) p(x) q(x) dx ≤ dx ⇐⇒ f q(x) ZQ (S) S S q(x) ZQ (S) Z Z 1 1 ⇐⇒ f p(x)dx ≤ p(x)α q(x)1−α dx ZQ (S) S ZQ (S) S α ZP (S) Iα (S) ⇐⇒ ≤ ZQ (S) ZQ (S)

(31)

⇐⇒ Iα (S) · ZQ (S)α−1 ≥ ZP (S)α . So Lemma 3 is proved. Lemma 4. for any x, y > 0 and α > 1, we have: (1 + x)α (1 + y)1−α − xα y 1−α ≤ 1.

(32)

Proof. we define g(x) = (1 + x)α (1 + y)1−α − xα y 1−α , we have: g ′ (x) = α(1 + x)α−1 (1 + y)1−α − αxα−1 y 1−α let

g ′ (x) = 0

⇐⇒ α(1 + x)α−1 (1 + y)1−α = αxα−1 y 1−α α−1 α−1 1+y 1+x = ⇐⇒ x y

(33)

⇐⇒ x = y. When x > y, g ′ (x) < 0; when x < y, g ′ (x) > 0 So we have: g(x) ≤ g(y) = (1 + y)α (1 + y)1−α − y α y 1−α = (1 + y)1 − y 1

(34)

= 1. so, Lemma 4 is proved. 1 Lemma 5. let Dα (S) = α−1 log ZP (S)IααZ(S) , if S1 ⊆ S2 , then Dα (S1 ) ≤ 1−α Q (S) R R R α 1−α Dα (S2 ). where Iα (S) = S p(x) q(x) dx, ZP (S) = S p(x)dx, ZQ (S) = S q(x)dx.

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

)

Proof. let S2 = S1 ∪ Srem , we can prove this as follows: Dα (S1 ) ≤ Dα (S2 ) Iα (S2 ) Iα (S1 ) ≤ α 1−α ZP (S1 ) ZQ (S1 ) ZP (S2 )α ZQ (S2 )1−α ZP (S2 ) α ZQ (S2 ) 1−α Iα (S2 ) ⇐⇒ ( ) ( ) ≤ ZP (S1 ) ZQ (S1 ) Iα (S1 ) ZP (Srem ) α ZQ (Srem ) 1−α Iα (Srem ) ⇐⇒ (1 + ) (1 + ) ≤1+ . ZP (S1 ) ZQ (S1 ) Iα (S1 ) ⇐⇒

(35)

According to Lemma 3 we have: Iα (Srem ) · ZQ (Srem )α−1 ≥ ZP (Srem )α Iα (S1 ) · ZQ (S1 )α−1 ≥ ZP (S1 )α

(36)

Iα (Srem ) ZP (Srem ) α ZQ (Srem ) 1−α ⇐⇒ ≥( ) ·( ) . Iα (S1 ) ZP (S1 ) ZQ (S1 ) ) So, let x = ZZP P(S(Srem ,y= 1)

ZQ (Srem ) ZQ (S1 ) , we need to prove

1 + xα y 1−α ≥ (1 + x)α (1 + y)1−α .

(37)

According to Lemma 4, Lemma 5 is proved. Theorem 7. Let p(t|x, λ) be a probability density function with support on a bounded domain D ⊂ R2 , defined as: ( 1 Lap(t|x, λ) if t ∈ D p(t|x, λ) = NC (38) 0 otherwise, RR where NC = D Lap(t|x, λ) dt. If a sample x′ is generated by Algorithm 2, then the probability distribution of x′ follows target distribution p(t|x, λ). Proof. To prove Theorems 4 and Theorems 7, we need to establish a more general result from which they follow. let noisy distribution be p(x) as follows: ( 1 f ∗ (x) if x ∈ D (39) p(x) = NC 0 otherwise, R where NC = D f ∗ (z) dz is the normalization constant. we assume D is a Euclidean sphere with a radius R and Y is the output of RSM. We will prove that P r[Y = x|accept] = p(x), in fact, we hava: P r[accept|Y = x] · P r[Y = x] P r[accpet] 1 P r[accept|Y = x] · πR 2 = . P r[accpet]

P r[Y = x|accept] =

(40)

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

For the first term in the numerator, we can calculate it in the following way: P r[accept|Y = x] = P r[u <

f ∗ (x) f ∗ (x) ]= , M M

(41)

where M is the max probability value in D, and u ∼ U nif orm(0, 1). For the denominator, we can calculate it in the following manner: Z P r[accept|Y = x] · P r[Y = x]dx

P r[accept] = x∈D

f ∗ (x) 1 dx · 2 M πR x∈D R f ∗ (x)dx = x∈D M πR2 Nc = . M πR2 Z

(42)

So, we have: 1 P r[accept|Y = x] · πR 2 P r[accpet] f ∗ (x) 1 M πR2 = · · M πR2 NC ∗ f (x) = Nc = p(x).

P r[Y = x|accept] =

(43)

Therefore, Theorem 4 and Theorem 7 are proved. Theorem 8. Let xc = (0, 0), R = 1. For any input point x ∈ [−1, 1] × [−1, 1], Algorithm 2 produces a perturbed output x′ = A(x). Then the expected distance between x and x′ is bounded as follows: EA [∥x′ − x∥1 ] ≤ 2(λ −

2 e2/λ − 1

(44)

Proof. In fact, the rejection sampling mechanism on the unit circle has no analytical solution. For this reason, we choose to calculate the expectation of the analytical expression on a square region S = [−1, 1]2 , because the region S is slightly larger than the unit circle, from which an upper bound can be obtained: RR ′

EA [|x − x |1 ] ≤

1 ∥y − x∥1 exp(− ∥y−x∥ )dy λ . RR ∥y−x∥1 exp(− λ )dy S

(45)

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

Let C2D (x) =

RR S

)

1 ∥y − x∥1 exp(− ∥y−x∥ )dy, we have: λ

Z 1Z 1

|y2 − x2 | |y1 − x1 | exp − dy1 dy2 exp − λ λ −1 −1 Z 1 Z 1 |t − x1 | |t − x2 | exp − exp − = dt · dt λ λ −1 −1

C2D (x) =

(46)

= C1D (x1 ) · C1D (x2 ). Let N2D (x) =

RR S

1 exp(− ∥y−x∥ )dy, we have: λ

ZZ X |yi − xi | N2D (x) = dy1 dy2 ( |yi − xi |)Πi exp − λ S i Z 1 Z 1 |y −x | |y −x | − 1λ 1 − 2λ 2 = dy1 · dy2 |y1 − x1 |e e −1

Z 1 +

−1

(47)

Z 1 |y2 −x1 | |y1 −x2 | e− λ dy2 · |y1 − x2 |e− λ dy1

−1

= N1D (x1 )C1D (x2 ) + C1D (x1 )N1D (x2 ). Hence, the original formula is represented as follows: N1D (x1 )C1D (x2 ) + C1D (x1 )N1D (x2 ) C1D (x1 )C1D (x2 ) N1D (x1 ) N1D (x2 ) + . = C1D (x1 ) C1D (x2 )

EA [|x − x′ |1 ] ≤

(48)

1D (x) Let E1D (x) = N C1D (x) , in fact we have:

R1 E1D (x) ≤ E1D (1) =

−1

dy |y − 1| exp − |y−1| λ R1 exp − |t−1| dt λ −1

ze−z/λ (−dz) = R2 0 e−z/λ (−dz) 2

(49)

λ2 − λ(λ + 2)e−2/λ λ(1 − e−2/λ ) 2 = λ − 2/λ . e −1 =

Therefore, Theorem 8 is proved as follows: EA [|x − x′ |1 ] ≤ 2E1D (x) ≤ 2(λ −

2 ). e2/λ − 1

(50)

Protecting K-Nearest Neighbor Queries from Location Inference Attacks

=5 5HFDOO

&HQWHUVQXPEHU

(a) Brightkite

&HQWHUVQXPEHU

(b) Gowalla

&HQWHUVQXPEHU

(d) Beta

Fig. 6: Performance impact on the number of interval centers for DPRS-Gau in 10-NN task at k = 10.

5HFDOO

DPRS-Lap

DPRS-Gau

SRR

(a) Brightkite

Square

(b) Gowalla

Laplace

(d) Beta

Fig. 7: Performance impact on the number of neighbors for all mechanisms in the 10-NN task at ϵ = 3.

Standard

(a) ϵ = 1

(b) R = 0.5

06(

5HFDOO

7LPHV

RSM

(a) Recall

(b) MSE

6FDOLQJ

Fig. 8: Time overhead for sampling al- Fig. 9: Performance impact on radius scaling selection. gorithms.

Additional Experiment Results

Experiments of RSM-Gau. Figures 6 and 7 demonstrate the performance of integrating RSM-Gau into DPRS. Specifically, the former shows that the recall of DPRS-Gau increases as the number of centers grows from 600 to 1000 and larger privacy budgets (ϵ) also yield higher recall, while the latter indicates that both DPRS-Gau and DPRS-Lap outperform the baselines (SRR, Square, and Laplace) across all datasets, confirming the effectiveness of the DPRS framework.

Zhiyu Sun, Jie Fu, Xinpeng Ling, Huifa Li, and Zhili Chen (

)

Time overhead analysis of DPRS. We set the interval center to (0, 0) and uniformly sample 100 samples from the square [−1, 1] × [−1, 1], then compare the time cost of perturbing these samples into the interval. As shown in Figure 8, compared to the standard noise-and-resampling mechanism, our RSM consistently maintains a minimal time overhead (less than 40ms) under varying radius (R) and privacy budget (ϵ) settings. Optimal τ Analysis. We evaluate the perturbation radius scaling at ϵ = 1. Figure 9 illustrates the impact of varying the scaling coefficient on k-NN recall and distance MSE. Specifically, setting the radius to 0.5 times the distance to the nearest PIC center yields the optimal performance, achieving the highest recall and the lowest MSE.

Record · ID 259364 · SHA-256 da9a38a8ff0cb92a
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.